Dualité
75
(la symétrie du théorème III et du théorème III bis est assurée par le fait que l'on
maximise
dans le dual).
De la même façon, nous allons démontrer le théorème suivant :
Théorème IV : À l'optimum des deux programmes, la valeur d'une variable d'écart
du dual est égale à l'opposé du gain marginal de la variable principale qui lui est
associée dans le primal.
En effet, les contraintes du dual s'écrivent :
c
A
y
Si on appelle le vecteur ligne
des variables d'écart du dual, on a :
c
y
A
y
o =
À l'optimum du dual, on a vu que le vecteur des variables principales était
si donne la base optimale du primal. On a donc alors :
Or,
est un vecteur ligne
qui est égal à l'opposé du vecteur des gains
marginaux des variables principales du programme primal à l'optimum de ce même
programme. D'où le théorème IV. Naturellement, on en déduit :
Théorème IV bis : À l'optimum des deux programmes, la valeur d'une variable
d'écart du primal est égale à l'opposé du gain marginal de la variable principale qui
lui est associée dans le dual.
Les théorèmes III, III bis, IV et IV bis aboutissent aux conséquences suivantes : on voit
que pour deux variables, l'une dans le primal et l'autre dans le dual, qui se correspondent,
valeur à l'optimum et gain marginal à l'optimum s'échangent (au signe près). Donc, cela
signifie, si l'on ne tient pas compte de dégénérescences éventuelles, que si une variable
du primal est de base à l'optimum, sa variable associée dans le dual est hors base à
l'optimum de ce dernier et réciproquement.
Pour être plus clair, unifions les notations, afin que deux variables associées portent le
même indice : Si le primal s'écrit, avec les variables d'écart :
1
1
1
1
11
= b
x
x
a
x
a
n
n
n
m
n
m
n
mn
m
b
x
x
a
x
a
=
1
1
0
, 2
1
n
m
x
x
x
écrivons le dual de la façon suivante, en affectant les indices 1, 2 … aux variables
d'écart.
1
1
1
11
1
= c
y
a
y
a
y
n
m
m
n
n
n
m
mn
n
n
n
c
y
a
y
a
y
=
1
1