Exos Branch&Bound
Exo 1
Considérer le problème suivant :
sous les contraintes :
- -x1 + 2x2 ≤ 4
- x1 - x2 ≤ 1
- 4x1 + x2 ≤ 12
- 0 ≤ x1
- 0 ≤ x2
- x1 et x2 entiers
et répondre aux questions suivantes :
- Résoudre graphiquement.
- Résoudre la relaxation linéaire graphiquement.
- Arrondir ce maximum à l'entier le plus proche et tester sa faisabilité.
- Arrondir les coordonnées du point solution de la relaxation linéaire de toutes les façons possibles (valeurs inf/sup),
tester la faisabilité et la valeur de Z en ces points.
Exo 2
Appliquer l'algorithme de Branch&Bound binaire (BIP) pour résoudre :
- max Z = 2x1 - x2 + 5x3 - 3x4 + 4x5
sous les contraintes :
- 3x1 - 2x2 + 7x3 - 5x4 + 4x5 ≤ 6
- x1 - x2 + 2x3 - 4x4 + 2x5 ≤ 0
- toutes les variables sont binaires
Exo 3
Appliquer l'algorithme de Branch&Bound binaire (BIP) pour résoudre :
- min Z = 5x1 + 6x2 + 7x3 + 8x4 + 9x5
sous les contraintes :
- 3x1 - x2 + x3 + x4 - 2x5 ≥ 2
- x1 + 3x2 - x3 - 2x4 + x5 ≥ 0
- - x1 - x2 + 3x3 + x4 + x5 ≥ 1
- toutes les variables sont binaires
Exo 4
Appliquer l'algorithme de Branch&Bound binaire (BIP) pour résoudre :
- max Z = 5x1 + 5x2 + 8x3 - 2x4 - 4x5
sous les contraintes :
- -3x1 + 6x2 - 7x3 + 9x4 + 9x5 ≥ 10
- x1 + 2x2 - x4 - 3x5 ≤ 0
- toutes les variables sont binaires
Exo 5
Considérer le problème suivant :
sous les contraintes :
- 5x1 - 7x2 ≥ 3
- 0 ≤ x1 ≤ 3
- 0 ≤ x2 ≤ 3
- toutes les variables sont entières
et répondre aux questions suivantes :
- Résoudre graphiquement.
- Appliquer l'algorithme de Branch&Bound mixte (MIP) pour résoudre manuellement ce problème.
La résolution des relaxations linéaires sera graphique.
- Reformuler ce problème en programmation binaire.
- Appliquer l'algorithme de Branch&Bound binaire (BIP) pour résoudre ce dernier problème.
Exo 6
Résoudre le programme linéaire entier de l'exo 1 en appliquant manuellement
l'algorithme de Branch&Bound mixte (MIP).
Exo 7
Appliquer l'algorithme de Branch&Bound mixte (MIP) pour résoudre :
- max Z = 5x1 + 4x2 + 4x3 + 2x4
sous les contraintes :
- x1 + 3x2 + 2x3 + x4 ≤ 10
- 5x1 + x2 + 3x3 + 2x4 ≤ 15
- x1 + x2 + x3 + x4 ≤ 6
- toutes les variables sont positives ou nulles
- x1, x2, x3 sont entières
Exo 8
Appliquer l'algorithme de Branch&Bound mixte (MIP) pour résoudre :
- min Z = 5x1 + x2 + x3 + 2x4 + 3x5
sous les contraintes :
- x2 - 5x3 + x4 + 2x5 ≥ -2
- 5x1 - x2 + x5 ≥ 7
- x1 + x2 + 6x3 + x4 ≥ 4
- toutes les variables sont positives ou nulles
- x1, x2, x3 sont entières
Exo 9
Résoudre les sept énoncés précédents à l'aide d'un solveur comme GLPK.
Fred Mesnard