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

1.

Решим -задачу методом последовательного улучшения плана.
  1. Если все базисные компоненты оптимального решения -задачи
целые, то и есть решение -задачи.

3.

Если некоторая компонента оптимального решения - задачи
  1. нецелая, то переходим к п.2.
  2. Если в оптимальном плане единственная компонента нецелая,то дополнительное ограничение (2.1). строится по этой координате.

Если нецелых компонент в плане более одной, то выберем координату с

наименьшим номером. Пусть этой компонентой оказалась .  

Дополнительное линейное ограничение запишем в виде:

(2.2)

 

, (2.3)

6. Добавим условия 2.2. и 2.3 к условиям -задачи. Получим новую -задачу. Так как оптимальное решение -задачи определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи.

Последнюю симплексную таблицу -задачи берем в качестве  

 

исходной для -задачи, дополнив ее условием 2.2.

Симплексная таблица для -задачи получается из последней путем

окаймления строкой с элементами , , j не  

 

принадлежит базису задачи задачи.

Причем,

,

, j принадлежит базису задачи.

Получим новую задачу, переменными которой являются .

Пусть имеет место максимизация целевой функции и решение -задачи оптимально. Поэтому процесс перехода к новому решению -задачи от псевдорешения осуществляется преобразованиями с пересчетом симплекс-таблицы.

Обозначим через k номер псевдорешения -задачи; тогда направляющей строкой является i+k+1-я строка, k=0,1,2,... Поэтому на каждом этапе преобразования таблицы вектор будет выводиться из таблицы.

Если решение задачи завершается построением оптимального целочисленного решения , то первые m компонент определяют решение целочисленной задачи; если среди координат решения есть дробные, то одна из дробных компонент порождает дополнительное ограничение и процесс решения должен быть продолжен с новой окаймляющей строкой. Строка, используемая ранее для окаймления, вычеркивается и больше для построения расширенных задач не восстанавливается.

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

решаемой задачи.

Теорема 2.3.(о конечности первого алгоритма Гомори)

Пусть множество оптимальных планов - задачи ограничено

и выполняются следующие условия:

1) - целые коэффициенты целевой функции F, строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;

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