Chapitre 3 Dualité
3.1. DEFINITION
On a vu que la forme la plus générale d'un programme linéaire était :
b
x
A
On appellera dual du programme linéaire (I), appelé lui-même primal, le programme
suivant :
c
A
y
)
(
0
II
y
Avec vecteur ligne (1, m)
Ainsi, si le programme primal s'écrit :
1
1
2
12
1
11
b
x
a
x
a
x
a
n
n
m
n
mn
m
m
b
x
a
x
a
x
a
2
2
1
1
0
, 2
1
n
x
x
x
le dual de programme est :
1
1
2
21
1
11
c
y
a
y
a
y
a
m
m
n
m
mn
n
n
c
y
a
y
a
y
a
2
2
1
1
0
, 2
1
n
y
y
y
)
(
0
I
x