Задача (2.22) – (2.24) решается без условия целочисленности. Если полученное оптимальное решение целочисленно, то исходная задача решена. В противном случае к ограничениям задачи добавляется новое линейное ограничение, «отсекающее» нецелочисленную вершину. Это ограничение оставляет допустимыми все целые точки исходного многогранника (такое отсечение называется правильным). Далее решается задача линейного программирования с добавлением нового ограничения и т.д.

Рассмотрим вариант метода. Предполагается что задача (2.22) – (2.24) имеет решение. Пусть уравнение из симплексной таблицы, содержащей оптимальный план имеет вид:

.                  (2.25)

Базисная переменная в этом уравнении имеет наибольшую дробную часть, и некоторые коэффициенты a_j, b являются дробными.

Поскольку x_j – неотрицательные целые числа, то к ограничениям (2.23) можно добавить:

.                    (2.26)

Здесь стоит знак «≤», так как ∑[a_j]x_j – целое и его всегда можно ограничить целой частью b. Откуда следует, что неравенство (2.26) сохраняет все целые точки многогранника множества (2.23). Можно преобразовать неравенство (2.26) к виду:

,                          (2.27)

добавив свободную переменную x_n+1 с условием ее неотрицательности и целочисленности. Выражение (2.26) будет выполняться при целых x_j.

Вычитая из уравнения (2.27) уравнение (2.25), получим ограничение, содержащее дробные части:

,                   (2.28)

 – это уравнение называется отсечением Гомори.

Вместо ограничения (2.26) будем использовать ограничение (2.28), так как ограничение (2.28) уже не содержит базисную переменную из выражения (2.25), а новая базисная переменная x_n+1 будет выражена через прежние свободные.