Решение оптимизационных задач средствами EXCEL




Симплексный метод решения задачи линейного программирования - часть 2


Понятно, что при больших m и n найти оптимальный план, перебирая указанным выше способом (прямым перебором) все опорные ЗЛП весьма трудно. Поэтому необходимо иметь схему, позволяющую осуществлять упорядоченный переход от одного опорного плана к другому. Такой схемой является симплексный метод.

Симплекс-метод с естественным базисом

Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).

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

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

Математический признак оптимальности состоит из следующих двух теорем:

1.      Если для всех векторов А1, А2,…, Аn выполняется условие

                         

  где  
,

то полученный опорный план является оптимальным.

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

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

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

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




Содержание  Назад  Вперед