2.2 Метод Гомори

C помощью отсечений выделяют целочисленные части полиэдров. Метод отсечений был разработан в конце 1950-х годов Гомори для решения целочисленных линейных программ с помощью симплекс-метода. Метод отсечений оказался полезным и с теоретической точки зрения он дает возможность описать целочисленную оболочку полиэдра.

Далее описывается метод отсечений Гомори, дающий алгоритм решения задач целочисленного линейного программирования. Данный метод, который также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП (целочисленной задачи линейного программирования) в канонической форме. Описываемая ниже версия алгоритма предназначена для решения полностью целочисленных задач, т.е. таких, у которых все параметры a_ij, c_j, b_i – целые.

Описание алгоритма.

Приведем обобщенную схему алгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждая большая итерация содержит этапы:

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

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

3. Построение для найденной компоненты условия отсечения. Исходя из уравнения по данной строке x_r=P0_r - a_r,1*x₁ - … - a_r,n*x_n в систему ограничений добавляем неравенство, в котором коэффициенты будут дробными частями коэффициентов данного уравнения: {P0_r}–{ a_r,1}*x₁ -… -{ a_r,n}*x_n ≤0. Переводим к каноническому виду добавляя новую переменную x_n+1, получим: {P0_r}–{ a_r,1}*x₁ -… -{a_r,n}*x_n+x_n+1 =0 И соответственно добавляем в симплекс-таблицу новый базисный вектор по новой переменной x_n+1.

4. Переход на начало следующей большой итерации.

Замечание:

При добавлении в симплекс-таблицу нового базисного вектора по новой переменной x_n+1 мы получаем недопустимое (отрицательное) решение. Для того, чтобы избавиться от недопустимого решения выбираем столбец замещения так, чтобы строкой замещения стала новая добавленная строка по переменной x_n+1. Продолжаем пересчет симплекс-таблицы. Если снова получаем дробное решение, то еще вводим дополнительный базисный вектор, и так до получения целочисленного решения. Но следует заметить, что если область допустимых решений очень мала, то она может и не содержать целых значений, это необходимо проверить графически. Если область допустимых решений не содержит целочисленного решения, то в применении метода Гомори нет необходимости, целого решения не будет.

Решить задачу.

Zmin=6*x1 +x2;

при ограничениях:

3*x1 - x2>=92*x1+3*x2=<50- x1+4*x2>=18

x1,x2>=0; x1,x2: целые числа

Математическая модель задачи:

Целевая функция:

S min = 6*x1+1*x2

при ограничениях:3*x1-1*x2>=92*x1+3*x2<=50 -1*x1+4*x2>=18

x1,x2 >=0; - условие не отрицательности переменных.

Решение задачи с использованием метода симплекс-таблиц.

Математическая модель задачи:

Целевая функция: S min = 6*x1+1*x2

при ограничениях: 3*x1-1*x2>=9 2*x1+3*x2<=50 -1*x1+4*x2>=18

x1,x2, >=0; - условие неотрицательности переменных.

Система неравенств приведена к каноническому виду:

Целевая функция: S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Система ограничений: -3*x1+x2+x3=-9 2*x1+3*x2+x4=50 x1-4*x2+x5=-18

Векторный анализ системы ограничений:

Расширенная целевая функция: S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Вектора:

P0	P1(x1)	P2(x2)	P3(x3)	P4(x4)	P5(x5)
-9	-3	1	1	0	0
50	2	3	0	1	0
-18	1	-4	0	0	1

Базис: Базисный вектор №1: P3(x3)

Базисный вектор №2: P4(x4)

Базисный вектор №3: P5(x5)

Расширенная целевая функция: S min = 6*x1+1*x2+0*x3+0*x4+0*x5

Заполним первую таблицу:

№	Base	CBase	P0	6	1	0	0	0
				P1	P2	P3	P4	P5
1	P3	0	-9	-3	1	1	0	0
2	P4	0	50	2	3	0	1	0
3	P5	0	-18	1	-4	0	0	1
S min =			0	-6	-1	0	0	0

Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P3 (1-я строка) Новый базисный вектор: P1 (1-й столбец) Заменяем базисный вектор P3 на P1.

№	Base	CBase	P0		6		1		0		0		0
					P1		P2		P3		P4		P5
1	P1	6	3		1		-0,3333		-0,3333		0		0
2	P4	0	44		0		3,6667		0,6667		1		0
3	P5	0	-21		0		-3,6667		0,3333		0		1
S min =				18		0		-3		-2		0		0

Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P5 (3-я строка) Новый базисный вектор: P2 (2-й столбец) Заменяем базисный вектор P5 на P2. 

№	Base	CBase		P0	6		1		0		0		0
					P1		P2		P3		P4		P5
1	P1	6		4,9091	1		0		-0,3636		0		-0,0909
2	P4	0		23	0		0		1		1		1
3	P2	1		5,7273	0		1		-0,0909		0		-0,2727
S min =			35,1818		0	0		-2,2727		0		-0,8182

Решение не целочисленное. Применим метод Гомори: выберем в таблице строку, в которой целая часть дробного свободного члена (P0) принимает наибольшее значение. Макс. целая часть дробного свободного члена при базисном векторе P2 (3-я строка). Составим уравнение ограничения и добавим в таблицу новый базисный вектор по новому уравнению и новой переменной. Добавляем базисный вектор: P6 (6-й столбец).

№	Base	CBase	P0	6	1	0	0	0	0
				P1	P2	P3	P4	P5	P6
1	P1	6	4,9091	1	0	-0,3636	0	-0,0909	0
2	P4	0	23	0	0	1	1	1	0
3	P2	1	5,7273	0	1	-0,0909	0	-0,2727	0
4	P6	0	-0,7273	0	0	-0,9091	0	-0,7273	1
S min =			35,1818	0	0	-2,2727	0	-0,8182	0

Невозможно выбрать столбец замещения, так как нет положительных dj! Выберем столбец таким образом. Чтобы избавиться от недопустимого решения, т.е. от отрицательных значений в столбце свободных членов (Р0). Замещаемый базисный вектор: P6 (4-я строка) Новый базисный вектор: P5 (5-й столбец) Заменяем базисный вектор P6 на P5.

№	Base	CBase	P0		6		1		0		0		0		0
					P1		P2		P3		P4		P5		P6
1	P1	6	5		1		0		-0,25		0		0		-0,125
2	P4	0	22		0		0		-0,25		1		0		1,375
3	P2	1	6		0		1		0,25		0		0		-0,375
4	P5	0	1		0		0		1,25		0		1		-1,375
S min =				36		0		0		-1,25		0		0		-1,125

Невозможно выбрать столбец замещения, так как нет положительных dj! Получено оптимальное решение! 

Из таблицы получим значения переменных целевой функции:

x1	x2	x3	x4	x5	p6
5	6	0	22	1	0

Целевая функция: S min = 6*5+1*6 И в результате: S min = 36; Задача решена.