Programmation Linéaire
Dualité
4Info
ESPRIT 2020-2021
Plan de la séance
• Programme linéaire dual
• Solution d’un programme dual(Primal)à partir du programme
primal(Dual)
2
Programme dual
Exemple:
• Une Entreprise fabrique deux produits: • X1: Quantité fabriqué des tables
Tables et chaises en utilisant deux
• X2: quantité fabriqué des chaises
ressources: machine de découpe et
machine de finition. • Le programme linéaire
Max Z= 200X1+300X2
Découpe Finition Profit
2𝑋1 + 2𝑋2 ≤ 200
Table (h) 2 3 200 3𝑋1 + 𝑋2 ≤ 100
Chaise (h) 2 1 100 𝑋1 ≥ 0
Capacité de (h) 200 100 𝑋2 ≥ 0
• Quelles sont les quantités à fabriquer pour
maximiser le profit?
3
Programme dual
Exemple • Y1 :coût d’une heure de découpe
• Y2 :coût d’une heure de finition
Découpe Finition • Programme linéaire
Table (h) 2 3
Chaise (h) 2 1 Min C= 200Y1+100Y2
Capacité de (h) 200 100 𝟐𝒀𝟏 + 𝟑𝒀 ≥ 𝟐𝟎
𝟐𝒀𝟏 + 𝒀𝟐 ≥ 𝟏𝟎
marges unitaires d’une table =20DNT 𝒀𝟏 ≥ 𝟎, 𝒀𝟐 ≥ 𝟎
marges unitaires d’une chaise=30DNT
• L’entreprise cherche un contrat de sous-traitance (ou Le programme linéaire de ce problème
vendre). Elle acceptera d’exploiter ses ressources si peut être déduit du programme initial
le prix de vente est à la hauteur des gains.
• Donner le programme linéaire de ce problème.
4
Programme dual
• A tout programme linéaire, on associe un second programme appelé programme dual.
• Le premier programme est dit primal
• Les deux programmes ont la même solution optimale
5
Programme dual
Du primal au dual: règles générales
Primal Dual
Max Min
C b
A 𝐴𝑡
Variables de décision Xi Contraintes i
Xi ≤0 ≤
Xi ≥0 ≥
Xi sans signe =
Contraintes j Variables de décision Yj
≤ Yj ≥0
≥ Yj ≤0
= Yj 𝑠𝑎𝑛𝑠 𝑠𝑖𝑔𝑛𝑒
6
Programme dual
Exemple 3 Variables
2 Variables
Primal Dual
Max Z= 9X1+7X2 Min C= 10Y1+7Y2+8Y3
Sc Sc
1𝑌1 + 𝟑𝑌2 + 5𝑌3 ≥ 𝟗
𝟐𝑌1 − 4𝑌2 = 𝟕
𝟏𝑋1 + 𝟐𝑋2 ≥ 𝟏𝟎
𝑌1 ≤ 0 , Y2 𝑆𝑎𝑛𝑠 𝑠𝑖𝑔𝑛𝑒 , Y3 ≥ 𝟎
𝟑𝑋1 − 𝟒𝑋2 =𝟕
𝟓𝑋1 ≤ 𝟖
𝑿𝟏 ≥ 𝟎, 𝑿𝟐 𝒔𝒂𝒏𝒔 𝒔𝒊𝒈𝒏𝒆
3 Contraintes 2 Contraintes
7
Programme dual
Du primal au dual: règles générales
Primal Dual
Min Max
C b
A 𝐴𝑡
Variables de décision Xi Contraintes i
Xi ≤0 ≥
Xi ≥0 ≤
Xi sans signe =
Contraintes j Variables de décision Yj
≤ Yj≤0
≥ Yj≥0
= 𝑌𝑗 𝑠𝑎𝑛𝑠 𝑠𝑖𝑔𝑛𝑒
8
Programme dual
Exemple 3 Variables
3 Variables
Primal
Dual
MinZ= 1X1+3X2-2X3
Max C= 12Y1+8Y2-10Y3
𝟏𝑋1 + 𝟐𝑋2 ≥ 𝟏𝟐 1𝑌1 + 𝟐𝑌2 + 2𝑌3 ≤ 𝟏
𝟐𝑋1 − 𝟑𝑋2 + 1𝑋3 =𝟖 𝟐𝑌1 − 𝟑𝑌2 = 𝟑
𝟐𝑋1 + 2𝑋3 ≤ −𝟏𝟎 𝟏𝑌2 + 𝟐𝑌3 ≤ −𝟐
𝑿𝟏 ≥ 𝟎, 𝑿𝟑 ≥ 𝟎 𝑌1 ≥ 0 , Y2 𝑆𝑎𝑛𝑠 𝑠𝑖𝑔𝑛𝑒 , Y3 ≤ 𝟎
3 Contraintes
3 Contraintes
9
Programme dual
Applications
Primal Dual
PL(1):Max Z= 10X1+6X2 Min C= 40Y1+60Y2-24Y3
𝑋1 + 4𝑋2 ≤ 40 𝑌1 + 3𝑌2 − 2𝑌3 ≥ 10
3𝑋1 + 2𝑋2 = 60 4𝑌1 + 2𝑌2 − 𝑌3 ≥ 6
−2𝑋1 − 𝑋2 ≤ −24 𝑌1 ≥ 0, 𝑌3 ≥ 0
𝑋1 ≥ 0, 𝑋2 ≥ 0
10
Programme dual
Applications
Primal Dual
PL(2):Min C= X1+3X2 Max Z= 30Y1+10Y2+20Y3
𝑋1 − 𝑋2 ≤ 30 𝑌1 + 3𝑌2 + 2𝑌3 ≤ 1
3𝑋1 + 2𝑋2 = 10 −𝑌1 + 2𝑌2 − 3𝑌3 = 3
2𝑋1 − 3𝑋2 ≥ 20 𝑌1 ≤ 0 , 𝑌3 ≥ 0
𝑋1 ≥ 0
11
Programme dual
Applications
Primal Dual
PL(3):Min C= 25X1+15X2 Max Z= 240Y1+140Y2
3𝑋1 + 5𝑋2 ≤ 240 3𝑌1 + 2𝑌2 ≤ 25
2𝑋1 + 𝑋2 ≤ 140 5𝑌1 + 𝑌2 ≤ 15
𝑋1 ≥ 0, 𝑌1 ≤ 0, 𝑌2 ≤ 0
𝑋2 ≥ 0
12
Plan de la séance
• Programme linéaire dual
• Solution d’un programme dual(Primal)à partir du programme primal(Dual)
15
Solution primal/ dual
Théorème des écarts complémentaires
Dans un programme primal
• si la contrainte est saturée à l’optimum la variable de décision correspondante dans le
programme dual est non nulle
• Si la variable est non nulle à l’optimum alors la contrainte de dual est saturée
16
Solution primal/ dual
Théorème des écarts complémentaires
• Exemple
Max Z= 10X1+15X2+60X3+95X4 Min C= 2Y1+5Y2+3Y3
𝑋1 + 𝑋3 + 2𝑋4 ≤ 2 𝑌1 ≥ 10
𝑋2 + 2𝑋3 + 𝑋4 ≤ 5 𝑌2 ≥ 15
P 𝑋3 + 2𝑋4 ≤ 3 D 𝑌1 + 2𝑌2 + 𝑌3 ≥ 60
2𝑌1 + 𝑌2 + 2𝑌3 ≥ 95
𝑋1 ≥ 0, 𝑋2, 𝑋3 ≥ 0, 𝑋4 ≥ 0
𝑌1 ≥ 0, 𝑌2 ≥ 0, 𝑌3 ≥ 0
Y1*? Y2*?Y3*?
• La solution optimale est
X1*=0, X2*=4, X3*=0 et X4*=1
Z*=155
17
Solution primal/ dual
Théorème des écarts complémentaires
• Exemple
Min C= 2Y1+5Y2+3Y3
Max Z= 10X1+15X2+60X3+95X4
𝑌1 ≥ 10
𝑋1 + 𝑋3 + 2𝑋4 ≤ 2 (1) 𝑌2 ≥ 15
𝑋2 + 2𝑋3 + 𝑋4 ≤ 5(2) D 𝑌1 + 2𝑌2 + 𝑌3 ≥ 60
P 𝑋3 + 2𝑋4 ≤ 3(3) 2𝑌1 + 𝑌2 + 2𝑌3 ≥ 95
𝑋1 ≥ 0, 𝑋2, 𝑋3 ≥ 0, 𝑋4 ≥ 0 𝑌1 ≥ 0, 𝑌2 ≥ 0, 𝑌3 ≥ 0
Y1 est non nulle
Y2*?Y3*?
PourX1=0 et X2=4, X3=0 et X4=1 (1):0+0x4+0+2x1=2
donc la contrainte(1) est saturée
18
Solution primal/ dual
Théorème des écarts complémentaires
• Exemple
Min C= 2Y1+5Y2+3Y3
Max Z= 10X1+15X2+60X3+95X4
𝑌1 ≥ 10
𝑋1 + 𝑋3 + 2𝑋4 ≤ 2 (1)
𝑌2 ≥ 15
𝑋2 + 2𝑋3 + 𝑋4 ≤ 5(2)
D 𝑌1 + 2𝑌2 + 𝑌3 ≥ 60
P 𝑋3 + 2𝑋4 ≤ 3(3) 2𝑌1 + 𝑌2 + 2𝑌3 ≥ 95
𝑋1 ≥ 0, 𝑋2, 𝑋3 ≥ 0, 𝑋4 ≥ 0 𝑌1 ≥ 0, 𝑌2 ≥ 0, 𝑌3 ≥ 0
Y1* est non nulle
PourX1=0 et X2=4, X3=0 et X4=1
Y2* est non nulle
(2): 0+4+0x2+1=5
Y3*?
donc la contrainte(2) est saturée
19
Solution primal/ dual
Théorème des écarts complémentaires
• Exemple
Max Z= 10X1+15X2+60X3+95X4 Min C= 2Y1+5Y2+3Y3
𝑋1 + 𝑋3 + 2𝑋4 ≤ 2 (1) 𝑌1 ≥ 10
𝑋2 + 2𝑋3 + 𝑋4 ≤ 5(2) 𝑌2 ≥ 15
P 𝑋3 + 2𝑋4 ≤ 3(3) D 𝑌1 + 2𝑌2 + 𝑌3 ≥ 60
𝑋1 ≥ 0, 𝑋2, 𝑋3 ≥ 0, 𝑋4 ≥ 0 2𝑌1 + 𝑌2 + 2𝑌3 ≥ 95
𝑌1 ≥ 0, 𝑌2 ≥ 0, 𝑌3 ≥ 0
PourX1=0 et X2=4, X3=0 et X4=1 Y1* ≠0
(3):0+0x4+0+2x1= 2<3 Y2* ≠0
donc la contrainte (3) est non saturée Y3* =0
20
Solution primal/ dual
Théorème des écarts complémentaires
• Exemple
Max Z= 10X1+15X2+60X3+95X4 Min C= 2Y1+5Y2+3Y3
𝑌1 ≥ 10 (𝐼)
𝑋1 + 𝑋3 + 2𝑋4 ≤ 2 (1) 𝑌2 ≥ 15(𝐼𝐼)
𝑋2 + 2𝑋3 + 𝑋4 ≤ 5(2) D 𝑌1 + 2𝑌2 + 𝑌3 ≥ 60(𝐼𝐼𝐼)
P 𝑋3 + 2𝑋4 ≤ 3(3) 2𝑌1 + 𝑌2 + 2𝑌3 ≥ 95(𝐼𝑉)
𝑌1 ≥ 0, 𝑌2 ≥ 0, 𝑌3 ≥ 0
𝑋1 ≥ 0, 𝑋2, 𝑋3 ≥ 0, 𝑋4 ≥ 0
Y*1≠0,Y*2≠0 et Y*3=0
𝑋1∗ =0, 𝑿∗𝟐 =4, 𝑋3∗ =0, 𝑿∗𝟒 =1
X2 ≠ 0 (II) est saturée
( IV) est saturée
X4 ≠ 0
21
Solution primal/ dual
Théorème des écarts complémentaires
• Exemple
Max Z= 10X1+15X2+60X3+95X4 Min C= 2Y1+5Y2+3Y3
𝑌1 ≥ 10 (𝐼)
𝑋1 + 𝑋3 + 2𝑋4 ≤ 2 (1)
𝑌2 = 15(𝐼𝐼)
𝑋2 + 2𝑋3 + 𝑋4 ≤ 5(2)
D 𝑌1 + 2𝑌2 + 𝑌3 ≥ 60(𝐼𝐼𝐼)
P 𝑋3 + 2𝑋4 ≤ 3(3)
2𝑌1 + 𝑌2 = 95(𝐼𝑉)
𝑋1 ≥ 0, 𝑋2, 𝑋3 ≥ 0, 𝑋4 ≥ 0 𝑌1 ≥ 0, 𝑌2 ≥ 0, 𝑌3 ≥ 0
𝑋1∗ =0, 𝑋2∗ =4, 𝑋3∗ =0, 𝑋4∗ =1 et (II) Saturée :Y*2=15
𝑍 ∗ =155 (IV) Saturée: 2Y1+Y2=95 donc Y*1=40
D’où 𝑌1∗ =40, 𝑌2∗ =15, 𝑌3∗ =0 et 𝐶 ∗ =155
22
Solution primal/ dual
Lecture de la solution à partir du tableau optimal (Problème de maximisation)
Primal (respectivement Dual) Dual (respectivement Primal)
Fonction objectif Z* C*=Z*
Pour les coef de la ligne objectif
La variable d’écart e* Variable de décision y*=-e*
La variable de décision X* Variable d’écart S*=-X*
23
Solution primal/ dual
Lecture de la solution à partir du tableau optimal
Primal Dual
Min C= 2X1+5X2+3X3 Max Z= 10Y1+15Y2+60Y3+95Y4
SC SC
𝑋1 ≥ 10 𝑌1 + 𝑌3 + 2𝑌4 ≤ 2 (1)
𝑋2 ≥ 15 𝑌2 + 2𝑌3 + 𝑌4 ≤ 5(2)
S 𝑋1 + 2𝑋2 + 𝑋3 ≥ 60 𝑌3 + 2𝑌4 ≤ 3(3)
2𝑋1 + 𝑋2 + 2𝑋3 ≥ 95 𝑌1 ≥ 0, 𝑌2, 𝑌3 ≥ 0, 𝑌4 ≥ 0
𝑋1 ≥ 0, 𝑋2 ≥ 0, 𝑋3 ≥ 0
24
Solution primal/ dual
Lecture de la solution à partir du tableau optimal
Solution de dual
Dernier tableau de simplexe après trois itérations
Y1 Y2 Y3 Y4 e1 e2 e3
Y4 -1/2 0 1/2 1 1/2 0 0 1
Y2 -1/2 1 3/2 0 -1/2 1 0 4
e3 1 0 0 0 -1 0 1 1
FO -30 0 -10 0 -40 -15 0 -155
• La solution optimale de dual est Z*=155, Y1*=0, Y2*=4, Y3*=0,
Y4*=1,e1*=0,e2*=0,e3*=1
• La solution optimale du primal est C*=155, X1*=40, X2*=15,X3*=0,
S1*=30, S2*=0, S3*=10, S4*=0
25
Solution primal/ dual
Liens entre primal et dual
• Si le problème primal admet une solution optimale alors le dual
admet aussi une solution optimale et on a : F(x*)=G(y*)
• Un PL peut :
- Avoir au moins une solution optimale
- Être non bornée et l’optimum est infini
- Sans solution réalisable
26
Solution primal/ dual
Liens entre primal et dual
Dual
Solution optimale Solution Pas de solutions
infinie
Solution optimale X Impossible Impossible
Primal
Solution infinie Impossible Impossible X
Pas de solutions Impossible X X
27
