§ 2. Второй алгоритм Гомори

В первом алгоритме Гомори существенно использовалась целочисленность всех переменных. Второй алгоритм Гомори имеет дело с более широким классом задач.

2.1. Рассматривается частично целочисленная задача линейного программирования.

Максимизировать

при условиях

Здесь

2.2. Теорема 2.1. Пусть оптимальный опорный план задачи и

— соответствующая симплексная таблица, не целое. Тогда неравенство

или, что то же самое,

является правильным отсечением. Здесь

2.3. Доказательство теоремы 2.1. Сначала проверим условие отсечения. Действительно,

так что условие отсечения выполнено.

Переходим к проверке условия правильности. Выпишем разложение по небазисным переменным

Пусть

где — некоторые целые числа, величины которых будут выбраны позже. Тогда

т. е.

Введем обозначения

Заметим, что

Эти неравенства можно переписать в следующем виде:

Далее получаем целое.

Возможны два случая:

Сначала разберем случай 1)

Тогда

и в силу нецелочисленности

а в силу целочисленности

так что

или

Последнее неравенство запишем в виде

Перейдем теперь к случаю 2)

Имеем

и в силу целочисленности

так что

Отсюда и из (2.10) получаем

Объединяя теперь в случае 1) неравенства (2.14) и (2.13), а в случае 2) неравенства (2.15) и (2.12), получаем

или, что то же самое,

Заметим, что неравенство (2.16) имеет вид

где причем правая часть не зависит от выбора чисел Следовательно, каждое из чисел следует выбрать так, чтобы было наименьшим — в этом случае будет «отсечена» как можно большая часть многогранника. Вспомним, что

так что

Сразу можно выделить случай, когда целое. Можно положить и получаем

Это — минимум так как

Теперь допустим, что

Тогда

Учитывая условия минимальности, получаем

Рассмотрим линейную функцию

т. е.

и

Окончательно получаем

Теорема 2.1 доказана.

2.4. Правило построения правильного отсечения. Пусть не удовлетворяет условию целочисленности (2.4) и - симплексная таблица, соответствующая

Выбираем

и строим правильное отсечение

где числа вычисляются по формулам

2.5. Конечность второго алгоритма Гомори доказывается так же, как и конечность первого алгоритма Гомори. При этом требуется соблюдение требований, подобных требованиям 1) и 2) § 3 гл. 5.

1) Целевая функция удовлетворяет условию целочисленности. Это учитывается при выборе строки для построения правильного отсечения.

2) Выполнено по крайней мере одно из двух условий:

2) целевая функция ограничена снизу на многогранном множестве задача имеет по крайней мере один план.

2.6. С помощью второго алгоритма Гомори можно (в случае решать и полностью целочисленную задачу линейного программирования. Однако в этом случае нет оснований для сравнения эффективности второго и первого алгоритмов Гомори. В табл. 1—7 приведено решение с помощью второго алгоритма Гомори численного примера, решенного выше посредством первого

алгоритма Гомори. В обоих случаях пришлось ввести четыре правильных отсечения.

(см. скан)

(см. скан)