Método Simplex de 2 Fases
Esta estrategia algoritmica se aplica cuando luego de llevar un modelo de programación lineal a su forma estándar no se dispone de una solución básica factible inicial.
Fase 1: Consideramos un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible. Luego se debe resolver utilizando el Método Simplex un nuevo problema que considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo alcanzado al finalizar la Fase 1 es cero ir a la Fase 2. En caso contrario, no existe solución factible.
Fase 2: Resolver a través del Método Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase1.
Ejemplo Simplex de 2 Fases
Considere el siguiente modelo de Programación Lineal:
FASE 1: Al agregar S1 como variable de exceso en la restricción 1 resulta evidente que no se dispone de una solución básica factible inicial, por tanto utilizaremos una variable auxiliar "y" que incluiremos en el lado izquierdo de la restricción y que servirá como variable básica inicial. Esto define el problema inicial de la Fase 1 junto a su tabla.
Luego la variable X2 entra a la base (costo reducido negativo) y claramente "y" deja la base. Se actualiza la tabla utilizando el método simplex:
Con esta tabla finaliza la Fase 1. Notar que el valor de la función objetivo al finalizar la Fase 1 es cero, por tanto podemos continuar la Fase 2.
FASE 2: Se elimina la columna asociada a la variable artificial "y" y se actualiza el vector de costos reducidos considerando la función objetivo original. De esta forma se obtiene la tabla inicial de la Fase 2.
Dado que X2 es variable básica al finalizar la Fase 1 buscamos dejar esta misma variable como básica al iniciar la Fase 2. Para ello multiplicamos por -3 la fila 1 y luego la sumamos a la fila 2.
En este sencillo ejemplo se llega inmediatamente a la tabla final de la Fase 2, con solución óptima X1=0 y X2=10. El valor óptimo V(P)=-30.