Résolution d'un problème de Simplexe
Traduit par
ScribdTranslationsRésolution d'un problème de Simplexe
Traduit par
ScribdTranslationsEXERCICE 1 :
Résoudre par méthode du Simplexe (ou ses variantes).
MÉTHODE SIMPLEX : Réécrivons le problème, nous avons
Min z−160x−120x−280x+0s+0s+
1 2 3 M
1 A+M
2 A 1 2
s . a 2 x 1 +x 2+ 4x3−s1 +0+ A 1+ 0=1
2x1+ 2 x 2 +2 x 3 +0−s 2 +0+ A2 =3/2
x 1, x 2, x 3, s 1 , s2A
, 1 , A2≥0
TABLE SIMPLEX :
Itération Cj 160 120 280 0 0 M M MINIMUM
1
B CB XB x1 x2 x3 S1 S2 A1 Un2 XB/x_3
A1 M 1 2 1 4 -1 0 1 0 ¼=0,25
A2 M 1,5 2 2 2 0 -1 0 1 1.5/2=0.75
Z=2,5M Zj 4M 3M 6M -M -M M M
Z j−Cj 4M- 3M- 6M- -M -M 0 0
160 120 280
Dans la colonne majeure, on observe la valeur 4, cette ligne sera appelée ligne 1
Les opérations qui sont effectuées sont :
F1 F1
→ F1F 2− →F2
4 2
Ainsi nous avons
Itération Cj 160 120 280 0 0 M MINIMUM
2
B CB XB x1 XB/x_3x2 x3 S1 S 2A 2
x3 280 0,25 0,5 0,25 1 -0,25 0,25/0,25=1
A2 M 1 1 1,5 0 0,5 -1 1/1.5=0.666
Z=M+70 Zj M+140 1,5M+70 280 0,5M - M
-70 M
Z j−C j M-20 1.6M-50 0 0,5 M 0
-70 M
La valeur la plus grande est 1,5 et en divisant XB/x_2, nous devons avoir que le minimum est dans la ligne 2 alors le
le pivot est 1,5, les opérations effectuées sont :
F2 F1 F2
→ F 2, − →F1
1,5 0,25
Itération Cj 160 120 280 0 0 MINIMUM
3
B CB XB x1 x2 x3 S1 S2 XB/x_1
x3280 0.08 0,33 0 1 -0,33
3
x2 120 0,66 0.66 1 0 0.33 0.6667 0.6667/0.6667=1
7
Z=103,3 Zj 173,3 120 280 -53,3 -33,3
Z j−C j 13.33 0 0 -53,3 -33,3
Dans ce cas, la valeur la plus petite est 0,25, donc la ligne 1 est le pivot avec la variable x_1, les
les opérations qui sont effectuées sont :
F1 F2 F1
→ F 2, − → F2
0,33 0,66 0,33
Nous avons
Itération Cj 160 120 280 0 0
n4
B CB XB x1 x2 x3 S1 S2
x1 160 0,25 1 0 3 -1 0,5
x2 120 0,5 0 1 -2 1 -1
Z=100 Zj 160 120 240 -40 -40
Z j−Cj 0 0 -40 -40 -40
PuisqueZ−C≤0
j j nous avons le processus itératif pour et nous obtenons déjà les solutions
Par conséquent, on parvient à la solution optimale avec les valeurs des variables suivantes :
x=0,25x=0,5=0
1 2 3 MinZ=10
EXERCICE 2 :
= 0,6 1+ 2,6 2 + 2,63+ 1,6 4
. .
1+ 2 2+ 0,2 3+ 0,5 4≤ 252
1+ 2= 200
1, 2 , 3, 4≥ 0
Formulez le problème dual et résolvez-le, puis effectuez une analyse de sensibilité complète.
Solution :
Transformons le problème primal en problème dual.
En primal, il y a 4 variables et 2 contraintes, donc en dual il doit y avoir 4 contraintes et
2 variables. En primal, le coefficient de la fonction objectif c1 = 0,6, c2 = 2,6, c3 = 2,6, c4 =
1.6 devient des constantes du côté droit en dual. En primal, les constantes du côté
droit b1 = 252, b2 = 200 se convertissent en coefficient de fonction objectif en dual. Dans
primal, la fonction objective est maximisée, donc dans la fonction objective duale doit
être en train de minimiser. Soient y1, y2 les variables duales. Étant donné que la deuxième contrainte dans le
primal est l'égalité, la variable duale correspondante y2 n'aura pas de restrictions dans le
signe.
dans W = 252y1+ 200y2
. .
y1+ y2≥ 0,6
2y1+ y2≥ 2.6
0,2y1≥ 2.6
0,5y1≥ 1,6
y1≥ 0, y2sans restrictions
MÉTHODE SIMPLEX : Réécrivons le problème.
MinW=252y1+200y2+0 s 1+ 0 s 2+ 0 s 3+ 0 s 4 +MA1+M A2 + MA3+ MA4
s. .
y 1 + y 2−s1+ A 1=0,6
2y1+ y 2−s 2 + A 2=2,6
0,2y1−s3 + Un 3=2 . 6
0,5y1−s 4 + Un 4=1 . 6
y 1,y2, s 1 , s2, s 3 , s4, A1A
, 2 , A3A
, 4≥ 0
Étant donné que y2 n'a pas de restrictions de signe, introduisez les variables non
négatives y2′,y2′′ de sorte que y2=y2′-y2′′;y2′,y2′′≥0. Alors nous avons
MinW=252y1+200y2+0 s 1+ 0 s 2+0 s 3+ 0 s 4 + MA1+ M A2 +MA3+ MA4
s. .
y 1 + y ' 2− y''2−s 1 + A1 =0,6
2y1+ y ' 2− y' 2−s2+ A 2=2.6
0,2y1−s3 + A 3=2,6
0,5y1−s 4 + A 4=1.6
y 1,y'2,y' '2, s 1, s 2 , s3, s 4A
, 1 , A2A
, 3A
, 4≥ 0
TABLEAU SIMPLEX :
Itération Cj 252 200 -200 0 0 0 0 M M M M MINIMUM
1
B C BX B y1 y2y''2S1S2S3S4Un1A2A3A 4 XB/y_1
Un1 M 0,6 1 1 -1 -1 0 0 0 1 0 0 0 0,6/1=0,6
A2 M 2.6 2 1 -1 0 -1 0 0 0 1 0 0 2,6/2=1,3
Un3 M 2,6 0,2 0 0 0 0 -1 0 0 0 1 0 2,6/0,2=13
A4 M 1,6 0,5 0 0 0 0 0 -1 0 0 0 1 1,6/0,5=3,2
Z=2,5M Z j 3,7 M -2M -M -M -M -M M M M M
Z j−C 3,7 M 2 M
- -M -M -M -M 0 0 0 0
-252 - 2M
200 +20
0
EXERCICE 3 :
Une entreprise fabrique deux produits à partir de plaques de plastique : des boîtes de rangement
aliments dans des conteneurs réfrigérés et des tubes pour systèmes de réfrigération, que
ils fournissent comme avantage 3 000 et 4 000 pesos par unité élaborée, respectivement.
La fabrication d'une boîte nécessite deux plaques et chaque tube trois plaques. Votre fournisseur
il livre 1 200 plaques par jour. La chaîne de production peut fonctionner
ininterrompu chaque jour et produire 100 boîtes toutes les 6 heures ou 100 tubes toutes les 4 heures.
Supposons que la demande des deux produits soit illimitée.