2.2.2 Решение задачи методом ветвей и границ
.
Задача №1 - исходная задача со снятым требованием целочисленности. Перепишем решение из таблицы 1.12.
Таблица 2.56
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
|
X4 |
7/2 |
0 |
0 |
-3/4 |
1 |
1/2 |
0 |
1/2 |
-3/4 |
|
X6 |
229/8 |
0 |
0 |
21/16 |
0 |
23/8 |
1 |
29/8 |
-99/16 |
|
X2 |
5/8 |
0 |
1 |
13/16 |
0 |
-1/8 |
0 |
-3/8 |
5/16 |
|
X1 |
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.
Выразим допустимый базис в форме Таккера:
x5=3-(-2x1+2x2-2x3+3x4)
x6=-2-(-3x1+0x2+3x3-5x4)
x7=-11-(-1x1-5x2-4x3-1x4)
x8=-10-(-2x1-2x2-3x3+0x4)
x9=-4-(0x1+0x2+0x3-1x4)
Целевая функция в форме Таккера:
Y=0-(4x1+5x2+17x3-2x4)
Таблица 2.57
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
3 |
-2 |
2 |
-2 |
3 |
1 |
0 |
0 |
0 |
0 |
|
X6 |
-2 |
-3 |
0 |
3 |
-5 |
0 |
1 |
0 |
0 |
0 |
|
X7 |
-11 |
-1 |
-5 |
-4 |
-1 |
0 |
0 |
1 |
0 |
0 |
|
X8 |
-10 |
-2 |
-2 |
-3 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X9 |
-4 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
5 |
17 |
-2 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7.
Таблица 2.58
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
-7/5 |
-12/5 |
0 |
-18/5 |
13/5 |
1 |
0 |
2/5 |
0 |
0 |
|
X6 |
-2 |
-3 |
0 |
3 |
-5 |
0 |
1 |
0 |
0 |
0 |
|
X2 |
11/5 |
1/5 |
1 |
4/5 |
1/5 |
0 |
0 |
-1/5 |
0 |
0 |
|
X8 |
-28/5 |
-8/5 |
0 |
-7/5 |
2/5 |
0 |
0 |
-2/5 |
1 |
0 |
|
X9 |
-4 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-11 |
3 |
0 |
13 |
-3 |
0 |
0 |
1 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X8.
Таблица 2.59
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
7 |
0 |
0 |
-3/2 |
2 |
1 |
0 |
1 |
-3/2 |
0 |
|
X6 |
17/2 |
0 |
0 |
45/8 |
-23/4 |
0 |
1 |
3/4 |
-15/8 |
0 |
|
X2 |
3/2 |
0 |
1 |
5/8 |
1/4 |
0 |
0 |
-1/4 |
1/8 |
0 |
|
X1 |
7/2 |
1 |
0 |
7/8 |
-1/4 |
0 |
0 |
1/4 |
-5/8 |
0 |
|
X9 |
-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.60
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
-1 |
0 |
0 |
-3/2 |
0 |
1 |
0 |
1 |
-3/2 |
2 |
|
X6 |
63/2 |
0 |
0 |
45/8 |
0 |
0 |
1 |
3/4 |
-15/8 |
-23/4 |
|
X2 |
1/2 |
0 |
1 |
5/8 |
0 |
0 |
0 |
-1/4 |
1/8 |
1/4 |
|
X1 |
9/2 |
1 |
0 |
7/8 |
0 |
0 |
0 |
1/4 |
-5/8 |
-1/4 |
|
X4 |
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.61
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X8 |
2/3 |
0 |
0 |
1 |
0 |
-2/3 |
0 |
-2/3 |
1 |
-4/3 |
|
X6 |
131/4 |
0 |
0 |
15/2 |
0 |
-5/4 |
1 |
-1/2 |
0 |
-33/4 |
|
X2 |
5/12 |
0 |
1 |
2/4 |
0 |
1/12 |
0 |
-1/6 |
0 |
5/12 |
|
X1 |
59/12 |
1 |
0 |
3/2 |
0 |
-5/12 |
0 |
-1/6 |
0 |
-13/12 |
|
X4 |
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 |
Решение
задачи удовлетворяет требованию
целочисленности для переменной х4,
и значение целевой функции больше, чем
найденное до этого оптимально
.
На данной итерации найдено новое
оптимально целочисленное решение.
Задача №3 - к исходным данным задачи №1 добавляется ограничение Х4<=3.
Выразим допустимый базис в форме Таккера:
x5=3-(-2x1+2x2-2x3+3x4)
x6=-2-(-3x1+0x2+3x3-5x4)
x7=-11-(-1x1-5x2-4x3-1x4)
x8=-10-(-2x1-2x2-3x3+0x4)
x9=3-(0x1+0x2+0x3+1x4)
Целевая функция в форме Таккера:
Y=0-(4x1+5x2+17x3-2x4)
Таблица 2.62
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
3 |
-2 |
2 |
-2 |
3 |
1 |
0 |
0 |
0 |
0 |
|
X6 |
-2 |
-3 |
0 |
3 |
-5 |
0 |
1 |
0 |
0 |
0 |
|
X7 |
-11 |
-1 |
-5 |
-4 |
-1 |
0 |
0 |
1 |
0 |
0 |
|
X8 |
-10 |
-2 |
-2 |
-3 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X9 |
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
5 |
17 |
-2 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7.
Таблица 2.63
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
-7/5 |
-12/5 |
0 |
-18/5 |
13/5 |
1 |
0 |
2/5 |
0 |
0 |
|
X6 |
-2 |
-3 |
0 |
3 |
-5 |
0 |
1 |
0 |
0 |
0 |
|
X2 |
11/5 |
1/5 |
1 |
4/5 |
1/5 |
0 |
0 |
-1/5 |
0 |
0 |
|
X8 |
-28/5 |
-8/5 |
0 |
-7/5 |
2/5 |
0 |
0 |
-2/5 |
1 |
0 |
|
X9 |
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-11 |
3 |
0 |
13 |
-3 |
0 |
0 |
1 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X8.
Таблица 2.64
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
7 |
0 |
0 |
-3/2 |
2 |
1 |
0 |
1 |
-3/2 |
0 |
|
X6 |
17/2 |
0 |
0 |
45/8 |
-23/4 |
0 |
1 |
3/4 |
-15/8 |
0 |
|
X2 |
3/2 |
0 |
1 |
5/8 |
1/4 |
0 |
0 |
-1/4 |
1/8 |
0 |
|
X1 |
7/2 |
1 |
0 |
7/8 |
-1/4 |
0 |
0 |
1/4 |
-5/8 |
0 |
|
X9 |
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.64
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
1 |
0 |
0 |
-3/2 |
0 |
1 |
0 |
1 |
-3/2 |
-2 |
|
X6 |
103/4 |
0 |
0 |
45/8 |
0 |
0 |
1 |
3/4 |
-15/8 |
23/4 |
|
X2 |
3/4 |
0 |
1 |
5/8 |
0 |
0 |
0 |
-1/4 |
1/8 |
-1/4 |
|
X1 |
17/4 |
1 |
0 |
7/8 |
0 |
0 |
0 |
1/4 |
-5/8 |
1/4 |
|
X4 |
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 |
Остановка: Решение задачи удовлетворяет требованию целочисленности для переменной х4, но значение целевой функции не больше, чем найденное до этого.
Список задач пуст. Блок-схема решения задачи представлена на рисунке 2.2.
Ответ: Y=-55/4, X=(59/12;5/12;0;4;0;131/4;0;2/3;0).
Рисунок 2.2 - Схема решения частично целочисленной задачи методом ветвей и границ.