V.3. La dualité en programmation linéaire
La résolution de ce système d’équations (dont une est non linéaire) fournit
x(σ) = (σ, σ, 1), y(σ) = (0, 1 − σ), u(σ) = (1, 1, σ).
Par suite
x
∗ = (0, 0, 1), y
∗ = (0, 1), u
∗ = (1, 1, 0).
Notons que la solution y ∗ de (D) obtenue par ce procédé est le milieu du
segment-solution de (D).
Commentaire : – Voir l’Exercice 4.12 pour une approche analogue dans la résolution d’un problème de minimisation convexe différentiable (moyennant le changement de paramètre α = 1/σ). Comme ici, σ −→ x(σ) (resp. σ −→ (y(σ), u(σ)) est
appelé « chemin central » conduisant à une solution de (P) (resp. à une solution
de ( ˜
D)).
– Prolongement de l’exercice : Démontrer que, sous les hypothèses qui ont
été faites, l’ensemble {(x, y, u) ∈ C 0 | f σ (x, y, u) r} est borné pour tout r ∈ R.
Cette propriété, combinée à la continuité de f σ , déclenche le résultat d’existence
admis à la 2 e question.
– La propriété particulière de la solution x ∗ = (x ∗
1 , . . . , x ∗
n ) de (P) et des
variables d’écart u ∗
1 , . . . , u ∗
n de ( ˜
D), mise en évidence dans la 3 e question, est
appelée « de Goldman et Tucker ».
215