2.1.7 Решение двойственной задачи

Прямая задача:

Двойственная задача:

Приводим к каноническому виду:

y₁,y₃– базисные переменные,y₂,y₄,y₅,y₆– свободные переменные

				↑
		b		y2		y4		y5		y6
←	y1	14		5		-5		2		-3		14/5
			14/5		1/5		-1		2/5		-3/5
	y3	9		3		-3		1		-2		3
			-42/5		-3/5		3		-6/5		9/5
	Ф’	112		35		-40		12		-25
			-98		-7		35		-14		21

b

y2

y4

y5

y6

y1

14/5

1/5

-1

2/5

-3/5

y3

3/5

-3/5

0

-1/5

-1/5

Ф’

14

-7

-5

-2

-4

x1	x2	x3	x4	x5	x6
↕	↕	↕	↕	↕	↕
y5	y6	y1	y2	y3	y4
2	4	7	0	0	5

F’ = Ф’ = 14

X = (2,4,7,0,0,5)

F= -F’ = -14

2.2 Задача целочисленного линейного программирования

2.2.1 Постановка задачи целочисленного линейного программирования

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

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

x₃,x₄– базисные переменные,x₁,x₂– свободные переменные

				↑
		b		x1		x2
	x3	11		2		3		11/2
			-5		-1/2		-1/2
←	x4	10		4		1		10/4
			5/2		1/4		1/4
	F’	0		2		1
			-5		-1/2		-1/2

						↑
		b		x4		x2
←	x3	6		-1/2		5/2		12/5
			12/5		-1/5		2/5
	x1	5/2		1/4		1/4		10
			-3/5		1/20		-1/10
	F’	-5		-1/2		1/2
			-6/5		1/10		-1/5

		b		x1		x2
	x3	12/5		-1/5		2/5
	x4	19/10		3/10		-1/10
	F’	-31/5		-2/5		-1/5

X= (19/10, 12/5, 0, 0)

F= -F’ = 31/5

Составляем неравенство Гомори:

						↑
		b		x4		x3
	F’	-31/5		-2/5		-1/5
			1/5		1/10		-1/2
	x2	12/5		-1/5		2/5
			-2/5		-1/5		1
	x1	19/10		3/10		-1/10
			1/10				-1/4
←	u2	-2/5		-1/5		-2/5
			1		1/2		-5/2

		b		x4		u2
	F’	-6		-3/10		-1/2
	x2	2		-2/5		1
	x1	2		7/20		-1/4
	x3	1		1/2		-5/2

X = (2, 2, 1, 0)

F= -F’ = 6