§ 3. Доказательство конечности первого алгоритма Гомори
В этом параграфе будет при определенных условиях обоснована конечность первого алгоритма Гомори. Как и в предыдущем параграфе, считаем, что множество оптимальных планов задачи 
ограничено.
3.1. Теорема 3.1. Пусть выполнены следующие условия:
1) гарантирована целочисленность целевой функции 
(например, все 
целые, 
учитывается при выборе строки для построения правильного отсечения;
2) по крайней мере одно из следующих двух утверждений верно:
2) целевая функция 
ограничена снизу на 
задача 
имеет хотя бы один план 
Тогда первый алгоритм Гомори требует лишь конечного числа больших итераций.
Доказательство теоремы 3.1 будет проведено в несколько этапов.
3.2. Пусть
Обозначим через 
псевдоплан, соответствующий таблице 
получающейся из 
после вывода из базиса 
и вычеркивания соответствующей строки. Лемма 3.1.
Доказательство леммы 3.1 сразу следует из правил 
-метода.
3.3. Лемма 3.2. Числа 
ограничены снизу.
При 
это следует из условия неотрицательности (2.3). При 
это следует из условия 2) теоремы 3.1. Действительно, если выполнено 2), то лемма 3.2 тривиально верна. Если же выполнено условие 
то заведомо
так что
и лемма 3.2 верна.
3.4. Лемма 3.3. Если 
не удовлетворяет условию целочисленности и 
не целое, то
Доказательство. Пусть
Тогда
Далее, пусть
и
Так как 
то и 
следовательно,
Возможны два случая:
В случае 1) 
в силу правил 
-метода, и лемма доказана.
В случае 2) 
и так как заведомо то 
. В силу правил 
-метода получаем
Но так как 
Лемма 3.3 доказана.
3.5. Переходим непосредственно к доказательству теоремы 3.1.
Пусть последовательность
бесконечна. Тогда (в силу лемм 3.1 и 3.2) найдется такое число 
, такое число 
и такая бесконечная последовательность
что
Заметим, что из леммы 3.1 и формулы (3.3) получается
Из (3.4), (3.5) и леммы 3.2 следует существование такого числа 
и таких целых чисел 
что
Из (3.3), (3.6) и леммы 3.3 получаем
что противоречит (3.6). Теорема 3.1 доказана
