70
Recherche opérationnelle
Par ailleurs, il est facile de voir que le programme dual du dual est le primal. En effet,
soit le programme (II). on peut l'écrire ainsi :
t
t
t
c
y
A
0
t
y
en réservant le symbole aux matrices transposées des matrices figurant dans (II). On
peut encore écrire ce programme :
t
t
t
c
y
A
0
t
y
Le dual de ce dernier programme s'écrit alors :
t
t
t
t
b
x
A
)
(
)
(
0
x
Soit
On retrouve bien le programme (I).
En conséquence, la correspondance ci-dessus marche également dans le sens dual
primal et on peut écrire :
à une variable d'écart du dual correspond biunivoquement une variable principale
du primal. Ces correspondances sont exprimées dans le tableau suivant :
Primal
Dual
Variables principales
Variables principales
Variables d’écart
Variables d’écart
Remarque importante : pour le dual, l'addition de variables d'écart doit se faire de la
façon suivante, pour que toutes les variables restent positives :
1
1
2
21
1
11
= c
y
y
a
y
a
y
a
m
m
l
m
n
n
m
m
mn
n
n
c
y
y
a
y
a
y
a
=
2
2
1
1
0
1
1
n
m
m
'
m
y
y
y
y
0
x
b
x
A