V.3. La dualité en programmation linéaire
se décompose en :
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
u 1 −
σ
x 1
, . . . , u n −
σ
xn
∈ Im A
et
x 1 −
σ
u 1
, . . . , x n −
σ
un
∈ Ker A.
(5.32)
Pour alléger l’écriture, notons
u
σ −
1
x le vecteur de R n de composantes
u i
σ −
1
x i
,
x
σ −
1
u le vecteur de R n de composantes
x i
σ −
1
u i
,
w le vecteur de R n de composantes
x i u i
σ .
Soit := diag
x 1
u 1
, . . . ,
xn
un
. De simples calculs font observer que
√
σ
u
σ
−
1
x
= w −
1
w
=
√
σ
−1
x
σ
−
1
u
.
Au vu de (5.32), il vient alors
w −
1
w
∈ Im(A
) et w −
1
w
∈ Ker (A).
Mais comme (A) = A , les deux sous-espaces Im(A ) et Ker(A) sont
orthogonaux, d’où w −
1
w = 0, c’est-à-dire x i u i = σ pour tout i = 1, . . . , n.
3 ◦ ) Après un passage à la limite (σ → 0), on obtient que
Ax ∗ = b, x ∗ 0
A y ∗ + u ∗ = c, y ∗ 0
x ∗ , u ∗ = 0,
(5.33)
c’est-à-dire (x ∗ , y ∗ , u ∗ ) est solution de (P ˜
D) (ou encore, x ∗ est solution de (P)
et (y ∗ , u ∗ ) est solution de ( ˜
D)).
En combinant (SO) σ et (5.33), on obtient
A(x(σ) − x
∗ ) = 0 et A
(y(σ) − y
∗ ) = u
∗
− u(σ),
d’où
0 = A(x(σ) − x
∗ ), y(σ) − y
∗
=
x(σ) − x
∗ , A
(y(σ) − y
∗ )
(5.34)
= x(σ) − x
∗ , u
∗
− u(σ) .
Par ailleurs
x(σ) − x
∗ , u(σ) − u
∗
= x(σ), u(σ) − (x
∗ , u(σ) + x(σ), u
∗
) ,
213