L3 SCI (Semestre 1 – 2017/2018)
Matière:
Recherche Opérationnelle (RO)
Assurée par: BOUZENADA Mourad
[email protected] DUALITE
2
DUALITE
3
DUALITE
4
DUALITE
Exemple
5
DUALITE
Le dual du dual est équivalent au primal
Exemple
6
DUALITE
Propriétés
Théorème 1: Dualité faible
Si le Primal P est de type max alors la valeur économique de
toutes solutions admissibles (réalisables) du dual D est supérieur
ou égal à la valeur économique du primal.
En d’autres termes, la fonction objectif du dual majore toujours la
fonction objectif du primal.
7
DUALITE
Exemple
Max Z = 6X1 + 5X2
X1 + X2 ≤ 5
3X1 + 2 X2 ≤ 12
X1 ≥ 0, X2 ≥ 0
(0, 0), (3, 1) et (2, 3) sol. réalisables de (P)
Z = 0, Z = 23 et Z = 27
Min W = 5Y1 + 12Y2
Y1 + 3Y2 ≥ 6
Y1 + 2Y2 ≥ 5
Y1 ≥ 0, Y2 ≥ 0
(3, 3), (1, 2) et (3, 1) sol. réalisables de (D)
W = 51, W = 29 et W = 27
8
DUALITE
Exemple
Max Z = 6X1 + 5X2 Min W = 5Y1 + 12Y2
X1 + X2 ≤ 5 Y1 + 3Y2 ≥ 6
3X1 + 2 X2 ≤ 12 Y1 + 2Y2 ≥ 5
X1 ≥ 0, X2 ≥ 0 Y1 ≥ 0, Y2 ≥ 0
Soient (X1 , X2) sol. réalisable de (P) et (Y1 , Y2) sol. réalisable de (D)
W
(X1 + X2 ≤ 5) x Y1
Y1(X1+ X2) + Y2(3X1+ 2X2) ≤ 5Y1+ 12Y2
(3X1 + 2 X2 ≤ 12) x Y2
≥6 ≥5
Y1(X1+ X2) + Y2(3X1+ 2X2) ≤ W X1(Y1+ 3Y2) + X2(Y1+ 2Y2) ≤ W
Z≤ W 6X1 + 5X2 ≤ W
9
Z
DUALITE
Théorème 2: Critère d’optimalité
Si des solutions admissibles (réalisables) du Primal P et du
dual D ont des valeurs économiques égales alors ces solutions
admissibles sont aussi des solutions optimales pour le primal et le
dual.
Max Z = 6X1 + 5X2 Min W = 5Y1 + 12Y2
X1 + X2 ≤ 5 Y1 + 3Y2 ≥ 6
3X1 + 2 X2 ≤ 12 Y1 + 2Y2 ≥ 5
X1 ≥ 0, X2 ≥ 0 Y1 ≥ 0, Y2 ≥ 0
(2, 3) sol. réalisable de (P) et Z=27 (2, 3) sol. optimale de (P)
(3, 1) sol. réalisable de (D) et W=27 (3, 1) sol. optimale de (D)
10
DUALITE
Théorème 3: Fondamental de la dualité
Etant donné deux PLs duaux P et D, Si P et D admettent
une solution réalisable, ils admettent alors une solution optimale
et leurs fonctions objectives sont égales à l’optimum.
-Si l’un des PLs duaux possède une classe de solutions pour
laquelle la valeur de la fonction objectif n’est pas bornée, alors
l’autre ne possède pas de solution réalisable.
-Si l’un des PLs duaux possède une solution réalisable et que
l’autre n’en possède pas, alors le PL qui possède la solution est
non borné.
- Il se peut que ni P ni D admettent des solutions réalisables.
11
DUALITE
Théorème 4: Complémentarité des écarts
Soient X* et Y* des solutions optimales respectivement du primal
P et du dual D. Soient U et V les vecteurs des variables d’écarts
respectivement du primal P et du dual D.
Alors à l’optimum X* V + Y* U = 0.
Exemple
Max Z = 6X1 + 5X2 Min W = 5Y1 + 12Y2
X1 + X2 ≤ 5 Y1 + 3Y2 ≥ 6
3X1 + 2 X2 ≤ 12 Y1 + 2Y2 ≥ 5
X1 ≥ 0, X2 ≥ 0 Y1 ≥ 0, Y2 ≥ 0
(2, 3) sol. optimale de (P) (3, 1) sol. optimale de (D)
12
