V.3. La dualité en programmation linéaire
Solution : 1 ◦ ) Lorsque a i = 1, ||a i , x − b i | représente la distance (euclidienne) du point x à l’hyperplan H i d’équation a i , x − b i = 0.
Lorsque tous les a i sont des vecteurs unitaires, le problème posé revient
donc à chercher les points x de R n minimisant la plus grande des distances de
x aux hyperplans H i .
2 ◦ ) Étant donné que ||a i , x − b i | = max (a i , x − b i , b i − −a i , x), chercher
x ∈ R n rendant max i ||a i , x − b i | le plus petit possible revient à chercher
(x, y) ∈ R n × R vérifiant
a i , x − b i y
− −a i , x + b i y
pour tout i = 1, . . . , m,
avec y le plus petit possible.
Considérons donc le programme linéaire suivant, posé dans R n × R :
(P)
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
Min y
−1
A
. . .
−1
−1
A
. . .
−1
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
x 1
. . .
. . .
. . .
x n
y
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
b 1
. . .
b m
−b 1
. . .
−b m
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
où A ∈ M m,n (R) est la matrice dont les vecteurs-lignes sont les a i .
Une solution (x, y) de (P) fournit une solution x de (P 1 ) et sa valeur optimale min
x∈R n
max
i
||a i , x − b i | = max
i
||a i , x − b i | .
L’ensemble-contrainte de (P) n’est pas vide (il suffit de prendre x ∈ R n
quelconque et y = max i ||a i , x − b i |), et tout y de cet ensemble-contrainte
est 0.
La fonction-objectif (linéaire) est bornée inférieurement sur le polyèdrecontrainte, donc elle y atteint sa borne inférieure : (P) – et donc (P 1 ) – a une
solution.
Pour résoudre numériquement (P 1 ), une possibilité intéressante est donc
de résoudre le programme linéaire (P) associé.
199