Метод Гомори

Метод Гомори решения задач целочисленного программирования является методом отсечения.

Суть метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана. Для этого сначала решается ослабленная задача линейного программирования без учета условия целочисленности переменных.

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

Для нахождения целочисленного решения задачи методом Гомори используется следующий алгоритм.

1. Решаем ослабленную задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.

2. Если в результате решения задачи линейного программирования в полученном оптимальном плане есть нецелая базисная переменная, то к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

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

Этой переменной соответствует строка симплексной таблицы, называемая строкой, производящей отсечение (производящей строкой).

Для изложения метода вводим следующие понятия. Пусть a – действительное число.

Под целой частью некоторого числа а понимается максимальное целое число [a], не превосходящее данного.

Под дробной частью некоторого числа а понимается наименьшее неотрицательное число такое, что разность между ним иа есть [a] – целая часть числа).

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

Обозначим ицелые части чисел и . Величины дробных частейи() определяются следующим образом

3. Составляем неравенство Гомори и включаем его в систему ограничений исходной задачи.

Для этого по производящей строке симплексной таблицы выписывается уравнение, предполагая, что первые m переменных являются базисными для данного оптимального плана

или

Переносим все целые части коэффициентов в одну сторону, оставляя все дробные в другой:

Так как <1, то заменяя в правой части , получим строгое неравенство

Так как левая часть неравенства должна принимать целые значения, то, следовательно, необходимое условие ее целочисленности можно записать только в следующем виде:

4. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу.

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

Пример. Методом Гомори найти решение задачи целочисленного программирования, состоящей в определении максимального значения функции при условии

Решение. Выравнивая неравенства с помощью вспомогательных переменных х₃, х₄, получаем задачу линейного программирования в канонической форме:

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

Б	СБ	В	С1=5	С2=11	С3=0	С4=0
			а1	а2	а3	а4
а3	0		3	4	1	0
а4	0	10	2	5	0	1
∆j =Zj–Сj		0	-5	-11	0	0

	СБ	В	С1=5	С2=11	С3=0	С4=0
			а1	а2	а3	а4
а2	11			1		0
а4	0			0		1
∆j =Zj–Сj				0		0

В найденном оптимальном плане значение переменной х₂ равно дробному числу. Находим его дробную часть и дробные части всех элементов строки, содержащей переменную х₂ , а именно:

Теперь составляем для найденных значений дробных частей неравенство Гомори:

.

Выравниваем неравенство Гомори с помощью новой вспомогательной переменной х₅, переносим свободный член уравнения в правую часть и получаем новое ограничение:

.

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

Б	СБ	В	С1=5	С2=11	С3=0	С4=0	С5=0
			а1	а2	а3	а4	а5
а2	110			1		0	0
а4	0			0		1	0
а5	0			0		0	1
∆j =Zj–Сj				0		0	0

Б	СБ	В	С1=5	С2=11	С3=0	С4=0	С5=0
			а1	а2	а3	а4	а5
а2	11	1	0	1	0	0	1
а4	0		0	0		1
а1	0		1	0		0
∆j =Zj–Сj			0	0		0

Полученное оптимальное решение расширенной задачи содержит нецелое значение переменной х₁, поэтому находим для этой строки дробные части всех нецелых чисел, а именно:

и новое неравенство Гомори имеет вид:

Выравниваем неравенство Гомори с помощью новой вспомогательной переменной х₆, переносим свободный член уравнения в правую часть и получаем новое ограничение: .

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

Б	СБ	В	С1=5	С2=11	С3=0	С4=0	С5=0	С6=0
			а1	а2	а3	а4	а5	а6
а2	110	1	0	1	0	0	1	0
а4	0		0	0		1		0
а1	0		1	0		0		0
а6	0		0	0		0		1
∆j =Zj–Сj			0	0		0		0

Б	СБ	В	С1=5	С2=11	С3=0	С4=0	С5=0	С6=0
			а1	а2	а3	а4	а5	а6
а2	110	1	0	1	0	0	1	0
а4	0	5	0	0	0	1	-1	-2
а1	0	0	1	0	0	0	-2	1
а3	0		0	0	1	0	2	-3
∆j =Zj–Сj		11	0	0	0	0	1	5

Таким образом, найдено оптимальное решение задачи целочисленного программирования: Z_max =11 при .

Замечания:

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