Método Simplex: Programación Lineal Resuelta

El método Simplex en lenguaje claro

¿Qué resuelve el Simplex?

Cualquier problema de la forma: maximizar (o minimizar) una función lineal sujeta a restricciones lineales con variables no negativas. Es la formulación matemática de miles de problemas reales: producción óptima, mezcla de ingredientes, asignación de presupuestos, planificación logística, dietas alimentarias, mezcla de inversiones.

La idea de George Dantzig (1947)

El conjunto de soluciones factibles de un problema lineal es un poliedro convexo. El óptimo siempre está en un vértice (a veces en varios, si hay óptimos múltiples). El Simplex se mueve de vértice en vértice mejorando la función objetivo hasta que ya no puede mejorar más. Es brillantemente eficiente en la práctica aunque teóricamente exponencial en el peor caso.

Forma estándar

Antes de aplicar Simplex, el problema se convierte a:

• Maximización (si es minimización, multiplica Z por -1).
• Restricciones ≤ b con b ≥ 0 (multiplica por -1 si b es negativo).
• Variables ≥ 0 (si una variable puede ser negativa, se descompone en x = x⁺ - x⁻).

Luego se agregan variables de holgura (slack) para convertir ≤ en =, variables de exceso + artificiales para ≥ y =.

Las dos fases

1. Fase I: encontrar una solución factible inicial. Se minimiza la suma de variables artificiales. Si el mínimo es 0, hay solución factible; si es positivo, el problema es infactible.
2. Fase II: con la solución básica factible de Fase I, optimizar la función objetivo original.

Si todas las restricciones son ≤ con b ≥ 0, se omite Fase I (la base inicial son las holguras).

Interpretación de la tabla final

• Variables básicas: las que tienen valor > 0 en la solución óptima.
• Variables no básicas: valen 0.
• Costos reducidos (fila Z): en máx, deben ser ≥ 0 al óptimo. Indican cuánto empeoraría Z si forzamos una unidad de esa variable no básica.
• Variables de holgura básicas: indican restricciones no activas (con sobra de recurso).
• Variables de holgura nulas: restricciones activas (recurso totalmente usado).

Análisis de sensibilidad

El Simplex no solo da el óptimo, también permite analizar cómo cambia la solución si cambian los parámetros. Los precios sombra (valores duales) dicen cuánto mejoraría Z si tuvieras una unidad más de cada recurso. Es la información más valiosa para gerentes.

Casos especiales que detecta el algoritmo

• Solución única óptima: el caso normal.
• Óptimos múltiples: cuando una variable no básica tiene costo reducido = 0 en el óptimo. Hay infinitas soluciones óptimas.
• No acotado: la función puede crecer indefinidamente. Indica error de modelado (faltó una restricción).
• Infactible: no existe ninguna solución que cumpla todas las restricciones. Restricciones contradictorias.
• Degenerado: una variable básica vale 0. Puede causar ciclos (resueltos con regla de Bland o lexicográfica).

Aplicaciones reales

• Producción: cuánto producir de cada producto dado el tiempo de máquina, materia prima y mano de obra disponible.
• Mezclas: cuánto de cada ingrediente para minimizar costo cumpliendo requisitos nutricionales (dieta humana, animal, combustible).
• Transporte: cuánto enviar de cada fábrica a cada destino minimizando costo total (caso especial: problema de transporte).
• Carteras: maximizar retorno dado un nivel de riesgo (con restricciones).
• Scheduling: asignar turnos minimizando costo de mano de obra.

Limitaciones

• Linealidad: todas las relaciones deben ser lineales. Para no lineales se usa programación cuadrática, no lineal, o aproximaciones lineales por partes.
• Variables continuas: si necesitas valores enteros (no se puede producir 0.7 autos), usa programación entera (branch and bound, planos cortantes).
• Determinístico: parámetros conocidos con certeza. Para incertidumbre, programación estocástica o robusta.

Tip de modelado: el 90% del trabajo en optimización es plantear correctamente el modelo (variables, función objetivo, restricciones). El Simplex es la parte fácil. Antes de programar, dibuja el problema en papel: ¿qué decides?, ¿qué quieres optimizar?, ¿qué te limita?.