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