V.3. La dualité en programmation linéaire
** Exercice V.3. Soit C un polyèdre convexe compact de R n décrit comme
{x ∈ R n | Ax = b, x 0}, avec A ∈ M m,n (R) de rang m. Montrer l’équivalence
suivante :
Chaque ´ el´ ement de C a au
moins m composantes > 0
⇔
Chaque sommet de C a
exactement m composantes > 0
.
Commentaire : On illustrera ce résultat avec le simplexe-unité de R n , c’est-à-dire
avec
C :=
x = (x 1 , . . . , x n ) ∈ R
n
|
n
i=1
x i = 1, x i 0 pour tout i = 1, . . . , n
.
Solution : [⇒]. Un sommet x de C est un élément de base admissible ; les n−m
composantes hors-base sont donc nulles. Comme x, élément de C, a au moins
m composantes > 0, il en résulte que x a exactement m composantes > 0.
[⇐]. Un élément x de C est une combinaison convexe de points extrémaux x i de C :
x =
k
i=1
α i x
i , avec α i > 0 pour tout i et
k
i=1
α i = 1.
(5.20)
Supposons que x ait l > n − m composantes nulles et montrons que cela
conduit à une contradiction. Soit J ⊂ {1, . . . , k} de cardinal l tel que x j = 0
pour tout j ∈ J. Il vient de (5.20)
k
i=1
α i
x
i
j
= 0 pour tout j ∈ J,
d’où
x i
j
= 0 pour tout j ∈ J, ce qui voudrait dire que x i a l > n − m
composantes nulles au moins. Ceci entre en contradiction avec le fait que x i a,
par hypothèse, m composantes > 0.
Dans le cas du simplexe-unité C de R n , les n points extrémaux e i de C ont
exactement 1 composante > 0, mais les éléments de C peuvent avoir 1, 2, . . .
ou n composantes > 0.
177