2015-10-13
412
Для применения этого метода задача линейного программирования должна быть сформулирована в канонической форме, причем матрица системы уравнений должна содержать единичную подматрицу размерностью 
. В этом случае очевиден начальный опорный план (неотрицательное базисное решение).
Для определенности предположим, что первые т векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: 
.
Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.
Полученный опорный план снова проверяется на оптимальность и т.д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получаются оптимальный опорный план и соответствующее ему оптимальное значение целевой функции.
Признак оптимальности заключается в следующих двух теоремах.
|
|
|
Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:
, где 
, 
то можно получить новый опорный план, для которого значение целевой функции будет больше исходного; при этом могут быть два случая:
1. если все координаты вектора, подлежащего вводу в базис, неположительны, то задача линейного программирования не имеет решения;
2. если имеется хотя бы одна положительная координата у вектора, подлежащего вводу в базис, то можно получить новый опорный план.
Теорема 2. Если для всех векторов выполняется условие 
, то полученный план является оптимальным.
На основании признака оптимальности в базис вводится вектор 
,давший минимальную отрицательную величину симплекс-разности: 
.
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор 
г, который дает минимальное положительное отношение:
; 
, 
.
Строка называется направляющей, столбец 
и элемент
— направляющими (последний называют также разрешающим элементом).
Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:
,
а элементы любой другой 
-й строки пересчитываются по формулам:
, ,
Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:
для 
; 
, для 
.
Если наименьшее значение 
достигается для нескольких базисных векторов, то чтобы исключить возможность зацикливания (повторения базиса), можно применить следующий способ.
Вычисляются частные, полученные от деления всех элементов строк, давших одинаковое минимальное значение на свои направляющие элементы. Полученные частные сопоставляются по столбцам слева направо, при этом учитываются и нулевые, и отрицательные значения. В процессе просмотра отбрасываются строки, в которых имеются большие отношения, и из базиса выводится вектор, соответствующий строке, в которой раньше обнаружится меньшее частное.
|
|
|
Для использования приведенной выше процедуры симплекс-метода к минимизации линейной формы 
следует искать максимум функции 
, затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной задачи линейного программирования.
