Двойственность в линейном программировании

1. Двойственность в линейном программировании

2.

(I)
(II)
L c1x1 ... cn xn max
L b1 y1 ... bm ym min
a11 x1 ... a1n xn b1
... ... ... ... ... ...
ak1x1 ... aknxn bk
ak 11 x1 ... ak 1n xn bk 1
... ... ... ... ... ...
am1x1 ... amn xn bm
x1 0
... ... ... ... ... ...
xl 0
x любое
l 1
... ... ... ... ... ...
x любое
n
y1 0
... ... ... ... ... ...
yk 0
yk 1 любое
... ... ... ... ... ...
ym любое
a11 y1 ... am1 ym c1
... ... ... ... ... ...
a1l y1 ... aml ym cl
a y ... a
1l 1 1
ml 1 ym cl 1
... ... ... ... ... ...
a y ... a y c
mn m
n
1n 1

3.

Пример 1
L( x) x1 3 x3 6 x4 max
3x4 2,
2 x1 3 x2
3 x 2 x 4 x x 5,
2
3
4
1
2 x1
3 x3 2 x4 1,
x1 0,
x 0,
2
x3 любое ,
x4 любое
Упорядочим запись исходной
задачи
L( x) x1 3 x3 6 x4 max
3 x4 2,
2 x1 3 x2
3 x 2 x 4 x x 5,
2
3
4
1
2 x1
3 x3 2 x4 1,
x1 0,
x 0,
2
x3 ëþáîå ,
x4 ëþáîå

4.

L( x) x1 3 x3 6 x4 max
L( y ) 2 y1 5 y2 y3 min
3 x4 2,
2 x1 3 x2
3 x 2 x 4 x x 5,
2
3
4
1
2 x1
3 x3 2 x4 1,
x1 0,
x 0,
2
x3 ëþáîå ,
x4 ëþáîå
y1 0,
y - любое ,
2
y3 0,
2 y1 3 y2 2 y3 1,
3 y 2 y
0,
1
2
4 y2 3 y3 3,
3 y1 y2 2 y3 6
3
2
2 3 0
3
2
4
1
5
2 0 3 2
1
1
0
3
6
L
(
x
)
3 2
1
2
0
0
3 2
0
4 3 3
6
3 1 2
2
5 1 L( x)

5.

Пример 2
•Составить задачу двойственную данной
L( x) x1 2 x2 max
2 x1 x2 1,
x 4 x 24,
2
1
x1 x2 3,
x1 x2 5,
x1 0,
x2 0,
L( y ) y1 24 y2 3 y3 5 y4 min
y1 0,
y 0,
2
y3 0,
y4 0,
2 y1 y2 y3 y4 1,
y1 4 y2 y3 y4 2

6.

Пример 3
L( x) 2 x1 3x2 max
x1 3x2 18,
2 x x 16,
1 2
x2 5,
3x1 21,
x1 0,
x2 0,
L( y ) 18 y1 16 y2 5 y3 21 y4 min
y1 0,
y 0,
2
y3 0,
y4 0,
y1 2 y2 3 y4 2,
3 y1 y2 y3 3

7.

Пример 4
L( x) 8 x1 2 x2 min
x1 2 x2 1,
2 x x 1,
1
2
x1 0,
x2 0,
L( y ) y1 y2 max
y1 0,
y 0,
2
y1 2 y2 8,
2 y1 y2 2