4.3. Метод Гомори (метод отсекающих плоскостей, метод отсечения)

Пусть необходимо найти решение задачи (1) - (4). Временно отбросив условие (4) (условие целочисленности), отыскиваем оптимальный опорный план, используя симплекс-метод.

Допустим, что найденный оптимальный план не является целочисленным. Тогда для i-той переменной, имеющей нецелочисленное значение, формируем дополнительное ограничение

(4.9)

где - дробная часть значения коэффициента- разложения небазиснойj-ой переменной по і-ой базисной.

- дробная часть значенияi-ой базисной переменной , т.е., причем;, причем; здесь- целая часть- целая часть, значити.

Нецелочисленный план Х^опт не удовлетворяет неравенству (4.9), так как , а левая часть неравенства равна нулю, поскольку небазисные переменные х_j равны нулю. В то же время любой целочисленный план удовлетворяет выражению (4.9) как строгому неравенству, так как для всехі .

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

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

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

(4.10)

Введением ограничения (10) мы увеличили размер базиса на единицу. Возьмем в качестве дополнительной базисной переменной х_n+1

и запишем (10) в виде

(4.11)

Сформулируем в оптимальной симлекс-таблице дополнительную строку, в которую запишем и, соответствующие (11). Получим некоторый псевдоплан с базисными компонентамих_іо и новой составляющей . Используя двойственный симплекс-метод, находим оптимальный план.

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

Пример

F(x)=x₁+4x₂ →max

2x₁+4x₂ ≤ 7

10x₁+3x₂ ≤ 15

x_1,2 ≥ 0, Z

Отбрасываем условие целочисленности, находим оптимальное решение симплекс-методом.

Абаз	Сбаз	Ао	1	4	0	0
			А1	А2	А3	А4
А3	0	7	2	4	1	0
А4	0	15	10	3	0	1
		0	-1	-4	0	0

А2	4	7/4	1/2	1	¼	0
А4	0	39/4	34/4	0	-3/4	1
		7	1	0	1	0

Таким образом Х^опт={0; 7/4}, Fmax=7

Данное решение не удовлетворяет условию целочисленности, поэтому формируем дополнительное условие для x₂:

отсюда получим дополнительное условие:

Данное условие запишем в виде:

Вводя дополнительную переменную, последнее неравенство запишем в виде равенства:

Умножая на -1, получим:

Данное ограничение дописываем к последней симплекс-таблице, вводя еще один базисный вектор A₅, и находим оптимальное решение двойственным симплекс-методом:

Абаз	Сбаз	Ао	1	4	0	0	0
			А1	А2	А3	А4	А5
А2	4	7/4	1/2	1	1/4	0	0
А4	0	39/4	34/4	0	-3/4	1	0
		7	1	0	1	0
А5	0	-3	-2	0	-1	0	1

А2	4	1	0	1	0	0	1/4
А4	0	-3	0	0	-5	1	17/4
A1	1	3/2	1	0	1/2	0	-1/2
		11/2	0	0	1/2	0	1/2

А2	4	1	0	1	0	0	1/4
А3	0	3/5	0	0	1	-1/5	-17/20
A1	1	12/10	1	0	0	1/10	-3/40
		52/10	0	0	0	1/10	37/40

Новое оптимальное решение опять не является целочисленным. Формируем дополнительное условие для х₁:

откуда –х₄ -7х₅ + х₆ = -2

Последнее условие дописываем в последнюю симплекс-таблицу и находим новое оптимальное решение двойственным симплекс-методом:

Абаз	Сбаз	Ао	1	4	0	0	0	0
			А1	А2	А3	А4	А5	А6
А2	4	1	0	1	0	0	¼	0
А3	0	3/5	0	0	1	-1/5	-17/20	0
А1		12/10	1	0	0	1/10	-3/40	0
		52/10	0	0	0	1/10	37/40	0
А6	0	-2	0	0	0	-1	-7	1

А2	4	1	0	1	0	0	¼	0
А3	0	1	0	0	1	0	11/20	-1/5
А1	1	1	1	0	0	0	-31/40	1/10
А6	0	2	0	0	0	1	7	-1
		5

Таким образом искомое целочисленное решение будет:

Х ^опт = {1;1}; Fmax =5