5.8 Описание полностью целочисленного алгоритма

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

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

2) Выбрать минимальное р > 1, такое, что гро < 0. Если {] | гр1 < 0, 2 > 1} = 0, то КОНЕЦ (задача неразрешима ввиду несовместности ограничений). Строку с номером р считать производящей; V := V + 1. По уравнению

 

3 = 1

соответствующему этой строке, вводится дополнительное ограничение согласно описанному выше способу при специально выбранном /г, 0 < /г < 1 (правило выбора /г формулируется отдельно):

X п-\-и —

3 = 1

(При /г = 1 дополнительное ограничение совпадает с производящим, поскольку 2р]- — целые). К симплекс-таблице добавляется (га + 1)-я строка, соответствующая введенному ограничению

 

3) Выбрать (га + 1)-ю строку в качестве ведущей, г := га + 1.

4) Выбрать ведущий столбец в :

---(38 = 1ехтгп{---$3  \ грз < 0, ] > 1}.

| <^гв | | <^г 3 |

5) Преобразовать симплекс-таблицу;

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

Правило выбора К должно быть нацелено на обеспечение ра­венства гГ8 = —1, т.е. [^рЛ = — 1- Пусть Зр = {] \ грз < 0, 2 > 1}. Тогда нужное нам К должно удовлетворять при некотором в £ .]р следующим требованиям:

а) [кгрз\ = -1,

Так как Ц^-г^'Л > 1 ПРИ Ь > 0 и ]' £ Зр, то условие б) может выполняться только в случае (Зе = 1ехтт{(33 \ 2 £ Зр}. Это озна­чает, что ведущий столбец, определяемый на шаге 4, может быть указан до построения дополнительного ограничения (до выбора /г) сразу после того, как станет известна производящая строка.

Если определить натуральные числа р,3, ]' £ Зр, положив ц8 = 1 и [13 = тах{д | р(Зе -< \33, р — целое } при ]' £ Зр \ {в}, то сформулированные выше требования будут эквивалентны следу­ющим:

[кгрз\ > -ц3, 2 £ Зр.

В силу целочисленности [13 последние неравенства эквивалент­ны

к^рз ^   ц3, ] £ Зр или, учитывая отрицательность грз,

Н < [1^11 %Р31 2 ^ '1р-

Естественно положить

Ь, = тт{-ц3/грз \ 2 € Зр},

выбрав из всех допустимых значений максимальное. Такой вы­бор является достаточно обоснованным, поскольку большим зна­чениям /г, как нетрудно убедиться, соответствует более сильное лексикографическое уменьшение нулевого столбца в результате преобразования симплекс-таблицы.

Таким образом, правило выбора К может быть сформулирова­но следующим образом:

1) Определить номер в:

/35 = 1ехтгп{^ \ ]' £ Зр}.

2) Определить натуральные числа р^ ]' £ Зр :

М« = 1,

ц3 = тах{д | д/35 -< /З.,-, ц — целое }, ]' £ 3,р \ {в}.

3) Положить

Ь, = тт{-ц3/гр] \ ] £ Зр}.

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

Опираясь на лексикографическую монотонность последователь­ности {/Зд}) как и прежде, приходим к выводу о стабилизации значений 2д0, т.е. 2д0 = 1оо при £ > Го.

Для доказательства стабилизации последующих компонент век­тора (30 достаточно заметить, что в результате выполнения ите­рации элемент гро возрастает (здесь р — номер производящей строки). Отсюда, в частности, следует, что в случае г1^1 = г\0 при г = 0,1,..., к — 1, к-я строка на (£ + 1)-й итерации не могла быть производящей, так как в противном случае мы бы имели

102

/3*+1 >- (ЗІ Значит, 40 > О на всех итерациях после стабилизации компонент вектора (30 с номерами, меньшими к. Учитывая да­лее лексикографическую монотонность последовательности {/З^} и целочисленность величин гк0, методом индукции по к доказы­вается стабилизация всех компонент вектора /Зд. Это и завершает доказательство конечности полностью целочисленного алгоритма Гомори.