Решение задачи методом ветвей и границ
Согласно методу для каждой целочисленной переменной возможно задать верхнюю и нижнюю границу, в пределах которых содержится ее оптимальное значение. В данном случае нижняя граница равна нулю. На практике верхний предел не вводят в виде дополнительного ограничения, а учитывают его в процессе решения не явно, то есть к исходным ограничения на практике добавляется ограничение, которое определяется самим методом.
Решаем исходную задачу - Задачу №1(п.1.3) до получения оптимального решения методом линейного программирования. Воспользуемся итоговой таблицей (Таблица 1.13). Эта таблица и будет исходной для нашей задачи (Таблица 2.1.6).
Таблица 2.1.6
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
|
X5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
|
X2 |
7/4 |
0 |
1 |
0 |
-2 |
0 |
1/4 |
-1 |
1/2 |
|
X3 |
5/4 |
0 |
0 |
1 |
-1 |
0 |
-1/4 |
0 |
1/2 |
|
Y |
-16 |
0 |
0 |
0 |
5 |
0 |
1 |
1 |
1 |
Полученное решение не удовлетворяет требованиям целочисленности.
Поэтому составляем относительно любой нецелочисленной переменной две новых порожденных задачи (2 и 3). Выберем переменную x1. ПримемY1 = 0.
Новые ограничения строятся по формуле:
х ≤ [х*]
x ≥ [х*] + 1
где [х*] – целая часть числа х* (нецелочисленная переменная)
Задача №2:
Добавляется ограничение x1≥5. Тогда задача примет вид:
При ограничениях:
x1≥5
и целые.
Выразим допустимый базис в форме Таккера:
x5=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=-5-(-x1+0x2+0x3+0x4)
Целевая функция в форме Таккера
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.7
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
X9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.8
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x7
Таблица 2.1.9
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
5/2 |
0 |
0 |
-2 |
-3 |
1 |
1/2 |
-2 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
|
X2 |
1/2 |
0 |
1 |
-1 |
-1 |
0 |
1/2 |
-1 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
|
Y |
-37/2 |
0 |
0 |
-2 |
7 |
0 |
3/2 |
1 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x9
Таблица 2.1.10
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
2 |
0 |
0 |
-2 |
-4 |
1 |
0 |
-2 |
0 |
1 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
X2 |
0 |
0 |
1 |
-1 |
-2 |
0 |
0 |
-1 |
0 |
1 |
|
X8 |
3 |
0 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
-1 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
|
Y |
-20 |
0 |
0 |
-2 |
4 |
0 |
0 |
1 |
0 |
3 |
Используем обычный симплекс-метод. Вводим в базис x3, выводим из базиса x8
Таблица 2.1.11
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
5 |
0 |
0 |
0 |
-5 |
1 |
0 |
-2 |
1 |
0 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
X2 |
3/2 |
0 |
1 |
0 |
-5/2 |
0 |
0 |
-1 |
1/2 |
1/2 |
|
X3 |
3/2 |
0 |
0 |
1 |
-1/2 |
0 |
0 |
0 |
1/2 |
-1/2 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
|
Y |
-17 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
1 |
2 |
Решение данной задачи: Y=-17; X=(5;3/2;3/2;0;5;1;0;0;0)
Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи.
Для образования порожденных задач выберем переменную x2
Задача №4:
Добавляется ограничение x2≥2.
Выразим допустимый базис в форме Таккера:
x5=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=-5-(-x1+0x2+0x3+0x4)
x10=-2-(0x1-x2+0x3+0x4)
Целевая функция в форме Таккера
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.12
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.13
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10
Таблица 2.1.14
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
|
X7 |
3/2 |
0 |
0 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
Y |
-20 |
0 |
0 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x9
Таблица 2.1.15
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
-2 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X7 |
2 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
0 |
-1 |
-1 |
|
X8 |
3 |
0 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
-1 |
0 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
Y |
-22 |
0 |
0 |
-3 |
2 |
0 |
0 |
0 |
0 |
4 |
1 |
Используем обычный симплекс-метод. Вводим в базис x3, выводим из базиса x8
Таблица 2.1.16
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
-2 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X7 |
1/2 |
0 |
0 |
0 |
5/2 |
0 |
0 |
1 |
-1/2 |
-1/2 |
-1 |
|
X3 |
3/2 |
0 |
0 |
1 |
-1/2 |
0 |
0 |
0 |
1/2 |
-1/2 |
0 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
Y |
-35/2 |
0 |
0 |
0 |
1/2 |
0 |
0 |
0 |
3/2 |
5/2 |
1 |
Решение данной задачи: Y=-35/2; X=(5;2;3/2;0;6;1;1/2;0;0;0)
Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи.
Для образования порожденных задач выберем переменную x3
Задача №6:
Добавляется ограничение x3≥2
Выразим допустимый базис в форме Таккера
x5=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=-5-(-x1+0x2+0x3+0x4)
x10=-2-(0x1-x2+0x3+0x4)
x11=-2-(0x1+0x2-x3+0x4)
Целевая функция в форме Таккера
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.17
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.18
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10
Таблица 2.1.19
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
3/2 |
0 |
0 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-20 |
0 |
0 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x3, выводим из базиса x11
Таблица 2.1.20
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
0 |
0 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
1 |
|
X8 |
-3/2 |
0 |
0 |
0 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
2 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
Y |
-14 |
0 |
0 |
0 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
-3 |
Используем двойственный симплекс-метод. Вводим в базис x4, выводим из базиса x8
Таблица 2.1.21
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
25/4 |
0 |
0 |
0 |
0 |
1 |
-1/4 |
0 |
-1/2 |
0 |
-2 |
-1 |
|
X1 |
21/4 |
1 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
-1/2 |
0 |
0 |
-1 |
|
X7 |
-5/4 |
0 |
0 |
0 |
0 |
0 |
-3/4 |
1 |
1/2 |
0 |
-1 |
2 |
|
X4 |
3/4 |
0 |
0 |
0 |
1 |
0 |
1/4 |
0 |
-1/2 |
0 |
0 |
-1 |
|
X9 |
1/4 |
0 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
-1/2 |
1 |
0 |
-1 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
Y |
-37/2 |
0 |
0 |
0 |
0 |
0 |
1/2 |
0 |
3 |
0 |
1 |
3 |
Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x7
Таблица 2.1.22
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
20/3 |
0 |
0 |
0 |
0 |
1 |
0 |
-1/3 |
-2/3 |
0 |
-5/3 |
-5/3 |
|
X1 |
17/3 |
1 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
-2/3 |
0 |
1/3 |
-5/3 |
|
X6 |
5/3 |
0 |
0 |
0 |
0 |
0 |
1 |
-4/3 |
-2/3 |
0 |
4/3 |
-8/3 |
|
X4 |
1/3 |
0 |
0 |
0 |
1 |
0 |
0 |
1/3 |
-1/3 |
0 |
-1/3 |
-1/3 |
|
X9 |
2/3 |
0 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
-2/3 |
1 |
1/3 |
-5/3 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
Y |
-58/3 |
0 |
0 |
0 |
0 |
0 |
0 |
2/3 |
10/3 |
0 |
1/3 |
13/3 |
Решение данной задачи: Y=-58/3;X=(17/3;2;2;1/3;20/3;5/3;0;0;2/3;0;0)
Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи.
Для образования порожденных задач выберем переменную x1
Задача №8:
Добавляется ограничение x1≥6
Выразим допустимый базис в форме Таккера:
x9=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=-5-(-x1+0x2+0x3+0x4)
x10=-2-(0x1-x2+0x3+0x4)
x11=-2-(0x1+0x2-x3+0x4)
x12=-6-(-x1+0x2+0x3+0x4)
Целевая функция в форме Таккера
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.23
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X12 |
-6 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.24
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X12 |
-3/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10
Таблица 2.1.25
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
3/2 |
0 |
0 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X12 |
-3/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-20 |
0 |
0 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x3, выводим из базиса x11
Таблица 2.1.26
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
0 |
0 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
1 |
0 |
|
X8 |
-3/2 |
0 |
0 |
0 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
2 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X12 |
-3/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-14 |
0 |
0 |
0 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
-3 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x4, выводим из базиса x8
Таблица 2.1.27
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
25/4 |
0 |
0 |
0 |
0 |
1 |
-1/4 |
0 |
-1/2 |
0 |
-2 |
-1 |
0 |
|
X1 |
21/4 |
1 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
-1/2 |
0 |
0 |
-1 |
0 |
|
X7 |
-5/4 |
0 |
0 |
0 |
0 |
0 |
-3/4 |
1 |
1/2 |
0 |
-1 |
2 |
0 |
|
X4 |
3/4 |
0 |
0 |
0 |
1 |
0 |
1/4 |
0 |
-1/2 |
0 |
0 |
-1 |
0 |
|
X9 |
1/4 |
0 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
-1/2 |
1 |
0 |
-1 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X12 |
-3/4 |
0 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
-1/2 |
0 |
0 |
-1 |
1 |
|
Y |
-37/2 |
0 |
0 |
0 |
0 |
0 |
1/2 |
0 |
3 |
0 |
1 |
3 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x7
Таблица 2.1.28
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
20/3 |
0 |
0 |
0 |
0 |
1 |
0 |
-1/3 |
-2/3 |
0 |
-5/3 |
-5/3 |
0 |
|
X1 |
17/3 |
1 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
-2/3 |
0 |
1/3 |
-5/3 |
0 |
|
X6 |
5/3 |
0 |
0 |
0 |
0 |
0 |
1 |
-4/3 |
-2/3 |
0 |
4/3 |
-8/3 |
0 |
|
X4 |
1/3 |
0 |
0 |
0 |
1 |
0 |
0 |
1/3 |
-1/3 |
0 |
-1/3 |
-1/3 |
0 |
|
X9 |
2/3 |
0 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
-2/3 |
1 |
1/3 |
-5/3 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X12 |
-1/3 |
0 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
-2/3 |
0 |
1/3 |
-5/3 |
1 |
|
Y |
-58/3 |
0 |
0 |
0 |
0 |
0 |
0 |
2/3 |
10/3 |
0 |
1/3 |
13/3 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x7, выводим из базиса x12
Таблица 2.1.29
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
7 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-2 |
0 |
-1 |
|
X1 |
6 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
|
X6 |
3 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
2 |
0 |
0 |
4 |
-4 |
|
X4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
-2 |
1 |
|
X9 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-1 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X7 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
0 |
-1 |
5 |
-3 |
|
Y |
-20 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
1 |
1 |
2 |
Решение данной задачи: Y=-20;X=(6;2;2;0;7;3;1;0;1;0;0;0)
Задача №9:
Добавляется ограничение x1≤5
Выразим допустимый базис в форме Таккера:
x5=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=-5-(-x1+0x2+0x3+0x4)
x10=-2-(0x1-x2+0x3+0x4)
x11=-2-(0x1+0x2-x3+0x4)
x12=5-(x1+0x2+0x3+0x4)
Целевая функция в форме Таккера:
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.30
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X12 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.31
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X12 |
1/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10
Таблица 2.1.32
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
3/2 |
0 |
0 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X11 |
-2 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X12 |
1/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-20 |
0 |
0 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x3, выводим из базиса x11
Таблица 2.1.33
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
0 |
0 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
1 |
0 |
|
X8 |
-3/2 |
0 |
0 |
0 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
2 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X12 |
1/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-14 |
0 |
0 |
0 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
-3 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x4, выводим из базиса x8
Таблица 2.1.34
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
25/4 |
0 |
0 |
0 |
0 |
1 |
-1/4 |
0 |
-1/2 |
0 |
-2 |
-1 |
0 |
|
X1 |
21/4 |
1 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
-1/2 |
0 |
0 |
-1 |
0 |
|
X7 |
-5/4 |
0 |
0 |
0 |
0 |
0 |
-3/4 |
1 |
1/2 |
0 |
-1 |
2 |
0 |
|
X4 |
3/4 |
0 |
0 |
0 |
1 |
0 |
1/4 |
0 |
-1/2 |
0 |
0 |
-1 |
0 |
|
X9 |
1/4 |
0 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
-1/2 |
1 |
0 |
-1 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X12 |
-1/4 |
0 |
0 |
0 |
0 |
0 |
1/4 |
0 |
1/2 |
0 |
0 |
1 |
1 |
|
Y |
-37/2 |
0 |
0 |
0 |
0 |
0 |
1/2 |
0 |
3 |
0 |
1 |
3 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x7
Таблица 2.1.35
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
20/3 |
0 |
0 |
0 |
0 |
1 |
0 |
-1/3 |
-2/3 |
0 |
-5/3 |
-5/3 |
0 |
|
X1 |
17/3 |
1 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
-2/3 |
0 |
1/3 |
-5/3 |
0 |
|
X6 |
5/3 |
0 |
0 |
0 |
0 |
0 |
1 |
-4/3 |
-2/3 |
0 |
4/3 |
-8/3 |
0 |
|
X4 |
1/3 |
0 |
0 |
0 |
1 |
0 |
0 |
1/3 |
-1/3 |
0 |
-1/3 |
-1/3 |
0 |
|
X9 |
2/3 |
0 |
0 |
0 |
0 |
0 |
0 |
-1/3 |
-2/3 |
1 |
1/3 |
-5/3 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X12 |
-2/3 |
0 |
0 |
0 |
0 |
0 |
0 |
1/3 |
2/3 |
0 |
-1/3 |
5/3 |
1 |
|
Y |
-58/3 |
0 |
0 |
0 |
0 |
0 |
0 |
2/3 |
10/3 |
0 |
1/3 |
13/3 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x10, выводим из базиса x12
Таблица 2.1.36
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
X12 |
|
X5 |
10 |
0 |
0 |
0 |
0 |
1 |
0 |
-2 |
-4 |
0 |
0 |
-10 |
-5 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
X6 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
2 |
0 |
0 |
4 |
4 |
|
X4 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
-2 |
-1 |
|
X9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
X2 |
4 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
-2 |
0 |
0 |
-5 |
-3 |
|
X3 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X10 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-2 |
0 |
1 |
-5 |
-3 |
|
Y |
-20 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
4 |
0 |
0 |
6 |
1 |
Решение данной задачи: Решения нет.
Задача №7:
Добавляется ограничение x3≤1
Выразим допустимый базис в форме Таккера:
x5=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=-5-(-x1+0x2+0x3+0x4)
x10=-2-(0x1-x2+0x3+0x4)
x11=1-(0x1+0x2+x3+0x4)
Целевая функция в форме Таккера:
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.37
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X11 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.38
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
|
X10 |
-2 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X11 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x10
Таблица 2.1.39
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
11/2 |
0 |
0 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
-2 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
0 |
|
X7 |
3/2 |
0 |
0 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
-1 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X11 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-20 |
0 |
0 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
1 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x9
Таблица 2.1.40
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
-2 |
0 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X7 |
2 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
0 |
-1 |
-1 |
0 |
|
X8 |
3 |
0 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X11 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-22 |
0 |
0 |
-3 |
2 |
0 |
0 |
0 |
0 |
4 |
1 |
0 |
Используем обычный симплекс-метод. Вводим в базис x3, выводим из базиса x11
Таблица 2.1.41
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
X11 |
|
X5 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
-2 |
0 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
|
X7 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
-1 |
-1 |
-1 |
|
X8 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
-1 |
0 |
-2 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
0 |
|
X2 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X3 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-19 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
4 |
1 |
3 |
Решение данной задачи: Y=-19;X=(5;2;1;0;6;1;1;1;0;0;0)
Задача №5:
Добавляется ограничение x2≤1
Выразим допустимый базис в форме Таккера:
x5=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=-5-(-x1+0x2+0x3+0x4)
x10=1-(0x1+x2+0x3+0x4)
Целевая функция в форме Таккера:
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.42
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
X9 |
-5 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X10 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.43
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
|
X10 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x7
Таблица 2.1.44
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
5/2 |
0 |
0 |
-2 |
-3 |
1 |
1/2 |
-2 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
0 |
|
X2 |
1/2 |
0 |
1 |
-1 |
-1 |
0 |
1/2 |
-1 |
0 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
1 |
0 |
|
X10 |
1/2 |
0 |
0 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
1 |
|
Y |
-37/2 |
0 |
0 |
-2 |
7 |
0 |
3/2 |
1 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x6, выводим из базиса x9
Таблица 2.1.45
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
2 |
0 |
0 |
-2 |
-4 |
1 |
0 |
-2 |
0 |
1 |
0 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X2 |
0 |
0 |
1 |
-1 |
-2 |
0 |
0 |
-1 |
0 |
1 |
0 |
|
X8 |
3 |
0 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
-1 |
0 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
|
X10 |
1 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
0 |
-1 |
1 |
|
Y |
-20 |
0 |
0 |
-2 |
4 |
0 |
0 |
1 |
0 |
3 |
0 |
Используем обычный симплекс-метод. Вводим в базис x3, выводим из базиса x10
Таблица 2.1.46
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
X10 |
|
X5 |
4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
2 |
|
X1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
X2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
X8 |
1 |
0 |
0 |
0 |
-5 |
0 |
0 |
-2 |
1 |
1 |
-2 |
|
X6 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
|
X3 |
1 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
0 |
-1 |
1 |
|
Y |
-18 |
0 |
0 |
0 |
8 |
0 |
0 |
3 |
0 |
1 |
2 |
Решение данной задачи: Y=-18;X=(5;1;1;0;4;1;0;1;0;0)
Задача №3:
Добавляется ограничение x1≤4
Выразим допустимый базис в форме Таккера:
x5=-3-(-x1-2x2+0x3+0x4)
x6=-9-(-2x1+0x2+0x3+2x4)
x7=-5-(-x1-x2+x3+2x4)
x8=-2-(-x1+0x2+2x3-x4)
x9=4-(x1+0x2+0x3+0x4)
Целевая функция в форме Таккера:
Y=0-(4x1+x2-3x3+2x4)
Таблица 2.1.47
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
-3 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
X6 |
-9 |
-2 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
|
X7 |
-5 |
-1 |
-1 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
|
X8 |
-2 |
-1 |
0 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
X9 |
4 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
4 |
1 |
-3 |
2 |
0 |
0 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6
Таблица 2.1.48
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
3/2 |
0 |
-2 |
0 |
-1 |
1 |
-1/2 |
0 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
|
X7 |
-1/2 |
0 |
-1 |
1 |
1 |
0 |
-1/2 |
1 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
1 |
|
Y |
-18 |
0 |
1 |
-3 |
6 |
0 |
2 |
0 |
0 |
0 |
Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x7
Таблица 2.1.49
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X5 |
5/2 |
0 |
0 |
-2 |
-3 |
1 |
1/2 |
-2 |
0 |
0 |
|
X1 |
9/2 |
1 |
0 |
0 |
-1 |
0 |
-1/2 |
0 |
0 |
0 |
|
X2 |
1/2 |
0 |
1 |
-1 |
-1 |
0 |
1/2 |
-1 |
0 |
0 |
|
X8 |
5/2 |
0 |
0 |
2 |
-2 |
0 |
-1/2 |
0 |
1 |
0 |
|
X9 |
-1/2 |
0 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
1 |
|
Y |
-37/2 |
0 |
0 |
-2 |
7 |
0 |
3/2 |
1 |
0 |
0 |
Решение данной задачи: Решения нет.
Т.к. список задач, подлежащих решению пуст, то можно сделать вывод о том, что решение задачи целочисленного программирования завершено.
Ответ: Y=-18;X=(5;1;1;0;4;1;0;1;0;0)
Рис 2.1.1 Блок схема решения.