El Método de las Dos Fases en Programación Lineal (Guía paso a paso)
Aprende a resolver problemas de programación lineal con variables artificiales usando el Método Simplex de las Dos Fases, una alternativa robusta al método de la Gran M.
Por Qué Existe el Método de las Dos Fases
El algoritmo Simplex estándar requiere una solución básica factible inicial (SBF) para comenzar a iterar. Para problemas que sólo contienen restricciones ≤, esto es trivial: añadir una variable de holgura a cada restricción proporciona instantáneamente una base identidad, y el origen (todas las variables de decisión = 0) es factible.
Sin embargo, cuando un modelo incluye restricciones de ≥ o =, el origen ya no es factible y no existe una base inicial obvia. El Método de las Dos Fases resuelve esto evitando el uso de constantes arbitrariamente grandes, con mayor estabilidad numérica que el método de la Gran M.
Configuración del Problema: Forma Estándar
Considera el siguiente programa lineal (PL):
Maximizar Z = 2x&sub1; + 3x&sub2;
Sujeto a:
x&sub1; + x&sub2; ≤ 4 (restricción 1)
x&sub1; + 2x&sub2; ≥ 6 (restricción 2)
x&sub1;, x&sub2; ≥ 0
Para convertirlo a forma estándar:
- Restricción 1 (≤): añadir variable de holgura s&sub1; → x&sub1; + x&sub2; + s&sub1; = 4
- Restricción 2 (≥): restar variable de exceso s&sub2; y añadir variable artificial a&sub1; → x&sub1; + 2x&sub2; − s&sub2; + a&sub1; = 6
Fase I: Encontrar una Solución Básica Factible Inicial
Olvida la función objetivo original Z. Construye una función objetivo auxiliar:
Minimizar W = a&sub1;
Si podemos llevar W a cero, habremos eliminado todas las variables artificiales de la base, lo que significa que tenemos una SBF genuina para el problema original.
Paso 1 — Construir el Tableau de Fase I
La fila W inicial debe actualizarse mediante operaciones de fila preliminares para que el coeficiente de a&sub1; sea cero en la fila objetivo:
Fila-W = Fila-W − (restricción 2)
⇒ W + x&sub1; + 2x&sub2; − s&sub2; = 6
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | a&sub1; | LD |
|---|---|---|---|---|---|---|
| W | 1 | 2 | 0 | −1 | 0 | 6 |
| s&sub1; | 1 | 1 | 1 | 0 | 0 | 4 |
| a&sub1; | 1 | 2 | 0 | −1 | 1 | 6 |
Paso 2 — Iteración 1
- Variable de entrada: x&sub2; (mayor coeficiente positivo en fila W para minimización).
- Prueba de razón mínima: Fila s&sub1;: 4/1 = 4; Fila a&sub1;: 6/2 = 3 ← mínimo. Sale a&sub1;.
- Pivote: Dividir fila pivote entre 2, luego eliminar x&sub2; de las demás filas.
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | a&sub1; | LD |
|---|---|---|---|---|---|---|
| W | 0 | 0 | 0 | 0 | −1 | 0 |
| s&sub1; | 1/2 | 0 | 1 | 1/2 | −1/2 | 1 |
| x&sub2; | 1/2 | 1 | 0 | −1/2 | 1/2 | 3 |
W = 0. Fase I completada. SBF: x&sub1; = 0, x&sub2; = 3, s&sub1; = 1, s&sub2; = 0.
Fase II: Optimizando el Objetivo Original
Ahora usamos la SBF encontrada para resolver el problema original. Eliminamos la columna a&sub1; y reemplazamos la fila W con la fila Z original, reexpreasada en términos de variables no básicas actuales.
Paso 3 — Tableau de Fase II inicial
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | LD |
|---|---|---|---|---|---|
| Z | −1/2 | 0 | 0 | −3/2 | −9 |
| s&sub1; | 1/2 | 0 | 1 | 1/2 | 1 |
| x&sub2; | 1/2 | 1 | 0 | −1/2 | 3 |
Paso 4 — Iteración 2
- Variable de entrada: s&sub2; (coeficiente más negativo −3/2 en fila Z).
- Prueba de razón mínima: Fila s&sub1;: 1 ÷ (1/2) = 2. s&sub1; sale.
- Pivote: Multiplicar fila pivote por 2, luego eliminar s&sub2; de demás filas.
Tableau final óptimo:
| VB | x&sub1; | x&sub2; | s&sub1; | s&sub2; | LD |
|---|---|---|---|---|---|
| Z | 2 | 0 | 3 | 0 | −12 |
| s&sub2; | 1 | 0 | 2 | 1 | 2 |
| x&sub2; | 1 | 1 | 1 | 0 | 4 |
Todos los coeficientes Z son no negativos → solución óptima alcanzada: x&sub1; = 0, x&sub2; = 4, Z = 12.
¿Qué Pasa si la Fase I Termina con W > 0?
Si el valor mínimo de W es estrictamente mayor que cero, al menos una variable artificial permanece en la base con valor positivo. Esto significa que el problema original es infactible: no existe ningún punto en la región factible. Detén el proceso; no tiene sentido continuar a la Fase II.
Dos Fases vs. Gran M: Comparativa
| Propiedad | Método Dos Fases | Método Gran M |
|---|---|---|
| Estabilidad numérica | Alta (sin constantes grandes) | Menor (M puede causar pérdida de precisión) |
| Facilidad de configuración | Moderada (dos PLs separados) | Simple (un solo PL) |
| Detección de infactibilidad | W > 0 al final de Fase I | Variable artificial en base final |
| Preferencia en software | Preferido por la mayoría de solucionadores | Común en ejemplos manuales de libros de texto |
Conclusión
El Método de las Dos Fases es el estándar para manejar restricciones de ≥ e = en programación lineal. Al separar limpiamente la detección de factibilidad (Fase I) de la optimización real (Fase II), evita los problemas numéricos de una penalización grande arbitraria y proporciona una señal clara cuando un problema no tiene solución factible.