Cette page présente un exercice corrigé détaillé du problème de programmation linéaire résolu par l’algorithme de branch and bound.
Le propriétaire d’un atelier d’usinage envisage de s’agrandir en achetant de nouvelles machines, des presses et des tours. Le propriétaire a estimé que chaque presse achetée augmentera les profits de 100 $ par jour et que chaque tour augmentera les profits de 150 $ par jour. Le nombre de machines que le propriétaire peut acheter est limité par le coût des machines et l’espace au sol disponible dans l’atelier. Les prix d’achat de la machine et les besoins en espace sont les suivants.
Le propriétaire dispose d’un budget de 40 000 $ pour l’achat de machines et de 200 pieds carrés d’espace au sol disponible. Le propriétaire veut savoir combien de chaque type de machine acheter pour maximiser l’augmentation quotidienne des bénéfices. Résoudre ce problème.
Solution
La première étape est de modélisation le problème, il s’agit d’un problème linéaire en nombre entier (donc le simplexe ne peut pas s’appliquer).
Avec x_1 le nombre de presses et x_2 le nombre de tours.
Nous commençons la méthode branch and bound en résolvant d’abord le problème comme un modèle de programmation linéaire régulier sans restrictions sur les nombres entiers (c’est-à-dire que les restrictions sur les nombres entiers sont assouplies ou relâchées). Le modèle de programmation linéaire pour le problème et la solution relâchée optimale est
La solution optimale relâchée est x_1=2.22 et x_2=5.56 avec Z=1055.56.
La méthode de branch and bound utilise un diagramme composé de nœuds et de branches comme cadre pour le processus de solution. Le premier nœud du diagramme de branches et de liens, illustré à la figure C-1 contient la solution de programmation linéaire relâchée illustrée précédemment et la solution arrondie.
On note upper bound (borne supérieur) le résultat de la solution optimale relâchée, et lower bound (borne inférieir) le résultat de la solution optimale en nombre entier (arrondi à l’inférieur).
Premier branchement
Créez deux contraintes (ou sous-ensembles) pour éliminer la partie fractionnaire de la valeur de la solution et voir laquelle est la plus éloignée de la valeur entière arrondie (c’est-à-dire quelle variable a la plus grande partie fractionnaire en valeur absolue). La partie 0,56 de 5,56 est la plus grande partie fractionnaire ; ainsi, x_2 sera la variable sur laquelle nous allons « brancher ».
En d’autres mots, nous allons créer deux programmes linéaires alternatifs en prenant en compte respectivement que x_2 doit être inférieur ou égale à 5 d’une part; et x_2 doit être supérieur ou égale à 6 d’autre part.
Nous avons donc le branchement suivant :
Résolvons le problème à gauche :
Cela donne pour solution x_1=2.5, x_2=5 et Z=1000.
Résolvons le système à droite :
Ce système à pour solution x_1=1.33 et x_2=6, Z=1033.33
D’un point de vue pratique, nous avons coupé le domaine de définition avec la contrainte x_2=6 et avons résolution de part et d’autre de la contrainte le système linéaire relâchée.
Mettons à jour notre graphe avec les nouvelles UB et LB de chaque système obtenu.
Puisque nous n’avons pas encore de solution entière optimale et faisable, nous devons continuer à brancher (c’est-à-dire partitionner) le modèle, à partir du nœud 2 ou du nœud 3. Un coup d’œil à la figure révèle que si nous nous branchons à partir du nœud 2, le maximum la valeur qui peut éventuellement être atteinte est de 1 000 $ (la limite supérieure).
Cependant, si nous partons du nœud 3, une valeur maximale plus élevée de 1 033 $ est possible. Ainsi, nous allons bifurquer à partir du nœud 3. En général, bifurquez toujours à partir du nœud avec la borne supérieure maximale.
Deuxième branchement
Maintenant, les étapes de branchement précédemment suivies au nœud 1 sont répétées au nœud 3. Tout d’abord, la variable qui a la valeur avec la plus grande partie fractionnaire est sélectionnée. Étant donné que x_2 a une valeur entière, x_1, avec une partie fractionnaire de 0,33, est la seule variable que nous pouvons sélectionner. Ainsi, deux nouvelles contraintes sont développées à partir de x_1.
En prenant le nœud 4, nous avons le programme linéaire suivant :
La solution au problème est x_1=1 et x_2=6.17 avec Z=1025.
Le deuxième problème est :
Ce problème n’admet pas de solution (première contrainte est violée). Nous avons donc le graphe de solution suivant :
Nous n’avons toujours pas de solution en nombre entier, il faut donc continuer l’algorithme de branch and bound
Troisième branchement
Le nœud 4 possède le meilleur UB. Puisque x_2 est la seule variable qui n’est pas un nombre entier, nous allons réaliser le branchement sur cette variable.
Après résolution des deux programmes linéaires aux nœuds 6 et 7, nous obtenons les résultats suivants :
La solution au nœud 6 correspond aux critères du problème originel (c’est à dire en nombre entier). Seul le branchement en 3 et 4 ont un UB supérieur au nœud 6, cependant, le branchement qui donne le nœud 5 et 7 ne possède pas de solution réalisable. Nous concluons que la solution optimale est trouvé au nœud 6.
Récapitulatif de la méthode (en anglais)
Voici un récapitulatif en anglais de la méthode que nous venons d’employer.
