2.5. Симплексный метод решения задачи

Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный. 2.

Множество всех планов задачи линейного программирования выпукло. 3.

Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек. 4.

Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом. Для применения этого метода ЗЛП должна быть сформулирована в канонической форме (2.12) - (2.14), причем матрица системы уравнений должна содержать единичную подматрицу размерностью т х т.

Для определенности предположим, что первые т векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: (Pi,b2,..., bm, 0,...,0).

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

Полученный опорный план снова проверяется на оптимальность и т. д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получаются оптимальный опорный план и соответствующее ему оптимальное значение целевой функции.

Признак оптимальности заключается в следующих двух теоремах.

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие

т.

Aj = Zj - Cj < 0, где Zj = j = ^

i=l

то можно получить новый опорный план, для которого значение целевой функции будет больше исходного; при этом могут быть два случая:

а) если все координаты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения;

б) если имеется хотя бы одна положительная координата у вектора, подлежащего вводу в базис, то можно получить новый опорный план.

Теорема 2. Если для всех векторов выполняется условие Дj = Zj — Cj > 0, то полученный план является оптимальным.

На основании признака оптимальности в базис вводится вектор Ah, давший минимальную отрицательную величину симплекс-разности:

zk- Ck = min(Z; - Cj).

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Аг, который дает минимальное положительное отношение

Q - nun— = ——; aik > 0, і = 1, т.

і aik ark

Строка Аг называется направляющей, столбец А^ и элемент ark — направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам

аг і —

j = l, п,

"rk

а элементы любой другой г-й строки пересчитываются по формулам:

atJ • агк - а • • а1к -— . — а , = , I = 1 ,т; ) = 1 ,п.

ark

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

bj.

Если наименьшее значение Q достигается для нескольких базисных векторов, "то чтобы исключить возможность зацикливания (повторения базиса), можно применить следующий способ.

Вычисляются частные, полученные от деления всех элементов строк, давших одинаковое минимальное значение Q, на свои направляющие элементы. Полученные частные сопоставляются по столбцам слева направо, при этом учитываются и нулевые, и отрицательные значения. В процессе просмотра отбрасываются строки, в которых имеются большие отношения, и из базиса выводится вектор, соответствующий строке, в которой раньше обнаружится меньшее частное.

Для использования приведенной выше процедуры симплекс-метода к минимизации линейной формы /(X) следует искать максимум функции Д(Х) = -/(X), затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП.

Рассмотрим алгоритмы симплекс-метода на конкретной задаче.

L Пример 7. Для производства продукции типа Пі и П2 предприятие использует два вида сырья: С і и С2. Данные об условиях приведены в табл. 2.1.

Таблица 2.1 Расход сырья на единицу Сырье продукции,кг/ед. Количество щ п2 сырья,кг Сі 1 3 300 С2 1 1 150 Прибыль, тыс. руб./ед. прод. 2 3 - Составить план производства по критерию «максимум прибыли».

Решение. Обозначим объем производства продукции П1 через Х\, продукции Л2~"ЧереЗ х2. С учетом этих обозначений математическая модель задачи имеет вид:

шах f(X) = 2xi + Зх2 xi + Зх2 < 300,

при ограничениях

xi + х2< 150, xi > 0; х2 > 0.

Приведем эту задачу к каноническому виду, введя дополнительные переменные Хз И X4'. А4 В fol ҐЗОО^І л, х4 = І150/ Ґ1 Гз' хі + <ь Л, Х2+\0\Х3 +

или xi + Зх2 + хз = 300, Х1 + х2 + х4 = 150,

Xj > о, і = М.

шах f(X) = 2xi + Зх2 + 0*3 + 0х4

Задача обладает исходным опорным планом (0,0,300,150), и ее можно решить симплекс-методом; решение ведется в симплекс-таблицах (табл.

В исходной симплекс-таблице строка оценок Д; определяется по приведенной выше формуле

Д: = Zi - Сі = 0 • 1 + 0 • 1 - 2 = -2,

Д2 = z2 - с2 = 0 • 3 + 0 • 1 - 3= -3.

100,

300 150

Q = min

т.е. вектор A3 следует вывести из базиса. Главным направляющим элементом является а12 = 3 (выделен рамочкой). Переход к следующей симплекс-таблице осуществляем с помощью преобразований Жордана-Гаусса.

Исходный опорный план (0,0,300,150) не является оптимальным, так как среди оценок Д,- имеются отрицательные. Переход к новому опорному плану осуществим, введя в базис вектор А2, имеющий минимальную отрицательную оценку.; Определяем вектор, выходящий из базиса:

Второй опорный план (0,100, 0,50) не оптимальный; переход к следующему опорному плану осуществим, вводя в базис вектор А\ и выводя вектор В результате получаем оптимальный план (75,75,0,0), т.е. предприятие получит» максимум прибыли в размере 375,0 тыс. руб., если выпустит 75 единиц продукции первого вида и 75 единиц продукции второго вида. ^