Théorie des écarts complémentaires
Contrainte primale saturée → variable associée non nulle
Variable primale ˃ 0 → contrainte associée saturée
La solution primale est optimale si la solution duale satisfait les contraintes
(solution duale réalisable pour les contraintes)
Solution :
1)
Max f(X) = 60 X1 + 20 X2 + 40 X3
4X1 + 2 X2 + X3 ≤ 6000
2 X1 + 0,5 X2 + 3 X3 ≤ 4000
X1 + X2 + X3 ≤ 2500
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0
2)
La forme standard
Max f(X) = 60 X1 + 20 X2 + 40 X3
4X1 + 2 X2 + X3 + e1 = 6000
2 X1 + 0,5 X2 + 3 X3 + e2 = 4000
X1 + X2 + X3 + e3 = 2500
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0 ; e1 ≥ 0 ; e2 ≥ 0 ; e3 ≥ 0
Variables hors bases
X1 = 0 ; X2 = 0 ; X3 = 0
Variables de bases
e1 = 6000 ; e2 = 4000 ; e3 = 2500
VB X1 X2 X3 e1 e2 e3 B R
e1 4 2 1 1 0 0 6000 1500
e2 2 0,5 3 0 1 0 4000 2000
e3 1 1 1 0 0 1 2500 2500
C 60 20 40 0 0 0 0 -
Variable entrante = X1 ; Variable sortante = e1 ; Pivot = 4
1ére transformation :
L1 L1
L’1 = =
𝑃𝑖𝑣𝑜𝑡 4
2
L’2 = L2 – Lp = L2 – 0,5 Lp
4
1
L’3 = L3 – Lp = L3 – 0,25 Lp
4
60
C’ = C – Lp = C – 15 Lp
4
VB X1 X2 X3 e1 e2 e3 B R
X1 1 0,5 0,25 0,25 0 0 1500 6000
e2 0 -0,5 2,5 -0,5 1 0 1000 400
e3 0 0,5 0,75 -0,25 0 1 1000 4000
3
C 0 -10 25 -15 0 0 -90000 -
Variable entrante = X3 ; Variable sortante = e2 ; Pivot = 2,5
2éme transformation :
0,25
L’’1 = L’1 – Lp = L’1 – 0,1 Lp
2,5
L’2 L’2
L’’2 = =
𝑃𝑖𝑣𝑜𝑡 2,5
0,75
L’’3 = L’3 – Lp = L’3 – 0,3 Lp
2,5
25
C’’ = C’ – Lp = C’ – 10 Lp
2,5
VB X1 X2 X3 e1 e2 e3 B
X1 1 0,55 0 0,3 -0,1 0 1400
X3 0 -0,2 1 -0,2 0,4 0 400
e3 0 0,65 0 -0,1 -0,3 1 700
C 0 -5 0 -10 -10 0 -100000
Variables de bases
X1 = 1400 ; X3 = 400 ; e3 = 700
Variables hors bases
X2 = 0 ; e1 = 0 ; e2 = 0
Max f(X) = 60 X1 + 20 X2 + 40 X3
Max f(X) = (60 × 1400) + (20 × 0) + (40 × 400)
Max f(X) = 100000
Pour maximiser le bénéfice, la société a intérêt de produire 1400 unités de A et
400 unités de C.
3) 1400 ; 0 ; 400
Max f(X) = 60 X1 + 20 X2 + 40 X3
4 X1 + 2 X2 + X3 ≤ 6000
2 X1 + 0,5 X2 + 3 X3 ≤ 4000
X1 + X2 + X3 ≤ 2500
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0
Programme dual
Min f (U ; V ; W) = 6000 U + 4000 V + 2500 W
4 U + 2 V + W ≥ 60
2 U + 0,5 V + W ≥ 20
U + 3 V + W ≥ 40
U≥ 0 ; V≥ 0; W ≥ 0
Pour (U ; V ; W) = (10 ; 10 ; 0)
Fonction objective :
Min f (U ; V ; W) = 6000 U + 4000 V + 2500 W = (6000 × 10) + (4000 × 10) +
(2500 × 0) = 100000
Vérification des contraintes :
4 U + 2 V + W = (4 × 10) + (2 × 10) + 0 = 60
La première contrainte est saturée alors la variable associée X1 est non nulle
2 U + 0,5 V + W = (2 × 10) + (0,5 × 10) + 0 = 25
La deuxième contrainte n’est pas saturée alors la variable associée X2 = 0
U + 3 V + W = 10 + (3 × 10) + 0 = 40
La troisième contrainte est saturée alors la variable associée X3 est non nulle
Vérification des variables :
U = 10 ˃ 0 alors la première contrainte associée est saturée
V = 10 ˃ 0 alors la deuxième contrainte associée est saturée
W = 0 alors la troisième contrainte associée n’est pas saturée
Donc :
4X1 + X3 = 6000
2 X1 + 3 X3 = 4000
On obtient :
X3 = 6000 – 4 X1
2 X1 + 3 × (6000 – 4 X1) = 4000 ↔ 2 X1 + 18000 – 12 X1 = 4000
Ce qui donne
X3 = 6000 – 4 X1
-10 X1 + 18000 = 4000 ↔ 10 X1 = 14000
Par conséquent :
X1 = 1400
X3 = 6000 – 4 X1 = 6000 – (4 × 1400) = 400
X2 = 0
Vérification de la solution optimale
Max f(X) = 60 X1 + 20 X2 + 40 X3 = (60 × 1400) + (20 × 0) + (40 × 400) = 100000
4X1 + 2 X2 + X3 = (4 × 1400) + (2 × 0) + 400 = 6000
La première contrainte est satisfaite
2 X1 + 0,5 X2 + 3 X3 = (2 × 1400) + (0,5 × 0) + (3 × 400) = 4000
La deuxième contrainte est satisfaite
X1 + X2 + X3 = 1400 + 0 + 400 = 1800
La troisième contrainte est satisfaite
Alors la solution proposée est une solution optimale
Solution :
Programme dual
Min f (Y) = 200 Y1 + 400 Y2 + 600 Y3 + 800 Y4
Y1 + 2 Y2 + Y4 ≥ 2
Y1 + 2 Y3 + Y4 ≥ 6
Y2 + Y3 + Y4 ≥ 4
Y1 ≥ 0 ; Y2 ≥ 0 ; Y3 ≥ 0 ; Y4 ≥ 0
Pour (X1 ; X2 ; X3) = (0 ; 200 ; 200)
Fonction objective :
Max f(X) = 2 X1 + 6 X2 + 4 X3 = (2 × 0) + (6 × 200) + (4 × 200) = 2000
Vérification des contraintes :
X1 + X2 = 0 + 200 = 200
La première contrainte est saturée alors la variable associée Y 1 est non nulle
2 X1 + X3 = (2 × 0) + 200 = 200
La deuxième contrainte n’est pas saturée alors la variable associée Y 2 = 0
2 X2 + X3 = (2 × 200) + 200 = 600
La troisième contrainte est saturée alors la variable associée Y 3 est non nulle
X1 + X2 + X3 = 0 + 200 + 200 = 400
La quatrième contrainte n’est pas saturée alors la variable associée Y 4 = 0
Vérification des variables :
X1 = 0 alors la première contrainte associée n’est pas saturée
X2 = 200 ˃ 0 alors la deuxième contrainte associée est saturée
X3 = 200 ˃ 0 alors la troisième contrainte associée est saturée
Donc :
Y1 + 2 Y3 = 6
Y3 = 4
Cela implique :
Y1 = 6 – 2 Y3 = 6 – (2 × 4) = -2
Y2 = 0
Y3 = 4
Y4 = 0
Par conséquent :
Min f (Y) = 200 Y1 + 400 Y2 + 600 Y3 + 800 Y4
Min f (Y) = (200 × -2) + (400 × 0) + (600 × 4) + (800 × 0) = 2000
Y1 + 2 Y2 + Y4 = -2 + (2 × 0) + 0 = -2
La première contrainte n’est pas satisfaite
La solution proposée n’est pas une solution optimale
Pour (X1 ; X2 ; X3) = (50 ; 150 ; 300)
Fonction objective :
Max f(X) = 2 X1 + 6 X2 + 4 X3 = (2 × 50) + (6 × 150) + (4 × 300) = 2200
Vérification des contraintes :
X1 + X2 = 50 + 150 = 200
La première contrainte est saturée alors la variable associée Y1 est non nulle
2 X1 + X3 = (2 × 50) + 300 = 400
La deuxième contrainte est saturée alors la variable associée Y2 est non nulle
2 X2 + X3 = (2 × 150) + 300 = 600
La troisième contrainte est saturée alors la variable associée Y 3 est non nulle
X1 + X2 + X3 = 50 + 150 + 300 = 500
La quatrième contrainte n’est pas saturée alors la variable associée Y 4 = 0
Vérification des variables :
X1 = 50 ˃ 0 alors la première contrainte associée est saturée
X2 = 150 ˃ 0 alors la deuxième contrainte associée est saturée
X3 = 300 ˃ 0 alors la troisième contrainte associée est saturée
Donc :
Y1 + 2 Y2 = 2
Y1 + 2 Y3 = 6
Y2 + Y3 = 4
Cela implique :
Y1 = 2 – 2 Y2
Y1 + 2 Y3 = 6 ↔ 2 – 2 Y2 + 2 Y3 = 6 ↔ -2 Y2 + 2 Y3 = 4
Y2 + Y3 = 4 ↔ Y2 = 4 – Y3
D’où :
Y1 = 2 – 2 Y2
-2 Y2 + 2 Y3 = 4 ↔ -2 × (4 – Y3) + 2 Y3 = 4 ↔ -8 + 2 Y3 + 2 Y3 = 4 ↔ 4 Y3 = 12
Y2 = 4 – Y3
Ce qui donne :
Y3 = 3
Y2 = 4 – Y3 = 4 – 3 = 1
Y1 = 2 – 2 Y2 = 2 – (2 × 1) = 0
Y4 = 0
Vérification de la solution optimale
Min f (Y) = 200 Y1 + 400 Y2 + 600 Y3 + 800 Y4
Min f (Y) = (200 × 0) + (400 × 1) + (600 × 3) + (800 × 0) = 2200
Y1 + 2 Y2 + Y4 = 0 + (2 × 1) + 0 = 2
La première contrainte est satisfaite
Y1 + 2 Y3 + Y4 = 0 + (2 × 3) + 0 = 6
La deuxième contrainte est satisfaite
Y2 + Y3 + Y4 = 1 + 3 + 0 = 4
La troisième contrainte est satisfaite
Alors la solution proposée est une solution optimale
