Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

NOM : Messaoudi PRENOM : Anis GROUPE : 3 SPECIALITÉ : ASR Travail TOP à remettr

NOM : Messaoudi PRENOM : Anis GROUPE : 3 SPECIALITÉ : ASR Travail TOP à remettre Question 1 : Z(x) = 19x1 + 27x2 + 23x3  max sc : 4x1 − 3x2 + x3 ≤ 7 2x1 + x2 − 2x3 ≤ 11 −3x1 + 4x2 + 2x3 ≤ 5 xj ≥ 0 et entier, j = 1, 2, 3 Le problème est converti en forme canonique en ajoutant des variables de marge, de surplus et artificielles selon les besoins. 1. Comme la contrainte 1 est de type '≤' nous devons ajouter la variable d'écart S1 2. Comme la contrainte 2 est de type '≤' nous devons ajouter la variable d'écart S2 3. Comme la contrainte 3 est de type '≤' nous devons ajouter la variable d'écart S3 On obtient : Z(x) = 19x1 + 27x2 + 23x3 + 0.S1 + 0.S2 + 0.s3  max sc : 4x1 − 3x2 + x3 + S1 = 7 2x1 + x2 − 2x3 + S2 = 11 −3x1 + 4x2 + 2x3 + S3 = 5 xj ≥ 0 et entier, j = 1, 2, 3 S1,S2,S3 ≥ 0 Itération 1 Cj 19 27 23 0 0 0 B CB XB x1 x2 x3 S1 S2 S3 xB/x2 S1 0 7 4 -3 1 1 0 0 --- S2 0 11 2 1 -2 0 1 0 11 S3 0 5 -3 4 2 0 0 1 1.25→ Z=0 Zj 0 0 0 0 0 0 Zj-Cj -19 -27↑ -23 0 0 0  Le minimum négatif Zj-Cj est de -27 et son indice de colonne est 2. Ainsi, la variable entrante est x2.  La variable de base de départ est S3.  L'élément pivot est 4.  Entrée = x2, Départ = S3, Élément clé = 4 Iteration 2 Cj 19 27 23 0 0 0 B CB XB x1 x2 x3 S1 S2 S3 xB/x1 S1 0 10.75 1.75 0 2.5 1 0 0.75 6.1429 S2 0 9.75 2.75 0 -2.5 0 1 -0.25 3.5455→ x2 27 1.25 -0.75 1 0.5 0 0 0.25 --- Z=33.75 Zj -20.25 27 13.5 0 0 6.75 Zj-Cj -39.25↑ 0 -9.5 0 0 6.75  Le minimum négatif Zj-Cj est de -39,25 et son indice de colonne est 1. Ainsi, la variable entrante est x1.  La variable de base de départ est S2.  L'élément pivot est de 2,75.  Entrée = x1, Départ = S2, Élément clé = 2,75 Iteration-3 Cj 19 27 23 0 0 0 B CB XB x1 x2 x3 S1 S2 S3 XB/X3 S1 0 4.5455 0 0 4.0909 1 -0.6364 0.9091 1.11 → x1 19 3.5455 1 0 -0.9091 0 0.3636 -0.0909 --- x2 27 3.9091 0 1 -0.1818 0 0.2727 0.1818 --- Z=172.909 1 Zj 19 27 -22.1818 0 14.2727 3.1818 Zj-Cj 0 0 -45.1818↑ 0 14.2727 3.1818  Le minimum négatif Zj-Cj est de -45,1818 et son indice de colonne est 3. Ainsi, la variable entrante est x3.  La variable de base de départ est S1.  L'élément pivot est le 4.0909.  Entrée = x3, Départ = S1, Élément clé = 4.0909 Iteration 4 Cj 19 27 23 0 0 0 B CB XB x1 x2 x3 S1 S2 S3 x3 23 1.1111 0 0 1 0.2444 -0.1556 0.2222 x1 19 4.5556 1 0 0 0.2222 0.2222 0.1111 x2 27 4.1111 0 1 0 0.0444 0.2444 0.2222 Z=223.1111 Zj 19 27 23 11.0444 7.2444 13.2222 Zj-Cj 0 0 0 11.0444 7.2444 13.2222 Puisque tout Zj-Cj sont supérieurs à 0, la solution optimale est obtenue avec la valeur des variables comme : x1 = 41 9 , x2 = 37 9 , x3 = 10 9 Zmax = 2008 9 = 223,11111 Puisque tout Zj-Cj≥0 Par conséquent, la solution optimale non entière est obtenue avec la valeur des variables comme : x1 = 4.5556, x2 = 4.1111, x3 = 1.1111 Zmax = 223,11111 ZL : obtenu par les valeurs de solution arrondies  Dans le sous-problème A, X1(=4.5556) doit être une valeur entière, donc deux nouvelles contraintes sont créées, X1≤4 et X1≥5.  Dans le sous-problème B, X2(=3.5) doit être une valeur entière, donc deux nouvelles contraintes sont créées, X2≤3 et X2??4  Dans le sous-problème E, X3(=0,5) doit être une valeur entière, donc deux nouvelles contraintes sont créées, X3≤0 et X3≥1 x1=4.55, x2=4.11, x3=1.11 ZA=223.1111 ZL=207 x1=4, x2=3.5, x3=1.5 ZB=205 ZL=180 Solution irréalisable x1=4, x2=4,x3=0.5 ZE=195.5 ZL=184 x1=3.545, x2=3,x3=1.8182 ZD=190.1818 ZL=161 Solution irréalisable Solution irréalisable x1≤4 x1≥5 x2≤3 x2≥4 x3≤0 x3≥1 A B C D E F G Question 2 : En utilisant les valeurs obtenus dans la dernière du simplex de la question 1 Et on cotinue Pour obtenir la solution à valeur entière, nous procédons à la construction de la coupe fractionnaire de Gomory, à l'aide de ligne x1 comme suit : 4.5556= 1x1 + 0.2222×S1 + 0.2222×S2 + 0.1111×S3 (4+0.5556) = (1+0)x1 + (0+0.2222)×S1 + (0+0.2222)×S2 + (0+0.1111)×S3 La coupe fractionnaire deviendra -0.5556 = Sg1 -0.2222×S1 -0.2222×S2 -0.1111×S3 → (coupe 1) Ajout de cette contrainte supplémentaire au bas de la table simplex optimale. Le nouveau tableau ainsi obtenu est :  Le xB négatif minimum est de -0,5556 et son indice de ligne est de 4. Ainsi, la variable de base de départ est Sg1.  Le rapport négatif maximum est de -32,6 et son index de colonne est de 5. Ainsi, la variable d'entrée est S2.  L'élément pivot est de -0.2222.  Entrée =S2, Départ =Sg1, Élément clé =-0.2222 Puisque tout Zj-Cj≥0 Par conséquent, la solution optimale non entière est obtenue avec la valeur des variables comme : x1 = 4, x2 = 3,5 , x3 = 1,5 Zmax=205 Pour obtenir la solution à valeur entière, nous procédons à la construction de la coupe fractionnaire de Gomory, à l'aide de ligne x3 comme suit : 1.5= 1x3 + 0.4S1 + 0.3S3 -0.7Sg1 (1+0,5) = (1+0)x3 + (0+0,4)S1 + (0+0,3)S3 + (-1+0,3)Sg1 La coupe fractionnaire deviendra -0,5 = Sg2 -0,4S1 -0,3S3 -0,3Sg1 → (coupe 2) Ajout de cette contrainte supplémentaire au bas de la table simplex optimale. Le nouveau tableau ainsi obtenu est :  Le xB négatif minimum est de -0,5 et son indice de ligne est de 5. Ainsi, la variable de base de départ est Sg2.  Le rapport négatif maximum est de -9,5 et son index de colonne est de 4. Ainsi, la variable d'entrée est S1.  L'élément pivot est de -0,4.  Entrée = S1, Départ = Sg2 , Élément clé = -0,4 Puisque tout Zj-Cj ≥ 0 Par conséquent, la solution optimale non entière est obtenue avec la valeur des variables comme : x1 = 4, x2 = 3.75, x3 = 1 Zmax = 200,25 Pour obtenir la solution à valeur entière, nous procédons à la construction de la coupe fractionnaire de Gomory, à l'aide de ligne x2 comme suit : 3,75 = x2 + 0,25S3 + 1,25Sg1 -0,5Sg2 (3+0,75) = (1+0)x2 + (0+0,25)S3 + (1+0,25)Sg1 + (-1+0,5)Sg2 La coupe fractionnaire deviendra -0,75 = Sg3 -0,25S3 -0,25Sg1 -0,5Sg2→ (Coupe 3) Ajout de cette contrainte supplémentaire au bas de la table simplex optimale. Le nouveau tableau ainsi obtenu est :  Le xB négatif minimum est de -0,75 et son indice de ligne est de 6. Ainsi, la variable de base de départ est Sg3.  Le rapport négatif maximum est de -19 et son index de colonne est de 8. Ainsi, la variable d'entrée est Sg2.  L'élément pivot est de -0,5.  Entrée = Sg2 , Départ = Sg3 , Élément clé = -0,5  Le xB négatif minimum est de -2,5 et son indice de ligne est de 4. Ainsi, la variable de base de départ est S2.  Le rapport négatif maximum est de -1.3333 et son index de colonne est 6. Ainsi, la variable d'entrée est S3.  L'élément pivot est de -1,5.  Entrée = S3, Départ = S2, Élément clé =-1,5 Puisque tout Zj-Cj ≥ 0 Par conséquent, la solution optimale non entière est obtenue avec la valeur des variables comme : x1 = 4, x2 = 3.6667, x3 = 0.3333 Max Z=182,6667 Pour obtenir la solution à valeur entière, nous procédons à la construction de la coupe fractionnaire de Gomory, à l'aide de la ligne x2 comme suit : 3.6667 = 1x2 + 0.3333S2 -0.6667Sg1 + 0.6667Sg3 (3+0.6667) = (1+0)x2 + (0+0.3333)S2 + (-1+0.3333)Sg1 + (0+0.6667)Sg3 La coupe fractionnaire deviendra -0.6667 = Sg4 -0.3333S2 -0.3333Sg1 -0.6667Sg3 → (Coupe 4) Ajout de cette contrainte supplémentaire au bas de la table simplex optimale. Le nouveau tableau ainsi obtenu est :  Le xB négatif minimum est de -0,6667 et son indice de ligne est de 7. Ainsi, la variable de base de départ est Sg4.  Le rapport négatif maximum est de -4 et son index de colonne est de 5. Ainsi, la variable d'entrée est S2.  L'élément pivot est de -0.3333.  Entrée = S2, Départ = Sg4, Élément clé =-0.3333  Le xB négatif minimum est -1 et son indice de uploads/Voyage/ devoirtop-solution.pdf