V.3. La dualité en programmation linéaire
Maintenant, puisque A I(x) est de rang n, il existe I ⊂ I (x) de cardinal n telle que la matrice A I (∈ M n (R)) soit régulière. Le système A I u = b I
n’a qu’une seule solution, et comme il a été observé que A I x = b I , A I y =
b I , A I z = b I , il s’ensuit x = y = z nécessairement. Ceci entre en contradiction
avec une assertion du début du raisonnement. L’hypothèse faite au départ est
donc absurde : x est un point extrémal de C.
–
rang de A I(x) < n
⇒ (x n’est pas un point extrémal de C)
.
Si rang de A I(x) < n, le système A I(x) u = 0 I(x) a une solution non nulle,
que nous notons u.
Si i /
∈ I (x) , a i , x < b i de sorte que
a i , x + αu < b i et a i , x − αu < b i
pour α = 0 suffisamment petit. On prend α = 0 faisant l’affaire pour tous
les i /
∈ I (x) .
Mais comme A I(x) (x ± α u) = A I(x) (x) ± A I(x) (u) = b I(x) , on a
A (x ± α u) b en tout état de cause. Il en résulte que x + α u et x − α u sont
dans C, et du coup x n’est pas extrémal dans C puisque x = 1/2 (x + α u) +
1/2 (x − α u) .
Commentaire : – En un point extrémal x de C, on a card I (x) n ; lorsque
card I (x) = n, le point x est appelé point extrémal non-dégénéré.
– Le résultat de l’exercice conduit à un majorant du nombre de points extrémaux de C, c’est
m
n
. Toutefois ce majorant est très grossier en général, et
une autre majoration a été donnée par McMullen en 1970 : le nombre de points
extrémaux de C est majoré par
e (m, n) :=
⎛
⎝
m −
n + 1
2
m − n
⎞
⎠ +
⎛
⎝
m −
n + 2
2
m − n
⎞
⎠ ,
où [k] désigne la partie entière de k. Cet entier e(m, n) est en général considérablement plus petit que
m
n
.
– On peut compléter l’exercice en cernant un peu plus les points extrémaux
non-dégénérés de C :
– un point extrémal non-dégénéré x a exactement n points extrémaux adjacents x i (c’est-à-dire que les segments de droites joignant x aux x i sont des arêtes
de C) ;
181
Maintenant, puisque A I(x) est de rang n, il existe I ⊂ I (x) de cardinal n telle que la matrice A I (∈ M n (R)) soit régulière. Le système A I u = b I
n’a qu’une seule solution, et comme il a été observé que A I x = b I , A I y =
b I , A I z = b I , il s’ensuit x = y = z nécessairement. Ceci entre en contradiction
avec une assertion du début du raisonnement. L’hypothèse faite au départ est
donc absurde : x est un point extrémal de C.
–
rang de A I(x) < n
⇒ (x n’est pas un point extrémal de C)
.
Si rang de A I(x) < n, le système A I(x) u = 0 I(x) a une solution non nulle,
que nous notons u.
Si i /
∈ I (x) , a i , x < b i de sorte que
a i , x + αu < b i et a i , x − αu < b i
pour α = 0 suffisamment petit. On prend α = 0 faisant l’affaire pour tous
les i /
∈ I (x) .
Mais comme A I(x) (x ± α u) = A I(x) (x) ± A I(x) (u) = b I(x) , on a
A (x ± α u) b en tout état de cause. Il en résulte que x + α u et x − α u sont
dans C, et du coup x n’est pas extrémal dans C puisque x = 1/2 (x + α u) +
1/2 (x − α u) .
Commentaire : – En un point extrémal x de C, on a card I (x) n ; lorsque
card I (x) = n, le point x est appelé point extrémal non-dégénéré.
– Le résultat de l’exercice conduit à un majorant du nombre de points extrémaux de C, c’est
m
n
. Toutefois ce majorant est très grossier en général, et
une autre majoration a été donnée par McMullen en 1970 : le nombre de points
extrémaux de C est majoré par
e (m, n) :=
⎛
⎝
m −
n + 1
2
m − n
⎞
⎠ +
⎛
⎝
m −
n + 2
2
m − n
⎞
⎠ ,
où [k] désigne la partie entière de k. Cet entier e(m, n) est en général considérablement plus petit que
m
n
.
– On peut compléter l’exercice en cernant un peu plus les points extrémaux
non-dégénérés de C :
– un point extrémal non-dégénéré x a exactement n points extrémaux adjacents x i (c’est-à-dire que les segments de droites joignant x aux x i sont des arêtes
de C) ;
181