Определяются относительные оценки с/ для небазисных переменных (оценки с.- базисных переменных равны нулю). Относительные оценки с- для />и, однозначно определяются из выражения [c.32]
В табл. 47 содержится шесть базисных переменных, т. е. т + ге — 1 = 6, и план является невырожденным. [c.73]
Общая задача линейного программирования не всегда имеет решение. Из теории систем линейных уравнений известно, что система (103) имеет единственное решение, если число линейно независимых уравнений г равно п. Если в этом решении хотя бы один ж,-<С 0, то оно недопустимо если все ж,- 0, то это решение допустимо и оптимально, так как оно единственно. Если число линейно независимых уравнений г меньше п и система (103) совместна, она имеет бесчисленное множество решений. При этом (п — г) переменным можно придавать произвольные значения (свободные переменные), а остальные выразятся через них (базисные переменные). [c.179]
Пусть в общей задаче линейного программирования имеется п переменных и т независимых линейных ограничений (103). Выберем в качестве свободных k = п — т переменных и выразим через них остальные т базисных переменных [c.179]
Чтобы на каждом шаге выбрать, какие именно свободные и базисные переменные необходимо поменять местами, применяют следующий способ. Запишем ограничения — равенства общей задачи линейного программирования следующим образом [c.181]
Преобразуем матрицу (3.12) в соответствии с указанным выше требованием получения базисных значений переменных величин. Для этого необходимо выполнить над ней такие преобразования, чтобы базисные переменные остались по одной в каждом из уравнений (строке матрицы), а коэффициенты при них были равны единице. Начинаем с коэффициента при х в первом уравнении. Чтобы сделать его равным единице, делим все коэффициенты первого уравнения на четыре. Для исключения переменной х, из остальных уравнений отнимаем от каждого из них первое уравнение, умноженное на такое число, при котором разность коэффициентов при х была бы равна нулю. Например, второе и третье уравнения (строки) нужно умножить на нуль, четвертое - на единицу. [c.67]
Теперь, приравнивая переменные х5 и х6 (соответственно пятый и шестой столбцы матрицы) нулю, можем написать значения базисных переменных, которые будут в этом случае равны свободным членам соответствующих уравнений [c.68]
Матрица А разбивается на подматрицы А0 и As, причем А0 содержит столбцы, соответствующие коэффициентам при переменных х5 и х6, равных нулю, а матрица As представляет собой столбцы, соответствующие коэффициентам при остальных (базисных) переменных [c.74]
Матрица X разбивается на подматрицы Х0 и Х , причем XQ содержит значения переменных, равных нулю, a Xs - значения остальных (базисных) переменных [c.74]
Матрица С разбивается на подматрицы С0 и s, причем С0 содержит коэффициенты в выражении для линейной формы при нулевых переменных, a s - для остальных (базисных) переменных [c.74]
Левый крайний столбец содержит номера к/ базисных переменных, верхняя строчка -— номера кт + / свободных переменных. В точке пересечения строки, соответствующей значению kt, и столбца, соответствующего кт + h стоит коэффициент а т +j — коэффициент, стоящий при свободной переменной в /-м уравнении, в котором выделена базисная переменная х Соответственно справа записаны постоянные члены уравнений, внизу — коэффициенты целевой функции от свободных переменных, а в правом нижнем углу — значение целевой функции Qq. [c.270]
Номер базисной переменной Номер свободной переменной Свободные члены [c.271]
Замена базиса при помощи разрешающего элемента — процесс, в ходе которого базисное переменное / становится свободным и одновременно свободное переменное Xj становится базисным. Если w — какое-либо значение в таблице, то W — значение, стоящее в новой таблице на том же самом месте [c.272]
В последней таблице все коэффициенты целевой функции неотрицательны. Следовательно, в точке х = 2, 2 = 2, Хз = 6, х = 0, Х5 = 0, д% = 0, xi = 2, xg =3 целевая функция принимает минимальное значение Q0 = -(-38) 38. (Переменным, индекс которых стоит в верхней строчке, приписывается значение 0 это свободные переменные. Каждое из переменных, индекс которого стоит в левом столбце, приравнивается числу, записанному в правом столбце той же самой строки — это базисные переменные.) Коэффициенты, стоящие в последней строке итоговой симплекс-таблицы, показывают, насколько изменится оптимальное значение целевой функции при изменении значения соответствующей переменной х на единицу, т.е. представляют собой "теневые цены". Например, уменьшение д на единицу приведет к уменьшению оптимального значения на 2. [c.275]
Систему уравнений (4.8), (4.9) можно разрешить относительно т+п-1 базисных переменных. Остальные тп-(т+п-1) переменных являются свободными. Каждое решение транспортной задачи находят следующим образом свободные тп-(т+п-1) переменные полагаются равными нулю, а базисные т+п-1 переменные находят из системы ограничений (4.8)—(4.9). Полученное решение проверяют на оптимальность. Если решение не оптимально, то осуществляют переход к новому решению путем [c.339]
Изложенные методы нахождения начального решения не единственные. В качестве начального решения может быть взят любой набор чисел, удовлетворяющих множеству допустимых планов (4.6) и условию баланса (4.7) (например, полученный по методу "юго-восточного" угла). Заметим, что для всех полученных решений число заполненных (отличных от нуля) клеток транспортной таблицы в точности равно числу базисных переменных задачи. [c.342]
Шаг 4.1. Выбор переменной, вводимой в список базисных переменных. [c.344]
Переменная транспортной задачи, соответствующая этой клетке, вводится в список базисных переменных, т. е. данная клетка транспортной таблицы заполняется. [c.344]
Шаг 4.2. Выбор переменной, выводимой из списка базисных переменных. [c.344]
Задача линейного программирования (2.7), (2.10), (2.9) с дополнительными ограничениями на неотрицательность переменных tt имеет размерность я + т. При этом число базисных переменных в случае линейной независимости системы ограничений (2.8) равно числу ограничений, т. е. т, а число свободных переменных совпадает с числом неизвестных в линейной форме (2.7), т. е. равно п. Обозначим через с значение целевой функции в форме (2.7). [c.67]
В исходном опорном плане задачи будем считать переменные группы tf базисными переменными, а группы х . — свободными. Выразив целевую функцию и базисные переменные через свободные, сформулируем задачу линейного программирования (2.7), (2.9), (2.10) в следующем виде [c.67]
Итерационную симплекс-процедуру начнем с первой таблицы, представленной коэффициентами матрицы (2.13), где пер -менные по строкам соответствуют базисным переменным, а по столбцам — свободным. [c.68]
Задача (2.14), (2.17), (2.18), (2.19) с дополнительными ограничениями tl > О, /2 > 0 является задачей линейного программирования размерности 5, у которой число базисных переменных равно 2 (соответствует числу актуальных ограничений), а число свободных переменных равно 3. Принимая хг хг и х3 за свободные переменные, приведем задачу к следующему виду [c.72]
На первом шаге (табл. 3.1(а)) наиболее выгоден план добычи угля, что обусловливает его введение в базис (план производства) следующего шага (см. табл. 3.1(6)). Какое же из первоначальных базисных переменных он заменит Для ответа на этот вопрос почленно разделим первый столбец на столбец xv т. е. неиспользованные остатки ресурсов делим на коэффициенты замены. Так как в плане первого шага ресурсы не используются в их полном объеме, то каждый из элементов частных покажет, какое количество угля можно добыть за счет полного использования соответствующего ресурса. Но добыча угля требует одновременной затраты всех трех ресурсов, и исчерпание какого-либо одного ресурса сделает дальнейшую добычу невозможной. Таким образом, максимальная добыча угля возможна лишь в размере 40 тыс. т, а не 180 или 128. При добыче 40 тыс. т угля будет полностью истрачен фонд оборотных средств в размере 20 тыс. руб., а его неиспользованный остаток х3 станет нулевым. [c.83]
В полученной матрице D строки соответствуют базисным переменным х/, х , х4, а столбцы — ресурсам. Сравнив ее с табл. 3.1(в), видим, что матрица эффективности D представлена в столбцах табл. 3.1 (в). Следует пояснить, что строки в табл. 3.1 (в) чередуются в порядке, сложившемся в процессе решения задачи (т. е. х2, х4, х,). [c.88]
Для заданного в исходной модели вектора наличного запаса ресурсов В = (20, 180, 32) значение целевой функции с°=62,3 тыс. т суммарной добычи условного топлива. В случае указанного выше изменения вектора ресурсов на величину Д5 = (10,0, —10) получено изменение оптимального плана добычи торфа — на величину Дх = 75 тыс. т и угля — на величину AxJ =27,5 тыс. т. Определим величину, на которую изменился критерий оптимальности А с° = 0,25 (-75) + 1,2 27,5 = 14,25 (тыс. т условного топлива). Таким образом, экономический эффект от указанного изменения вектора ресурсов оказывается положительным. Оценим данный результат с позиций двойственных оценок ресурсов. Исходя из последней симплекс-таблицы 3.1 (в) (значений коэффициентов пер- вой строки), двойственная оценка оборотных средств предприятия равна 2,075 т усл. топлива/руб., двойственная оценка трудовых ресурсов — 0,65 т усл. топлива/чел.-ч, а двойственная оценка ресурсов электроэнергии — нулевая (так как переменная х4 находится среди базисных переменных исходной задачи, являющейся по определению прямой). [c.89]
Рассмотрим важный для дальнейшего изложения случай, когда одна из свободных переменных должна в результате подходящей замены вытеснить из оптимального плана одну из базисных переменных. Обозначим через k индекс той свободной переменной, которую [c.91]
Тогда можно переразрешить систему уравнений (105) относительно других базисных переменных, выведя из числа свободных переменных х1 и заменив его на хц. [c.180]
В уравнениях (105) не всг pV (i = k + 1,. .., п) неотрицательны. В этом случае опорное решение надо искать с помощью аналогичной процедуры обмена местами некоторых свободных и базисных переменных, переразрешая уравнения (105) до тех пор, пока все свободные члены не станут неотрицательными, либо пока не станет ясно, что опорное решение не существует. [c.181]