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

Приведём решение исходной задачи симплекс-методом, опустив требование целочисленности. Оно представлено в таблице 2.53.

Таблица 2.53

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8
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
Y	-109/8			139/16		9/8		11/8	3/16

Значение переменной x₄ не удовлетворяет требованиям целочисленности. Поэтому вводим дополнительное отсечение, исходя из данной строки.

Ограничения для частично-целочисленных задач по методу Гомори формируются в виде:

где - дробная часть свободного члена базисной переменной,

- коэффициент, рассчитываемый для небазисных переменных.

Для не подчиненных требованию целочисленности коэффициент рассчитывается по формуле:

Для подчиненных требованию целочисленности коэффициент рассчитывается по формуле:

Вычислим отсекающую плоскость и представим ее в форме Таккера:

X9=-1/2-(-3/4*X3-1/2*X5-1/2*X7-3/4*X8)

Добавим в базис таблицы 2.53 полученное ограничение. Результат представлен в таблице 2.54.

Таблица 2.54

БП	СЧ	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	-1/2			-3/4		-1/2		-1/2	-3/4
Y	-109/8			139/16		9/8		11/8	3/16

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

Таблица 2.55

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9
X4										-1
X6	131/4			15/2				31/4		-33/4
X2	5/12			2/4		-2/6		-7/12		5/12
X1	59/12			6/4		4/6		11/12		-13/12
X8	2/3					2/3		2/3		-4/3
Y	-55/4			17/2				5/4		1/4

Полученное оптимальное решение удовлетворяет требованию целочисленности х₄.

Ответ: Y=-55/4, X=(59/12;5/12;0;4;0;131/4;0;2/3;0).

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