Первый алгоритм Гомори

Все коэффициенты в ограничениях должны быть целыми, чтобы решение было целочисленным.

Пример 1:

Начинаем с решения задачи (задача, у которой нет требования целочисленности). Так как она непрерывна, то может быть применен симплекс-метод. Пусть итоговая симплекс-таблица имеет вид (m-дополнительных переменных, n-базисных переменных, m+n-число переменных): БП СП

Базис	Свободный член
f

Предполагается, что решение не является целочисленным .

Среди решения есть нецелые числа. Выберем строку в симплекс-таблице, в которой соответствующий нецелочисленный коэффициент . Ей соответствует уравнение:

(5.4)

Каждую строку симплекс-таблицы с нецелым будем называть производящими строками.

Пусть – некоторое действительное число,

– целая часть числа.

Целой частью числа называется наибольшее целое число, не превышающее , то есть всегда выполняется

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

Пример 2:

В дробной части нет отрицательных переменных.

Подставим эти выражения в соотношение (5.4):

Сгруппируем полученное соотношение, перенеся влево дробные части:

(5.5)

Проанализируем приведенное уравнение. В правой части все переменные должны быть целыми. Если это так, то и левая часть тоже целое число.

По условию , .

.

Левая часть (5.5) может быть целой и меньше единицы, то есть принимать значения из набора чисел

Таким образом, необходимое условие целочисленности левой части (5.5) можно записать в виде:

(5.6)

(5.6) – отсечение Гомори для полностью целочисленной задачи.

Так как – свободные, то- невозможно, так как нецелочисленное оптимальное решение условию (5.6) не удовлетворяет. Так как в процессе учитывается целочисленность, то условие 2 выполняется. Следовательно (5.6) задает правильное отсечение.

Преобразуем (5.6) к виду:

(5.7)

Получаем задачу :

Наиболее удобным методом решения является двойственный симплекс-метод.

m+1 – число базисных переменных

m+n+1 – число переменных.

Переменную вводим в базис и знаем, что эта переменная принимает отрицательные значения.

Начальная симплекс-таблица для задачи :

Базис	Свободный член
f

Недостатки алгоритма Гомори:

1)ошибки округления могут привести к неоптимальному решению. Предлагается хранить в отдельных таблицах числитель и знаменатель.

2)на каждом шаге получается недопустимое решение. У нас нет допустимого базисного решения. Только в конце мы получаем целочисленное решение.

Если производящих строк две, то для выбора производящей строки используют эмпирические правила:

1)

2)

Замечание: нет гарантий, что выбранная строка дает наименьшее число шагов.