Calculadora de Programación Entera (Ramificación y Acotación)
Resuelve modelos lineales con restricciones enteras mediante el árbol de Ramificación y Acotación, analizando relajaciones continuas y nodos podados.
Tamaño del Problema
Objetivo
Función Objetivo — Maximizar Z
Restricc.
Programación Lineal Entera y Branch and Bound: Guía Académica
Comprende cómo el algoritmo de Ramificación y Acotación (Branch & Bound) explora el árbol de relajaciones, poda ramas dominadas y garantiza el óptimo entero exacto sin redondeos heurísticos.
1. ¿Qué problema resuelve la Programación Entera?
La Programación Lineal continua asume variables divisibles en números reales. Sin embargo, en la gestión de operaciones real, muchas decisiones corresponden a entidades indivisibles: operarios, vehículos, paquetes o decisiones binarias sí/no (0-1). La Programación Lineal Entera (PLE) añade la restricción xⱼ ∈ ℤ. Dado que el espacio factible entero no es un poliedro continuo sino una cuadrícula de puntos aislados, los métodos de gradiente fallan, requiriendo algoritmos de exploración como Branch and Bound.
2. El Algoritmo de Ramificación y Acotación (Branch & Bound)
Se eliminan temporalmente las restricciones de integralidad (permitiendo xⱼ ∈ ℝ) y se resuelve mediante el método Simplex ordinario. El valor Z_LP actúa como cota superior teórica absoluta para maximización.
Si la solución continua es entera, es el óptimo definitivo. Si una variable xₖ es fraccionaria con valor v, se generan dos subproblemas excluyentes: Rama Izquierda (xₖ ≤ ⌊v⌋) y Rama Derecha (xₖ ≥ ⌈v⌉).
Se resuelve la relajación continua de cada nuevo nodo del árbol. Se mantiene la 'solución incumbente' (el mejor valor entero Z* conocido hasta el momento).
Un nodo se poda (cierra) si: (1) Es infactible, (2) Su cota Z_nodo ≤ Z* (dominado por la solución incumbente), o (3) Alcanza una solución completamente entera (si Z_nodo > Z*, se actualiza la incumbente).
3. Ejemplo Académico Resuelto: Programación Entera de 2 Variables
Descubre por qué redondear la solución continua falla y cómo el árbol completo de 9 nodos converge a Z* = 40.
¿Por qué el Redondeo Ingenuo Fracasa Estrepitosamente?
La relajación continua arroja el óptimo en (x₁ = 2,25; x₂ = 3,75) con Z = 41,25. Si se redondea al entero más cercano (2, 4), la Restricción 2 produce 5(2) + 9(4) = 46 > 45 (¡Infactible!). Si se redondea hacia abajo a (2, 3), se obtiene Z = 34, perdiendo 6 unidades respecto al óptimo real. Branch & Bound explora de forma exhaustiva el espacio discreto.
Evolución Completa del Árbol de Branch & Bound (Recorrido DFS)
| Tree Node | Branch Constraint | LP Relaxation Point | Objective Z | Branch & Bound Action |
|---|---|---|---|---|
| Nodo 1 (Raíz) | Relajación continua de PL (sin condición entera) | x₁ = 2,25; x₂ = 3,75 | Z = 41,25 | Variable x₁ = 2,25 fraccionaria. Se ramifica en x₁ ≤ 2 (Nodo 2) y x₁ ≥ 3 (Nodo 3). |
| Nodo 2 | Añadir restricción: x₁ ≤ 2 (desde Raíz) | x₁ = 2,00; x₂ = 35/9 ≈ 3,89 | Z = 370/9 ≈ 41,11 | Variable x₂ ≈ 3,89 fraccionaria. Se ramifica en x₂ ≤ 3 (Nodo 4) y x₂ ≥ 4 (Nodo 5). |
| Nodo 4 | Nodo 2 + restricción: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3) | x₁ = 2; x₂ = 3 | Z = 34,00 | ¡Solución entera! Incumbente inicial establecida: Z* = 34 en (2, 3). |
| Nodo 5 | Nodo 2 + restricción: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4) | x₁ = 1,80; x₂ = 4,00 | Z = 41,00 | Variable x₁ = 1,80 fraccionaria (Z = 41 > 34). Se ramifica en x₁ ≤ 1 (Nodo 6) y x₁ ≥ 2 (Nodo 7). |
| Nodo 6 | Nodo 5 + restricción: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4) | x₁ = 1,00; x₂ = 40/9 ≈ 4,44 | Z = 365/9 ≈ 40,56 | Variable x₂ ≈ 4,44 fraccionaria (Z ≈ 40,56 > 34). Se ramifica en x₂ ≤ 4 (Nodo 8) y x₂ ≥ 5 (Nodo 9). |
| Nodo 8 | Nodo 6 + restricción: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4) | x₁ = 1; x₂ = 4 | Z = 37,00 | ¡Solución entera! Como 37 > 34, se actualiza la incumbente: Z* = 37 en (1, 4). |
| Nodo 9 | Nodo 6 + restricción: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0) | x₁ = 0; x₂ = 5 | Z = 40,00 | ¡Solución entera! Como 40 > 37, se actualiza la incumbente: Z* = 40 en (0, 5) (ÓPTIMO GLOBAL). |
| Nodo 7 | Nodo 5 + restricción: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4) | Sin solución factible (5(2)+9(4) = 46 > 45) | Infactible | Podado por Infactibilidad. |
| Nodo 3 | Añadir restricción: x₁ ≥ 3 (desde Raíz) | x₁ = 3; x₂ = 3 | Z = 39,00 | Solución entera, pero Z = 39 ≤ Z* (40). Podado por Cota Dominada. |
Solución Óptima Entera Demostrada
Los 9 nodos del árbol han sido completamente explorados o podados. Solución Óptima Entera Global: x₁* = 0, x₂* = 5 con Máximo Z* = 40. (Coincide exactamente con el motor de Branch & Bound).
4. Errores Frecuentes en Ejámenes de Programación Entera
Creer que el Óptimo Entero es Vecino del Óptimo Continuo
La solución óptima entera puede encontrarse lejos del vértice de la relajación continua. Siempre debe desarrollarse el árbol en lugar de probar puntos adyacentes a ciegas.
No Podar Ramas Dominadas por la Cota Incumbente
Continuar ramificando un nodo cuya cota continua es menor o igual que la mejor solución entera ya encontrada (Z ≤ Z*) genera trabajo innecesario y ralentiza el algoritmo.
Formulación Incorrecta de las Desigualdades de Ramificación
Las ramas deben cubrir el hueco entero con xₖ ≤ ⌊v⌋ y xₖ ≥ ⌈v⌉. Usar desigualdades estrictas (< o >) omite soluciones válidas.