5.6 Конечность первого алгоритма Гомори

Доказательство конечности алгоритма будет проведено при следующих предположениях:

1) Известна некоторая (условная) нижняя граница М для опти­мального значения целевой функции жо (состоятельность которой имеет место в случае существования оптимума). Это дает воз­можность прекращать вычисления, если в какой-то момент ока­жется, что 2^00 < М.

2) Целевая функция жо принимает целочисленные значения на множестве допустимых решений задачи (5.1)-(5.4). В этом случае нулевая строка наравне с другими строками симплекс-таблицы может (и будет) использоваться в качестве производящей.

Условимся относительно терминологии. Как уже делалось вы­ше, однократное последовательное выполнение шагов 1)-5) будем называть итерацией. Целесообразно различать итерации двух ти­пов. К первому типу отнесем итерации, на которых не вводится дополнительное ограничение. Это обычные итерации Ь/Уметода или ГИ-итерации. При выполнении итераций второго типа вво­дится дополнительное ограничение. Такие итерации будем назы­вать особыми или итерациями Гомори.

Предположим, что в процессе решения задачи данным алго­ритмом выполняется бесконечная последовательность итераций. Элементы и столбцы симплекс-таблицы, полученной в результате выполнения первых £ итераций, будем обозначать г1- и /3^ соот­ветственно (2°- - элементы начальной симплекс-таблицы). При выполнении итерации любого типа нулевой столбец симплекс-таблицы лексикографически уменьшается (см. замечание 2 к ЬИ-методу), т.е.

Р°0у Р10у Р20у ...у Р1у /3*+1 >- ... . (5.16)

Если бы в рассматриваемой бесконечной последовательности ите­раций было конечное число особых итераций, то это противоре­чило бы доказанной ранее конечности £_0-метода, так как в этом случае начиная с некоторого момента решалась бы £_0-методом одна и та же задача ЛП. Поэтому можно считать, что особых итераций в нашей последовательности бесконечно много. Пусть tu -\- 1, V = 1,2,..., — порядковые номера этих итераций. Из (5.16) следует

^оо — гоо — гоо — • • • — ^оо — ^оо1 — • • • • (5-17)

Кроме того, по сделанному нами допущению относительно огра­ниченности оптимального значения жо, г00 > М. Рассмотрим подпоследовательность

(5.18)

образованную элементами 2оо симплекс-таблиц, являющихся вход­ными для особых итераций. Если — нецелое, то согласно правилам алгоритма нулевая строка на итерации tu -\- 1 станет производящей и будем иметь 2д0+ < [-^оо] < гоо (см- замечание 2 к описанию алгоритма). Поскольку < 2вд+1, отсюда сле-

дует, что в каждом открытом интервале вида (2, 2+1), где 2 — целое число, может располагаться не более одного члена после­довательности (5.18). Учитывая монотонность и ограниченность этой последовательности, из сказанного вытекает, что начиная с некоторого места все члены последовательностей (5.18) и (5.17)

-00'будут равны одному и тому же целому числу ^оо, т.е. последова­тельность (5.17) стабилизируется. Отсюда, в частности, следует, что начиная с этого момента на всех последующих итерациях эле­мент 2ое из ведущего столбца и нулевой строки будет равняться нулю. (Последнее свойство обеспечивает применимость упоми­навшегося выше замечания 2 к той ситуации, когда первая строка оказывается производящей).

Обозначим через Го номер итерации, начиная с которой для всех последующих итераций £ имеет место равенство = ^оо-Тогда, учитывая (5.16), будем иметь

г^>г^+1>...Уг\0>г\+01>... • (5-19)

Проведя далее рассуждения, аналогичные вышеприведенным, мы придем к выводу о том, что найдется номер Т\ > Го, начиная с которого, т.е. при £ > Г1, будет выполняться равенство г\0 = 1ю, где 1ю — некоторое неотрицательное целое число. (Ограничен­ность последовательности (5.19) и неотрицательность 1ю следует из того, что > 0 ввиду прямой допустимости симплекс-таблиц с номерами

Продолжая рассуждения, мы в конечном счете докажем суще­ствование такого номера Тп, что при всех i = 1,... ,п ж t > Тп бу­дут иметь место равенства г\0 = 1^, где 1^ — неотрицательные целые числа. Подобный вывод противоречит сделанному нами допущению о бесконечности числа итераций. Тем самым доказа­на конечность первого алгоритма Гомори.