V.3. La dualité en programmation linéaire
Figure 12.
Π 1 de sommets (0,0,1), (0,1,0), (0,0,1)
Π 2 de sommets (0,1,1), (1,0,1), (1,1,0)
Π 3 = {(1, 1, 1)}.
b) Appelons E m l’ensemble des points extrémaux de Π m et x, ·· la forme
linéaire sur R n définie par x, (α 1 , . . . , α n ) =
n
i=1
α i x i . Le maximum de x, ··
est le même sur Π m et sur E m :
max
α∈Πm
x, α = max
α∈Em
x, α .
Au vu de l’expression des α ∈ E m , ce dernier maximum est la somme des
m plus grands nombres parmi les x 1 , . . . , x n .
** Exercice V.16. Soit C un polyèdre convexe fermé de R n . Pour tout d ∈ R n ,
on note F (d) la face de C exposée par d, c’est-à-dire
F (d) =
x ∈ C | |x, d = max
x∈C
x, d
.
1 ◦ ) Soit d ∈ R n . Montrer qu’il existe un voisinage V de d tel que
F (d) ⊂ F (d) pour tout d ∈ V.
2 ◦ ) On considère le programme linéaire suivant :
(P)
Max x, d
x ∈ C.
Quelle conséquence pour la résolution de (P) peut-on tirer du résultat de la
1 re question ?
195
Figure 12.
Π 1 de sommets (0,0,1), (0,1,0), (0,0,1)
Π 2 de sommets (0,1,1), (1,0,1), (1,1,0)
Π 3 = {(1, 1, 1)}.
b) Appelons E m l’ensemble des points extrémaux de Π m et x, ·· la forme
linéaire sur R n définie par x, (α 1 , . . . , α n ) =
n
i=1
α i x i . Le maximum de x, ··
est le même sur Π m et sur E m :
max
α∈Πm
x, α = max
α∈Em
x, α .
Au vu de l’expression des α ∈ E m , ce dernier maximum est la somme des
m plus grands nombres parmi les x 1 , . . . , x n .
** Exercice V.16. Soit C un polyèdre convexe fermé de R n . Pour tout d ∈ R n ,
on note F (d) la face de C exposée par d, c’est-à-dire
F (d) =
x ∈ C | |x, d = max
x∈C
x, d
.
1 ◦ ) Soit d ∈ R n . Montrer qu’il existe un voisinage V de d tel que
F (d) ⊂ F (d) pour tout d ∈ V.
2 ◦ ) On considère le programme linéaire suivant :
(P)
Max x, d
x ∈ C.
Quelle conséquence pour la résolution de (P) peut-on tirer du résultat de la
1 re question ?
195