Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
1 ◦ ) Vérifier que C n’est pas vide et est borné.
2 ◦ ) Quels sont les points extrémaux de C ?
3 ◦ ) Décrire la face de C constituée de l’ensemble des solutions de (P).
4 ◦ ) Illustrer les résultats précédents en faisant n = 3, a 1 = a 2 = a 3 = b 0 =
1, et en choisissant successivement c = (0, 0, 1) , c = (0, 1, 1) et c = (1, 1, 1) .
Solution : 1 ◦ ) C n’est pas vide puisque (0, . . . , 0) y appartient. De plus, C
est borné puisque
(x = (x 1 , . . . , x n ) ∈ C) ⇒
0 x j
b 0
min j a j
pour tout j = 1, . . . , n
.
2 ◦ ) 1 re méthode. Décrivons C sous la forme standard. Pour cela posons
˜
C := {(x, u) ∈ R
n
× R | |a, x + u = b 0 , x 0, u 0} .
Les points extrémaux de ˜
C sont faciles à déterminer ; les points extrémaux
de C s’ensuivront (cf. Exercice V.4).
Dans l’équation
[a 1 . . . a n 1]
⎡
⎢
⎢
⎢
⎣
x 1
. . .
x n
u
⎤
⎥
⎥
⎥
⎦
= b 0,
les éléments de base admissibles sont :
n
0, . . . , 0, b 0
correspondant à la base {n + 1} ;
0, . . . , 0,
b 0
a j
, 0, . . . , 0
correspondant à la base {j} , 1 j n.
Ce sont les points extrémaux de ˜
C.
Par suite, les points extrémaux de C sont
(0, . . . , 0) ,
0, . . . , 0,
b 0
a j
, 0, . . . , 0
, 1 j n. (Il y en a n + 1 au total.)
2 e méthode. Écrivons C sous la forme Ax b où
A :=
a 1 . . . a n
−I n
∈ M n+1,n (R) et b :=
⎛
⎜
⎜
⎜
⎝
b 0
0
. . .
0
⎞
⎟
⎟
⎟
⎠
,
et utilisons le résultat de l’Exercice V.6.
192