Задача линейного программирования. Двойственная задача, двойственный симплекс-метод

1. Задача линейного программирования. Двойственная задача, двойственный симплекс-метод

2.

Прямая задача
Двойственная задача
min CX
AX b
X 0
max b Y
T
T
A Y C
Y 0
max CX
AX b
X 0
min b Y
T
T
A Y C
Y 0
T
T
CX opt b Yopt
T

3.

Прямая задача
min CX
AX b
X 0
max CX
AX b
X 0
ОДР пуста
ОДР незамкнута
Двойственная задача
max b Y
T
T
A Y C
T
min b Y
T
T
A Y C
T
ОДР незамкнута
ОДР пуста

4. Рассмотрим ЗЛП

max x1 3 x2
2
x
x
x
1
1
2
3
x1 2 x2 x4 1
x 0, x 0
2
1
x3 0, x4 0
max 1x1 3 x2 0 x3 0 x4
2 x1 1x2 1x3 0 x4 1
1x1 2 x2 0 x3 1x4 1
x 0, x 0
2
1
x3 0, x4 0
max CX
AX b
X 0
min y1 y2
2 y1 y2 1
y1 2 y2 3
y 0y 0
2
1
0 y1 y2 0
min b Y
T
T
A Y C
T

5. Рассмотрим ЗЛП

max 3 x1 4 x2
2 x1 x2 5
6 x1 7 x2 8
x 0
1
x2 0
max CX
AX b
X 0
min 5 y1 8 y2
2 y1 6 y2 3
y1 7 y2 4
y 0
1
y2 0
min b Y
T
T
A Y C
Y 0
T

6.

Прямой
симплекс-метод
Допустимость
bi 0
Оптимальность
cj 0
Двойственный
симплекс-метод
cj 0
bi 0
Неограниченность
air 0 при cr 0
asj 0 при bs 0

7. Рассмотрим ЗЛП

max 3 x1 4 x2
x1 2 x2 8
2 x1 x2 10
x 0
1
x2 0
x2
2
(x2, x4)
x1=0
x2=4
x3=0
x4=6
f=16
4
x3
x4
b
x1
1/3
-2/3
4
x2
-2/3
1/3
2
f
-5/3
-2/3
20
2x1+x2=10
(x4=0)
(x1, x2)
x1=4
x2=2
x3=0
x4=0
f=20
x1=0
3
2
x1+2x2=8
(x3=0)
1
0
(x3, x4)
x1=0
x2=0
x3=8
x4=10
f=0
4
x1
5
x2=0

8. Добавим дополнительное ограничение

x1 x2 5
x1 x2 x5 5
x5 5 x1 x2
1
2
x1 3 x3 3 x4 4
x2 23 x3 13 x4 2
x3
x4
b
x1
1/3
-2/3
4
x2
-2/3
1/3
2
f
-5/3
-2/3
20
x5 5 x1 x2 5 x3 x4 4
1
3
2
3
x3 x4 2 1 x3 x4
2
3
1
3
1
3
1
3

9.

x5 1 x3 x4
1
3
1
3
x3
x4
b
x1
1/3
-2/3
4
x2
-2/3
1/3
2
x5
1/3
1/3
-1
f
-5/3
-2/3
20
Базис оптимален
Прямой
симплекс-метод
Базис недопустим

10.

x5 1 x3 x4
1
3
1
3
x3
x4
b
x1
1/3
-2/3
4
x2
-2/3
1/3
2
x5
1/3
1/3
-1
f
-5/3
-2/3
20
Базис допустим
Двойственный
симплекс-метод
Базис неоптимален

11.

x4
b
x1
1/3
-2/3
4
x2
-2/3
1/3
2
x5
1/3
1/3
-1
f
-5/3
-2/3
20
Двойственный
симплекс-метод
x3
x5
b
x1
1
-2
2
x2
-1
1
3
x4
-1
3
3
f
-1
-2
18
Базис допустим
Базис оптимален
x3

12.

x2
4
x1=0
x1+x2=5
(x5=0) (x1, x2, x4)
x1=2
x2=3
x3=0
x4=3
x5=0
f=18
4
2
0
2x1+x2=10
(x4=0)
(x1, x2, x5)
x1=4
x2=2
x3=0
x4=0
x5=-1
3
f=20
4
x1+2x2=8
(x3=0)
x1
5
x2=0