Алгоритм метода Гомори

1. Решаем задачу ЛП (1)-(3) с помощью симплекс-метода.

а) Если эта задача не имеет решения, то задача ЦЛП (1)-(4) также не имеет решения.

б) Если решение этой задачи целочисленное, то оно и будет решением исходной задачи ЦЛП (1)-(4). И на этом процесс поиска решения завершается.

в) Если решение задачи ЦЛП (1)-(4) не найдено, то переходим к следующему шагу.

2. Выбираем одну из нецелых компонент оптимального плана задачи ЛП (1)-(3) (рекомендуется выбирать компоненту с наибольшей дробной частью). Пусть это будет компонента . Для этой компоненты строим правильное отсечение вида (7):

.

3. Путем введения неотрицательной вспомогательной переменной преобразуем это неравенство в равенство:

(8)

Добавляем условие (8) в систему ограничений задачи (1)-(4) вместе с условием . Заметим, что на вспомогательную переменную условие целочисленности не накладывается.

4. Решаем задачу ЛП вида (1)-(3) с дополнительным условием (8) с

n + 1 переменными с помощью симплекс-метода.

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

б) Если оптимальный план указанной задачи ЛП не является целочисленным в части основных переменных , то возвращаемся к шагу 2, и итерационный процесс продолжается. При этом только нужно учитывать, что выбирается одна из нецелых компонент оптимального плана в части основных переменных.

Замечание. Отметим, что алгоритм Гомори сходится к оптимальному решению задачи ЦЛП (1)-(4) за конечное число шагов. Доказательство этого утверждения опустим.

Дата добавления: 2014-01-06