I. introduction
télécharger 296.05 Kb.
|
3 800 000 P P2 P1 P3 P4 x3=1 x3=0 x2=0 x2=1 P5 P6 x1=0 x1=1 4 200 000 P7 P8 x4=0 x4=1 x2=0 x2=1 P9 P10 x1=0 x1=1 P11 P12 3 600 000 3 800 000 2 400 000 3 000 000 Commentaires :
Solution réelle x* = (1 , 1 , 0.5 , 0) Z* = 4 400 000 Solution arrondie  = (1 , 1 , 0 , 0)  = 3 800 000On enregistre cette solution comme meilleure solution rencontrée : xbest = et Zbest = 3 800 000Nous avons 3 800 000 ≤ Zopt ≤ 4 400 000 Création de deux sous problèmes P1 (x3 = 1) et P2 (x3 = 0)
Création de deux sous problèmes P3 (x2 = 0) et P4 (x2 = 1) Note : On va appliquer comme stratégie de parcours le DFS (Parcours en profondeur)
Arrêt de cette branche, puisque nous avons obtenu une solution entière (qui n’est pas optimale < Zbest)
Création de deux sous problèmes P5 (x1 = 0) et P6 (x1 = 1)
Arrêt de cette branche, puisque nous avons obtenu une solution entière. Mise à jour de xbest et Zbest = 4 200 000
Création de deux sous problèmes P7 (x4 = 0) et P8 (x4 = 1)
Arrêt de cette branche.
Création de deux sous problèmes P9 (x2 = 0) et P10 (x2 = 1)
Arrêt de cette branche, car solution entière.
Création de deux sous problèmes P11 (x1 = 0) et P12 (x1 = 1)
Arrêt de cette branche.
La meilleure solution trouvée est donc la solution optimale (Nœud P5), ainsi Solution optimale xopt = (0 , 1 , 1 , 1) Zopt = 4 200 000 Note : Seules 7 combinaisons ont été considérées (P3 , P5 , P6 , P7 , P9 , P11 , P12), une énumération complète aurait considéré 24=16 combinaisons. II.2. La Méthode des coupes de Gomory (Gomory cutting planes) La méthode des coupes (on dit également algorithme du plan sécant ou méthode des troncatures) développé par Ralph E. Gomory (1958) fournit une méthode de résolution des PLNE. L’idée principale est d’ajouter des contraintes qui n’excluent aucun point entier admissible. La méthode consistera à ajouter de telles contraintes linéaires une par une, jusqu’à ce que la solution optimale de la relaxation soit entière. Les contraintes ajoutées sont appelées troncatures ou coupes. On peut résumer la méthode comme suit :
Notation : étant donné un réel y, [y] désigne le plus grand entier inférieur ou égal à y. Ainsi y = [y] + f , f étant la partie fractionnaire de y. Par exemple : y = 2.7 [y] = 2 f = 0.7 y = 16/5 [y] = 3 f = 1/5 y = -8.1 [y] = -9 f = 0.9 y = 2 [y] = 2 f = 0 Pour générer la nouvelle contrainte (coupe de Gomory), on remplace tout simplement tous les coefficients dans la contrainte obtenue du tableau optimal par leur partie fractionnaire correspondante (fij) et déclarons par la suite que l’expression résultante doit être à la partie fractionnaire du second membre (fi). On obtient la contrainte :  Remarque : Plusieurs autres méthodes plus ou moins sophistiquées ont été conçues pour générer des coupes permettant d’obtenir plus ou moins rapidement la solution optimale du PLNE.
On veut résoudre le PLNE suivant : Max Z = 100 x1 + 120 x2 Avec 3x1 + 4x2 4100 heures x1 + 3x2 2400 heures 2x1 + 2x2 2625 heures x1 , x2 IN où x1 et x2 représentent les quantités respectives des produits P1 et P2. En appliquant l’algorithme du simplexe, on obtient le tableau optimal suivant :
Solution optimale : x1 = 1150 unités de P1 et x2 = 325/2 = 165.5 unités de P2 Bénéfice maximum Z = 134 500 DA. Puisque la solution optimale n’est pas entière, on doit poursuivre en construisant la première contrainte additionnelle dont le but est d’éliminer la solution optimale réelle sans enlever des solutions entières réalisables. Il s’agit de créer une contrainte supplémentaire à partir d’une des contraintes du tableau optimal dont la valeur n’est pas entière (x2 ou t2). La pratique consiste à choisir la variable dont la valeur a la plus grande partie fractionnaire. Dans notre cas, la partie fractionnaire de x2 et t2 est la même soit 1/2 (0.5), on choisit arbitrairement de rendre entier x2. D’après le tableau optimal, nous avons : 0 x1 + x2 + t1 + 0 t2 – 3/2 t3 = 325/2 On sépare la partie entière et la partie fractionnaire : 0 x1 + (1+0) x2 + (1+0) t1 + 0 t2 + (-2+1/2) t3 = (162+1/2) On déduit la coupe de Gomory : 1/2 t3 1/2 Interprétation géométrique de la coupe de Gomory Puisque le PLNE ne comporte que 2 variables, on peut tracer le graphe des contraintes, puis on trace la coupe de Gomory sur le graphe. Pour cela il faut exprimer la nouvelle contrainte en fonction de x1 et x2. Ceci peut se faire car nous avons d’après la 3ème contrainte 2x1 + 2x2 + t3 = 2625, il s’ensuit que 1/2 t3 1/2 équivaut à x1+x2 1312. Coupe de Gomory x1 + x2 1312 Région de solutions réelles exclues par la coupe x2 x1 Détermination du nouveau tableau optimal L’algorithme dual simplexe permet de continuer avec le tableau optimal précédent après ajout de la coupe de Gomory. On a : 1/2 t3 1/2 1/2 t3 - t4 = 1/2 -1/2 t3 + t4 = -1/2
La solution optimale est : x1 = 1148 unités de P1 et x2 = 164 unités de P2 Bénéfice maximum Z = 134 480 DA. Puisque cette solution est entière, il n’est pas nécessaire d’effectuer une autre coupe de Gomory. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
