2.5 Алгоритм симплекс-метода

Имея описание элементарного преобразования симплекс-таблицы, мы можем теперь сформулировать основные шаги алгоритма симплекс-метода.

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

1) Если симплекс-таблица двойственно допустима, т.е.

> 0, 2 = 1,..., п, то КОНЕЦ (получено оптимальное решение).

2) Выбрать ведущий столбец в : г08 < 0, в > 1.

3) Если {г | 2{в > 0} ф 0, то выбрать ведущую строку г:

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

Далее под итерацией будем понимать однократное выполне­ние шагов с 1-го по 4-й.

 

2і.

(2.6)

 

*І8   > 0}

Замечания

1. Выполнение шага 0 предполагает нахождение прямо до­пустимого базиса, что представляет собой достаточно трудную задачу, и об этом речь пойдет чуть позже.

2. Если на шаге 3 имеем Z{s < 0, г = 1,...,то, то это сви­детельствует о неразрешимости задачи ввиду неограниченности целевой функции снизу на множестве допустимых решений. В самом деле, вектор ж*, имеющий компоненты Xj = 0 при j G S"\{s}, xs = t и ха^ = Zio — Zist, i= 1,.. .,m, является решением системы (2.2") при любом t. Так как Z{q > 0, г = 1,..., т (ввиду того, что симплекс-таблица прямо допустима), то при t > 0 все компоненты ж* неотрицательны, т.е. ж* — допустимое решение задачи. Кроме того, из (2.1") имеем w(xr) = — zqq + zost, так что w{xr) —т- —со при t —т- +оо.

3. Для корректной работы алгоритма необходимо, чтобы на каждой итерации симплекс-таблица была прямо допустимой. По­этому нам следует убедиться, что это свойство таблицы при вы­полнении элементарного преобразования на шаге 4 сохраняется. Согласно правилу преобразования (2.6) в новой симплекс-таблице элементы нулевого столбца будут равны z'i0 = Z{q — f^^ro ПРИ г ф г и z'r0 = j^. Неотрицательность z'r0 следует непосредственно из неравенств zro > 0 и zrs > 0. Для доказательства неравенств zio ^ 0 [г ф г, г > 1) рассмотрим два случая:

а) если zis < 0, то z'M = zM - ^zr0 > zM > 0,

б) если Zis > 0, то в силу правила выбора ведущей строки имеем f2- >      и, следовательно, z'i0 = zls(^- - ^-) > 0.

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

20правила такие, например, как

а) правило Данцига: выбрать s с минимальным zos;

б) правило Блэнда: из числа возможных в соответствии с основным правилом выбрать сначала минимальный номер s, а затем — гс минимальным о [г).