Recherche Opérationnelle
Correction de la Série No4
Dualité et Analyse de sensibilité
Exercice n° 1.
1- Dual
2- Résolution
d
Cj
VB
S’1
d
Zj
0
-M
A2
-30
y1
-1
1
10
+
y2
3
2
-10
-
y2
-3
-2
20
y3
2
-3
Cj
d- Zj
d
𝑀 − 30 2𝑀 + 10 −2𝑀 − 10 −3𝑀 + 20
d
Cj
d VB
Zj
10
y2
+
-M A2
Cj
d- Zj
d
-30
y1
1
3
5
3
−
5
3
𝑀 −
80
3
10
+
y2
-10
-
y2
1 −1
0
0
0
0
20
y3
2
3
13
3
−
−
13
3
𝑀 +
40
3
−
2
3
𝑀 −
10
3
0
S’1
-M
A2
1
0
0
0
S’1
1
3
2
3
−
0
1
0
-M
A2
0
1
0
b
1
3
Q
1
3
3
2
b
1
3
7
3
Q
−1
7
5
1
12312312313 -301020 . - 3 21 2 33 0, 0Maxyyyscyyyyyyyy12232'12231122321223'12 -30101020 . - 3 3 21 2 2 33 0, 0, 0, 0 0, 0MaxyyyyMAscyyyySyyyyAyyyySA'''11221, 23LLLLL''''''''2211231, 53LLLLL
Recherche Opérationnelle
d
Cj
VB
y2
+
d
Zj
10
-30
y1
Cj
d- Zj
d
-30
y1
10
+
y2
0
1
0
1
0
0
-10
-
y2
−1
0
0
−
20
y3
1
5
13
5
−56
−
0
S’1
1
5
2
5
−14
−
-M
A2
1
5
3
5
−𝑀 + 16
b
4
5
7
5
34
y2
+ =
+ - y2
- = 0 ; y2 = y2
4
, y2
5
, y2 = 4
y1 = 7
, y3 = 0, S’1 = 0, Z= -34
5
5
- = 4
5
3- Résultat du Primal :
x1 = - S’1 = 14
Z = -34
Z = x1+3x2 x2 = (Z – x1) / 3 = -16
⇨ x1 = 14, x2 = -16, Z = -34
4- Variation de C’1
C’1 varie de -30 à -30+∆
d
Cj
VB
y2
+
d
Zj
10
-30+∆
y1
Cj
d- Zj
d
-30+∆ 10
y1
y2
+ y2
-10
-
0
1
0
1
0
0
-1
0
0
20
−
y3
1
5
13
5
13
5
−
−56 +
0
S’1
1
5
2
5
−
-M
A2
1
5
3
5
b
4
5
7
5
∆
−56
−𝑀 + 16 −
3
5
∆
−56 +
13
5
∆ ≤ 0 → ∆ ≤
280
13
−14 + 2
5
∆ ≤ 0 → ∆ ≤ 35 ⇒ Δ ≤ 280
13
⇓⇒ 𝐶1
′ ≤ −
110
13
2
Recherche Opérationnelle
5- Variation de b’1
b’1 varie de 1 à 1+∆
d
Cj
VB
y2
+
d
Zj
10
-30
y1
Cj
d- Zj
d
-30
y1
10
+
y2
0
1
0
1
0
0
-10
-
y2
−1
0
0
−
20
y3
1
5
13
5
−56
−
0
S’1
1
5
2
5
−14
−
-M
A2
1
5
3
5
−𝑀 + 16
4
5
7
5
9
2
+
1
5
2
5
∆ ≥ 0 → ∆ ≥ −4
4
5
7
7
5
2
⇒ − 4 ≤ Δ ≤ 7
2
∆ ≥ 0 → ∆ ≤
−
⇓⇒ −3 ≤ 𝑏1
′ ≤
Exercice n° 2.
1- Dual
2- Résolution
Cj
d
VB
S’1
S’2
d
Zj
d
0
0
Cj
d- Zj
30
y1
1
1
30
40
y2
1
2
40
0
S’1
1
0
0
0
S’2
0
1
0
b
20
24
Q
20
12
b
1
5
2
5
+
−
∆
∆
3
'12121212 3040 . 20 224 0, 0MaxZyyscyyyyyy'121211221212 3040 . '20 2'24 0, 0, '0, '0MaxZyyscyySyySyySS'''22112, 2LLLLL
Recherche Opérationnelle
Cj
d
VB
Zj
d
0 S’1
40 y2
Cj
d- Zj
d
30 40 0
0
y1
1
2
1
2
10
y2
S’1
0
1
0
1
0
0
−
S’2
1
2
1
Publicité
2
−20
b
8
12
Q
16
24
Cj
d
VB
Zj
d
30 40 0
0
y1
y2
S’1
S’2
b
30 y1
1
0
2
-1 16
40 y2
d- Zj
Cj
d
0
1
-1 1
4
0
0 -20 -10 -640
Y1=16, Y2=4, S’1=0, S’2=0, Z= 640
3- Résultat du Primal :
x1 = - S’1 = 20
x2 = - S’2 = 10
Z = 640
x1 = 20, x2 = 10, Z = 640
4- Variation de C’1
C’2 varie de 40 à 40+∆
Cj
d
VB
Zj
d
30 y1
40+∆ y2
30 40+∆
0
0
y1
y2
S’1
S’2
b
1
0
2
-1 16
0
1
-1 1
4
Cj
d- Zj
d
0
0 -20+∆ -10-∆
-20+∆ ≤ 0 ∆ ≤ 20
-10-∆≤0∆≥-10
⇓⇒ 30 ≤ 𝐶2
′ ≤ 60
⇒ -10 ≤ Δ ≤ 20
4
''''''''1122112, 2LLLLL
5- Variation de b’2
b’2 varie de 24 à 24+∆
Cj
d
VB
Zj
d
Recherche Opérationnelle
30 40 0
0
y1
y2
S’1
30 y1
1
0
2
b
S’2
-1 16-∆
40 y2
0
1
-1 1 4+∆
Cj
d- Zj
d
0
0 -20 -10
16-∆ ≥ 0 ∆ ≤ 16
4+∆ ≥ 0
∆ ≥ -4
⇒ − 4 ≤ Δ ≤ 16
⇓⇒ 20 ≤ 𝑏1
′ ≤ 40
Exercice n° 3.
𝑀𝑎𝑥 𝑧 = −2𝑥1 + 𝑥2 − 2𝑥3
𝑠. 𝑐. 𝑥1 + 𝑥2 + 𝑥3 ≤ 3
𝑥2 + 𝑥3 ≥ 2
2𝑥1 + 𝑥3 = 1
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
𝑀𝑎𝑥 𝑧 = −2𝑥1 + 𝑥2 − 2𝑥3
𝑠. 𝑐. 𝑥1 + 𝑥2 + 𝑥3 ≤ 3
-𝑥2 − 𝑥3 ≤ −2
2𝑥1 + 𝑥3 = 1
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
1- Le programme Dual
𝑀𝑖𝑛 𝑧′ = 3𝑦1 − 2𝑦2 + 𝑦3
𝑠. 𝑐. 𝑦1 + 2𝑦3 ≥ −2
𝑦1 − 𝑦2 ≥ 1
𝑦1 − 𝑦2 + 𝑦3 ≥ −2
𝑦1 ≥ 0, 𝑦2 ≥ 0
𝑀𝑖𝑛 𝑧′ = 3𝑦1 − 2𝑦2 + 𝑦3
𝑠. 𝑐. -𝑦1 − 2𝑦3 ≤ 2
𝑦1 − 𝑦2 ≥ 1
5
Recherche Opérationnelle
-𝑦1 + 𝑦2 − 𝑦3 ≤ 2
𝑦1 ≥ 0, 𝑦2 ≥ 0
𝑀𝑖𝑛 𝑧′ = 3𝑦1 − 2𝑦2 + 𝑦3
𝑠. 𝑐. -𝑦1 − 2𝑦3 ≤ 2
𝑦1 − 𝑦2 ≥ 1
-𝑦1 + 𝑦2 − 𝑦3 ≤ 2
𝑦1 ≥ 0, 𝑦2 ≥ 0
2- Résolution
𝑀𝑖𝑛 𝑧′ = 3𝑦1 − 2𝑦2 + 𝑦3
𝑠. 𝑐. -𝑦1 − 2𝑦3
−
+ − 𝑦3
+ + 2𝑦3
− ≤ 2
𝑦1 − 𝑦2 ≥ 1
-𝑦1 + 𝑦2 − 𝑦3
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
+ + 𝑦3
− ≤ 2
+ ≥ 0, 𝑦3
− ≥ 0
𝑀𝑖𝑛 𝑧′ = 3𝑦1 − 2𝑦2 + 𝑦3
+ + 2𝑦3
𝑠. 𝑐. -𝑦1 − 2𝑦3
− + 𝑀𝐴2
+ − 𝑦3
− + 𝑆′1 = 2
𝑦1 − 𝑦2 − 𝑆′2 + 𝐴2 = 1
− + 𝑆′3 = 2
− ≥ 0
+ ≥ 0, 𝑦3
𝑆′1 ≥ 0, 𝑆′2 ≥ 0, 𝐴2 ≥ 0
+ + 𝑦3
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
-𝑦1 + 𝑦2 − 𝑦3
𝑀𝑎𝑥 𝑧′ = −3𝑦1 + 2𝑦2 − 𝑦3
+ + 2𝑦3
𝑠. 𝑐. -𝑦1 − 2𝑦3
+ + 𝑦3
− + 𝑆′1 = 2
− − 𝑀𝐴2
𝑦1 − 𝑦2 − 𝑆′2 + 𝐴2 = 1
-𝑦1 + 𝑦2 − 𝑦3
+ + 𝑦3
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
− + 𝑆′3 = 2
− ≥ 0
+ ≥ 0, 𝑦3
𝑆′1 ≥ 0, 𝑆′2 ≥ 0, 𝐴2 ≥ 0
-3
y1
-1
1
-1
M-3
2
y2
0
-1
1
2-M
-1
+
y3
-2
0
-1
-1
1
-
y3
2
0
1
1
0
S’1
1
0
0
0
0
S’2
0
-1
0
-M
0
S’3
0
0
1
0
-M
A2
0
1
0
0
b Q
-2
2
1
1
-2
2
6
d
Cj
VB
S’1
A2
S’3
d
d- Zj
d
Zj
0
-M
0
Cj
333 0, 0 33Soityyyavecyy
Recherche Opérationnelle
′ =
𝐿2
𝐿2
1
= 𝐿2, 𝐿1
′ = 𝐿1 + 𝐿2
′ , 𝐿3
′
′ = 𝐿3 + 𝐿2
d
Cj
VB
S’1
y1
S’3
d
d- Zj
d
Zj
0
-3
0
Cj
d
Cj
VB
-
y3
y1
S’3
d
d- Zj
d
Zj
1
-3
0
Cj
-3
y1
0
1
0
0
2
y2
-1
-1
0
-1
-1
+
y3
-2
0
-1
-1
1
-
y3
2
0
1
1
0
S’1
1
0
0
0
0
S’2
-1
-1
-1
-3
0
S’3
0
0
1
0
-M
A2
1
1
1
-M+3
b
3
1
3
Q
5/2
∞
3
-3
y1
0
1
0
0
2
y2
-1/2
-1
1/2
-1/2
-1
+
y3
-1
0
0
0
1
-
y3
1
0
0
0
0
S’1
1/2
0
-1/2
-1/2
0
S’2
-1/2
-1
-1/2
-5/2
0
S’3
0
0
1
0
-M
A2
1/2
1
1/2
-M+5/2
b
3/2
1
3/2
3/2
y3
+ = 0, y3
- = 3/2 ; y3 = y3
+ - y3
- = -3/2
y1 = 1, y2 = 0, y3 = -3/2, Z = 3/2
3- Déduction de la solution du primal (P)
x1 = - S’1 = 1/2
x2 = - S’1 = 5/2
x3 = - S’1 = 0
Z = 3/2
x1 = 1/2, x2 = 5/2, x3 = 0, Z = 3/2
4- Variation de C’1
C’1 varie de -3 à -3+∆
d
Cj
VB
-
y3
y1
S’3
d
d
Zj
1
-3+∆
0
Cj
d- Zj
-3+∆
y1
0
1
0
0
2
y2
-1/2
-1
1/2
-1/2+∆
-1
y3
-1
0
0
Publicité
0
1
-
+ y3
1
0
0
0
0
S’1
1/2
0
-1/2
-1/2
0
S’2
-1/2
-1
-1/2
-5/2+∆
0
S’3
0
0
1
0
-M
A2
1/2
1
1/2
-M+5/2-∆
b
3/2
1
3/2
3/2
−
1
2
+ 𝛥 ≤ 0 → Δ ≤
1
2
7
'''''''''''1122331, , 2LLLLLLL
Recherche Opérationnelle
− 5
2
+ 𝛥 ≤ 0 → Δ ≤ 5
2
⇒ 𝛥 ≤
1
2
⇓⇒ 𝐶1
′ ≤ −
5
2
5- Variation de b’2
b’2 varie de 1 à 1+∆
-3
y1
0
1
0
0
2
y2
-1/2
-1
1/2
-1/2
-1
+
y3
-1
0
0
0
1
-
y3
1
0
0
0
0
S’1
1/2
0
-1/2
-1/2
0
S’2
-1/2
-1
-1/2
-5/2
0
S’3
0
0
1
0
-M
A2
1/2
1
1/2
-M+5/2
b
3/2-1/2∆
1-∆
3/2-1/2∆
3/2
d
Cj
d VB
Zj
-
1
y3
y1
-3
0
S’3
d
d- Zj
Cj
1
2
−
3
2
𝛥 ≥ 0 → Δ ≤ 3
1 − 𝛥 ≥ 0 → Δ ≤ 1
− 1
2
𝛥 ≥ 0 → Δ ≤ 3
2
3
⇒ Δ ≤ 1
⇓⇒ 𝑏2
′ ≤ 2
Exercice n° 4.
Primal
𝑀ax 𝑧 = 20𝑥1 + 35𝑥2 − 30𝑥3
𝑠. 𝑐. 𝑥1 − 2𝑥2 + 3𝑥3 ≥ 20
2𝑥1 − 5𝑥3 ≤ 30
𝑥2 + 𝑥3 = 10
𝑥1 ≥ 0, 𝑥2 ≥ 0
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 35𝑥2 − 30𝑥3
1) Programme Dual
𝑠. 𝑐. − 𝑥1 + 2𝑥2 − 3𝑥3 ≤ −20
2𝑥1 − 5𝑥3 ≤ 30
𝑥2 + 𝑥3 = 10
𝑥1 ≥ 0, 𝑥2 ≥ 0
𝑀𝑖𝑛 𝑧 = −20𝑦1 + 30𝑦2 + 10𝑦3
𝑠. 𝑐. − 𝑦1 + 2𝑦2 ≥ 20
2𝑦1 + 𝑦3 ≥ 35
− 3𝑦1 − 5𝑦2 + 𝑦3 = −30
𝑦1 ≥ 0, 𝑦2 ≥ 0
8
Recherche Opérationnelle
𝑀𝑖𝑛 𝑧 = −20𝑦1 + 30𝑦2 + 10𝑦3
𝑠. 𝑐. − 𝑦1 + 2𝑦2 ≥ 20
2𝑦1 + 𝑦3 ≥ 35
3𝑦1 + 5𝑦2 − 𝑦3 = 30
𝑦1 ≥ 0, 𝑦2 ≥ 0
2) Résolution
𝑀𝑖𝑛 𝑧 = −20𝑦1 + 30𝑦2 + 10𝑦3
−
+ − 10𝑦3
𝑠. 𝑐. − 𝑦1 + 2𝑦2 ≥ 20
+ − 𝑦3
2𝑦1 + 𝑦3
3𝑦1 + 5𝑦2 − 𝑦3
− ≥ 35
+ + 𝑦3
− = 30
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
+ ≥ 0, 𝑦3
− ≥ 0
− + MA1 + MA2 + MA3
+ − 10𝑦3
𝑀𝑖𝑛 𝑧 = −20𝑦1 + 30𝑦2 + 10𝑦3
𝑠. 𝑐. − 𝑦1 + 2𝑦2 − S'1 + 𝐴1 = 20
+ − 𝑦3
2𝑦1 + 𝑦3
3𝑦1 + 5𝑦2 − 𝑦3
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
− − S'2 + 𝐴2 = 35
− + 𝐴3 = 30
+ + 𝑦3
+ ≥ 0, 𝑦3
+ + 10𝑦3
𝑀ax 𝑧 = 20𝑦1 − 30𝑦2 − 10𝑦3
𝑠. 𝑐. − 𝑦1 + 2𝑦2 − S'1 + 𝐴1 = 20
+ − 𝑦3
2𝑦1 + 𝑦3
3𝑦1 + 5𝑦2 − 𝑦3
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
− − S'2 + 𝐴2 = 35
− + 𝐴3 = 30
+ + 𝑦3
+ ≥ 0, 𝑦3
d
Cj
d VB
Zj
-M A1
-M A2
-M A3
d
d- Zj
Cj
20
y1
-1
2
3
-30
y2
2
0
5
4M+20 7M-30
-10
+
y3
0
1
-1
-10
d
Cj
d VB
Zj
-M A1
-M A2
-30 y2
−
20
y1
11
5
2
3
5
Cj
d- Zj
d −
1
5
𝑀 + 38 0
-30
y2
0
0
1
-10
+
y3
2
5
1
1
5
−
𝑀 − 16 −
7
5
7
5
10
-
y3
0
-1
1
10
−
10
-
y3
2
5
−1
1
5
− ≥ 0,S'1 ≥ 0,S'2 ≥ 0, 𝐴1 ≥ 0, 𝐴2 ≥ 0, 𝐴3 ≥ 0
− − MA1 − MA2 − MA3
− ≥ 0,S'1 ≥ 0,S'2 ≥ 0, 𝐴1 ≥ 0, 𝐴2 ≥ 0, 𝐴3 ≥ 0
0
S’1
-1
0
0
-M
0
-M
S’2 A1
1
0
0
-1
0
0
0
-M
-M
A2
0
1
0
0
-M
A3
0
0
1
0
b
20
35
30
Q
10
∞
6
0
-M -M
0
S’1 S’2 A1 A2
−1 0
1 0
0 −1 0 1
0
0
0 0
𝑀 + 16 −𝑀 −𝑀 0 0 −
b Q
8 20
35 35
6 −30
−
-M
A3
2
5
0
1
5
7
5
𝑀 + 6
9
''''3311322, 2, 5LLLLLLL 333 0, 0 33Soityyyavecyy'''''''''''''1122133151, , 25LLLLLLLL
Recherche Opérationnelle
−
20
y1
11
2
15
2
1
2
−
d
Cj
d VB
Zj
-10 y3
+
-M A2
-30
y2
Cj
d- Zj
d 15
2
-30
y2
-10 10
-
+ y3
y3
0
0
1
1 −1
0
0
0
0
0
0
5
2
0
S’2
0
−1
0
−
0
S’1
5
2
5
2
1
2
−
𝑀 − 40 −𝑀 −
-M
A1
5
2
5
2
1
2
−
𝑀 + 40
7
2
-M
-M
A2 A3
0
b
−1 20 −
Q
40
11
1
0
0
1
0
15
2
10 −20
−10
𝑀 − 50 0
d 20
Cj
d VB y1
Zj
-30
y2
-10 10
-
y3
y3
Publicité
+
-10 y3
+
20
y1
-30
y2
Cj
d- Zj
d
0
1
0
0
0
0
1
0
0
S’1
2
3
1
3
1
3
70
3
1 −1 −
−
0
0
0
0
0
−
−
0 −
−
0
S’2
11
15
2
15
1
15
20
3
-M
A1
2
3
1
3
1
3
−
-M
A2
11
15
2
15
1
15
−
-M
A3
4
15
2
15
1
15
b
31
2
11
−𝑀 +
70
3
−𝑀 +
20
3
−𝑀 −
10
3
600
−
y3
+ = 31, y3
- = 0 ; y3 = y3
+ - y3
- = 31
y1 = 2, y2 = 11, y3 = 31, Z= 600
3) Résultat du Primal
x1 = - S’1 = 70/3
x2 = - S’2 = 20/3
Z = 600
Z = 20x1+35x2-30x3 x3 = (-Z +20x1+35x2)/30 = 10/3
x1 = 70/3, x2 = 20/3, x3 = 10/3, Z = 600
4) Variation de C’1
C’1 varie de 20 à 20+∆
0
0
Cj
d VB
d 20+∆ -30 -10 10
-
+ y3
y3
y1
y2
Zj
-10 y3
+
20+∆ y1
-30
y2
0
1
0
0
0
1
1 −1
0
0
0
0
−
S’1
2
3
1
3
1
3
−
Zj
d- Cj
d
0
0
0
0 −
70
3
−
1
3∆
−
−
−
S’2
11
15
2
15
1
15
20
3
2
15∆
−
+
-M
A1
2
3
1
3
1
3
−
-M
A2
11
15
2
15
1
15
-M
−
A3
4
15
2
15
1
15
b
31
2
11
70
3
−𝑀 +
+
1
3∆
20
3
−𝑀 +
−
2
15∆
−𝑀 −
10
3
−
2
15∆
600
10
'''''''''''''''''''''221123322111, , 1522LLLLLLLL
Recherche Opérationnelle
𝛥 ≤ 0 → Δ ≥ −70
−70
3
−20
−
1
3
+ 2
15
3
𝛥 ≤ 0 → Δ ≤ 50
⇒ −70 ≤ 𝛥1 ≤ 50
⇓⇒ −50 ≤ 𝐶1
′ ≤ 70
5) Variation de b’1
b’1 varie de 20 à 20+∆
d 20
Cj
d VB y1
-30
y2
Zj
-10 10
-
+ y3
y3
-10 y3
+ 0
20
y1
-30
y2
Zj
d- Cj
d
1
0
0
0
0
1
0
0
S’1
2
3
1
3
1
3
70
3
1 −1 −
−
0
0
0
0
0
−
−
0 −
−
0
S’2
11
15
2
15
1
15
20
3
-M
A1
2
3
1
3
1
3
−
-M
A2
11
15
2
15
1
15
−
-M
A3
4
15
2
15
1
15
b
31 −
2 +
11 −
2
3∆
1
3∆
1
3∆
−𝑀 +
70
3
−𝑀 +
20
3
−𝑀 −
10
3
600
−
31 −
2
3
𝛥 ≥ 0 → Δ ≤
93
2
𝛥 ≥ 0 → Δ ≥ −6
2 +
1
3
11 − 1
3
𝛥 ≥ 0 → Δ ≤ 33
⇒ − 6 ≤ Δ ≤ 33
⇓⇒ 14 ≤ 𝑏1
′ ≤ 53
Exercice n° 5.
Primal
𝑀𝑖𝑛 𝑧 = −5𝑥1 + 4𝑥2 + 10𝑥3
𝑠. 𝑐. 2𝑥1 + 𝑥3 ≥ 30
𝑥2 − 𝑥3 ≤ 20
− 5𝑥1 + 2𝑥2 + 𝑥3 = 40
𝑥1 ≥ 0, 𝑥2 ≥ 0 𝑀𝑖𝑛 𝑧 = −5𝑥1 + 4𝑥2 + 10𝑥3
𝑠. 𝑐. 2𝑥1 + 𝑥3 ≥ 30
− 𝑥2 + 𝑥3 ≥ −20
− 5𝑥1 + 2𝑥2 + 𝑥3 = 40
𝑥1 ≥ 0, 𝑥2 ≥ 0
11
Recherche Opérationnelle
1) Dual
𝑀𝑎𝑥 30𝑦1 − 20𝑦2 + 40𝑦3
𝑠. 𝑐. 2𝑦1 − 5𝑦3 ≤ −5
-𝑦2 + 2𝑦3 ≤ 4
𝑦1 + 𝑦2 + 𝑦3 = 10
𝑦1 ≥ 0, 𝑦2 ≥ 0 𝑀𝑎𝑥 30𝑦1 − 20𝑦2 + 40𝑦3
𝑠. 𝑐. -2𝑦1 + 5𝑦3 ≥ 5
-𝑦2 + 2𝑦3 ≤ 4
𝑦1 + 𝑦2 + 𝑦3 = 10
𝑦1 ≥ 0, 𝑦2 ≥ 0
2) Résolution
𝑦3 = 𝑦3
+ − 𝑦3
− 𝑀𝑎𝑥 30𝑦1 − 20𝑦2 + 40(𝑦3
𝑠. 𝑐. -2𝑦1 + 5(𝑦3
-𝑦2 + 2(𝑦3
+ − 𝑦3
𝑦1 + 𝑦2 + (𝑦3
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
+ − 𝑦3
+ − 𝑦3
+ − 𝑦3
−)
−) ≥ 5
−) ≤ 4
−) = 10
+ ≥ 0, 𝑦3
− ≥ 0
𝑀𝑎𝑥 30𝑦1 − 20𝑦2 + 40𝑦3
− − 𝑀𝐴1 − 𝑀𝐴3
+ − 40𝑦3
𝑠. 𝑐. − 2𝑦1 + 5𝑦3
− 𝑦2 + 2𝑦3
𝑦1 + 𝑦2 + 𝑦3
+ − 5𝑦3
− − 𝑆′1 + 𝐴1 = 5
− + 𝑆′2 = 4
− + 𝐴3 = 10
+ − 𝑦3
+ − 𝑦3
𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3
+ ≥ 0, 𝑦3
− ≥ 0
Cj
Zj VB
-M A1
0
S2
-M A3
30
y1
-2
0
1
-20
y2
0
-1
1
40
y3
+
5
2
1
-40
y3
-
-5
-2
-1
Cj-Zj
30-M M-20
40+6M
-40-6M
-M
0
0
-M
-M
S1 S2 A1 A3
-1
0
0
0
1
0
Publicité
0
1
0
0
0
Cj
Zj VB
40
0
y3
+
S2
-M A3
30
y1
-2/5
4/5
7/5
-20
y2
0
-1
1
Cj-Zj
7/5M+46 M-20
40
y3
+
1
0
0
0
-40
y3
-
-1
0
0
0
0
S1
-1/5
2/5
1/5
1/5M+8
0
S2
0
1
0
0
-M
A1
1/5
-2/5
-1/5
-6/5M-8
0
0
1
0
-M
A3
0
0
1
0
b
5
4
Q
1
2
10
10
b
1
2
9
Q
-5/2
5/2
45/7
12
'''''11221331, 2, 5LLLLLLLL'''''''''''''22112332527, , 455LLLLLLLL
Recherche Opérationnelle
Cj 30
Zj VB y1
40 y3
+
30
y1
-M A2
Cj-Zj
0
1
0
0
-20
y2
-1/2
-5/4
11/4
11/4M+74/2
40
-40
y3
+ y3
-
1
0
0
0
-1
0
0
0
0
S1
0
½
-1/2
0
S2
½
5/4
-7/4
-M
A1
0
-1/2
½
-1/2M-15
-7/4M-115/2
-1/2M+15
-M
A3
0
0
1
0
b Q
2
5/2
-4
-2
11/2 2
Cj
30
-20
40
-40
Zj VB
y1
y2
y3
+
40
y3
+
30
y1
-20
y2
Cj - Zj
0
1
0
0
0
0
1
0
1
0
0
0
y3
-
-1
0
0
0
0
S1
−
1
11
3
11
2
11
-90/11
−
0
S2
2
11
5
11
7
11
-370/11
−
-M
A1
−
1
11
3
11
2
11
-M+90/11
-M
A3
2
11
5
11
4
11
-M-150/11
b
3
5
2
-230
y1 = 5, y2 = 2, y3 = y3
+ - y3
- = 3, Z = 230
3) Résultat du Primal
x1 =90/11, x2 = 370/11, x3 = ?, Z = 230
Z = -5x1 + 4x2 + 10x3 x3 = (230 + 5x1 - 4x2)/10 = 150/11
4) Variation de C’1
C’1 varie de 30 à 30+∆
Cj
30+∆
-20 40
-40
Zj VB
y1
y2 y3
+ y3
-
0
S1
0
S2
-M
A1
-M
A3
40
y3
+
30+∆ y1
-20
y2
Cj-Zj
0
1
0
0
0
0
1
0
1
0
0
0
-1
0
0
0
−
− 90
11
− 3
11
∆ ≤ 0 ∆ ≥ −30
−
1
11
3
11
2
11
3
11
−
2
11
5
11
7
11
5
11
−
−
370
11
∆ −
−
90
11
−
1
11
3
11
2
11
90
11
+
2
11
5
11
4
11
150
11
−
5
11
∆
3
11
∆ −𝑀 −
∆ −𝑀 +
b
3
5
2
13
'''''''''''''''''''''33113223415, , 1124LLLLLLLL
Recherche Opérationnelle
− 370
11
− 5
11
∆ ≤ 0 ∆ ≥ −74 ∆ ≥ −30 C1
′ ≥ 0
5) Variation de b’2
b’2 varie de 4 à 4+∆
Cj
30
-20 40
-40
Zj VB y1
y2
y3
+
y3
-
0
S1
40
y3
+
30
y1
-20
y2
Cj-Zj
0
1
0
0
0
0
1
0
1
0
0
0
-1
0
0
0
−
1
11
3
11
2
11
−
0
S2
2
11
5
11
7
11
−
-M
A1
−
1
11
3
11
2
11
-M
A3
2
11
5
11
4
11
b
3 +
5 +
2 −
2
11
5
11
7
11
∆
∆
∆
-90/11
-370/11
-M+90/11
-M-150/11
-230
3 + 2
11
5 + 5
11
2 − 7
11
∆ ≥ 0 ∆ ≥ − 33
2
∆ ≥ 0 ∆ ≥ −11 −11 ≤ ∆ ≤ 22
7
−7 ≤ b2
′ ≤ 50
7
∆ ≥ 0 ∆ ≤ 22
7
14