§ 3. Доказательство конечности третьего алгоритма Гомори

3.1. В этом параграфе будет рассматриваться полностью целочисленная задача линейного программирования (2.3) — (2.6), условия которой записаны в виде целочисленной -нормальной таблицы

Теорем а 3.1. Если существует план задачи то третий алгоритм Гомори конечен.

3.2. Доказательство. Напомним некоторые обозначения. Элементы таблицы обозначаются через где множество индексов небазисных переменных, соответствующих таблице Через обозначается расширенный -псев-доплан соответствующий таблице Пусть Обозначим через номер направляющего столбца итерации:

Очевидно,

Отсюда следует, что

3.3. Существует такое что

Действительно, так как целое при любом то целое и Следовательно, количество итераций для которых не превышает откуда и следует (3.3).

3.4. Допустим, что количество итераций бесконечно. Тогда найдутся такие и что

2) Найдется сколь угодно большое для которого

Из (3.1), (3.4) и (3.5) имеем

Следовательно, найдется такое что

Рассмотрим итерацию при Из (3.8) следует, что

т. е.

откуда в силу отрицательности и лексикографической положительности получаем

Из (3.11) следует, что

Сравнивая (3.7) и (3.12), получаем противоречие. Конечность третьего алгоритма Гомори доказана.