Programmation Linéaire
DUALITE
Y. AL MERIOUH
Dualité
• À tout problème de PL (le primal) on peut
associer un autre problème PL, son dual
• Le problème dual permet de donner une
autre interprétation économique au
problème primal
Formulation du Primal
max z = c1 x1 + c2 x2 + ... + cr xr
sc
a1 1 x1 + a1 2 x2 + ... + a1 r xr ≤ b1
a2 1 x1 + a2 2 x2 + ... + a2 r xr ≤ b2
...
am 1 x1 + am 2 x2 + ... + am r xr ≤ bm
xj ≥ 0 , ∀ j = 1,2, … , r
Formulation du Dual
min v = b1 u1 + b2 u2 + ... + bm um
sc
a1 1 u1 + a2 1 u2 + ... + am 1 um ≥ c1
a1 2 u1 + a2 2 u2 + ... + am 2 um ≥ c2
…
a1 r u 1 + a 2 r u2 + ... + am r um ≥ cr
ui ≥ 0 , ∀ i = 1,2, … , m
Formulation du Dual
Pour obtenir la formulation du problème dual, il faut :
• Associer à chacune des m inégalités une nouvelle
variable u1 , u2 , …….. , um ≥ 0
• La fo est une fonction v à minimiser
• Il y’a r contraintes + les contraintes de non négativité
• Inversement, si le problème initiale est un problème
de minimisation, son dual serait un problème de
maximisation. Les problème de PL se présentent
donc par paires.
Primal et son Dual
Si on observe le jeu de permutations des coefficients entre
les deux programmes, on remarque que :
1. Le dual d’un problème de max. est un problème min, et
réciproquement.
2. Le sens des inégalités dual est inverse de celui des
inégalités du primal, sauf les contraintes de non
négativité.
3. Le dual comporte autant des contraintes qu’il y’a de
variables dans le primal, et et réciproquement
4. Les coefficients de la f.o. du primal apparaissent
comme des constantes des contraintes du dual, et
inversement
5. Les coefficients, lus en colonne dans le primal, sont
écrits en ligne dans le dual, et inversement
Dualité
Exemple :
régime alimentaire :
– 6 produits alimentaires comme sources
de vitamines A et C
– but : minimiser le coût du régime tout en
satisfaisant la valeur nutritionnelle
minimale de chaque vitamine
Dualité
Exemple :
Valeurs nutritionnelles & coût par produit
produit ( i ) Produits demande
(unités/kg) 1 2 3 4 5 6 (unité)
vitamine A 1 0 2 2 1 2 9
vitamine C 0 1 3 1 3 2 19
prix par kg 35 30 60 50 27 22
Dualité
Le modèle :
xj = quantité consommée de chaque produit (en kg)
min z = 35 x1 + 30 x2 + 60 x3 + 50 x4 + 27 x5 + 22 x6
sc
x1 + 2 x3 + 2 x4 + x5 + 2 x6 ≥ 9
x 2 + 3 x3 + x4 + 3 x5 + 2 x6 ≥ 19
x 1 , x2 , x 3 , x 4 , x5 , x6 ≥ 0
Dualité
Exemple : une autre vision du problème
producteur de cachets de vitamines synthétiques :
– 6 produits alimentaires contenant vitamines
A et C
– but : être compétitif tout en maximisant son
profit et en remplissant la demande
Dualité
Exemple :
Prix maximum & composition de chaque produit
produit ( i ) Produits demande
(unité/kg) 1 2 3 4 5 6 (unité)
vitamine A 1 0 2 2 1 2 9
vitamine C 0 1 3 1 3 2 19
prix par kg 35 30 60 50 27 22
par exemple, prix compétitif du produit 5 ⇒ inférieur
ou égal à 27
Dualité
Le modèle :
wi = prix d’une unité de chaque vitamine
produit 5 = 1 unité de vitamine A + 3 unités de vitamine C
⇒ w1 + 3w2 ≤ 27
max v = 9 w1 + 19 w2
sc
w1 ≤ 35
w2 ≤ 30
2 w1 + 3 w2 ≤ 60
2 w1 + w2 ≤ 50
w1 + 3 w2 ≤ 27
2 w1 + 2 w2 ≤ 22
w1 , w2 ≥ 0
Dualité
Primal Dual
min z = 35 x1 + 30 x2 + 60 x3 max v = 9 w1 + 19 w2
+ 50 x4 + 27 x5 + 22 x6 sc
w1 ≤ 35
sc w2 ≤ 30
x1 + 2x3 + 2x4 + x5 + 2x6 ≥ 9 2 w1 + 3 w2 ≤ 60
2 w1 + w2 ≤ 50
x2 + 3x3 + x4 + 3x5 + 2x6 ≥ 19 w1 + 3 w2 ≤ 27
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 2 w1 + 2 w2 ≤ 22
w1 , w2 ≥ 0
Dualité
Primal Dual bw
cx
max v = 9 w1 + 19 w2
min z = 35 x1 + 30 x2 + 60 x3
sc
+ 50 x4 + 27 x5 + 22 x6 w1 ≤ 35
sc w2 ≤ 30
2 w1 + 3 w2 ≤ 60
x1 + 2x3 + 2x4 + x5 + 2x6 ≥ 9
2 w1 + w2 ≤ 50
x2 + 3x3 + x4 + 3x5 + 2x6 ≥ 19 w1 + 3 w2 ≤ 27
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 2 w1 + 2 w2 ≤ 22
w1 , w2 ≥ 0
Ax ≥ b Aw ≤ c
Dualité - Généralisation
Primal ( P ) Dual ( D )
min z = cx max v = bw
1× n n×1 1× m m×1
sc sc
Ax ≥ b Aw ≤ c
m×n m×1 n×m n×1
x≥ 0 w≥ 0
Dualité - Théorèmes
1. Le dual et le primal ont le même
optimum. Cela signifie que le max. de
l’un est égale au min. de l’autre.
2. À l’optimum, lorsqu’une contrainte n’est
pas saturée, la variable duale
correspondante est nulle.