V.3. La dualité en programmation linéaire
où les δ i sont les vecteurs de R n suivants :
δ 1 = (−1, 0, . . . , 0)
δ 2 = (−1, −1, 0, . . . , 0) , . . . , δ n−1 = (−1, . . . , −1, 0)
δ n = (−1, −1, . . . , −1) , δ n+1 = −δ n .
Par suite
K 1 = (K
◦
1 )
◦ = cône {δ 1 , . . . , δ n , −δ n } .
*** Exercice V.9. On considère dans R n , n 2, les cônes convexes fermés
polyédriques suivants :
K 2 := {x = (x 1 , . . . , x n ) ∈ R n | 0 x 1 x 2 . . . x n } ;
K 3 :=
x = (x 1 , . . . , x n ) ∈ R n | x 1
x 1 +x 2
2
. . .
x 1 +...+x k
k
. . .
x 1 +...+xn
n
;
K 4 :=
x = (x 1 , . . . , x n ) ∈ R n | x 1
x 1 +x 2
2
. . .
x 1 +...+x k
k
. . .
x 1 +...+xn
n
0
.
Déterminer K ◦
2 , K ◦
3 et K ◦
4 .
Indication. Utiliser le résultat de l’exercice précédent.
Solution : Soit K 1 le cône convexe fermé polyédrique de l’exercice précédent.
Le passage de K 1 à K 2 se fait par l’ajout d’une nouvelle inégalité linéaire « −x 1 0 », i.e. x, d n 0 avec d n = (−1, 0, . . . , 0) . Un élément
y = (y 1 , . . . , y n ) =
n
i=1
α i d i ∈ K ◦
2 a donc pour composantes
y 1 = α 1 − α n , y 2 = α 2 − α 1 , . . . , y n−1 = α n−1 − α n−2 , y n = −α n−1 .
Sachant que les α i sont tous positifs ou nuls, il s’ensuit :
y n 0, y n−1 + y n 0, . . . , y k + . . . + y n 0, y 1 + . . . + y n 0.
Réciproquement, partant de y 1 , . . . , y n vérifiant les conditions ci-dessus,
posons :
α n = − (y 1 + . . . + y n ) ,
α n−1 = −y n , α n−2 = − (y n−1 + y n ) , . . . , α k = − (y k+1 + . . . + y n ) , . . . ,
α 1 = − (y 2 + . . . + y n ) .
185