Полученное уравнениеесть не что иное как отсечение Гомори. Для 
имеем 
и уравнение (19)приобретает вид:
Уравнение (21) должно выполняться для любого целочисленногорешения задачи (12). Заметим, что если a0
в уравнении (21).Потому уравнение (21) может использоваться в качестве ведущей строки всимплекс-методе. В частности, всегда можно выбрать 
достаточно большим,так чтобы ведущий элемент 
в строке (21) сталравным –1, что позволит сохранить целочисленность таблицы. Выбор соответствующего будет влиять наскорость сходимости алгоритма. Прежде всего опишем самалгоритм. В качестве начального необходимо взять двойственно допустимоерешение, которое можно получить добавлением ограничения xn+m+1=M – x1 - - … - xn 
0, где M – достаточнобольшая константа, и проведением одной итерации с добавленной строкой и слексикографически минимальным столбцом, взятыми вкачестве ведущих. Алгоритм состоит из следующих шагов: Шаг 0. Начать с двойственнодопустимой матрицы A0 в уравнении (13), элементы которой – целыечисла (матрица A0 может содержать и нецелые элементы, обэтом см. [2], стр. 306).
Шаг 1. Среди строк с ai0i0 0 (i=1, …, n+m), то задачарешена.)
Шаг 2. Выбрать 
(правило выбора будетописано дальше) и написать внизу таблицы дополнительную строку
Эта строка выбирается в качестве ведущей.
Шаг 3. Провести шагдвойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться кшагу 1.
Доказательство конечности алгоритма см.[2], стр. 303-304.
Правило выбора формулируетсяследующим образом.
Шаг 0. Пусть строка сномером v является производящей.
Шаг 1. Пусть 
- лексикографическиминимальный столбец среди столбцов с avj
Шаг 2. Для каждого avj
- наибольшее целое,такое, что 
(лексикографическименьше). Шаг 3. Пусть 
, а 
(строка v -производящая). Тогда
.
Шаг 4. Положить 
для avj
Правило выбора , описанное выше, позволяет сделать ведущий элемент равным–1, при этом сохраняется двойственная допустимость таблицы ив то же время нулевой столбец будет максимально лексикографическиуменьшаться.
Подробнее об алгоритме можно прочитать в [2], стр. 300.
2.2.2Прямой алгоритм целочисленного программированияТермин “прямой”, примененный к алгоритму целочисленногопрограммирования, обозначает метод, который приводит к оптимальному решениюпосредством получения последовательно “улучшаемых” решений. Каждой из этихрешений допустимо в том смысле, что оно удовлетворяет как линейнымограничениям, так и условию целочисленности. Одним из вероятных достоинствалгоритма является возможность прервать вычисления, до того как полученооптимальное решение, и использовать наилучшее из полученных решений какприближенное. Кроме того, можно использовать прямой алгоритм в соединении сдвойственными алгоритмами, чтобы получать различные составные алгоритмы,которые могут переходить от фазы, дающей двойственно допустимые решения, кфазе, дающей прямо допустимые решения.
Естественным прецедентом для прямого алгоритма являетсяполностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритмаполучается последовательность двойственно допустимых целочисленных решений.Следует напомнить, что полностью целочисленный алгоритм Гомори представляетсобой модификацию двойственного симплекс-метода. Основное отличие этогоалгоритма состоит в том, что в качестве ведущей строки используется отсечениеГомори с ведущим элементом, равным –1. Это отсечение получается из производящейстроки, которая определяется как одна из возможных ведущих строк в двойственномсимплекс-методе. Использование такого отсечения в качестве ведущей строкисохранит после итерации двойственную допустимость и целочисленность таблицы.
Оказывается, можно аналогично модифицировать симплекс-методтаким образом, чтобы получить алгоритм, который сохраняет прямую допустимость ицелочисленность таблиц. Для описания вычислительной процедуры рассмотримследующую задачу целочисленного программирования:
максимизировать
при условиях
,
(целые) (k=1,…,n),
где a0j, aij и ai0 – целые числа и ai0 0.
Предположим, что столбец 
выбран в качествеведущего и строка v – ведущая строка в итерации симплекс-метода, т.е. 
для всех строк I, в которых ais>0.Прежде чем провести процедуру исключения Гаусса в симплекс-методе, добавим ктаблице отсечение Гомори, полученное из строки v: 
где J – множество индексов небазисных переменных в (22), sk –новая (базисная) слабая переменная и - неопределенная(временно) положительная константа.
