Решение задачи методом отсекающих плоскостей (метод Гомори)

Для решения целочисленной задачи воспользуется решением линейной задачи без требования целочисленности. Перепишем симплекс-таблицу решённой задачи из пункта 1.3.

Таблица 2.1

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8
X5					-5			-2
X1	9/2				-1		-1/2
X2	7/4				-2		1/4	-1	1/2
X3	5/4				-1		-1/4		1/2
Y	-16

На основе этой симплекс-таблицы для базисной переменной x₁ (у нее наибольшая дробная часть) строим уравнение отсекающей плоскости по следующей формуле:

где f – дробная часть свободного члена;

f_ij – дробные части коэффициентов строки.

Представим новое ограничение в форме Куна-Таккера:

x₉=-1/2-(-5/16*x₃-7/8*x₅-5/8*x₇-13/16*x₈)

Добавляем это ограничение к условиям оптимального решения и решаем новую расширенную задачу симплекс-методом.

Таблица 2.2

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9
X4	7/2			-3/4		1/2		1/2	-3/4
X6	229/8			21/16		23/8		29/8	-99/16
X2	5/8			13/16		-1/8		-3/8	5/16
X1	35/8			11/16		1/8		3/8	-13/16
X9	-5/8			-5/16		-7/8		-5/8	-13/16
Y	-109/8			139/16		9/8		11/8	3/16

Используем двойственный симплекс-метод. Вводим в базис X8, выводим из базиса X9.

Таблица 2.3

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9
X4	53/13			-6/13		17/13		14/13		-12/13
X6	434/13			48/13		124/13		109/13		-99/13
X2	5/13			9/13		-6/13		-8/13		5/13
X1										-1
X8	10/13			5/13		14/13		10/13		-16/13
Y	-179/13			112/13		12/13		16/13		3/13

Решение оптимально. Так как переменная X8, подчиненная требованию целочисленности, и имеет дробное значение, то необходимо ввести дополнительное сечение относительно этой переменной:

x₁₀=-10/13-(-5/13*x₃-1/13*x₅-10/13*x₇-10/13*x₉)

Таблица 2.4

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X4	53/13			-6/13		17/13		14/13		-12/13
X6	434/13			48/13		124/13		109/13		-99/13
X2	5/13			9/13		-6/13		-8/13		5/13
X1										-1
X8	10/13			5/13		14/13		10/13		-16/13
X10	-10/13			-5/13		-1/13		-10/13		-10/13
Y	-179/13			112/13		12/13		16/13		3/13

Используем двойственный симплекс-метод. Вводим в базис X9, выводим из базиса X10.

Таблица 2.5

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X4						7/5					-6/5
X6				15/2		103/10					-99/10
X2				1/2		-1/2		-1			1/2
X1				3/2		11/10					-13/10
X8						6/5					-8/5
X9				1/2		1/10					-13/10
Y	-182/13			17/2		9/10					3/10

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

Ответ: Y=-14, X=(6;0;0;5;0;41;0;2;1;0).

Дата добавления: 2015-09-07