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

x1
+
x2

Restricc.

C1
x1
+
x2
C2
x1
+
x2
Optimización Discreta y Programación Entera Mixta

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)

Paso 1: Relajación Continua del PL

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.

Paso 2: Comprobación de Integralidad y Ramificació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⌉).

Paso 3: Evaluación de Subproblemas y Acotación

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

Paso 4: Poda Sistemática de Ramas

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.

Maximizar Z = 5x₁ + 8x₂
Restricción 1: x₁ + x₂ ≤ 6
Restricción 2: 5x₁ + 9x₂ ≤ 45
No negatividad: x₁ ≥ 0, x₂ ≥ 0
Condición entera: x₁, x₂ ∈ ℤ (ambas variables deben ser números enteros)

¿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 NodeBranch ConstraintLP Relaxation PointObjective ZBranch & Bound Action
Nodo 1 (Raíz)Relajación continua de PL (sin condición entera)x₁ = 2,25; x₂ = 3,75Z = 41,25Variable x₁ = 2,25 fraccionaria. Se ramifica en x₁ ≤ 2 (Nodo 2) y x₁ ≥ 3 (Nodo 3).
Nodo 2Añadir restricción: x₁ ≤ 2 (desde Raíz)x₁ = 2,00; x₂ = 35/9 ≈ 3,89Z = 370/9 ≈ 41,11Variable x₂ ≈ 3,89 fraccionaria. Se ramifica en x₂ ≤ 3 (Nodo 4) y x₂ ≥ 4 (Nodo 5).
Nodo 4Nodo 2 + restricción: x₂ ≤ 3 (x₁ ≤ 2, x₂ ≤ 3)x₁ = 2; x₂ = 3Z = 34,00¡Solución entera! Incumbente inicial establecida: Z* = 34 en (2, 3).
Nodo 5Nodo 2 + restricción: x₂ ≥ 4 (x₁ ≤ 2, x₂ ≥ 4)x₁ = 1,80; x₂ = 4,00Z = 41,00Variable x₁ = 1,80 fraccionaria (Z = 41 > 34). Se ramifica en x₁ ≤ 1 (Nodo 6) y x₁ ≥ 2 (Nodo 7).
Nodo 6Nodo 5 + restricción: x₁ ≤ 1 (x₁ ≤ 1, x₂ ≥ 4)x₁ = 1,00; x₂ = 40/9 ≈ 4,44Z = 365/9 ≈ 40,56Variable x₂ ≈ 4,44 fraccionaria (Z ≈ 40,56 > 34). Se ramifica en x₂ ≤ 4 (Nodo 8) y x₂ ≥ 5 (Nodo 9).
Nodo 8Nodo 6 + restricción: x₂ ≤ 4 (x₁ ≤ 1, x₂ = 4)x₁ = 1; x₂ = 4Z = 37,00¡Solución entera! Como 37 > 34, se actualiza la incumbente: Z* = 37 en (1, 4).
Nodo 9Nodo 6 + restricción: x₂ ≥ 5 (5x₁ + 9(5) ≤ 45 ⇒ x₁ = 0)x₁ = 0; x₂ = 5Z = 40,00¡Solución entera! Como 40 > 37, se actualiza la incumbente: Z* = 40 en (0, 5) (ÓPTIMO GLOBAL).
Nodo 7Nodo 5 + restricción: x₁ ≥ 2 (x₁ ≥ 2, x₂ ≥ 4)Sin solución factible (5(2)+9(4) = 46 > 45)InfactiblePodado por Infactibilidad.
Nodo 3Añadir restricción: x₁ ≥ 3 (desde Raíz)x₁ = 3; x₂ = 3Z = 39,00Solució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.