V.3. La dualité en programmation linéaire
2 ◦ ) Montrer que sous la condition (C), l’ensemble Π des solutions de (P) est
décrit comme suit :
Π =
x ∈ C | x =
i∈I 1
α i u i +
j∈J 2
β j v j +
p
k=1
γ k w k ;
α i 0,
i∈I 1
α i = 1, β j 0, γ k ∈ R
,
où I 1 :=
i | |c, u i = f
, J 2 := {j | |c, v j = 0} , f := inf x∈C f (x).
3 ◦ ) On suppose K = L = {0}, c’est-à-dire C = C 0 borné, et Π = C.
On pose alors : α := min
i /
∈I 1
c, u i − f
d Π (u i )
, où d Π désigne la fonction-distance à Π.
Montrer que : ∀x ∈ C 0 , d Π (x)
c,x−f
α
(5.29)
(on pourra utiliser la convexité de la fonction d Π ).
On admettra pour la suite que le résultat de cette question est encore valable
pour un C décrit en (5.28) (non nécessairement borné), et que tout C décrit
comme en (5.27) peut être représenté sous la forme (5.28) .
3 e partie. On revient à la représentation (5.27) de C, et on considère le
programme linéaire suivant (dans R n × R m × R m ) :
(P L)
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
Minimiser
m
i=1
t i
a i , x − b i = t i − z i pour i = 1, . . . , m
(les a i désignent les vecteurs-lignes de A)
t i 0, z i 0 pour i = 1, . . . , m.
1 ◦ ) Vérifier que pour tout x ∈ R n , le vecteur (x, (Ax − b) + , (b − Ax) + ) est
admissible pour (P L) .
2 ◦ ) Établir que toute solution de (P L) est de la forme (x, 0, b − Ax), où
x ∈ C.
En déduire, à l’aide du résultat de la 3 e question de la 2 e partie, qu’il existe
α > 0 tel que :
∀x ∈ R
n , d C (x)
1
α
m
i=1
(a i , x − b i )
+ .
(5.30)
201