Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Вятский государственный университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Тело мой курсач2.doc

Скачиваний:

Добавлен:

02.06.2015

Размер:

1.95 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 125 6 7 8 9 10 11 12 > Следующая >>>

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

Согласно методу для каждой целочисленной переменной возможно задать верхнюю и нижнюю границу, в пределах которых содержится ее оптимальное значение. В данном случае нижняя граница равна . На практике верхний предел не вводят в виде дополнительного ограничения, а учитывают его в процессе решения не явно, то есть к исходным ограничения на практике добавляется ограничение, которое определяется самим методом.

Задача №1 - ослабленная задача. Данная задача решена в пункте 1.3. Добавим задачу в основной список. Решение:

Таблица 2.6

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈
X₄	7/2	0	0	-3/4	1	1/2	0	1/2	-3/4
X₆	229/8	0	0	21/16	0	23/8	1	29/8	-99/16
X₂	5/8	0	1	13/16	0	-1/8	0	-3/8	5/16
X₁	35/8	1	0	11/16	0	1/8	0	3/8	-13/16
Y	-109/8	0	0	139/16	0	9/8	0	11/8	3/16

Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи. Для образования порожденных задач выберем переменную Х4.

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

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

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₄)

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

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

Таблица 2.7

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	3	-2	2	-2	3	1	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0
X₉	-4	0	0	0	-1	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0

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

Таблица 2.8

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0
X₉	-4	0	0	0	-1	0	0	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0

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

Таблица 2.9

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	7	0	0	-3/2	2	1	0	1	-3/2	0
X₆	17/2	0	0	45/8	-23/4	0	1	3/4	-15/8	0
X₂	3/2	0	1	5/8	1/4	0	0	-1/4	1/8	0
X₁	7/2	1	0	7/8	-1/4	0	0	1/4	-5/8	0
X₉	-4	0	0	0	-1	0	0	0	0	1
Y	-43/2	0	0	83/8	-9/4	0	0	1/4	15/8	0

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

Таблица 2.10

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	-1	0	0	-3/2	0	1	0	1	-3/2	2
X₆	63/2	0	0	45/8	0	0	1	3/4	-15/8	-23/4
X₂	1/2	0	1	5/8	0	0	0	-1/4	1/8	1/4
X₁	9/2	1	0	7/8	0	0	0	1/4	-5/8	-1/4
X₄	4	0	0	0	1	0	0	0	0	-1
Y	-25/2	0	0	83/8	0	0	0	1/4	15/8	-9/4

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

Таблица 2.11

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₈	2/3	0	0	1	0	-2/3	0	-2/3	1	-4/3
X₆	131/4	0	0	15/2	0	-5/4	1	-1/2	0	-33/4
X₂	5/12	0	1	2/4	0	1/12	0	-1/6	0	5/12
X₁	59/12	1	0	3/2	0	-5/12	0	-1/6	0	-13/12
X₄	4	0	0	0	1	0	0	0	0	-1
Y	-55/4	0	0	17/2	0	5/4	0	3/2	0	1/4

Решение оптимально. Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи. Для образования порожденных задач выберем переменную Х2.

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

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

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₄)

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

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

Таблица 2.12

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	3	-2	2	-2	3	1	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0
X₁₀	-1	0	-1	0	0	0	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0	0

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

Таблица 2.13

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0
X₁₀	6/5	1/5	0	4/5	1/5	0	0	-1/5	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0	0

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

Таблица 2.14

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	7	0	0	-3/2	2	1	0	1	-3/2	0	0
X₆	17/2	0	0	45/8	-23/4	0	1	3/4	-15/8	0	0
X₂	3/2	0	1	5/8	1/4	0	0	-1/4	1/8	0	0
X₁	7/2	1	0	7/8	-1/4	0	0	1/4	-5/8	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0
X₁₀	1/2	0	0	5/8	1/4	0	0	-1/4	1/8	0	1
Y	-43/2	0	0	83/8	-9/4	0	0	1/4	15/8	0	0

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

Таблица 2.15

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	-1	0	0	-3/2	0	1	0	1	-3/2	2	0
X₆	63/2	0	0	45/8	0	0	1	3/4	-15/8	-23/4	0
X₂	1/2	0	1	5/8	0	0	0	-1/4	1/8	1/4	0
X₁	9/2	1	0	7/8	0	0	0	1/4	-5/8	-1/4	0
X₄	4	0	0	0	1	0	0	0	0	-1	0
X₁₀	-1/2	0	0	5/8	0	0	0	-1/4	1/8	1/4	1
Y	-25/2	0	0	83/8	0	0	0	1/4	15/8	-9/4	0

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

Таблица 2.16

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₈	2/3	0	0	1	0	-2/3	0	-2/3	1	-4/3	0
X₆	131/4	0	0	15/2	0	-5/4	1	-1/2	0	-33/4	0
X₂	5/12	0	1	2/4	0	1/12	0	-1/6	0	5/12	0
X₁	59/12	1	0	3/2	0	-5/12	0	-1/6	0	-13/12	0
X₄	4	0	0	0	1	0	0	0	0	-1	0
X₁₀	-7/12	0	0	2/4	0	1/12	0	-1/6	0	5/12	1
Y	-55/4	0	0	17/2	0	5/4	0	3/2	0	1/4	0

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

Таблица 2.17

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₈	3	0	0	-1	0	-1	0	0	1	-3	-4
X₆	69/2	0	0	6	0	-3/2	1	0	0	-19/2	-3
X₂	1	0	1	0	0	0	0	0	0	0	-1
X₁	11/2	1	0	1	0	-1/2	0	0	0	-3/2	-1
X₄	4	0	0	0	1	0	0	0	0	-1	0
X₇	7/2	0	0	-3	0	-1/2	0	1	0	-5/2	-6
Y	-19	0	0	13	0	2	0	0	0	4	9

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

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

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₁₁=-6-(-1x₁+0x₂+0x₃+0x₄)

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

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

Таблица 2.18

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	3	-2	2	-2	3	1	0	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0
X₁₀	-1	0	-1	0	0	0	0	0	0	0	1	0
X₁₁	-6	-1	0	0	0	0	0	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0	0	0

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

Таблица 2.19

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0
X₁₀	6/5	1/5	0	4/5	1/5	0	0	-1/5	0	0	1	0
X₁₁	-6	-1	0	0	0	0	0	0	0	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0	0	0

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

Таблица 2.20

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	13	0	0	-18/5	13/5	1	0	2/5	0	0	0	-12/5
X₆	16	0	0	3	-5	0	1	0	0	0	0	-3
X₂	1	0	1	4/5	1/5	0	0	-1/5	0	0	0	1/5
X₈	4	0	0	-7/5	2/5	0	0	-2/5	1	0	0	-8/5
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0
X₁₀	0	0	0	4/5	1/5	0	0	-1/5	0	0	1	1/5
X₁	6	1	0	0	0	0	0	0	0	0	0	-1
Y	-29	0	0	13	-3	0	0	1	0	0	0	3

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

Таблица 2.21

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	13/5	0	0	-18/5	0	1	0	2/5	0	13/5	0	-12/5
X₆	36	0	0	3	0	0	1	0	0	-5	0	-3
X₂	1/5	0	1	4/5	0	0	0	-1/5	0	1/5	0	1/5
X₈	12/5	0	0	-7/5	0	0	0	-2/5	1	2/5	0	-8/5
X₄	4	0	0	0	1	0	0	0	0	-1	0	0
X₁₀	-4/5	0	0	4/5	0	0	0	-1/5	0	1/5	1	1/5
X₁	6	1	0	0	0	0	0	0	0	0	0	-1
Y	-17	0	0	13	0	0	0	1	0	-3	0	3

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

Таблица 2.22

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	1	0	0	-2	0	1	0	0	0	3	2	-2
X₆	36	0	0	3	0	0	1	0	0	-5	0	-3
X₂	1	0	1	0	0	0	0	0	0	0	-1	0
X₈	4	0	0	-3	0	0	0	0	1	0	-2	-2
X₄	4	0	0	0	1	0	0	0	0	-1	0	0
X₇	4	0	0	-4	0	0	0	1	0	-1	-5	-1
X₁	6	1	0	0	0	0	0	0	0	0	0	-1
Y	-21	0	0	17	0	0	0	0	0	-2	5	4

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

Таблица 2.23

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₉	1/3	0	0	-2/3	0	1/3	0	0	0	1	2/3	-2/3
X₆	113/3	0	0	-1/3	0	5/3	1	0	0	0	10/3	-19/3
X₂	1	0	1	0	0	0	0	0	0	0	-1	0
X₈	4	0	0	-3	0	0	0	0	1	0	-2	-2
X₄	13/3	0	0	-2/3	1	1/3	0	0	0	0	2/3	-2/3
X₇	13/3	0	0	-14/3	0	1/3	0	1	0	0	-13/3	-5/3
X₁	6	1	0	0	0	0	0	0	0	0	0	-1
Y	-61/3	0	0	47/3	0	2/3	0	0	0	0	19/3	8/3

Задача №8 - к исходным данным задачи №6 добавляется ограничение Х4>=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₁₁=-6-(-1x₁+0x₂+0x₃+0x₄)

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

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

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

Таблица 2.24

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	3	-2	2	-2	3	1	0	0	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0	0	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0	0
X₁₀	-1	0	-1	0	0	0	0	0	0	0	1	0	0
X₁₁	-6	-1	0	0	0	0	0	0	0	0	0	1	0
X₁₂	-5	0	0	0	-1	0	0	0	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0	0	0	0

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

Таблица 2.25

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0	0	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0	0
X₁₀	6/5	1/5	0	4/5	1/5	0	0	-1/5	0	0	1	0	0
X₁₁	-6	-1	0	0	0	0	0	0	0	0	0	1	0
X₁₂	-5	0	0	0	-1	0	0	0	0	0	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0	0	0	0

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

Таблица 2.26

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	13	0	0	-18/5	13/5	1	0	2/5	0	0	0	-12/5	0
X₆	16	0	0	3	-5	0	1	0	0	0	0	-3	0
X₂	1	0	1	4/5	1/5	0	0	-1/5	0	0	0	1/5	0
X₈	4	0	0	-7/5	2/5	0	0	-2/5	1	0	0	-8/5	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0	0
X₁₀	0	0	0	4/5	1/5	0	0	-1/5	0	0	1	1/5	0
X₁	6	1	0	0	0	0	0	0	0	0	0	-1	0
X₁₂	-5	0	0	0	-1	0	0	0	0	0	0	0	1
Y	-29	0	0	13	-3	0	0	1	0	0	0	3	0

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

Таблица 2.27

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	0	0	0	-18/5	0	1	0	2/5	0	0	0	-12/5	13/5
X₆	41	0	0	3	0	0	1	0	0	0	0	-3	-5
X₂	0	0	1	4/5	0	0	0	-1/5	0	0	0	1/5	1/5
X₈	2	0	0	-7/5	0	0	0	-2/5	1	0	0	-8/5	2/5
X₉	1	0	0	0	0	0	0	0	0	1	0	0	-1
X₁₀	-1	0	0	4/5	0	0	0	-1/5	0	0	1	1/5	1/5
X₁	6	1	0	0	0	0	0	0	0	0	0	-1	0
X₄	5	0	0	0	1	0	0	0	0	0	0	0	-1
Y	-14	0	0	13	0	0	0	1	0	0	0	3	-3

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

Таблица 2.28

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	-2	0	0	-2	0	1	0	0	0	0	2	-2	3
X₆	41	0	0	3	0	0	1	0	0	0	0	-3	-5
X₂	1	0	1	0	0	0	0	0	0	0	-1	0	0
X₈	4	0	0	-3	0	0	0	0	1	0	-2	-2	0
X₉	1	0	0	0	0	0	0	0	0	1	0	0	-1
X₇	5	0	0	-4	0	0	0	1	0	0	-5	-1	-1
X₁	6	1	0	0	0	0	0	0	0	0	0	-1	0
X₄	5	0	0	0	1	0	0	0	0	0	0	0	-1
Y	-19	0	0	17	0	0	0	0	0	0	5	4	-2

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

Таблица 2.29

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₁₁	1	0	0	1	0	-1/2	0	0	0	0	-1	1	-3/2
X₆	44	0	0	6	0	-3/2	1	0	0	0	-3	0	-19/2
X₂	1	0	1	0	0	0	0	0	0	0	-1	0	0
X₈	6	0	0	-1	0	-1	0	0	1	0	-4	0	-3
X₉	1	0	0	0	0	0	0	0	0	1	0	0	-1
X₇	6	0	0	-3	0	-1/2	0	1	0	0	-6	0	-5/2
X₁	7	1	0	1	0	-1/2	0	0	0	0	-1	0	-3/2
X₄	5	0	0	0	1	0	0	0	0	0	0	0	-1
Y	-23	0	0	13	0	2	0	0	0	0	9	0	4

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

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

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

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₁₁=-6-(-1x₁+0x₂+0x₃+0x₄)

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

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

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

Таблица 2.30

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	3	-2	2	-2	3	1	0	0	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0	0	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0	0
X₁₀	-1	0	-1	0	0	0	0	0	0	0	1	0	0
X₁₁	-6	-1	0	0	0	0	0	0	0	0	0	1	0
X₁₂	4	0	0	0	1	0	0	0	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0	0	0	0

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

Таблица 2.31

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0	0	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0	0
X₁₀	6/5	1/5	0	4/5	1/5	0	0	-1/5	0	0	1	0	0
X₁₁	-6	-1	0	0	0	0	0	0	0	0	0	1	0
X₁₂	4	0	0	0	1	0	0	0	0	0	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0	0	0	0

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

Таблица 2.32

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	13	0	0	-18/5	13/5	1	0	2/5	0	0	0	-12/5	0
X₆	16	0	0	3	-5	0	1	0	0	0	0	-3	0
X₂	1	0	1	4/5	1/5	0	0	-1/5	0	0	0	1/5	0
X₈	4	0	0	-7/5	2/5	0	0	-2/5	1	0	0	-8/5	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0	0
X₁₀	0	0	0	4/5	1/5	0	0	-1/5	0	0	1	1/5	0
X₁	6	1	0	0	0	0	0	0	0	0	0	-1	0
X₁₂	4	0	0	0	1	0	0	0	0	0	0	0	1
Y	-29	0	0	13	-3	0	0	1	0	0	0	3	0

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

Таблица 2.33

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	13/5	0	0	-18/5	0	1	0	2/5	0	13/5	0	-12/5	0
X₆	36	0	0	3	0	0	1	0	0	-5	0	-3	0
X₂	1/5	0	1	4/5	0	0	0	-1/5	0	1/5	0	1/5	0
X₈	12/5	0	0	-7/5	0	0	0	-2/5	1	2/5	0	-8/5	0
X₄	4	0	0	0	1	0	0	0	0	-1	0	0	0
X₁₀	-4/5	0	0	4/5	0	0	0	-1/5	0	1/5	1	1/5	0
X₁	6	1	0	0	0	0	0	0	0	0	0	-1	0
X₁₂	0	0	0	0	0	0	0	0	0	1	0	0	1
Y	-17	0	0	13	0	0	0	1	0	-3	0	3	0

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

Таблица 2.34

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	1	0	0	-2	0	1	0	0	0	3	2	-2	0
X₆	36	0	0	3	0	0	1	0	0	-5	0	-3	0
X₂	1	0	1	0	0	0	0	0	0	0	-1	0	0
X₈	4	0	0	-3	0	0	0	0	1	0	-2	-2	0
X₄	4	0	0	0	1	0	0	0	0	-1	0	0	0
X₇	4	0	0	-4	0	0	0	1	0	-1	-5	-1	0
X₁	6	1	0	0	0	0	0	0	0	0	0	-1	0
X₁₂	0	0	0	0	0	0	0	0	0	1	0	0	1
Y	-21	0	0	17	0	0	0	0	0	-2	5	4	0

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

Таблица 2.35

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁	X₁₂
X₅	1	0	0	-2	0	1	0	0	0	0	2	-2	-3
X₆	36	0	0	3	0	0	1	0	0	0	0	-3	5
X₂	1	0	1	0	0	0	0	0	0	0	-1	0	0
X₈	4	0	0	-3	0	0	0	0	1	0	-2	-2	0
X₄	4	0	0	0	1	0	0	0	0	0	0	0	1
X₇	4	0	0	-4	0	0	0	1	0	0	-5	-1	1
X₁	6	1	0	0	0	0	0	0	0	0	0	-1	0
X₉	0	0	0	0	0	0	0	0	0	1	0	0	1
Y	-21	0	0	17	0	0	0	0	0	0	5	4	2

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

Задача №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

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	3	-2	2	-2	3	1	0	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0
X₁₀	-1	0	-1	0	0	0	0	0	0	0	1	0
X₁₁	5	1	0	0	0	0	0	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0	0	0

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

Таблица 2.37

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0
X₁₀	6/5	1/5	0	4/5	1/5	0	0	-1/5	0	0	1	0
X₁₁	5	1	0	0	0	0	0	0	0	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0	0	0

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

Таблица 2.38

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	7	0	0	-3/2	2	1	0	1	-3/2	0	0	0
X₆	17/2	0	0	45/8	-23/4	0	1	3/4	-15/8	0	0	0
X₂	3/2	0	1	5/8	1/4	0	0	-1/4	1/8	0	0	0
X₁	7/2	1	0	7/8	-1/4	0	0	1/4	-5/8	0	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0	0
X₁₀	1/2	0	0	5/8	1/4	0	0	-1/4	1/8	0	1	0
X₁₁	3/2	0	0	-7/8	1/4	0	0	-1/4	5/8	0	0	1
Y	-43/2	0	0	83/8	-9/4	0	0	1/4	15/8	0	0	0

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

Таблица 2.39

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₅	-1	0	0	-3/2	0	1	0	1	-3/2	2	0	0
X₆	63/2	0	0	45/8	0	0	1	3/4	-15/8	-23/4	0	0
X₂	1/2	0	1	5/8	0	0	0	-1/4	1/8	1/4	0	0
X₁	9/2	1	0	7/8	0	0	0	1/4	-5/8	-1/4	0	0
X₄	4	0	0	0	1	0	0	0	0	-1	0	0
X₁₀	-1/2	0	0	5/8	0	0	0	-1/4	1/8	1/4	1	0
X₁₁	1/2	0	0	-7/8	0	0	0	-1/4	5/8	1/4	0	1
Y	-25/2	0	0	83/8	0	0	0	1/4	15/8	-9/4	0	0

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

Таблица 2.40

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₈	2/3	0	0	1	0	-2/3	0	-2/3	1	-4/3	0	0
X₆	131/4	0	0	15/2	0	-5/4	1	-1/2	0	-33/4	0	0
X₂	5/12	0	1	2/4	0	1/12	0	-1/6	0	5/12	0	0
X₁	59/12	1	0	3/2	0	-5/12	0	-1/6	0	-13/12	0	0
X₄	4	0	0	0	1	0	0	0	0	-1	0	0
X₁₀	-7/12	0	0	2/4	0	1/12	0	-1/6	0	5/12	1	0
X₁₁	1/12	0	0	-6/4	0	5/12	0	1/6	0	13/12	0	1
Y	-55/4	0	0	17/2	0	5/4	0	3/2	0	1/4	0	0

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

Таблица 2.41

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₈	3	0	0	-1	0	-1	0	0	1	-3	-4	0
X₆	69/2	0	0	6	0	-3/2	1	0	0	-19/2	-3	0
X₂	1	0	1	0	0	0	0	0	0	0	-1	0
X₁	11/2	1	0	1	0	-1/2	0	0	0	-3/2	-1	0
X₄	4	0	0	0	1	0	0	0	0	-1	0	0
X₇	7/2	0	0	-3	0	-1/2	0	1	0	-5/2	-6	0
X₁₁	-1/2	0	0	-1	0	1/2	0	0	0	3/2	1	1
Y	-19	0	0	13	0	2	0	0	0	4	9	0

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

Таблица 2.42

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀	X₁₁
X₈	7/2	0	0	0	0	-3/2	0	0	1	-9/2	-5	-1
X₆	63/2	0	0	0	0	3/2	1	0	0	-1/2	3	6
X₂	1	0	1	0	0	0	0	0	0	0	-1	0
X₁	5	1	0	0	0	0	0	0	0	0	0	1
X₄	4	0	0	0	1	0	0	0	0	-1	0	0
X₇	5	0	0	0	0	-2	0	1	0	-7	-9	-3
X₃	1/2	0	0	1	0	-1/2	0	0	0	-3/2	-1	-1
Y	-51/2	0	0	0	0	17/2	0	0	0	47/2	22	13

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

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	3	-2	2	-2	3	1	0	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0
X₁₀	0	0	1	0	0	0	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0	0

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

Таблица 2.44

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0
X₁₀	-11/5	-1/5	0	-4/5	-1/5	0	0	1/5	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0	0

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

Таблица 2.45

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	7	0	0	-3/2	2	1	0	1	-3/2	0	0
X₆	17/2	0	0	45/8	-23/4	0	1	3/4	-15/8	0	0
X₂	3/2	0	1	5/8	1/4	0	0	-1/4	1/8	0	0
X₁	7/2	1	0	7/8	-1/4	0	0	1/4	-5/8	0	0
X₉	-4	0	0	0	-1	0	0	0	0	1	0
X₁₀	-3/2	0	0	-5/8	-1/4	0	0	1/4	-1/8	0	1
Y	-43/2	0	0	83/8	-9/4	0	0	1/4	15/8	0	0

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

Таблица 2.46

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₅	-1	0	0	-3/2	0	1	0	1	-3/2	2	0
X₆	63/2	0	0	45/8	0	0	1	3/4	-15/8	-23/4	0
X₂	1/2	0	1	5/8	0	0	0	-1/4	1/8	1/4	0
X₁	9/2	1	0	7/8	0	0	0	1/4	-5/8	-1/4	0
X₄	4	0	0	0	1	0	0	0	0	-1	0
X₁₀	-1/2	0	0	-5/8	0	0	0	1/4	-1/8	-1/4	1
Y	-25/2	0	0	83/8	0	0	0	1/4	15/8	-9/4	0

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

Таблица 2.47

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₈	2/3	0	0	1	0	-2/3	0	-2/3	1	-4/3	0
X₆	131/4	0	0	15/2	0	-5/4	1	-1/2	0	-33/4	0
X₂	5/12	0	1	2/4	0	1/12	0	-1/6	0	5/12	0
X₁	59/12	1	0	3/2	0	-5/12	0	-1/6	0	-13/12	0
X₄	4	0	0	0	1	0	0	0	0	-1	0
X₁₀	-5/12	0	0	-2/4	0	-1/12	0	1/6	0	-5/12	1
Y	-55/4	0	0	17/2	0	5/4	0	3/2	0	1/4	0

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

Таблица 2.48

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉	X₁₀
X₈	2	0	0	13/5	0	-2/5	0	-6/5	1	0	-16/5
X₆	41	0	0	87/5	0	2/5	1	-19/5	0	0	-99/5
X₂	0	0	1	0	0	0	0	0	0	0	1
X₁	6	1	0	14/5	0	-1/5	0	-3/5	0	0	-13/5
X₄	5	0	0	6/5	1	1/5	0	-2/5	0	0	-12/5
X₉	1	0	0	6/5	0	1/5	0	-2/5	0	1	-12/5
Y	-14	0	0	41/5	0	6/5	0	8/5	0	0	3/5

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

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

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

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₉=3-(0x₁+0x₂+0x₃+1x₄)

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

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

Таблица 2.49

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	3	-2	2	-2	3	1	0	0	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0
X₇	-11	-1	-5	-4	-1	0	0	1	0	0
X₈	-10	-2	-2	-3	0	0	0	0	1	0
X₉	3	0	0	0	1	0	0	0	0	1
Y	0	4	5	17	-2	0	0	0	0	0

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

Таблица 2.50

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	-7/5	-12/5	0	-18/5	13/5	1	0	2/5	0	0
X₆	-2	-3	0	3	-5	0	1	0	0	0
X₂	11/5	1/5	1	4/5	1/5	0	0	-1/5	0	0
X₈	-28/5	-8/5	0	-7/5	2/5	0	0	-2/5	1	0
X₉	3	0	0	0	1	0	0	0	0	1
Y	-11	3	0	13	-3	0	0	1	0	0

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

Таблица 2.51

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	7	0	0	-3/2	2	1	0	1	-3/2	0
X₆	17/2	0	0	45/8	-23/4	0	1	3/4	-15/8	0
X₂	3/2	0	1	5/8	1/4	0	0	-1/4	1/8	0
X₁	7/2	1	0	7/8	-1/4	0	0	1/4	-5/8	0
X₉	3	0	0	0	1	0	0	0	0	1
Y	-43/2	0	0	83/8	-9/4	0	0	1/4	15/8	0

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

Таблица 2.52

БП	СЧ	X₁	X₂	X₃	X₄	X₅	X₆	X₇	X₈	X₉
X₅	1	0	0	-3/2	0	1	0	1	-3/2	-2
X₆	103/4	0	0	45/8	0	0	1	3/4	-15/8	23/4
X₂	3/4	0	1	5/8	0	0	0	-1/4	1/8	-1/4
X₁	17/4	1	0	7/8	0	0	0	1/4	-5/8	1/4
X₄	3	0	0	0	1	0	0	0	0	1
Y	-59/4	0	0	83/8	0	0	0	1/4	15/8	9/4

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

Остановка: текущее значение целевой функции <=-14.

Список задач пуст. Блок-схема решения задачи представлена на рисунке 2.1.

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

Рисунок 2.1 - Схема решения целочисленной задачи методом ветвей и границ.

<<< < Предыдущая 1 2 3 45 / 125 6 7 8 9 10 11 12 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
02.06.201579.36 Кб52тексты по английскому 6-10.doc
#
09.08.2019344.58 Кб38Текущий тестовый контроль (Лечебное дело).doc
#
02.06.20153.4 Mб92Телекомм_в_инф_сетях_лекции.doc
#
02.06.2015295.14 Кб18Тело мой курсач 5.docx
#
02.06.2015295.05 Кб30Тело мой курсач 9.docx
#
02.06.20151.95 Mб58Тело мой курсач2.doc
#
02.06.20151.14 Mб25Тело мой курсач3.doc
#
16.08.2019495.62 Кб15Тема 1. Задачи 1-4.doc
#
21.04.2019201.73 Кб85Тема 1. Организация создания ГДЗС -11.doc
#
02.06.2015468.76 Кб85Тема 1.pdf
#
02.06.2015727.57 Кб27Тема 2 .pdf