Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Solution : 1 re partie
1 ◦ ) a) Soit x 0 quelconque dans C. On rappelle :
(d ∈ C ∞ ) ⇔ (x 0 + td ∈ C pour tout t > 0) .
Dans le cas présent, d ∈ C ∞ si et seulement si Ax 0 + tAd b pour tout
t > 0.
De façon évidente, (Ad 0) ⇒ (d ∈ C ∞ ). Réciproquement, soit d ∈ C ∞ et
supposons (Ad) i 0 > 0 pour un certain i 0 . Alors
(Ax 0 + td) i 0 = (Ax 0 ) i 0 + t (Ad) i 0 b pour tout t > 0
est contredit.
b) (C borné) ⇔ (C ∞ = {0}) . Pour obtenir le résultat annoncé, il suffit de
traduire ceci avec l’expression de C ∞ obtenue précédemment.
2 ◦ ) Soient a 1 , . . . , a m les vecteurs-lignes de A. Dire que « A y = c a, pour
tout c ∈ R n , une solution y 0 », revient à dire que « cône{a 1 , . . . , a m } = R n ».
Grâce au lemme de Minkowski-Farkas, cela équivaut à
{d ∈ R
n
| |a i , d 0 pour tout i = 1, . . . , m} = {0} .
2 e partie. Soit x ∈ C,
x =
s
i=1
α i u i +
r
j=1
β j v j +
p
k=1
γ k w k ,
avec :
α i 0 pour tout i, α 1 + . . . + α s = 1 ;
β j 0 pour tout j ; γ k ∈ R pour tout k.
(5.31)
1 ◦ ) Puisque c, x =
i
α i c, u i +
j
β j c, v j +
k
γ k c, w k avec les
contraintes sur α i et β j énoncées ci-dessus, il vient facilement :
c, x f pour tout x ∈ C
⇔
⎛
⎜
⎝
c, v j 0 pour tout j = 1, . . . , r
et
c, w k = 0 pour tout k = 1, . . . , p
⎞
⎟
⎠ .
Ceci est une manière de dire que −c doit se trouver dans le cône normal à
K et dans le sous-espace orthogonal à L.
2 ◦ ) On suppose que la condition (C) est vérifiée. Le problème (P) a alors
des solutions ; il est, en effet, clair que tout x ∈ Π est solution de (P) car
c, x =
i∈I 1
α i c, u i = f.
202