V.3. La dualité en programmation linéaire
On considère {x k } une suite minimisante pour (P L), i.e. vérifiant : x k ∈ C
pour tout k et c, x k → α quand k → +∞.
1 ◦ ) Vérifier que Ax k ∈ K pour tout k.
2 ◦ ) En déduire qu’il existe λ 0 dans R n tel que α = c, λ et b = Aλ.
Conclure.
Solution : 1 ◦ ) Puisque x k =
n
j=1
(x k ) j e j et A est linéaire, Ax k =
n
j=1
(x k ) j Ae j .
Comme tous les (x k ) j sont dans R + , on a bien
Ax k ∈ K pour tout k.
2 ◦ ) Notons que Ax k =
c, x k
Ax k
=
c, x k
b
et que la suite {Ax k }
converge, quand k → +∞, vers
α
b
.
Le cône K étant fermé, la limite de {Ax k } se trouve encore dans K.
Ainsi, il existe λ = (λ 1 , . . . , λ n ) ∈ (R + )
n tel que
α
b
=
n
j=1
λ j Ae j ,
c’est-à-dire, puisque Ae j =
c j
Ae j
,
α =
n
j=1
λ j c j et b = Aλ.
Donc λ ∈ C et c, λ = α = inf x∈C c, x ; en clair λ est une solution
de (P L) .
** Exercice V.14. Soient c = (c 1 , . . . , c n ) ∈ R n , a = (a 1 , . . . , a n ) ∈ R n et b 0 ∈ R
tels que :
b 0 > 0 et c j > 0, a j > 0 pour tout j = 1, . . . , n.
On considère le programme linéaire suivant :
(P)
Max c, x
x ∈ C := {x ∈ R n | |a, x b 0 , x j 0 pour tout j = 1, . . . , n} .
191