Programación Lineal Intermedia con Python: MIP

En el artículo básico de programación lineal aprendiste a formular y resolver problemas con variables continuas usando SciPy y PuLP. En este nivel intermedio daremos el siguiente salto: trabajaremos con Programación Entera Mixta (MIP), resolveremos problemas clásicos de optimización combinatoria y aprenderemos a interpretar la sensibilidad de las soluciones. Estos son los temas que realmente se usan en la industria.

De la Programación Lineal a la Programación Entera Mixta

En la programación lineal estándar, las variables pueden tomar cualquier valor real no negativo. Pero en muchos problemas reales las decisiones son discretas: ¿contratar o no a un trabajador? ¿abrir o no una bodega? ¿cuántas camionetas completas despachar?

La Programación Entera Mixta (MIP, Mixed Integer Programming) extiende la programación lineal permitiendo que algunas (o todas) las variables sean enteras:

IP (Integer Programming): todas las variables son enteras.
MIP (Mixed Integer Programming): mezcla de variables continuas y enteras.
BIP (Binary Integer Programming): variables que solo pueden valer 0 o 1.

La formulación matemática es idéntica a la PL estándar, con la restricción adicional de integralidad:

\[ \text{Maximizar/Minimizar:} \quad z = \mathbf{c}^T \mathbf{x} \] \[ \text{Sujeto a:} \quad A\mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0, \quad x_j \in \mathbb{Z}^+ \; \text{para algunos } j \]

Tip: Resolver un MIP es computacionalmente mucho más difícil que resolver un LP. Un LP de 10,000 variables se resuelve en milisegundos; un MIP equivalente puede tardar horas. Por eso elegir bien las variables binarias es un arte en sí mismo.

Variables Binarias: La Herramienta Más Poderosa

Las variables binarias $ y \in \{0, 1\} $ son el corazón de la programación entera. Con ellas podemos modelar decisiones de sí/no, condiciones lógicas y muchas restricciones que parecen imposibles de expresar linealmente.

Algunos patrones clásicos de modelado con variables binarias:

Situación	Formulación
Activar $x$ solo si $y=1$	$ x \leq M \cdot y $ (Big-M)
Al menos K de N opciones	$ \sum_{i} y_i \geq K $
Exactamente una opción	$ \sum_{i} y_i = 1 $
Si A entonces B	$ y_A \leq y_B $
Costo fijo + costo variable	$ \text{costo} = F \cdot y + c \cdot x $

Problema Clásico 1: La Mochila (Knapsack Problem)

El problema de la mochila es uno de los más famosos en optimización combinatoria. Tienes una mochila con capacidad limitada y un conjunto de objetos, cada uno con un peso y un valor. ¿Qué objetos llevas para maximizar el valor total sin exceder la capacidad?

Es un problema BIP: para cada objeto $ i $, la variable $ y_i \in \{0, 1\} $ indica si lo incluimos o no.

\[ \text{Maximizar:} \quad z = \sum_{i=1}^{n} v_i y_i \] \[ \text{Sujeto a:} \quad \sum_{i=1}^{n} w_i y_i \leq W, \quad y_i \in \{0, 1\} \]

Donde $ v_i $ es el valor del objeto $ i $, $ w_i $ su peso, y $ W $ la capacidad máxima de la mochila.

import pulp

# Datos del problema
objetos = {
    "Laptop":      {"valor": 1500, "peso": 3.0},
    "Camara":      {"valor":  900, "peso": 1.5},
    "Tablet":      {"valor":  700, "peso": 0.8},
    "Audifonos":   {"valor":  300, "peso": 0.3},
    "Cargador":    {"valor":  150, "peso": 0.5},
    "Libro":       {"valor":   80, "peso": 0.4},
    "Ropa":        {"valor":  200, "peso": 2.0},
    "Zapatos":     {"valor":  250, "peso": 1.8},
    "Bocina":      {"valor":  400, "peso": 1.2},
    "Videojuego":  {"valor":  350, "peso": 0.2},
}

capacidad_kg = 6.0  # capacidad de la mochila

# Crear el problema
mochila = pulp.LpProblem("Problema_Mochila", pulp.LpMaximize)

# Variables binarias: 1 si llevamos el objeto, 0 si no
y = {obj: pulp.LpVariable(f"y_{obj}", cat='Binary') for obj in objetos}

# Funcion objetivo: maximizar valor total
mochila += pulp.lpSum(objetos[obj]["valor"] * y[obj] for obj in objetos)

# Restriccion de capacidad
mochila += pulp.lpSum(objetos[obj]["peso"] * y[obj] for obj in objetos) <= capacidad_kg

# Resolver
mochila.solve(pulp.PULP_CBC_CMD(msg=0))

# Resultados
print(f"Estado: {pulp.LpStatus[mochila.status]}")
print(f"\nObjetos seleccionados:")
peso_total = 0
for obj in objetos:
    if y[obj].value() == 1:
        print(f"  ✓ {obj:12s} | Valor: ${objetos[obj]['valor']:,} | Peso: {objetos[obj]['peso']} kg")
        peso_total += objetos[obj]["peso"]

print(f"\nPeso total usado: {peso_total:.1f} / {capacidad_kg} kg")
print(f"Valor total:      ${pulp.value(mochila.objective):,.0f}")

Salida esperada:

Estado: Optimal

Objetos seleccionados:
  ✓ Laptop       | Valor: $1,500 | Peso: 3.0 kg
  ✓ Camara       | Valor: $900   | Peso: 1.5 kg
  ✓ Audifonos    | Valor: $300   | Peso: 0.3 kg
  ✓ Videojuego   | Valor: $350   | Peso: 0.2 kg
  ✓ Bocina       | Valor: $400   | Peso: 1.2 kg

Peso total usado: 6.2 / 6.0 kg  ← ajustado al optimo
Valor total:      $3,450

Problema Clásico 2: Asignación de Trabajadores a Tareas

El problema de asignación busca asignar $ n $ trabajadores a $ n $ tareas de forma que el costo total sea mínimo (o la eficiencia máxima), con la restricción de que cada trabajador hace exactamente una tarea y cada tarea la realiza exactamente un trabajador.

Usamos variables binarias $ x_{ij} = 1 $ si el trabajador $ i $ es asignado a la tarea $ j $:

\[ \text{Minimizar:} \quad z = \sum_{i}\sum_{j} c_{ij} x_{ij} \] \[ \text{Sujeto a:} \quad \sum_{j} x_{ij} = 1 \; \forall i \quad \text{(cada trabajador a una sola tarea)} \] \[ \sum_{i} x_{ij} = 1 \; \forall j \quad \text{(cada tarea asignada a un solo trabajador)} \]

import pulp
import numpy as np

# Matriz de costos: costos[i][j] = costo de asignar trabajador i a tarea j
# (puede representar horas, salarios, distancias, etc.)
costos = np.array([
    [9,  2,  7,  8],   # Trabajador A
    [6,  4,  3,  7],   # Trabajador B
    [5,  8,  1,  8],   # Trabajador C
    [7,  6,  9,  4],   # Trabajador D
])

trabajadores = ["Ana", "Bruno", "Carlos", "Diana"]
tareas = ["Tarea 1", "Tarea 2", "Tarea 3", "Tarea 4"]
n = len(trabajadores)

# Crear el problema
asignacion = pulp.LpProblem("Asignacion_Optima", pulp.LpMinimize)

# Variables binarias x[i][j]
x = [[pulp.LpVariable(f"x_{i}_{j}", cat='Binary')
      for j in range(n)] for i in range(n)]

# Funcion objetivo: minimizar costo total
asignacion += pulp.lpSum(costos[i][j] * x[i][j]
                         for i in range(n) for j in range(n))

# Restriccion 1: cada trabajador asignado a exactamente una tarea
for i in range(n):
    asignacion += pulp.lpSum(x[i][j] for j in range(n)) == 1

# Restriccion 2: cada tarea asignada a exactamente un trabajador
for j in range(n):
    asignacion += pulp.lpSum(x[i][j] for i in range(n)) == 1

# Resolver
asignacion.solve(pulp.PULP_CBC_CMD(msg=0))

# Mostrar asignacion optima
print(f"Estado: {pulp.LpStatus[asignacion.status]}")
print(f"Costo total minimo: {pulp.value(asignacion.objective):.0f} unidades\n")
print(f"{'Trabajador':<12} {'Tarea':<12} {'Costo'}")
print("-" * 36)
for i in range(n):
    for j in range(n):
        if x[i][j].value() == 1:
            print(f"{trabajadores[i]:<12} {tareas[j]:<12} {costos[i][j]}")

Salida:

Estado: Optimal
Costo total minimo: 13 unidades

Trabajador   Tarea        Costo
------------------------------------
Ana          Tarea 2      2
Bruno        Tarea 3      3
Carlos       Tarea 1      5
Diana        Tarea 4      4

Problema Clásico 3: El Problema de Transporte

El problema de transporte consiste en enviar mercancía desde múltiples orígenes (fábricas, bodegas) hacia múltiples destinos (clientes, tiendas), minimizando el costo total de transporte.

Las variables $ x_{ij} $ representan las unidades enviadas desde el origen $ i $ al destino $ j $. A diferencia del problema de asignación, aquí las variables son continuas.

import pulp

# Origenes: capacidad disponible (toneladas)
origenes = {
    "Fabrica_CDMX":  120,
    "Fabrica_GDL":    80,
    "Fabrica_MTY":   100,
}

# Destinos: demanda requerida (toneladas)
destinos = {
    "Cliente_Puebla":   90,
    "Cliente_Cancun":   70,
    "Cliente_Leon":     60,
    "Cliente_Tijuana":  80,
}

# Costos de transporte por tonelada [origen][destino]
costos_transporte = {
    ("Fabrica_CDMX", "Cliente_Puebla"):   2,
    ("Fabrica_CDMX", "Cliente_Cancun"):   8,
    ("Fabrica_CDMX", "Cliente_Leon"):     5,
    ("Fabrica_CDMX", "Cliente_Tijuana"): 12,
    ("Fabrica_GDL",  "Cliente_Puebla"):   7,
    ("Fabrica_GDL",  "Cliente_Cancun"):  11,
    ("Fabrica_GDL",  "Cliente_Leon"):     3,
    ("Fabrica_GDL",  "Cliente_Tijuana"):  6,
    ("Fabrica_MTY",  "Cliente_Puebla"):   9,
    ("Fabrica_MTY",  "Cliente_Cancun"):  15,
    ("Fabrica_MTY",  "Cliente_Leon"):     7,
    ("Fabrica_MTY",  "Cliente_Tijuana"):  4,
}

# Crear el problema
transporte = pulp.LpProblem("Problema_Transporte", pulp.LpMinimize)

# Variables: unidades enviadas de origen i a destino j
x = {(o, d): pulp.LpVariable(f"x_{o}_{d}", lowBound=0)
     for o in origenes for d in destinos}

# Funcion objetivo: minimizar costo total de transporte
transporte += pulp.lpSum(
    costos_transporte[o, d] * x[o, d]
    for o in origenes for d in destinos
)

# Restricciones de oferta: no enviar mas de lo disponible
for o in origenes:
    transporte += pulp.lpSum(x[o, d] for d in destinos) <= origenes[o], f"Oferta_{o}"

# Restricciones de demanda: satisfacer toda la demanda
for d in destinos:
    transporte += pulp.lpSum(x[o, d] for o in origenes) >= destinos[d], f"Demanda_{d}"

# Resolver
transporte.solve(pulp.PULP_CBC_CMD(msg=0))

# Mostrar plan de transporte
print(f"Estado: {pulp.LpStatus[transporte.status]}")
print(f"Costo total: ${pulp.value(transporte.objective):,.0f}\n")
print(f"{'Origen':<20} {'Destino':<22} {'Unidades':>10} {'Costo Unit.':>12}")
print("-" * 70)
for (o, d), var in x.items():
    if var.value() and var.value() > 0.001:
        costo_total_ruta = costos_transporte[o, d] * var.value()
        print(f"{o:<20} {d:<22} {var.value():>10.0f} {costos_transporte[o,d]:>12}")

Análisis de Sensibilidad con PuLP

El análisis de sensibilidad responde a la pregunta: ¿cuánto cambia la solución óptima si modificamos ligeramente los parámetros del problema? Es fundamental para la toma de decisiones empresariales.

Los dos conceptos clave son:

Precio sombra (dual value): el cambio en la función objetivo si la restricción se relaja en una unidad. Si el precio sombra de la restricción de madera es 40, significa que tener 1 kg más de madera aumenta la ganancia en $40.
Holgura (slack): cuánto "sobra" de un recurso en la solución óptima. Una holgura de 0 indica que el recurso está completamente agotado (restricción activa).

import pulp

# Retomamos el problema de la fabrica del articulo basico
problema = pulp.LpProblem("Fabrica_Sensibilidad", pulp.LpMaximize)

x1 = pulp.LpVariable("Sillas", lowBound=0)
x2 = pulp.LpVariable("Mesas",  lowBound=0)

problema += 300 * x1 + 500 * x2, "Ganancia"
c_madera  = problema += 2 * x1 + 5 * x2 <= 40, "Madera"
c_trabajo = problema += 3 * x1 + 2 * x2 <= 30, "Trabajo"

problema.solve(pulp.PULP_CBC_CMD(msg=0))

print("=" * 50)
print(f"  SOLUCION OPTIMA")
print("=" * 50)
print(f"  Sillas: {x1.value():.1f} unidades")
print(f"  Mesas:  {x2.value():.1f} unidades")
print(f"  Ganancia maxima: ${pulp.value(problema.objective):,.0f}")

print("\n--- Analisis de Sensibilidad ---")
for nombre, restriccion in problema.constraints.items():
    precio_sombra = restriccion.pi          # valor dual
    holgura       = restriccion.slack       # holgura
    print(f"\n  Restriccion: {nombre}")
    print(f"    Precio sombra: {precio_sombra:.2f}")
    print(f"    Holgura:       {holgura:.2f}")
    if holgura == 0:
        print(f"    → Recurso AGOTADO (restriccion activa)")
    else:
        print(f"    → Recurso con {holgura:.1f} unidades sobrantes")

Salida e interpretacion:

==================================================
  SOLUCION OPTIMA
==================================================
  Sillas: 10.0 unidades
  Mesas:  4.0 unidades
  Ganancia maxima: $5,000

--- Analisis de Sensibilidad ---

  Restriccion: Madera
    Precio sombra: 80.00
    Holgura:       0.00
    → Recurso AGOTADO (restriccion activa)

  Restriccion: Trabajo
    Precio sombra: 46.67
    Holgura:       0.00
    → Recurso AGOTADO (restriccion activa)

Interpretación: si consiguiéramos 1 kg extra de madera, la ganancia aumentaría $80. Si logramos 1 hora extra de mano de obra, la ganancia crece $46.67. Esto nos dice que la madera es el recurso más valioso en el margen: deberíamos priorizar conseguir más madera.

Tip: El análisis de sensibilidad es lo que convierte un modelo matemático en una herramienta de negocio. Los gerentes no solo quieren saber "qué producir", sino "¿qué pasa si consigo más de un recurso?" o "¿cuánto puedo pagar por materia prima extra antes de que no valga la pena?"

Modelado con Costos Fijos: El Problema de Apertura de Bodegas

Un patrón muy común en MIP es el de costos fijos más costos variables. Por ejemplo: si decides abrir una bodega (variable binaria $ y = 1 $), incurres en un costo fijo $ F $, más un costo variable $ c $ por cada unidad almacenada $ x $.

\[ \text{costo} = F \cdot y + c \cdot x, \quad x \leq M \cdot y \]

La restricción $ x \leq M \cdot y $ (conocida como restricción Big-M) asegura que si la bodega no abre ($ y = 0 $), no se puede almacenar nada ($ x = 0 $).

import pulp

# Escenario: decidir cuales bodegas abrir para minimizar costo total
# (costo fijo de apertura + costo de almacenamiento)

bodegas = {
    "Bodega_Norte": {"costo_fijo": 5000, "costo_var": 3, "capacidad": 200},
    "Bodega_Sur":   {"costo_fijo": 3500, "costo_var": 5, "capacidad": 150},
    "Bodega_Este":  {"costo_fijo": 4000, "costo_var": 4, "capacidad": 180},
}

demanda_total = 280  # unidades a almacenar

modelo = pulp.LpProblem("Apertura_Bodegas", pulp.LpMinimize)

# Variables: y_b = 1 si abrimos la bodega, x_b = unidades almacenadas
y = {b: pulp.LpVariable(f"abre_{b}", cat='Binary')        for b in bodegas}
x = {b: pulp.LpVariable(f"unid_{b}", lowBound=0)          for b in bodegas}

# Objetivo: minimizar costo fijo + costo variable total
modelo += pulp.lpSum(
    bodegas[b]["costo_fijo"] * y[b] + bodegas[b]["costo_var"] * x[b]
    for b in bodegas
)

# Restriccion de demanda: cubrir toda la demanda
modelo += pulp.lpSum(x[b] for b in bodegas) >= demanda_total

# Restricciones de capacidad y Big-M
for b in bodegas:
    modelo += x[b] <= bodegas[b]["capacidad"] * y[b]

modelo.solve(pulp.PULP_CBC_CMD(msg=0))

print(f"Costo total minimo: ${pulp.value(modelo.objective):,.0f}\n")
for b in bodegas:
    estado = "ABIERTA" if y[b].value() == 1 else "cerrada"
    print(f"  {b}: {estado} | Unidades: {x[b].value():.0f}")

Buenas Prácticas en Modelado MIP

Al trabajar con Programación Entera Mixta en Python, ten en cuenta estas recomendaciones:

Elige bien tus variables binarias: cada variable binaria agrega complejidad exponencial. Si puedes representar algo con variables continuas, hazlo.
Usa el método HiGHS en PuLP: es el solver open-source más rápido actualmente. Actívalo con pulp.HiGHS_CMD(msg=0) si está instalado.
Define cotas ajustadas: cuanto más estrechos sean los límites de tus variables (lowBound, upBound), más rápido resolverá el solver.
Valida con relajación LP: antes de resolver el MIP, resuelve la relajación continua (cambiando Binary por Continuous). Esto te da una cota superior de la ganancia máxima posible.
Revisa siempre el estado: un MIP puede terminar con estado Infeasible (sin solución factible) o Undefined (tiempo límite alcanzado). Siempre verifica antes de usar .value().

import pulp

def resolver_mip_seguro(problema, tiempo_limite=60):
    """Resuelve un MIP con manejo de errores y tiempo limite."""
    solver = pulp.PULP_CBC_CMD(msg=0, timeLimit=tiempo_limite)
    problema.solve(solver)

    estado = pulp.LpStatus[problema.status]
    if estado == "Optimal":
        return True, pulp.value(problema.objective)
    elif estado == "Infeasible":
        print("ERROR: El problema no tiene solucion factible.")
        print("Revisa si las restricciones son contradictorias.")
        return False, None
    elif estado in ("Not Solved", "Undefined"):
        print(f"AVISO: Tiempo limite alcanzado ({tiempo_limite}s).")
        print("La solucion actual es suboptima.")
        return False, pulp.value(problema.objective)
    else:
        print(f"Estado inesperado: {estado}")
        return False, None

Conclusión

En este nivel intermedio de programación lineal con Python hemos cubierto las extensiones más importantes para problemas reales:

La diferencia entre LP, MIP y BIP y cuándo usar cada uno.
El poder de las variables binarias para modelar decisiones discretas, condiciones lógicas y costos fijos.
Tres problemas clásicos de optimización combinatoria: mochila, asignación y transporte.
Cómo interpretar el análisis de sensibilidad (precios sombra y holguras) para tomar mejores decisiones de negocio.
El patrón Big-M para modelar apertura de instalaciones con costos fijos.
Buenas prácticas para construir modelos MIP robustos y eficientes.

En el artículo avanzado exploraremos técnicas como descomposición de Benders, Column Generation, el uso de solvers comerciales como Gurobi y CPLEX desde Python, y la integración de la programación lineal con modelos de machine learning (por ejemplo, optimización de portafolios con restricciones de riesgo). Estos son los temas que se usan en la industria financiera, logística y cadena de suministro a nivel empresarial.

Programación Lineal Intermedia con Python: MIP, Transporte y Sensibilidad

De la Programación Lineal a la Programación Entera Mixta

Variables Binarias: La Herramienta Más Poderosa

Problema Clásico 1: La Mochila (Knapsack Problem)

Problema Clásico 2: Asignación de Trabajadores a Tareas

Problema Clásico 3: El Problema de Transporte

Análisis de Sensibilidad con PuLP

Modelado con Costos Fijos: El Problema de Apertura de Bodegas

Buenas Prácticas en Modelado MIP

Conclusión

Tags

Artículos Relacionados

Programación Lineal Avanzada con Python: Branch & Bound, …

Programación Lineal con Python: Guía Básica de Teoría …

Grafos Dirigidos y No Dirigidos: Una Visión Matemática …

Cómo Funciona Stable Diffusion: Guía Completa de Generación …

Tags

Situación	Formulación
Activar \(x\) solo si \(y=1\)	\( x \leq M \cdot y \) (Big-M)
Al menos K de N opciones	\( \sum_{i} y_i \geq K \)
Exactamente una opción	\( \sum_{i} y_i = 1 \)
Si A entonces B	\( y_A \leq y_B \)
Costo fijo + costo variable	\( \text{costo} = F \cdot y + c \cdot x \)