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

x1
+
x2

Contraintes

C1
x1
+
x2
C2
x1
+
x2
Optimisation Discrète et Programmation en Nombres Entiers

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)

Étape 1 : Relaxation Linéaire Continue

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.

Étape 2 : Test d'Intégrité et Séparation

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

Étape 3 : Évaluation et Encadrement

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

Étape 4 : Élagage Systématique (Fathoming)

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.

Maximiser Z = 5x₁ + 8x₂
Contrainte 1 : x₁ + x₂ ≤ 6
Contrainte 2 : 5x₁ + 9x₂ ≤ 45
Non-négativité : x₁ ≥ 0, x₂ ≥ 0
Condition d'intégrité : x₁, x₂ ∈ ℤ (les deux variables doivent être entières)

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 NodeBranch ConstraintLP Relaxation PointObjective ZBranch & Bound Action
Nœud 1 (Racine)Relaxation continue (sans contrainte d'intégrité)x₁ = 2,25 ; x₂ = 3,75Z = 41,25Variable x₁ = 2,25 fractionnaire. Séparation : x₁ ≤ 2 (Nœud 2) et x₁ ≥ 3 (Nœud 3).
Nœud 2Ajout contrainte : x₁ ≤ 2 (depuis la Racine)x₁ = 2,00 ; x₂ = 35/9 ≈ 3,89Z = 370/9 ≈ 41,11Variable x₂ ≈ 3,89 fractionnaire. Séparation : x₂ ≤ 3 (Nœud 4) et x₂ ≥ 4 (Nœud 5).
Nœud 4Nœud 2 + contrainte : x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3)x₁ = 2 ; x₂ = 3Z = 34,00Solution entière ! Incumbente initiale : Z* = 34 en (2, 3).
Nœud 5Nœud 2 + contrainte : x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4)x₁ = 1,80 ; x₂ = 4,00Z = 41,00Variable x₁ = 1,80 fractionnaire (Z = 41 > 34). Séparation : x₁ ≤ 1 (Nœud 6) et x₁ ≥ 2 (Nœud 7).
Nœud 6Nœud 5 + contrainte : x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4)x₁ = 1,00 ; x₂ = 40/9 ≈ 4,44Z = 365/9 ≈ 40,56Variable x₂ ≈ 4,44 fractionnaire (Z ≈ 40,56 > 34). Séparation : x₂ ≤ 4 (Nœud 8) et x₂ ≥ 5 (Nœud 9).
Nœud 8Nœud 6 + contrainte : x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4)x₁ = 1 ; x₂ = 4Z = 37,00Solution entière ! Comme 37 > 34, mise à jour incumbente : Z* = 37 en (1, 4).
Nœud 9Nœud 6 + contrainte : x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0)x₁ = 0 ; x₂ = 5Z = 40,00Solution entière ! Comme 40 > 37, mise à jour incumbente : Z* = 40 en (0, 5) (OPTIMUM GLOBAL).
Nœud 7Nœ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 3Ajout contrainte : x₁ ≥ 3 (depuis la Racine)x₁ = 3 ; x₂ = 3Z = 39,00Solution 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.