1 Exercice corrigé Branch and Bound

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.

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.

branch and bound séparation et évaluation

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).

branch and bound séparation et évaluation

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

branch and bound séparation et évaluation

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.

branch and bound séparation et évaluation

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 :

branch and bound séparation et évaluation

Résolvons le problème à gauche :

branch and bound séparation et évaluation

Cela donne pour solution x_1=2.5, x_2=5 et Z=1000.

Résolvons le système à droite :

branch and bound séparation et évaluation

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.

branch and bound séparation et évaluation

Mettons à jour notre graphe avec les nouvelles UB et LB de chaque système obtenu.

branch and bound séparation et évaluation

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.

branch and bound séparation et évaluation

En prenant le nœud 4, nous avons le programme linéaire suivant :

branch and bound séparation et évaluation

La solution au problème est x_1=1 et x_2=6.17 avec Z=1025.

Le deuxième problème est :

branch and bound séparation et évaluation

Ce problème n’admet pas de solution (première contrainte est violée). Nous avons donc le graphe de solution suivant :

branch and bound séparation et évaluation

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.

branch and bound séparation et évaluation

Après résolution des deux programmes linéaires aux nœuds 6 et 7, nous obtenons les résultats suivants :

branch and bound séparation et évaluation

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.

branch and bound séparation et évaluation

Partager