Corrigé série dualité et analyse de sensibilité

Exercice 1 :

Le directeur de production d’une entreprise qui consiste à fabriquer des climatiseurs

cherche à planifier les opérations de la semaine prochaine, qui sera consacrée aux trois types
C1, C2 et C3. La fabrication des types de climatiseurs nécessite deux composantes principales
les moteurs « M » et les plaques rafraîchissantes « R » ainsi qu’à des heures de main d’œuvre
« MOD ».

Pour sa planification, le directeur utilise un modèle linéaire continu, dont les variables de
décision xj (1 ≤ j ≤ 3) sont définies ainsi :

xj = nombre d’unités de Cj fabriquées durant la semaine.

Le tableau suivant résume les informations de planification auquel se consacre le directeur :

Produits M R MOD Profit (en dinars

(en unité) (en unité) (en heures) par unité)
C1 1 1 8 70
C2 1 2 12 100
C3 1 4 14 140
Disponibilités 240 400 2400
Le directeur doit respecter une commande lui imposant de fabriquer 230 climatiseurs de
types C1 et C2 par semaine.

Pour maximiser son profit le directeur utilise le modèle suivant:

Max Z = 70 x1 + 100 x2 + 140 x3

Sous les contraintes :
x1 + x2 + x3 ≤ 240
x1 + 2 x2 + 4 x3 ≤ 400
8 x1 + 12 x2 + 14 x3 ≤ 2400
x1 + x2 ≥ 230
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0
Et voici le tableau final du simplexe :

Ci Base x1 x2 x3 e1 e2 e3 e4 Valeur
bi
70 x1 1 0 0 7/2 0 -1/4 1/2 125
140 x3 0 0 1 1 0 0 1 10
100 x2 0 1 0 -7/2 0 1/4 -3/2 105
0 e2 0 0 0 -1/2 1 -1/4 -3/2 25
cj 70 100 140 0 0 0 0
zj 70 100 140 35 0 15/2 25 Z=20650
cj-zj 0 0 0 -35 0 -15/2 -25
 1. Décrire le plan optimal de production associé au tableau du simplexe.
x1 =125 ; x2 =105 ; x3 =10 ; Z=20650. e2=25, e1= e3= e4=0,

2. Donner le dual associé à ce problème, et en déduire le tableau optimal du dual.

Primal Dual
Max Z = 70 x1 + 100 x2 + 140 x3 Min W = 240y1 +400y2+2400y3 -230y4
Sous les contraintes :
x1 + x2 + x3 +e1=240 y1 S/C
x1 + 2 x2 + 4 x3 ≤ 400 y2 x1 y1+ y2 +8 y3 - y4-S1+A1=70
8 x1 + 12 x2 + 14 x3 ≤ 2400 y3 x2 y1+ 2y2 +12 y3 - y4≥100
x1 + x2 ≥ 230 -x1 - x2 ≤ -230 y4 x3 y1+ 4y2 +14 y3 ≥140

x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0 y1 ≥ 0 ; y2 ≥ 0 ; y3 ≥ 0 ; y4 ≥ 0

Base x1 S1 x2 S2 x3 S3 e1 y1 e2 y2 e3 y3 e4 y4 Valeur

x1 S1 1 0 0 7/2 0 -1/4 1/2 125

x3 S3 0 0 1 1 0 0 1 10
x2 S2 0 1 0 -7/2 0 1/4 -3/2 105
e2 y2 0 0 0 -1/2 1 -1/4 -3/2 25
cj 70 100 140 0 0 0 0
zj 70 100 140 35 0 15/2 25 Z=20650
cj-zj 0 0 0 -35 0 -15/2 -25

Tableau optimal du dual

ci y1 y2 y3 y4 S1 S2 S3 Valeur
Base
240 y1 1 1/2 0 0 -7/2 7/2 -1 35
2400 y3 0 1/4 1 0 1/4 -1/4 0 15/2
-230 y4 0 3/2 0 1 -1/2 3/2 -1 25
cj 240 400 2400 -230 0 0 0
zj 240 375 2400 -230 -125 -105 -10 W=20650
cj-zj 0 25 0 0 125 105 10
 3. Donner l’intervalle de variation du coefficient de x2 dans la fonction objective
permettant de maintenir la structure de la solution de base optimale.
Max Z = 70 x1 + (100+a) x2 + 140 x3

ci Base x1 x2 x3 e1 e2 e3 e4 Valeur
70 x1 1 0 0 7/2 0 -1/4 1/2 125
140 x3 0 0 1 1 0 0 1 10
100+ a x2 0 1 0 -7/2 0 1/4 -3/2 105
0 e2 0 0 0 -1/2 1 -1/4 -3/2 25
cj 70 100+a 140 0 0 0 0
zj 70 100+a 140 35-(7/2)a 0 15/2+(1/4)a 25-(3/2)a 20650+105*a
cj-zj 0 0 0 -35+(7/2)a 0 -15/2-(1/4)a -25+(3/2)a

-35+(7/2)a ≤0 sig (7/2)a ≤35 sig a≤35/(7/2) sig a≤10

-15/2-(1/4)a≤0 -15/2 ≤+(1/4)a (-15/2)/(1/4) ≤a -30 ≤a
-25+(3/2)a≤0 (3/2)a≤25 a≤50/3
-30 10 50/3

-30≤a≤10
100-30≤c2≤100+10
70≤c2≤110 tant que c2 est compris entre 70 et 110 la base ne change pas
4. Que deviendraient le plan optimal et le profit Z associé ? Si le profit des climatiseurs
de type C3 serait de 110 au lieu de 140.
VE
Max Z = 70 x1 + 100x2 + 110 x3

ci Base x1 x2 x3 e1 e2 e3 e4 bi RT=
VS bi
aij de VE> 0
70 x1 1 0 0 7/2 0 -1/4 1/2 125 125/(1/2)=250
110 x3 0 0 1 1 0 0 1 10 10 (min)
100 x2 0 1 0 -7/2 0 1/4 -3/2 105 -----
0 e2 0 0 0 -1/2 1 -1/4 -3/2 25 -----
cj 70 100 110 0 0 0 0
zj 70 100 110 5 0 15/2 -5
cj-zj 0 0 0 -5 0 -(15/2) 5

ci Base x1 x2 x3 e1 e2 e3 e4 Valeur bi
70 x1 1 0 -1/2 3 0 -1/4 0 120
0 e4 0 0 1 1 0 0 1 10
100 x2 0 1 3/2 -2 0 1/4 0 120
0 e2 0 0 3/2 1 1 -1/4 0 40
cj 70 100 110 0 0 0 0
zj 70 100 115 10 0 15/2 0 Z=8400+12000=20400
 cj-zj 0 0 -5 -10 0 -(15/2)
x1 =120 ; x2 =1020 ; x3 =0 ; Z=20400. e2=40, e1= e3= 0, e4=10

5. Que deviendraient le plan optimal et le profit Z associé ? Si le second membre de la

quatrième contrainte est égal à 210 au lieu de 230.
x1 + x2 ≥ 210

Max Z = 70 x1 + 100 x2 + 140 x3

Sous les contraintes :
x1 + x2 + x3 ≤ 240
x1 + 2 x2 + 4 x3 ≤ 400
8 x1 + 12 x2 + 14 x3 ≤ 2400
x1 + x2 ≥ 210=230-20
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0

Ci Base x1 x2 x3 e1 e2 e3 e4 Valeur
70 x1 1 0 0 7/2 0 -1/4 1/2 125
140 x3 0 0 1 1 0 0 1 10
100 x2 0 1 0 -7/2 0 1/4 -3/2 105
0 e2 0 0 0 -1/2 1 -1/4 -3/2 25
cj 70 100 140 0 0 0 0
zj 70 100 140 35 0 15/2 25 20650
cj-zj 0 0 0 -35 0 -15/2 -25
230 210 variation =-20

Nouvelle Valeur
125+(-1/2)(-20)=135
10+(-1)(-20)=30
105+(+3/2)(-20)=75
25+3/2(-20)=-5
 VE

Ci Base x1 x2 x3 e1 e2 e3 e4 bi
70 x1 1 0 0 7/2 0 -1/4 1/2 135
140 x3 0 0 1 1 0 0 1 30
VS 100 x2 0 1 0 -7/2 0 1/4 -3/2 75
0 e2 0 0 0 -1/2 1 -1/4 -3/2 -5
cj 70 100 140 0 0 0 0
zj 70 100 140 35 0 15/2 25 20650
cj-zj 0 0 0 -35 0 -15/2 -25
RT= (-35)/(-1/2)=70 30 50/3
cj−zj (min)
aij de VS< 0

Ci Base x1 x2 x3 e1 e2 e3 e4 bi
70 x1 1 0 0 10/3 1/3 -1/3 0 400/3
140 x3 0 0 1 2/3 2/3 -1/6 0 80/3
100 x2 0 1 0 -3 -1 ½ 0 80
0 e4 0 0 0 1/3 -2/3 1/6 1 10/3
cj 70 100 140 0 0 0 0
zj 70 100 140 80/3 50/3 10/3 0
cj-zj 0 0 0 -80/3 -50/3 -10/3 0

Exercice 2 :

Le directeur de production d’une entreprise cherche à planifier les opérations de la semaine

prochaine, qui sera consacrée à la fabrication de trois produits P 1, P2 et P3. La fabrication de ces
produits nécessite l’utilisation de deux matières premières E 1 et E2.

Pour sa planification, le directeur utilise un modèle linéaire continu, dont les variables de
décision xi (1 ≤ i ≤ 4) sont définies ainsi :

xi = nombre d’unités de Pi fabriquées durant la semaine.

Le tableau suivant résume les informations de planification auquel se consacre le directeur :

Produits E1 E2 Profit (en dinars

par unité)
P1 5 2 3
P2 2 3 4
P3 4 2 5
Disponibilités (en Kg) 240 180
Le directeur doit respecter une commande lui imposant de fabriquer 60 unités de P 1, P2 et P3
par semaine.
Pour maximiser son profit le directeur utilise le modèle suivant:

Max Z = 3 x1 + 4 x2 + 5 x3
Sous les contraintes :
5 x1 + 2 x2 + 4 x3 ≤ 240
2 x1 + 3 x2 + 2 x3 ≤ 180
x1 + x2 + x3 ≥ 60
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0
Et voici le tableau final du simplexe :

Ci Base x1 x2 x3 e1 e2 e3 Valeur
4 x2 -1/4 1 0 -1/4 1/2 0 30
5 x3 11/8 0 1 3/8 -1/4 0 45
0 e3 1/8 0 0 1/8 1/4 1 15
cj 3 4 5 0 0 0
zj 47/8 4 5 7/8 3/4 0 Z=345
cj-zj -23/8 0 0 -7/8 -3/4 0

1. Décrire le plan optimal de production associé au tableau du simplexe.

x1= 0 ;x2 30 ; x3 = 45 ; e3=15 :e1=e2=0 ; Z= 345 .
2. Donner le dual associé à ce problème, et en déduire le tableau optimal du dual.

Primal Dual
Max Z = 3 x1 + 4 x2 + 5 x3 Min W = 240y1 +180y2-60y3
Sous les contraintes :
5 x1 + 2 x2 + 4 x3 ≤ 240 S/C
2 x1 + 3 x2 + 2 x3 ≤ 180 x1 5y1+ 2y2 - y3 ≥3
x1 + x2 + x3 ≥ 60 - x1 - x2- x3 ≤ -60
x2 2y1+ 3y2 - y3 ≥4
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0
x3 4 y1+ 2y2 - y3 ≥5

y1 ≥ 0 ; y2 ≥ 0 ; y3 ≥ 0

Ci Base S1 x1 S2 x2 S3 x3 y1 e1 Y2 e 2 Y3 e 3 Valeur
4 S2x2 -1/4 1 0 -1/4 1/2 0 30
5 S3x3 11/8 0 1 3/8 -1/4 0 45
0 Y3 e 3 1/8 0 0 1/8 1/4 1 15
cj 3 4 5 0 0 0
zj 47/8 4 5 7/8 3/4 0
cj-zj -23/8 0 0 -7/8 -3/4 0 345

Tableau optimal dual

Ci Base y1 y2 y3 s1 s2 s3 Valeur
0 S1 0 0 -1/8 1 1/4 -11/8 23/8
240 Y1 1 0 -1/8 0 1/4 -3/8 7/8
180 Y2 0 1 -1/4 0 -1/2 1/4 3/4
cj 240 180 -60 0 0 0
 zj 240 180 -75 0 -30 -45
cj-zj 0 0 15 0 30 45

3. Que seraient le plan optimal et le profit Z associé ? Si la quantité disponible de la matière

première E1 diminue de 160 unités.
5 x1 + 2 x2 + 4 x3 ≤ 80=240-160 variation=( -160)
Ci Base x1 x2 x3 e1 e2 e3 Valeur
4 x2 -1/4 1 0 -1/4 1/2 0 30
5 x3 11/8 0 1 3/8 -1/4 0 45
0 e3 1/8 0 0 1/8 1/4 1 15
cj 3 4 5 0 0 0
zj 47/8 4 5 7/8 3/4 0
cj-zj -23/8 0 0 -7/8 -3/4 0 345

Valeur
30+(-1/4)*(-160)=70
45+(3/8)*(-160)=-15
15+(1/8)*(-160)=-5

Ci Base x1 x2 x3 e1 ( VE)e2 e3 Valeur

4 x2 -1/4 1 0 -1/4 1/2 0 70
5 (VS)x3 11/8 0 1 3/8 -1/4 0 -15
0 e3 1/8 0 0 1/8 1/4 1 -5
cj 3 4 5 0 0 0
zj 47/8 4 5 7/8 3/4 0
cj-zj -23/8 0 0 -7/8 -3/4 0 345
RT (-3/4)/(-1/4)
=3

Ci Base x1 x2 x3 e1 e2 e3 Valeur
4 x2 5/2 1 2 1/2 0 0 125/2
0 e2 -11/2 0 -4 -3/2 1 0 60
0 e3 3/2 0 1 1/2 0 1 -20
cj 3 4 5 0 0 0
zj 10 4 8 2 0 0 250
cj-zj -7 0 -3 -2 0 0

Le tableau n’est pas optimal pas de solution

 4. Donner l’intervalle de variation du coefficient de x 3 dans la fonction objective tout en gardant
la structure de la solution de base optimale.
Max Z = 3 x1 + 4 x2 + (5+a) x3

Ci Base x1 x2 x3 e1 e2 e3 Valeur
4 x2 -1/4 1 0 -1/4 1/2 0 30
5+a x3 11/8 0 1 3/8 -1/4 0 45
0 e3 1/8 0 0 1/8 1/4 1 15
cj 3 4 5+a 0 0 0
zj 47/8+(11/8)a 4 5+a 7/8+(3/8)a ¾-(1/4)a 0
cj-zj -23/8-(11/8)a 0 0 -7/8-(3/8)a -3/4+(1/4)a 0 345

-23/8-(11/8)a≤0 signifie -23/11≤a

-7/8-(3/8)a≤0 signifie -7/3≤a
-3/4+(1/4)a≤0 signifie a≤3
D’où -23/11≤ a≤3

5. Quelle serait la solution optimale, si le profit de P1 est de 6 dinars au lieu de 3 dinars?

Max Z = 6 x1 + 4 x2 + 5 x3

Ci Base (VE)x1 x2 x3 e1 e2 e3 Valeur RT

4 x2 -1/4 1 0 -1/4 1/2 0 30 ---
5 (Vs)x3 11/8 0 1 3/8 -1/4 0 45 360/11
0 e3 1/8 0 0 1/8 1/4 1 15 120
cj 6 4 5 0 0 0
zj 47/8 4 5 7/8 3/4 0
cj-zj 1/8 0 0 -7/8 -3/4 0 345

Ci Base x1 x2 x3 e1 e2 e3 Valeur
4 x2 0 1 2/11 -2/11 5/11 0 420/11
6 x1 1 0 8/11 3/11 -2/11 0 360/11
0 e3 0 0 -1/11 -1/11 5/22 1 120/11
cj 6 4 5 0 0 0
zj 6 4 56/11 10/11 8/11 0
cj-zj 0 0 -1/11 -10/11 -8/11 0

x1= 360/11 ;x2 =420/1130 ; x3 = 0 ; e3=120/11 :e1=e2=0