Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Indication. Pour répondre à la 1 re question on pourra
– raisonner par l’absurde,
– utiliser dans le raisonnement le fait que C a un nombre fini de faces.
Solution : 1 ◦ ) Raisonnons par l’absurde. Supposer le contraire de l’assertion
que l’on veut prouver revient à supposer qu’il existe une suite (d k ) convergeant
vers d telle que :
∀k, F (d k ) n’est pas inclus dans F (d).
(5.26)
Puisque C a un nombre fini de faces, il existe une sous-suite de (d k ) , notée
(d k l ) l , et une face F de C telles que
F (d k l ) = F pour tout l.
Soit y quelconque dans F. Alors, pour tout l :
y, d k l x, d k l pour tout x ∈ C.
Un passage à la limite sur l (l → +∞) conduit à :
y, d
x, d
pour tout x ∈ C,
soit encore : y ∈ F (d).
Nous avons donc prouvé que F ⊂ F (d), ce qui entre en contradiction avec
(5.26) .
2 ◦ ) Soit (d k ) convergeant vers d et soit (P k ) le programme linéaire suivant :
(P k )
Max x, d k
x ∈ C.
196
Indication. Pour répondre à la 1 re question on pourra
– raisonner par l’absurde,
– utiliser dans le raisonnement le fait que C a un nombre fini de faces.
Solution : 1 ◦ ) Raisonnons par l’absurde. Supposer le contraire de l’assertion
que l’on veut prouver revient à supposer qu’il existe une suite (d k ) convergeant
vers d telle que :
∀k, F (d k ) n’est pas inclus dans F (d).
(5.26)
Puisque C a un nombre fini de faces, il existe une sous-suite de (d k ) , notée
(d k l ) l , et une face F de C telles que
F (d k l ) = F pour tout l.
Soit y quelconque dans F. Alors, pour tout l :
y, d k l x, d k l pour tout x ∈ C.
Un passage à la limite sur l (l → +∞) conduit à :
y, d
x, d
pour tout x ∈ C,
soit encore : y ∈ F (d).
Nous avons donc prouvé que F ⊂ F (d), ce qui entre en contradiction avec
(5.26) .
2 ◦ ) Soit (d k ) convergeant vers d et soit (P k ) le programme linéaire suivant :
(P k )
Max x, d k
x ∈ C.
196