76
Recherche opérationnelle
0
1
m
n
y
y
On a ainsi la correspondance, puisqu'une variable principale du primal est associée à une
variable d'écart du dual :
i
i
y
x
Les résultats que l'on vient d'énoncer peuvent alors s'écrire, si on se place à l'optimum
des deux programmes, et si et sont les gains marginaux de et de .
(11)
Ces relations sont appelées relations d'exclusion.
Terminons ce paragraphe en donnant la correspondance complète entre les deux tableaux
optimaux du simplexe, l'un pour le primal, l'autre pour le dual.
À l'optimum du primal, on a, on le sait, si est l'ensemble d'indices de base :
Posons comme dans le premier chapitre
et
on a donc :
(12)
La matrice
étant la matrice unité,
représente le tableau optimal du
simplexe , permettant d'exprimer les variables de base en fonction des variables hors
base est appelée matrice simpliciale. Par ailleurs, on a
Posons
et
avec
, puisque l'on se place à l'optimum. Avec ces notations :
(13)
D'après ce qu'on a vu, à l'optimum des deux programmes une variable de base du primal
correspond à une variable hors base du dual. Par conséquent, si est l'ensemble des
indices de base dans le primal, avec les conventions ci-dessus, sera l'ensemble des
indices hors base dans le dual et l'ensemble des indices de base.
Puisque par ailleurs, lorsque l'on passe au dual, valeur des variables et gains marginaux
s'échangent (au signe près), on aura à l'optimum du dual :
(14)
(15)