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

1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также не имеет оптимального решения.

2. Пусть на s-й итерации развязана вспомогательная ЗЛП, что имеет M ограничений и N переменных, x(s) — ее оптимальное решение.

Будем считать, что x(s) определяется каноничными ограничениями последней итерации, то есть:

x_i + b_i,M+1 x_M+1 +...+ b_iN x_N = b_i0, i=1...,M

Откуда

x(s)= ( b₁₀...,b_M0,0,...,0 ).

3. Если b_i0 (i=1...,M) — цели, то — конец, x(s) является оптимальным решением исходной ЦЗЛП. Если существует хотя бы одно и такое, что b_i0 — дробь, то переход к пункту 4.

4. Находим r=min{i} по всем и таким, что b_i0 — дробь и строим дополнительное ограничение

x_N+1 – {_br,M+1} x_M+1 –...– {b_rN} x_N = – {b_r0}

где x_N+1 ³ 0 — дополнительная переменная.

5. Расширяем симплекс-таблицу за счет (M+1) -ой строки (дополнительное ограничение) и (N+1) -го столбца, что отвечает дополнительной переменной xN+1.

6. Решаем расширенную таким образом ЗЛП двойственным симплекс-методом и переходим к пункту 2 с заменой s на s+1. Если при этом на какой-либо итерации двойственного симплекс-метода одна из дополнительных переменных задачи повторно становится базисной, то исключаются из последующего рассмотрения соответствующие ей строка и столбец.