102
Recherche opérationnelle
colonne du second membre du primal, c ligne des coefficients de la fonction économique
du primal. Alors primal et dual s'écrivent :
(Primal)
(dual)
Où 0 désigne un vecteur ligne rempli de 0, où on a omis la dimension, par simplification,
et I la matrice carrée unité, dimensions également omises.
Les fonctions « barrières », pour les deux programmes, s'écrivent :
)
Pr
(
=
1
=
1
=
imal
x
Log
x
Log
cX
L
e
j
n
m
n
j
j
n
j
)
(
=
1
=
1
=
Dual
y
Log
y
Log
Y
b
L
e
i
n
m
m
i
i
n
i
t
D
Les conditions du premier ordre, après calculs, donnent :
b
X
I
AX
e =
t
e
t
c
Y
I
Y
A
=
n
x
y
j
j
e
j
m
1.....
=
=
m
y
x
i
i
e
i
n
1.....
=
=
Il s'agit d'un système non linéaire. Si µ = 0, on retrouve les résultats généraux sur les
optima des deux programmes : lorsqu'une variable est de base - positive sauf
dégénérescence -, la variable qui lui correspond dans l'autre programme est nulle. En
effet dans ce cas les deux dernières conditions donnent :
(avec
se
correspondant).
En général, on ne peut pas résoudre de façon directe ce système, mais on peut adopter
une méthode de résolution pas à pas. De telles méthodes existent (Newton-Raphson par
exemple) et sont exposées dans des ouvrages généraux sur l'optimisation. Comme elles
consistent à partir d'une solution admissible et à la transformer progressivement de façon
à s'orienter vers les valeurs des variables qui respectent l'ensemble des contraintes, on
adopte alors ce cheminement ici, en partant à chaque fois du point obtenu à l'étape
précédente, et en diminuant progressivement µ. (Prendre µ d'emblée très faible conduit à