Chapitre V. Polyèdres convexes fermés. Optimisation à données affines...
ce qui conduit, puisque x(σ), u(σ) = nσ et x(σ) − x ∗ , u(σ) − u ∗ = 0
(cf. (5.34)), à :
x
∗ , u(σ) + x(σ), u
∗
=
n
i=1
[x
∗
i u(σ) i + x(σ) i u
∗
i ] = nσ.
Divisons les deux membres de la dernière égalité ci-dessus par σ (= x(σ) i u(σ) i
pour tout i = 1, . . . , n) ; il s’ensuit
n
i=1
x ∗
i
x(σ) i
+
u ∗
i
u(σ) i
= n.
(5.35)
Comme x ∗ 0, u ∗ 0 et x ∗ , u ∗ = 0, on a x ∗
i u ∗
i = 0 pour tout i, de sorte
que (5.35) se réécrit en
i∈I
x ∗
i
x(σ) i
+
i∈J
u ∗
i
u(σ) i
= n
(5.36)
où I := {i | x ∗
i > 0} et J := {i | u ∗
i > 0} (I et J sont disjoints). Mais
lim
σ→0
x ∗
i
x(σ) i
= 1 si i ∈ I et lim
σ→0
u ∗
i
u(σ) i
= 1 si i /
∈ I,
ce qui, avec (5.36), donne bien le résultat escompté.
4 ◦ ) Le programme dual (D) de (P) est un programme linéaire dans R 2 , à
savoir :
(D)
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
Maximiser y 2
−y 1 1
y 1 1
y 2 1.
(P) et (D) peuvent être résolus graphiquement : x = (0, 0, 1) est la seule solution de (P) tandis que {(y 1 , 1) | −1 y 1 1} est l’ensemble-solution de (D).
(SO) σ devient ici :
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
−x 1 + x 2 = 0, x 3 = 1, (x 1 > 0, x 2 > 0)
−y 1 + u 1 = 1,
y 1 + u 2 = 1, (u 1 > 0, u 2 > 0, u 3 > 0)
y 2 + u 3 = 1,
x 1 u 1 = x 2 u 2 = x 3 u 3 = σ.
214