Calculateur de Programmation en Nombres Entiers (Branch and Bound)
Résolvez vos programmes linéaires à variables entières avec l'arbre de séparation et évaluation (Branch and Bound), relaxations et élagages.
Taille du Problème
Objectif
Fonction Objectif — Maximiser Z
Contraintes
Programmation Linéaire en Nombres Entiers et Branch & Bound : Guide Académique
Comprenez comment l'algorithme de Séparation et Évaluation (Branch and Bound) explore l'arbre des relaxations, élague les branches dominées et assure l'optimum entier exact sans heuristique d'arrondi.
1. Quel problème résout la Programmation en Nombres Entiers ?
La Programmation Linéaire classique suppose des variables réelles continues. Or, en recherche opérationnelle appliquée, de nombreuses décisions impliquent des quantités indivisibles : véhicules, personnels, machines ou choix binaires 0-1. La Programmation Linéaire en Nombres Entiers (PLNE) impose xⱼ ∈ ℤ. Comme le domaine admissible est un maillage discret de points et non un polyèdre convexe continu, les méthodes de gradient échouent, nécessitant une recherche arborescente systématique comme le Branch and Bound.
2. L'Algorithme Branch and Bound (Séparation et Évaluation)
On ignore provisoirement l'intégrité (en autorisant xⱼ ∈ ℝ) et on résout par le Simplexe classique. La valeur optimale Z_LP constitue une borne supérieure absolue pour une maximisation.
Si la solution continue est entière, elle est optimale. Si une variable xₖ présente une valeur fractionnaire v, on sépare le problème en deux sous-problèmes : Branche Gauche (xₖ ≤ ⌊v⌋) et Branche Droite (xₖ ≥ ⌈v⌉).
On résout la relaxation continue de chaque nouveau nœud. On garde en mémoire la 'solution incumbente' (la meilleure solution réalisable entière Z* trouvée jusqu'ici).
Un nœud est élagué (fermé) si : (1) Il est non réalisable, (2) Sa borne Z_nœud ≤ Z* (branche dominée), ou (3) Il aboutit à une solution entière (mise à jour de Z* si Z_nœud > Z*).
3. Exemple Académique Résolu : PLNE à 2 Variables
Découvrez pourquoi arrondir la solution continue échoue et comment l'arbre complet de 9 nœuds converge vers Z* = 40.
Pourquoi l'Arrondi Naïf Échoue Invariablement
La relaxation continue donne le sommet (x₁ = 2,25 ; x₂ = 3,75) avec Z = 41,25. Arrondir à l'entier le plus proche (2, 4) enfreint la Contrainte 2 : 5(2) + 9(4) = 46 > 45 (Infaisable !). Arrondir par défaut à (2, 3) donne Z = 34, soit 6 unités de moins que l'optimum réel. L'algorithme Branch & Bound garantit la solution exacte sans aucune approximation.
Progression Complète de l'Arbre de Séparation et Évaluation (Parcours DFS)
| Tree Node | Branch Constraint | LP Relaxation Point | Objective Z | Branch & Bound Action |
|---|---|---|---|---|
| Nœud 1 (Racine) | Relaxation continue (sans contrainte d'intégrité) | x₁ = 2,25 ; x₂ = 3,75 | Z = 41,25 | Variable x₁ = 2,25 fractionnaire. Séparation : x₁ ≤ 2 (Nœud 2) et x₁ ≥ 3 (Nœud 3). |
| Nœud 2 | Ajout contrainte : x₁ ≤ 2 (depuis la Racine) | x₁ = 2,00 ; x₂ = 35/9 ≈ 3,89 | Z = 370/9 ≈ 41,11 | Variable x₂ ≈ 3,89 fractionnaire. Séparation : x₂ ≤ 3 (Nœud 4) et x₂ ≥ 4 (Nœud 5). |
| Nœud 4 | Nœud 2 + contrainte : x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3) | x₁ = 2 ; x₂ = 3 | Z = 34,00 | Solution entière ! Incumbente initiale : Z* = 34 en (2, 3). |
| Nœud 5 | Nœud 2 + contrainte : x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4) | x₁ = 1,80 ; x₂ = 4,00 | Z = 41,00 | Variable x₁ = 1,80 fractionnaire (Z = 41 > 34). Séparation : x₁ ≤ 1 (Nœud 6) et x₁ ≥ 2 (Nœud 7). |
| Nœud 6 | Nœud 5 + contrainte : x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4) | x₁ = 1,00 ; x₂ = 40/9 ≈ 4,44 | Z = 365/9 ≈ 40,56 | Variable x₂ ≈ 4,44 fractionnaire (Z ≈ 40,56 > 34). Séparation : x₂ ≤ 4 (Nœud 8) et x₂ ≥ 5 (Nœud 9). |
| Nœud 8 | Nœud 6 + contrainte : x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4) | x₁ = 1 ; x₂ = 4 | Z = 37,00 | Solution entière ! Comme 37 > 34, mise à jour incumbente : Z* = 37 en (1, 4). |
| Nœud 9 | Nœud 6 + contrainte : x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0) | x₁ = 0 ; x₂ = 5 | Z = 40,00 | Solution entière ! Comme 40 > 37, mise à jour incumbente : Z* = 40 en (0, 5) (OPTIMUM GLOBAL). |
| Nœud 7 | Nœud 5 + contrainte : x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4) | Aucune solution réalisable (5(2)+9(4) = 46 > 45) | Infaisable | Élagué pour non-réalisabilité. |
| Nœud 3 | Ajout contrainte : x₁ ≥ 3 (depuis la Racine) | x₁ = 3 ; x₂ = 3 | Z = 39,00 | Solution entière, mais Z = 39 ≤ Z* (40). Élagué par dominance de borne. |
Solution Optimale Entière Prouvée
Les 9 nœuds de l'arbre ont été complètement explorés ou élagués. Solution Optimale Entière Globale : x₁* = 0, x₂* = 5 avec Maximum Z* = 40. (Conforme au solveur Branch & Bound du site).
4. Erreurs Classiques en Examen
Croire que l'Optimum Entier est Voisin de l'Optimum Continu
Le point entier optimal peut être géométriquement éloigné du sommet de relaxation. L'exploration de l'arbre est indispensable.
Omettre d'Élaguer les Nœuds Dominés
Continuer à séparer un nœud dont la borne continue est inférieure ou égale à l'incumbente entière (Z ≤ Z*) engendre des calculs superflus.
Formulation Erronée des Branches
Les branches doivent couvrir l'intervalle entier : xₖ ≤ ⌊v⌋ et xₖ ≥ ⌈v⌉. L'emploi d'inégalités strictes élimine des solutions valides.