Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Solution : 1 ◦ ) C est décrit sous la forme : Ax = b, x 0, avec A ∈ M 3,4 (R)
de rang 3 ; les éléments de base admissibles (et donc les points extrémaux de C)
sont :
0,
3
4
,
1
4
, 0
correspondant à la base {2, 3, 4} ,
1
2
, 0,
1
2
, 0
correspondant à la base {1, 3, 4} .
2 ◦ ) x =
0,
3
4 ,
1
4 , 0
est la seule solution de (P), et val(P) = 1.
3 ◦ ) On a introduit une légère perturbation dans un des coefficients de A,
par exemple
4
3 est remplacé par 1,333333. Il s’ensuit par des calculs similaires
à ceux de la question précédente que la (seule) solution de (P ε ) est à présent
x ε =
1
2 , 0,
1
2 , 0
, et la valeur optimale correspondante val(P ε ) = 2.
Il n’y a donc pas, en général, de « continuité » de la valeur optimale ou
de l’ensemble-solution d’un programme linéaire
Min c, x
Ax = b, x 0
considérés
comme fonctions des coefficients de A.
** Exercice V.18. Étant donnés a 1 , . . . , a m dans R n , b 1 , . . . , b m dans R, et le
système d’équations
(S)
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
a 1 , x − b 1 = 0
a 2 , x − b 2 = 0
. . .
a m , x − b m = 0,
on cherche le (ou les) point(s) minimisant
x −→ f (x) := max i=1,...,m ||a i , x − b i | sur R n (problème appelé (P 1 ) dans
la suite).
1 ◦ ) Que représente géométriquement ||a i , x − b i | lorsque a i = 1 ?
Quelle est la signification géométrique du problème posé ci-dessus lorsque
tous les a i sont de norme égale à 1 ?
2 ◦ ) Formaliser (P 1 ) comme un problème de programmation linéaire, et en
tirer toutes les conséquences.
198
Solution : 1 ◦ ) C est décrit sous la forme : Ax = b, x 0, avec A ∈ M 3,4 (R)
de rang 3 ; les éléments de base admissibles (et donc les points extrémaux de C)
sont :
0,
3
4
,
1
4
, 0
correspondant à la base {2, 3, 4} ,
1
2
, 0,
1
2
, 0
correspondant à la base {1, 3, 4} .
2 ◦ ) x =
0,
3
4 ,
1
4 , 0
est la seule solution de (P), et val(P) = 1.
3 ◦ ) On a introduit une légère perturbation dans un des coefficients de A,
par exemple
4
3 est remplacé par 1,333333. Il s’ensuit par des calculs similaires
à ceux de la question précédente que la (seule) solution de (P ε ) est à présent
x ε =
1
2 , 0,
1
2 , 0
, et la valeur optimale correspondante val(P ε ) = 2.
Il n’y a donc pas, en général, de « continuité » de la valeur optimale ou
de l’ensemble-solution d’un programme linéaire
Min c, x
Ax = b, x 0
considérés
comme fonctions des coefficients de A.
** Exercice V.18. Étant donnés a 1 , . . . , a m dans R n , b 1 , . . . , b m dans R, et le
système d’équations
(S)
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
a 1 , x − b 1 = 0
a 2 , x − b 2 = 0
. . .
a m , x − b m = 0,
on cherche le (ou les) point(s) minimisant
x −→ f (x) := max i=1,...,m ||a i , x − b i | sur R n (problème appelé (P 1 ) dans
la suite).
1 ◦ ) Que représente géométriquement ||a i , x − b i | lorsque a i = 1 ?
Quelle est la signification géométrique du problème posé ci-dessus lorsque
tous les a i sont de norme égale à 1 ?
2 ◦ ) Formaliser (P 1 ) comme un problème de programmation linéaire, et en
tirer toutes les conséquences.
198