9 Прямой симплекс—метод

Пусть x — некоторое базисное допустимое решение задачи (5)-(7), соответствующее базису В. В результате исследования симплекс-таблицы с базисом В выявляется:

1. либо оптимальность решения x; либо неразрешимость задачи; либо возможность перехода к новому базису.

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

Описание алгоритма:

0. Построить симплекс-таблицу, соответствующую заданному базисному допустимому решению (таблица, естественно, будет прямо допустимой, т.е. Zio >=0,i = 1,т).

1. Если симплекс-таблица двойственно допустима, т.е. Z_qj >= 0, j = 1,п, то КОНЕЦ (получено оптимальное решение).

2. Иначе, выбрать ведущий столбец s : z_os < 0, s >=1.

3. Если {i | Z_is > 0, i >= 1} ≠(пуст. Множ.), то выбрать ведущую строку r по правилу:

z_r0=z_rs=min{ z_i0=z_is | z_is>0 i>=1}

иначе КОНЕЦ (задача неразрешима из-за неограниченности целевой функции).

4) Преобразовать симплекс-таблицу, положить σ (r) := s и перейти на шаг 1.

Под итерацией понимается однократное выполнение шагов с 1-го по 4-й.

Утверждение 9. На каждой итерации алгоритма симплекс - таблица остается прямо допустимой.

Определение. Задача линейного программирования называется вырожденной, если у нее существует вырожденное базисное допустимое решение x, т. е. такое решение x, что |{j|x_j ≠0}|<т.

Утверждение 10. В случае невырожденной задачи линейного программирования ал­горитм симплекс-метода конечен.

В случае вырожденной задачи возможно так называемое зацикливание, когда в резуль­тате реализации нескольких итераций алгоритма происходит возврат к базису, встречавше­муся ранее. Следовательно, алгоритм может неограничено выполнять один и тот же цикл преобразования базиса. Для избежания зацикливания используется лексикографический вариант симплекс-метода, описанный в следующем подразделе.

10 Лексикографический вариант прямого симплекс-метода

Этот метод позволяет устранить зацикливание и за конечное число шагов получить решение.

Определение. Ненулевой вектор а = (z₀, Z₁,..., z_n) лексикографически больше нуля (а > 0), если первая отличная от нуля компонента положительна: z_p > 0, где р = min{i | z_i ≠ 0}.

Если a', a" € Е_п+1, то считается, что вектор а' лексикографически больше вектора а" (а' > а"), если а' — а" > 0.

Тем самым на Е_п+1 определено отношение линейного порядка, так что в любой конечной совокупности векторов {аⁱ} имеется лексикографически минимальный вектор, обозначае­мый lex min{аⁱ}

Определение. Симплекс-таблица называется нормальной, если ее строки а_i = (z_i0, Z_i1,..., z_in), i = 1,т, лексикографически положительны.

Утверждение 11. Любую прямо допустимую симплекс-таблицу можно преобразовать в нормальную путем перенумерации переменных (с соответствующей перестановкой столб­цов).

При этом очевидно, что нормальная симплекс-таблица является прямо допустимой.

Отличия лексикографического варианта прямого симплекс-метода от обычного касают­ся только 0-го и 3-го шагов (остальные шаги остаются без изменений):

О') Начать с нормальной симплекс-таблицы.

3') Если {i | Z_is > 0, i >= 1} ≠(пуст. Множ.), то выбрать ведущую строку r:

1/z_rs =lex min {1/z_isa_i|z_is>0 i>=1}

иначе КОНЕЦ (задача неразрешима).

Элементарное преобразование базиса при этом сохраняет нормальность симплекс-таблицы.

Утверждение 12. В результате одной итерации лексикографического симплекс-метода происходит лексикографическое возрастание нулевой строки а_o = (z₀₀, Z₀₁,..., z_0n)

Утверждение 13. В ходе работы лексикографического симплекс - метода базисы не повторяются, что гарантирует его конечность.