Метод Гомори

Ясно, что когда задача целочисленного программирования имеет более двух переменных, её необходимо решать аналитическими методами. Одним из таких методов является метод Гомори. Он заключается в следующем.

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

2. Допустим, b_i - нецелочисленная компонента решения, полученного на 1-м шаге, , , …, - коэффициенты при свободных переменных , , …, соответствующего ограничения, из которых хотя бы один – не целый. Тогда к ограничениям, полученным в последней симплекс-таблице, добавляется дополнительное ограничение { } +{ } +…+{ } ³ { b_i }, которое после введения очередной дополнительной переменной примет вид

{ } +{ } +…+{ } - x_{n +1}={ b_i }. (1.1)

Здесь { a } - дробная часть числа a, n - количество переменных задачи в последней симплекс-таблице. Идём к пункту 1.

Если нецелочисленных компонент в оптимальном решении, полученном на первом шаге, несколько, то берём ту, у которой дробная часть наибольшая.

Если b_i - дробное, а все коэффициенты , , …, при свободных переменных (в последней симплекс-таблице)являются целыми, то задача целочисленного программирования не имеет решения. Ясно, что задача целочисленного программирования решения не будет иметь, если задача решений не имеет вообще.

Пример 2. Решить задачу целочисленного программирования методом Гомори:

2 x ₁+4 x ₂®max

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

Базис	Сб	Св. чл.					q 1	q 2
x 1	x 2	x 3	x 4
x 3
x 4
D j		-2	-4
x 3						-
x 2
D j		-				-
x 1						-
x 2					-
D j

Таким образом, X ₀= - оптимальное решение, то есть нецелочисленных компонент в оптимальном решении, полученном на первом шаге, два. Найдём их дробные части и сравним:

, и

Поэтому составляем дополнительное ограничение по первой компоненте оптимального решения, которой в последней симплекс-таблице соответствует ограничение . Имеем , . Поэтому дополнительное ограничение (1.1) в нашем случае принимает вид

.

Полученную задачу снова решаем как обычную:

Базис	Сб	Св. чл.						q 3
x 1	x 2	x 3	x 4	x 5
x 1						-
x 2					-
-	-						-1
x 1						-1
x 2							-
x 3							-
D j

Получили оптимальное решение X ₀= данной задачи. Но так как исходная задача зависит только от двух переменных x ₁ и x ₂, которые принимают в этом решении целочисленные значения, то задача целочисленного программирования решена.

Ответ: X _цел.=(1, 3), F _{max цел.}=14.

Метод Гомори - не единственный аналитический метод решения целочисленной задачи. Разработан целый ряд аналитических методов, отличных от данного. В учебной литературе можно найти, например, метод ветвей и границ.