5.5 Описание первого алгоритма Гомори

0) Начать с нормальной симплекс-таблицы (для задачи (5.1)—(5.3)). Положить V := 0.

1) Если симплекс-таблица прямо допустима и все элементы ^г-о, г = 1,..., га, целые, то КОНЕЦ (получено оптимальное решение задачи (5.1)-(5.4)).

2) Если симплекс-таблица прямо допустима, то выбрать минимальное р > 1, такое, что 2ро — нецелое, положить V := V + 1. Строку с номером р считать производящей. Этой строке соответствует уравнение

 

3 = 1

по которому строится дополнительное ограничение согласно описанному выше способу при К = 1 (роль £ играет х,р):

 

3 = 1

гДе 1-рз — дробная часть числа ^ (грз = \.2рз\ + $р31 0 < 1'рз < !)•

95

К симплекс-таблице добавляется (га + 1)-я строка, соответствующая дополнительному ограничению (базисной переменной хп+и).

3)

4)

Если {] | 2,р]- < 0, 3 >1\ ф 0, то выбрать ведущий столбец в :

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

1

/35 = 1ехтгп{ 1 < 0, ^' > 1}

2,

'Г5

иначе КОНЕЦ (текущая задача ЛП, а следовательно, и исходная задача ЦЛП, неразрешима ввиду несовместности ее ограничений). 5) Преобразовать симплекс-таблицу;

положить т{в) := га + V и отбросить (га + 1)-ю строку, если таковая имелась, иначе г(в) := г; перейти на шаг 1.

Замечания.

1) Базисное решение х° = (гю,..., гпо)т, соответствующее текущей симплекс-таблице в момент введения дополнительного ограничения, является допустимым решением задачи (5.1)—(5.3) (и оптимальным решением соответствующей ЛП-релаксации). Вви­ду того, что 2ро — нецелое, имеем /ро > 0, хп+1У(х°) = — /ро < О и, следовательно, х° дополнительному ограничению не удовлетворя­ет, т.е. отсекается.

2) Если на шаге 2 было введено дополнительное ограничение, то на шаге 3 в качестве ведущей будет выбрана единственно воз­можная (га + 1)-я строка и в преобразованной симплекс-таблице элемент из производящей строки и нулевого столбца примет зна­чение г'р0 = %о-^г^у(-/Ро)- В случае грз > 0 имеем 2ре//ре > 1 и 2р0 < гр0 - /р0 = [гр0\, т.е. 2^0 < [гр0\ < гр0. Поскольку грз ф 0 и

/35 >- О, ТО Последнее уСЛОВИе гр& > 0 будет ВЫПОЛНеНО, еСЛИ 2{в = О

при г < р.

3) В результате выполнения итерации, на 2-м шаге которой вводилось дополнительное ограничение, вновь введенная перемен­ная хп+1У становится небазисной, а соответствующая ей строка из симплекс-таблицы удаляется. Это фактически означает, что на последующих итерациях в случае перехода переменной хп+и в разряд базисных, соответствующее этой переменной дополни­тельное ограничение хп+и > 0 перестает учитываться, т.е. оно отбрасывается. Таким образом, максимальное число учитыва­емых дополнительных ограничений не превосходит числа неба­зисных переменных /.