Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Déduire de ce qui précède et des relations liant les solutions de (P) et de
(D) les valeurs x 2 , x 3 , . . . , x n de toute solution x = (x 1 , x 2 , . . . , x n ) de (P).
3 ◦ ) Résoudre complètement (P).
Solution : Commençons par visualiser le cas où n = 2.
Figure 14.
(P) consiste à minimiser c, x sous les contraintes Ax b, x 0, où
b =
⎛
⎜
⎜
⎜
⎝
1
2
. . .
n
⎞
⎟
⎟
⎟
⎠
, c =
⎛
⎜
⎜
⎜
⎝
1
2
. . .
n
⎞
⎟
⎟
⎟
⎠
et A =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
1 0 0 . . . . . .
1 1 0 . . . . . .
1 1 1 0 . . .
. . .
. . .
1 1 1 . . . 1
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
1 ◦ ) Le problème dual de (P) consiste à maximiser b, y sous les contraintes
A y c et y 0, soit :
(D)
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
Maximiser y 1 + 2y 2 + . . . + ny n
y 1 + y 2 + . . . + y n 1
y 2 + . . . + y n 2
y 3 + . . . + y n 3
. . .
y n n
y i 0 pour tout i = 1, 2, . . . , n.
208