Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Solution : 1 ◦ ) On observe que x = (x 1 , . . . , x n ) ∈ K si et seulement si les
n − 1 inégalités linéaires suivantes sont vérifiées :
x 1 − x 2 0, x 2 − x 3 0, . . . , x n−1 − x n 0,
c’est-à-dire encore :
x, d i 0 pour tout i = 1, . . . , n − 1,
où d i := (0, . . . , 0, 1, −1, 0, . . . , 0) .
↑ ↑
i e
position
(i + 1)
e
position
2 ◦ ) Il vient de la représentation ci-dessus de K 1 :
K
◦
1 =
n−1
i=1
α i d i | α i 0 pour tout i = 1, . . . , n − 1
.
Explicitons K ◦
1 . Un élément y = (y 1 , . . . , y n ) de K ◦
1 a pour composantes
y 1 = α 1 , y 2 = α 2 − α 1 , . . . , y n−1 = α n−1 − α n−2 , y n = −α n−1 .
Il s’ensuit : y 1 0, y 1 + y 2 0, . . . , y 1 + . . . + y n−1 0 et y 1 + . . . + y n = 0.
Réciproquement, partant de y 1 , . . . , y n vérifiant les conditions ci-dessus,
posons :
α 1 = y 1 , α 2 = y 1 + y 2 , . . . , α n−2 = y 1 + . . . + y n−2 et α n−1 = −y n .
Il est clair que α 1 0, α 2 0, . . . , α n−2 0, α n−1 = y 1 + . . . + y n−1 0,
et (y 1 , . . . , y n ) =
n−1
i=1
α i d i .
On a donc démontré l’expression annoncée de K ◦
1 .
3 ◦ ) K ◦
1 peut aussi s’exprimer de la manière suivante :
K
◦
1 = {y ∈ R
n
| |y, δ i 0 pour i = 1, . . . , n + 1} ,
184