Пример решения задачи методом Гомори

Пусть требуется решить следующую задачу целочисленного линейного программирования:

(9)

Сначала приведем задачу к канонической форме, добавляя две вспомогательные неотрицательные переменные :

(10)

Решим задачу (10), отбросив последнее условие целочисленности, с использованием симплекс-метода. В результате получаем оптимальный план

Так как первые две основные компоненты оптимального плана задачи ЛП нецелочисленные, то переходим к шагу 2. Выберем для построения правильного отсечения вторую компоненту Правильное отсечение, после добавления вспомогательной переменной будет иметь вид:

или

С учетом правильного отсечения получаем новую задачу ЛП:

Решаем эту задачу симплекс-методом и получаем оптимальный план

Так как из первых двух основных компонент оптимального плана задачи ЛП первая компонента нецелочисленная, то переходим к шагу 2. Выберем для построения правильного отсечения вторую компоненту Правильное отсечение, после добавления вспомогательной переменной будет иметь вид:

или

С учетом правильного отсечения получаем новую задачу ЛП:

Решаем эту задачу симплекс-методом и получаем оптимальный план

Его основные компоненты целочисленные, поэтому процесс поиска решения завершен, и оптимальный план исходной задачи ЦЛП (9) имеет вид

Оптимальное значение целевой функции при этом равно

Задачи для самостоятельного решения (Лугинин О.Е. ЭММиМ).

Решить методом Гомори задачи:

1.	2.
3.	4.
5.	6.