5.4 Описание £_0-метода

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

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

2) Выбрать ведущую строку г : гго < 0, г > 1.

3) Если     | 2Г]- < 0,^ > 1} / 0, то выбрать ведущий столбец в:

--ф3 = 1ехтт{---\33- | гГ]- < 0, ] > 1},

| ^Гй | |     ^' |

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

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

Замечания.

1) При выполнении преобразования (5.15) сохраняется нор­мальность симплекс-таблицы, что может быть доказано, по су­ществу, тем же способом, что и в случае лексикографического варианта прямого симплекс-метода.

2) Нулевой столбец симплекс-таблицы при каждом ее преобра­зовании лексикографически уменьшается:

/Зо - — & < /Зо,

так как гго < 0, гГ8 < 0 и (Зе У 0. Это свойство влечет невоз­можность повторения базисов, что обеспечивает конечность чи­сла итераций.

3) Достаточно общий способ получения нормальной симплекс-таблицы на шаге 0 состоит в следующем. Пусть в полученной тем или иным способом симплекс-таблице столбец (Зе = 1ехтгп{^ \ ] ~> 1} лексикографически отрицателен и для всех допустимых решений задачи выполняется неравенство ^2^еЗ' хз — М- Тогда добавление ограничения хп+\ = М + '}2]^з'{~хз) > 0 не изменяет множества допустимых решений. Дополнив (временно) симплекс-таблицу новой (га + 1)-й строкой (М, 1,..., 1), соответствующей переменной хп+1, и произведя преобразование с ведущим столб­цом в и ведущей строкой г = га + 1, мы получим нормальную симплекс-таблицу. После этого добавленную строку можно уда­лить.