V.3. La dualité en programmation linéaire
Réciproquement, soit x =
i
α i u i +
j
β j v j +
k
γ k w k une solution de (P) ;
on a :
i
α i c, u i +
j
β j c, v j
i
α i c, u i +
j
β j c, v j = f
pour tout (α 1 , . . . , α r ) et (β 1 , . . . , β s ) vérifiant les conditions décrites en (5.31) .
Avoir β j > 0 et c, v j > 0 est impossible car cela contredirait le caractère
optimal de x (on construirait facilement un ˜
x ∈ C qui ferait « mieux » que x,
c, ˜
x < f ).
Ensuite, sachant que c, u i f pour tout i, l’égalité
i
α i
c, u i − f
= 0
ne souffre pas qu’on puisse avoir simultanément α i > 0 et c, u i − f > 0.
Donc x est bien dans Π.
3 ◦ ) Ici C = C 0 = conv{u 1 , . . . , u s } . Puisque Π = C, il existe un i pour
lequel c, u i > f. De par la convexité de Π, lorsque x =
s
i=1
α i u i ∈ C 0 ,
d Π
s
i=1
α i u i
s
i=1
α i d Π (u i ) .
Nous avons deux cas possibles :
i ∈ I 1 , ce qui revient à u i ∈ Π, auquel cas d Π (u i ) = 0 ;
i /
∈ I 1 , auquel cas d Π (u i )
c,u i −f
α
.
En conséquence,
d Π (x)
i /
∈I 1
α i
c, u i − f
α
c, x − f
α
·
3 e partie
Le programme linéaire (P L) est posé dans R n × R m × R m en les variables
x 1 , . . . , x n , t 1 , . . . , t m , z 1 , . . . , z m .
1 ◦ ) Pour x quelconque dans R n , posons pour i = 1, . . . , m
t i := (a i , x − b i )
+ , z i := (b i − −a i , x)
+ .
Le vecteur
x 1 , . . . , x n , (a 1 , x − b 1 )
+ , . . . , ( a m , x − b m )
+ ,
b 1 − −a 1 , x)
+ , . . . , (b m − −a m , x)
+
est admissible pour (P L) .
2 ◦ ) On a par définition même de C : (x ∈ C) ⇔ ((Ax − b)
+ = 0).
203