Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
** Probl` eme V.19. Dans tout le problème, C désigne un polyèdre convexe fermé
non vide de R n .
1 re partie. On suppose ici que C est représenté de la manière suivante :
C := {x ∈ R
n
| Ax b} , où A ∈ M m,n (R) et b ∈ R
m .
(5.27)
1 ◦ ) a) Montrer que le cône asymptote C ∞ de C est
C ∞ = {d ∈ R
n
| Ad 0} .
b) En déduire que C est borné si, et seulement si, le système d’inéquations
Ad 0 n’a que la solution d = 0.
2 ◦ ) Montrer l’équivalence des deux assertions suivantes :
(i) {d ∈ R n | Ad 0} = {0} ;
(ii) Pour tout c ∈ R n , le système d’équations A y = c a une solution y 0.
2 e partie. On suppose que C a la représentation suivante :
C := C 0 + K + L,
(5.28)
où
C 0 = conv {u 1 , . . . , u s } est un convexe compact (de R n ),
K = cône {v 1 , . . . , v r } un cône convexe fermé,
L = vect {w 1 , . . . , w p } un sous-espace vectoriel.
On considère le programme linéaire suivant :
(P)
Minimiser c, x ,
x ∈ C
où c ∈ R n est donné.
1 ◦ ) Montrer que la fonction f : x −→ f (x) := c, x est bornée inférieurement
sur C si, et seulement si,
(C)
c, v i 0 pour tout i = 1, . . . , r et
c, w j = 0 pour tout j = 1, . . . , p.
200