Решение задачи методом ветвей и границ 3 страница

Таблица 2.34

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12
X5				-2								-2
X6										-5		-3
X2											-1
X8				-3							-2	-2
X4										-1
X7				-4						-1	-5	-1
X1												-1
X12
Y	-21									-2

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

Таблица 2.35

БП

СЧ

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12

X5

-2

-2

-3

X6

-3

X2

-1

X8

-3

-2

-2

X4

X7

-4

-5

-1

X1

-1

X9

Y

-21

Решение оптимально.

Задача №7 - к исходным данным задачи №4 добавляется ограничение Х1<=5.

Выразим допустимый базис в форме Таккера;

x₅=3-(-2x₁+2x₂-2x₃+3x₄)

x₆=-2-(-3x₁+0x₂+3x₃-5x₄)

x₇=-11-(-1x₁-5x₂-4x₃-1x₄)

x₈=-10-(-2x₁-2x₂-3x₃+0x₄)

x₉=-4-(0x₁+0x₂+0x₃-1x₄)

x₁₀=-1-(0x₁-1x₂+0x₃+0x₄)

x₁₁=5-(1x₁+0x₂+0x₃+0x₄)

Целевая функция в форме Таккера:

Y=0-(4x₁+5x₂+17x₃-2x₄)

Таблица 2.36

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X5		-2		-2
X6	-2	-3			-5
X7	-11	-1	-5	-4	-1
X8	-10	-2	-2	-3
X9	-4				-1
X10	-1		-1
X11
Y					-2

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

Таблица 2.37

БП

СЧ

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X5

-7/5

-12/5

-18/5

13/5

2/5

X6

-2

-3

-5

X2

11/5

1/5

4/5

1/5

-1/5

X8

-28/5

-8/5

-7/5

2/5

-2/5

X9

-4

-1

X10

6/5

1/5

4/5

1/5

-1/5

X11

Y

-11

-3

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

Таблица 2.38

БП

СЧ

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X5

-3/2

-3/2

X6

17/2

45/8

-23/4

3/4

-15/8

X2

3/2

5/8

1/4

-1/4

1/8

X1

7/2

7/8

-1/4

1/4

-5/8

X9

-4

-1

X10

1/2

5/8

1/4

-1/4

1/8

X11

3/2

-7/8

1/4

-1/4

5/8

Y

-43/2

83/8

-9/4

1/4

15/8

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

Таблица 2.39

БП

СЧ

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X5

-1

-3/2

-3/2

X6

63/2

45/8

3/4

-15/8

-23/4

X2

1/2

5/8

-1/4

1/8

1/4

X1

9/2

7/8

1/4

-5/8

-1/4

X4

-1

X10

-1/2

5/8

-1/4

1/8

1/4

X11

1/2

-7/8

-1/4

5/8

1/4

Y

-25/2

83/8

1/4

15/8

-9/4

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

Таблица 2.40

БП

СЧ

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X8

2/3

-2/3

-2/3

-4/3

X6

131/4

15/2

-5/4

-1/2

-33/4

X2

5/12

2/4

1/12

-1/6

5/12

X1

59/12

3/2

-5/12

-1/6

-13/12

X4

-1

X10

-7/12

2/4

1/12

-1/6

5/12

X11

1/12

-6/4

5/12

1/6

13/12

Y

-55/4

17/2

5/4

3/2

1/4

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

Таблица 2.41

БП

СЧ

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X8

-1

-1

-3

-4

X6

69/2

-3/2

-19/2

-3

X2

-1

X1

11/2

-1/2

-3/2

-1

X4

-1

X7

7/2

-3

-1/2

-5/2

-6

X11

-1/2

-1

1/2

3/2

Y

-19

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

Таблица 2.42

БП

СЧ

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X8

7/2

-3/2

-9/2

-5

-1

X6

63/2

3/2

-1/2

X2

-1

X1

X4

-1

X7

-2

-7

-9

-3

X3

1/2

-1/2

-3/2

-1

-1

Y

-51/2

17/2

47/2

Решение оптимально. Остановка: текущее значение целевой функции <=-21.

Задача №5 - к исходным данным задачи №2 добавляется ограничение Х2<=0.

Выразим допустимый базис в форме Таккера:

x₅=3-(-2x₁+2x₂-2x₃+3x₄)

x₆=-2-(-3x₁+0x₂+3x₃-5x₄)

x₇=-11-(-1x₁-5x₂-4x₃-1x₄)

x₈=-10-(-2x₁-2x₂-3x₃+0x₄)

x₉=-4-(0x₁+0x₂+0x₃-1x₄)

x₁₀=0-(0x₁+1x₂+0x₃+0x₄)

Целевая функция в форме Таккера:

Y=0-(4x₁+5x₂+17x₃-2x₄)

Таблица 2.43

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X5		-2		-2
X6	-2	-3			-5
X7	-11	-1	-5	-4	-1
X8	-10	-2	-2	-3
X9	-4				-1
X10
Y					-2

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

Таблица 2.44

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X5	-7/5	-12/5		-18/5	13/5			2/5
X6	-2	-3			-5
X2	11/5	1/5		4/5	1/5			-1/5
X8	-28/5	-8/5		-7/5	2/5			-2/5
X9	-4				-1
X10	-11/5	-1/5		-4/5	-1/5			1/5
Y	-11				-3

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

Таблица 2.45

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X5				-3/2					-3/2
X6	17/2			45/8	-23/4			3/4	-15/8
X2	3/2			5/8	1/4			-1/4	1/8
X1	7/2			7/8	-1/4			1/4	-5/8
X9	-4				-1
X10	-3/2			-5/8	-1/4			1/4	-1/8
Y	-43/2			83/8	-9/4			1/4	15/8

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

Таблица 2.46

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X5	-1			-3/2					-3/2
X6	63/2			45/8				3/4	-15/8	-23/4
X2	1/2			5/8				-1/4	1/8	1/4
X1	9/2			7/8				1/4	-5/8	-1/4
X4										-1
X10	-1/2			-5/8				1/4	-1/8	-1/4
Y	-25/2			83/8				1/4	15/8	-9/4

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

Таблица 2.47

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

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

Таблица 2.48

БП	СЧ	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
X8				13/5		-2/5		-6/5			-16/5
X6				87/5		2/5		-19/5			-99/5
X2
X1				14/5		-1/5		-3/5			-13/5
X4				6/5		1/5		-2/5			-12/5
X9				6/5		1/5		-2/5			-12/5
Y	-14			41/5		6/5		8/5			3/5

Решение оптимально.

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