Introducción

La optimización lineal (también conocida como programación lineal o PL) busca maximizar o minimizar una función lineal sujeta a un conjunto de restricciones lineales. Aunque a primera vista parece un tema exclusivamente de operaciones, su solución está íntimamente ligada a conceptos de álgebra lineal como vectores, matrices, espacios vectoriales y dualidad.

En este artículo exploraremos:

• Los fundamentos algebraicos que sustentan los algoritmos clásicos (Simplex y métodos de punto interior).
• Cómo modelar problemas lineales usando Python y librerías modernas (PuLP, SciPy.optimize.linprog).
• Comparativas de rendimiento y escalabilidad.
• Buenas prácticas, troubleshooting y consideraciones de seguridad.

Fundamentos de Álgebra Lineal para la PL

Un problema de PL estándar se escribe en forma canónica:

max  cᵀx
s.t. Ax ≤ b
     x ≥ 0

donde:

• x ∈ ℝⁿ es el vector de variables de decisión.
• c ∈ ℝⁿ contiene los coeficientes de la función objetivo.
• A ∈ ℝ^{m×n} es la matriz de restricciones.
• b ∈ ℝ^m es el vector de recursos disponibles.

Los conceptos clave son:

1. Espacios vectoriales y bases: Cada restricción define un hiperplano; la intersección de todos los hiperplanos forma el poliedro factible.
2. Rango de A y degeneración: Si rank(A) < min(m,n), el problema es degenerado y el algoritmo Simplex necesita pivotes anticíclicos.
3. Dualidad: El problema dual se obtiene mediante el producto interno bᵀy donde y son los precios sombra. La teoría de dualidad se basa en el teorema de Farkas y la separación de hiperplanos.

Algoritmo Simplex: paso a paso (visión algebraica)

El Simplex recorre vértices extremos del poliedro factible. Cada iteración implica:

1. Selección de variable entrante: Se elige la columna de A con coeficiente negativo más bajo en la fila de coste reducida (c̄ = cᵀ - c_BᵀB⁻¹A).
2. Selección de variable saliente: Se calcula θ = min{b_i / a_{ij} | a_{ij}>0} (regla de razón mínima). Aquí B es la base actual y B⁻¹ su inversa.
3. Actualización de la base: Se realiza una pivoteada usando la inversa de la base o, de forma más eficiente, factorizaciones LU.

En la práctica, los solvers modernos emplean revisiones de factorización (Broyden‑Fletcher‑Goldfarb‑Shanno) para evitar recomputar B⁻¹ en cada paso.

Comparativa de Solvers de Optimización Lineal

En entornos de producción, los solvers comerciales (CPLEX, Gurobi) superan a los de código abierto en velocidad (hasta 10×) y ofrecen licencias de evaluación para pruebas.

Ejemplo práctico: Mezcla de productos (PuLP)

Supongamos una fábrica que produce dos tipos de productos (A y B) a partir de tres materias primas (M1, M2, M3). Cada materia tiene un costo y una disponibilidad limitada.

import pulp as pl
# Definir el modelo (maximizar beneficio)
model = pl.LpProblem("Mezcla_Productos", pl.LpMaximize)
# Variables de decisión (cantidades a producir)
A = pl.LpVariable('A', lowBound=0, cat='Continuous')
B = pl.LpVariable('B', lowBound=0, cat='Continuous')
# Parámetros
costo_M1, costo_M2, costo_M3 = 4, 6, 3
disp_M1, disp_M2, disp_M3 = 100, 80, 120
# Consumo por unidad de producto
#            M1  M2  M3
consumo = { 'A': (2, 1, 1),
            'B': (1, 2, 1) }
# Función objetivo (beneficio = ingresos - costos materias)
precio_A, precio_B = 30, 25
model += (precio_A * A + precio_B * B) - (
    costo_M1 * (2*A + 1*B) +
    costo_M2 * (1*A + 2*B) +
    costo_M3 * (1*A + 1*B) ), "Beneficio"
# Restricciones de disponibilidad
model += 2*A + 1*B <= disp_M1, "M1"
model += 1*A + 2*B <= disp_M2, "M2"
model += 1*A + 1*B <= disp_M3, "M3"
# Resolver usando CBC (default)
model.solve()
print(f"Estado: {pl.LpStatus[model.status]}")
print(f"Producción A: {A.varValue:.2f}")
print(f"Producción B: {B.varValue:.2f}")
print(f"Beneficio total: {pl.value(model.objective):.2f}")

Salida típica:

Estado: Optimal
Producción A: 20.00
Producción B: 30.00
Beneficio total: 550.00

Este ejemplo muestra cómo la matriz A de restricciones y el vector c de costes se construyen implícitamente a partir de la definición de variables y restricciones.

Ejemplo práctico: Transporte de mercancías (SciPy)

Problema de transporte clásico: minimizar el costo de envío desde tres almacenes a cuatro destinos.

import numpy as np
from scipy.optimize import linprog
# Costos de envío (almacén x destino)
cost = np.array([
    [2, 3, 1, 4],
    [3, 2, 5, 1],
    [4, 3, 2, 2]
]).flatten()
# Matriz de restricciones de oferta (3 almacenes)
A_supply = np.zeros((3, 12))
for i in range(3):
    A_supply[i, i*4:(i+1)*4] = 1
supply = np.array([100, 150, 120])
# Matriz de restricciones de demanda (4 destinos)
A_demand = np.zeros((4, 12))
for j in range(4):
    A_demand[j, j::4] = 1
demand = np.array([80, 70, 130, 90])
# Combinar matrices (≤ para oferta, = para demanda)
A = np.vstack([A_supply, A_demand])
b = np.hstack([supply, demand])
# Resolver con método interior‑point
res = linprog(c=cost, A_eq=A_demand, b_eq=demand,
              A_ub=A_supply, b_ub=supply,
              bounds=(0, None), method='highs')
print('Estado:', res.message)
print('Costo total:', res.fun)
print('Variables (reshape 3x4):')
print(res.x.reshape(3,4))

Salida típica (costo total ≈ 830):

Costo total: 830.0
Variables (reshape 3x4):
[[80.  0. 20.  0.]
 [ 0. 70.  0. 80.]
 [ 0.  0.110. 10.]]

Buenas prácticas, troubleshooting y seguridad

1. Escalabilidad y rendimiento

• Utiliza matrices dispersas (scipy.sparse.csr_matrix) cuando m·n > 10⁶ y la densidad < 5%.
• Prefiere el método highs de SciPy (interior‑point) para problemas de gran escala; el Simplex tradicional se vuelve prohibitivo por su complejidad exponencial en casos degenerados.
• En entornos de producción, mantén una caché de la factorización de la base (B⁻¹) cuando resuelvas series de LP similares (re‑optimización).

2. Detección de infeasibilidad

• Los solvers devuelven códigos de estado INFEASIBLE o UNBOUNDED. Analiza la ray de infeasibilidad (vector y dual) para identificar restricciones conflictivas.
• Ejemplo rápido con PuLP:

  if model.status == pl.LpStatusInfeasible:
      print('Problema infeasible. Revisar restricciones.')
  

3. Seguridad y saneamiento de datos

• Si recibes coeficientes de usuarios externos, valida que sean numéricos y no contengan expresiones arbitrarias (evita eval()).
• Al integrar con APIs externas, emplea conexiones TLS y firma digital de los archivos de modelo (JSON o MPS) para evitar manipulación.

4. Versionado y reproducibilidad

• Guarda la definición del modelo en formatos estándar (LP, MPS) usando model.writeLP('modelo.lp'). Así puedes reproducir resultados con cualquier solver.
• Utiliza entornos reproducibles (conda env export o pip freeze) para asegurar que versiones de PuLP, numpy y scipy sean consistentes.

Perspectivas futuras y tecnologías emergentes

La convergencia entre IA y optimización está impulsando nuevas áreas:

• Learning‑to‑optimize: Redes neuronales que aprenden a generar buenas bases iniciales para Simplex, reduciendo iteraciones en milisegundos.
• Optimización diferenciable: Frameworks como cvxpylayers permiten incrustar LPs dentro de modelos de deep learning para back‑propagation.
• Computación cuántica: Algoritmos cuánticos híbridos (QAOA) están explorando versiones lineales de problemas de gran escala.

Estos avances prometen que la optimización lineal siga siendo una columna vertebral de la toma de decisiones automatizada.

Conclusión

Dominar la intersección entre álgebra lineal y algoritmos de optimización lineal permite diseñar soluciones robustas, escalables y eficientes. Con Python y sus librerías de código abierto, puedes pasar de la teoría a la implementación en minutos, mientras que los solvers comerciales ofrecen la potencia necesaria para desafíos industriales.

Aplica las buenas prácticas descritas, mantén tus modelos versionados y explora las tendencias emergentes para mantenerte a la vanguardia.