Calculadora de Programació Entera (Ramificació i Acotació)

Resol models lineals amb restriccions enteres mitjançant l'arbre de Ramificació i Acotació, analitzant relaxacions contínues i nodes podats.

Mida del Problema

Objectiu

Funció Objectiu — Maximitzar Z

x1
+
x2

Restricc.

C1
x1
+
x2
C2
x1
+
x2
Optimització Discreta i Programació Entera Mixta

Programació Lineal Entera i Branch and Bound: Guia Acadèmica

Comprèn com l'algorisme de Ramificació i Acotació (Branch & Bound) explora l'arbre de relaxacions, poda branques dominades i garanteix l'òptim enter exacte sense errors d'arrodoniment.

1. Quin problema resol la Programació Entera?

La Programació Lineal contínua assumeix variables divisibles en nombres reals. No obstant això, en problemes reals de gestió d'operacions, moltes decisions involucren unitats indivisibles: operaris, combois, maquinària o variables binàries sí/no (0-1). La Programació Lineal Entera (PLE) imposa que xⱼ ∈ ℤ. Atès que l'espai factible enter està format per una malla de punts discrets i no pas per un políedre continu, els mètodes de gradient no funcionen i cal emprar algorismes d'arbre com Branch and Bound.

2. L'Algorisme de Ramificació i Acotació (Branch & Bound)

Pas 1: Relaxació Contínua de PL

S'elimina temporalment la condició d'enter (permetent xⱼ ∈ ℝ) i es resol amb el mètode Simplex habitual. El valor continu Z_LP fixa una cota superior teòrica absoluta per a problemes de maximització.

Pas 2: Comprovació d'Integralitat i Ramificació

Si la solució contínua és entera, és l'òptim definitiu. Si una variable xₖ és fraccionària amb valor v, es generen dos subproblemes: Branca Esquerra (xₖ ≤ ⌊v⌋) i Branca Dreta (xₖ ≥ ⌈v⌉).

Pas 3: Avaluació de Subproblemes i Acotació

Es resol la relaxació contínua de cada nou node de l'arbre. Es manté en memòria la 'solució incumbent' (el millor valor enter Z* trobat fins al moment).

Pas 4: Poda Sistemàtica de Branques

Un node es poda (es tanca) si: (1) És infactible, (2) La seva cota Z_node ≤ Z* (dominat per la solució incumbent), o (3) Arriba a una solució entera (si Z_node > Z*, s'actualitza la incumbent).

3. Exemple Acadèmic Resol: Programació Entera de 2 Variables

Descobreix per què arrodonir la solució contínua falla i com l'arbre complet de 9 nodes arriba a Z* = 40.

Maximitzar Z = 5x₁ + 8x₂
Restricció 1: x₁ + x₂ ≤ 6
Restricció 2: 5x₁ + 9x₂ ≤ 45
No-negativitat: x₁ ≥ 0, x₂ ≥ 0
Restricció entera: x₁, x₂ ∈ ℤ (ambdues variables han de ser nombres enters)

Per què l'Arrodoniment Ingenu Fracassa Estrepitosament?

La relaxació contínua dona l'òptim a (x₁ = 2,25; x₂ = 3,75) amb Z = 41,25. Si s'arrodoneix a l'enter més proper (2, 4), la Restricció 2 dona 5(2) + 9(4) = 46 > 45 (Infactible!). Si s'arrodoneix a la baixa a (2, 3), s'obté Z = 34, perdent 6 unitats respecte a l'òptim enter real. Branch & Bound analitza de manera exhaustiva l'espai discret.

Evolució Completa de l'Arbre de Branch & Bound (Recorregut DFS)

Tree NodeBranch ConstraintLP Relaxation PointObjective ZBranch & Bound Action
Node 1 (Arrel)Relaxació contínua de PL (sense condició d'enter)x₁ = 2,25; x₂ = 3,75Z = 41,25Variable x₁ = 2,25 fraccionària. Es ramifica en x₁ ≤ 2 (Node 2) i x₁ ≥ 3 (Node 3).
Node 2Afegir restricció: x₁ ≤ 2 (des de l'Arrel)x₁ = 2,00; x₂ = 35/9 ≈ 3,89Z = 370/9 ≈ 41,11Variable x₂ ≈ 3,89 fraccionària. Es ramifica en x₂ ≤ 3 (Node 4) i x₂ ≥ 4 (Node 5).
Node 4Node 2 + restricció: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3)x₁ = 2; x₂ = 3Z = 34,00Solució entera! Incumbent inicial fixada: Z* = 34 a (2, 3).
Node 5Node 2 + restricció: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4)x₁ = 1,80; x₂ = 4,00Z = 41,00Variable x₁ = 1,80 fraccionària (Z = 41 > 34). Es ramifica en x₁ ≤ 1 (Node 6) i x₁ ≥ 2 (Node 7).
Node 6Node 5 + restricció: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4)x₁ = 1,00; x₂ = 40/9 ≈ 4,44Z = 365/9 ≈ 40,56Variable x₂ ≈ 4,44 fraccionària (Z ≈ 40,56 > 34). Es ramifica en x₂ ≤ 4 (Node 8) i x₂ ≥ 5 (Node 9).
Node 8Node 6 + restricció: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4)x₁ = 1; x₂ = 4Z = 37,00Solució entera! Com que 37 > 34, s'actualitza la incumbent: Z* = 37 a (1, 4).
Node 9Node 6 + restricció: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0)x₁ = 0; x₂ = 5Z = 40,00Solució entera! Com que 40 > 37, s'actualitza la incumbent: Z* = 40 a (0, 5) (ÒPTIM GLOBAL).
Node 7Node 5 + restricció: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4)Sense solució factible (5(2)+9(4) = 46 > 45)InfactiblePodat per Infactibilitat.
Node 3Afegir restricció: x₁ ≥ 3 (des de l'Arrel)x₁ = 3; x₂ = 3Z = 39,00Solució entera, però Z = 39 ≤ Z* (40). Podat per Cota Dominada.

Solució Òptima Entera Demostrada

Tots els 9 nodes de l'arbre han estat explorats o podats. Solució Òptima Entera Global: x₁* = 0, x₂* = 5 amb Màxim Z* = 40. (Coincideix exactament amb el resultat del calculador).

4. Errors Freqüents en Exàmens de Programació Entera

⚠

Creure que l'Òptim Enter és Veí de l'Òptim Continu

L'òptim enter pot estar geomètricament allunyat del vèrtex continu de la relaxació. Sempre cal desenvolupar l'arbre de decisions.

⚠

No Podar Branques Dominades per la Cota Incumbent

Continuar ramificant un node la cota del qual és inferior o igual a la millor solució entera coneguda (Z ≤ Z*) malgasta càlculs sense millorar el resultat.

⚠

Formulació Errònia de les Desigualtats de Branca

Les branques han de cobrir el buit enter amb xₖ ≤ ⌊v⌋ i xₖ ≥ ⌈v⌉. Emprar desigualtats estrictes (< o >) exclou punts enters vàlids.