Exos Branch&Bound

Exo 1

• max Z = 5x1 + x2

• -x1 + 2x2 ≤ 4
• x1 - x2 ≤ 1
• 4x1 + x2 ≤ 12
• 0 ≤ x1
• 0 ≤ x2
• x1 et x2 entiers

1. Résoudre graphiquement.
2. Résoudre la relaxation linéaire graphiquement.
3. Arrondir ce maximum à l'entier le plus proche et tester sa faisabilité.
4. 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

• max Z = 2x1 - x2 + 5x3 - 3x4 + 4x5

• 3x1 - 2x2 + 7x3 - 5x4 + 4x5 ≤ 6
• x1 - x2 + 2x3 - 4x4 + 2x5 ≤ 0
• toutes les variables sont binaires

Exo 3

• min Z = 5x1 + 6x2 + 7x3 + 8x4 + 9x5

• 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

• max Z = 5x1 + 5x2 + 8x3 - 2x4 - 4x5

• -3x1 + 6x2 - 7x3 + 9x4 + 9x5 ≥ 10
• x1 + 2x2 - x4 - 3x5 ≤ 0
• toutes les variables sont binaires

Exo 5

• max Z = -3x1 + 5x2

• 5x1 - 7x2 ≥ 3
• 0 ≤ x1 ≤ 3
• 0 ≤ x2 ≤ 3
• toutes les variables sont entières

1. Résoudre graphiquement.
2. Appliquer l'algorithme de Branch&Bound mixte (MIP) pour résoudre manuellement ce problème. La résolution des relaxations linéaires sera graphique.
3. Reformuler ce problème en programmation binaire.
4. Appliquer l'algorithme de Branch&Bound binaire (BIP) pour résoudre ce dernier problème.

Exo 6

Exo 7

• max Z = 5x1 + 4x2 + 4x3 + 2x4

• 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

• min Z = 5x1 + x2 + x3 + 2x4 + 3x5

• 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