Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
Si x ∈ C, i.e. si t := (Ax − b)
+ = 0 et z := b−Ax, le point (x, 0, b − Ax) est
solution de (P L) puisque la valeur de la fonction-objectif (toujours positive)
en ce point est nulle. Réciproquement, en une solution
x, t, z
de (P L), on
doit avoir a i , x − b i = t i − z i
= (a i , x − b i )
+
− (b i − −a i , x)
+
pour tout
i = 1, . . . , m ; si a i , x − b i > 0 pour un certain i, on pourrait faire « mieux »
que
x, t, z
en prenant ˜
x ∈ C et le point (˜ x, ˜
t := 0, ˜
z := b−A˜ x) correspondant.
Donc x ∈ C en fait et t = 0, z = b − Ax.
La valeur du programme (P L) est 0 et la valeur de sa fonction-objectif en
un point
x, (Ax − b)
+ , (b − Ax)
+
, x ∈ R n , est
m
i=1
(a i , x − b i )
+ . Il résulte
alors de la 3 e question de la 2 e partie, l’existence de α > 0 tel que :
∀x ∈ R
n ,
d C (x) d Π
x, (Ax − b)
+ , (b − Ax)
+
1
α
m
i=1
(a i , x − b i )
+ .
** Exercice V.20. Soit C := {x ∈ R n | Ax b, x 0} un polyèdre convexe
que l’on suppose borné. On considère le problème d’optimisation fractionnaire
suivant :
(P)
⎧
⎨
⎩
Min
c, x + γ
d, x + δ
x ∈ C
,
où c et d sont des vecteurs de R n , γ et δ des réels, et où on suppose que
d, x + δ > 0 pour tout x ∈ C.
On se propose de résoudre (P) par l’intermédiaire du programme linéaire
(en la variable (c, z) ∈ R n × R) suivant :
ˆ
P
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
Min c, y + γz
Ay − zb 0
d, y + δz = 1
y 0, z 0.
1 ◦ ) Montrer que si (y, z) est admissible pour ( ˆ
P), alors z > 0 nécessairement.
2 ◦ ) Démontrer que si (y, z) est une solution de ( ˆ
P), alors x := y/z est une
solution de (P).
204