Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Il existe donc α 1 , α 2 , . . . , α m non tous nuls tels que
m
i=1
α i a i = 0. On s’arrange pour que I := {i | α i < 0} ne soit pas vide. Tout vecteur x de K peut
alors s’écrire
x =
m
i=1
t i + tα i
a i , où t := min
i∈I
−
t i
α i
(0) .
Par choix de t, t i + tα i 0 pour tout i, mais l’un d’entre eux au moins est
nul, disons celui correspondant à i 0 . Ainsi
K =
m
i 0 =1
⎧
⎨
⎩
v | v =
i = i 0
τ i a i | τ i 0 pour tout i = i 0
⎫
⎬
⎭
.
On réitère le procédé jusqu’à exprimer K comme réunion finie de cônes
convexes engendrés par des familles libres de vecteurs, donc fermés d’après le
résultat du 1 er point.
** Exercice V.13. R n est muni de la base canonique {e 1 , e 2 , . . . , e n } et du produit
scalaire canonique noté ., . . Étant donnés A ∈ M m,n (R), b ∈ R m et c ∈ R n
(de coordonnées c j ), on considère le programme linéaire suivant :
(P L)
Minimiser c, x
x ∈ C := {x 0 : Ax = b} .
On suppose C = φ et α := inf
x∈C
c, x > −∞. L’objet de l’exercice est de
démontrer directement que (P L) a alors une solution (au moins). On pourra
utiliser librement le résultat suivant : si v 1 , . . . , v p sont des vecteurs de R q , alors
le cône convexe de R q engendré par v 1 , . . . , v p , i.e.
cône {v 1 , . . . , v p } :=
⎧
⎨
⎩
p
j=1
λ j v j : λ j 0 pour tout j
⎫
⎬
⎭
est fermé.
Soit A :=
c 1 , . . . , c n
A
∈ M m+1,n (R) et désignons par K le cône convexe de
R m+1 engendré par les vecteurs Ae 1 , . . . , Ae n .
190
Il existe donc α 1 , α 2 , . . . , α m non tous nuls tels que
m
i=1
α i a i = 0. On s’arrange pour que I := {i | α i < 0} ne soit pas vide. Tout vecteur x de K peut
alors s’écrire
x =
m
i=1
t i + tα i
a i , où t := min
i∈I
−
t i
α i
(0) .
Par choix de t, t i + tα i 0 pour tout i, mais l’un d’entre eux au moins est
nul, disons celui correspondant à i 0 . Ainsi
K =
m
i 0 =1
⎧
⎨
⎩
v | v =
i = i 0
τ i a i | τ i 0 pour tout i = i 0
⎫
⎬
⎭
.
On réitère le procédé jusqu’à exprimer K comme réunion finie de cônes
convexes engendrés par des familles libres de vecteurs, donc fermés d’après le
résultat du 1 er point.
** Exercice V.13. R n est muni de la base canonique {e 1 , e 2 , . . . , e n } et du produit
scalaire canonique noté ., . . Étant donnés A ∈ M m,n (R), b ∈ R m et c ∈ R n
(de coordonnées c j ), on considère le programme linéaire suivant :
(P L)
Minimiser c, x
x ∈ C := {x 0 : Ax = b} .
On suppose C = φ et α := inf
x∈C
c, x > −∞. L’objet de l’exercice est de
démontrer directement que (P L) a alors une solution (au moins). On pourra
utiliser librement le résultat suivant : si v 1 , . . . , v p sont des vecteurs de R q , alors
le cône convexe de R q engendré par v 1 , . . . , v p , i.e.
cône {v 1 , . . . , v p } :=
⎧
⎨
⎩
p
j=1
λ j v j : λ j 0 pour tout j
⎫
⎬
⎭
est fermé.
Soit A :=
c 1 , . . . , c n
A
∈ M m+1,n (R) et désignons par K le cône convexe de
R m+1 engendré par les vecteurs Ae 1 , . . . , Ae n .
190