Metodo De Las Dos Fases

MÉTODO DE LAS DOS FASES

El Método de las Dos Fases es una variante del Algoritmo simplex, que es usado como alternativa al Método de la Gran M, donde se evita el uso de la constante M para las variables artificiales.

Este es otra variante del simplex que se aplica para resolver modelos de PL que requieren una matriz unitaria de base artificial para poder iniciar el algoritmo. El nombre indica que consiste de dos fases: En la 1ª, se reducen las artificiales Wi a cero y en tal caso se optimiza en la 2ª, o bien, se concluye que no hay solución factible para el problema porque Wi es diferente de cero en fase 1, y por lo tanto no es necesaria la fase2.

PRIMERA FASE

En este método siempre se minimiza una función objetivo constituida por la suma de las variables artificiales utilizadas para completar la matriz I:

Las variables artificiales son útiles para formar la primera base del simplex, pero si se logra que toda Wi = 0, entonces Z = 0 representa lo deseable u óptimo, pues lo contrario significa un problema que no tiene solución factible, en tal caso no aplica la segunda fase. Si todo va bien, las variables artificiales Wi deben salir de la base, excepto en algún caso degenerado en que Wi = 0, es básica.

SEGUNDA FASE

Se continúa con ésta sólo si ocurre la optimización del problema en la fase anterior. Para ello sirve la tabla simplex óptima de la primera, que se ajusta eliminando las columnas de las variables artificiales Wi; además, el renglón Z se cambia a los coeficientes de la función Z original. El procedimiento continúa con el arreglo de la tabla simplex inicial para cumplir los requisitos necesarios de una solución básica factible; es decir, coeficientes cero para las variables básicas en el renglón Z de la tabla. A veces esto es suficiente para lograr el óptimo del problema; si no es así, se aplican los criterios del simplex para el objetivo original del problema. En resumen, la fase1 intenta lograr un punto extremo factible; la fase 2, el punto extremo óptimo:

EL ALGORITMO DE LAS DOS FASES

Escríbase el PPL en forma estándar:

En donde A es una matriz m x n de rango completo por filas.

Si A contiene una submatriz identidad m x m y b ≥ 0m

Permiten definir una SPB inicial para aplicar el algoritmo del Simplex:

En otro caso, A se completa con tantas columnas (variables artificiales) como

sea necesario para conseguir dicha situación, y se aplica el algoritmo de las

2 fases.

FASE 1: Construir el problema auxiliar resultante de añadir las variables artificiales:

Resolver el problema auxiliar con el algoritmo del Simplex. Sea (x*, xa*) la solución óptima.

FASE 2: Utilizar la SPB obtenida al final de la Fase 1 para resolver el problema inicial. Sean Xb las variables básicas en dicha solución. Consideremos la tabla óptima al final de la Fase 1.

. Si en Xb NO HAY variables artificiales: eliminando las columnas asociadas a las variables artificiales y actualizando convenientemente la fila asociada a la función objetivo obtenemos la tabla inicial para resolver el problema original con el algoritmo Simplex.

. Si en Xb HAY variables artificiales: tratamos de obtener una SPB sin variables artificiales.

EJEMPLO 1

Min Z = X1 + 2X2

Sujeto a:

X1 + X2 ≥ 2

-X1 + X2 ≥ 3

X1 + 3X2 ≤ 12

X1, X2 ≥ 0

ESTANDARIZAMOS

Min Z = X1 + 2X2 + 0S1 + 0S2 + 0S3 + MA1 + MA2

Sujeto a:

X1 + X2 – S1 + A1 = 2

-X1 + X2 - S2 + A2 = 3

X1 + 3X2 + S3 = 12

X1, X2, S1, S2, S3, A1, A2 ≥ 0

INICIO DEL MÉTODO DE LAS DOS FASES:

Min Z = A1 + A2

Sujeto a:

X1 + X2 – S1 + A1 = 2

-X1 + X2 - S2 + A2 = 3

X1 + 3X2 + S3 = 12

X1, X2, S1, S2, S3, A1, A2 ≥ 0

FASE 1

En la siguiente figura encontramos la tabla simplex clásica. En la segunda fila los nombres de las variables de decisión, y justo arriba de ellas, los coeficientes de estas variables en la función objetivo. Cómo en la primera fase minimizamos la suma de las variables artificiales, por eso sólo encontramos un valor de 1 arriba de A1 (variable artificial 1) y de A2 (variable artificial 2).

Se espera que el valor de la Z óptima sea cero para proseguir a la fase 2, de lo contrario el problema no tiene solución.

Cj 0 0 0 0 0 1 1

CB VB X1 X2 S1 S2 S3 A1 A2 Bi RAZON

1 A1 1 1 -1 0 0 1 0 2 2

1 A2 -1 1 0 -1 0 0 1 3 3

0 S3 1 3 0 0 1 0 0 12 4

Zj 0 2 -1 -1 0 1 1 5

Cj - Zj 0 -2 1 1 0 0 0

Cj 0 0 0 0 0 1 1

CB VB X1 X2 S1 S2 S3 A1 A2 Bi RAZON

0 X2 1 1 -1 0 0 1 0 2 --------

1 A2 -2 0 1 -1 0 -1 1 1 1

0 S3 -2 0 3 0 1 -3 0 6 2

Zj -2 0 1 -1 0 -1 1 1

Cj - Zj 2 0 -1 1 0 2 0

Cj 0 0 0 0 0 1 1

CB VB X1 X2 S1 S2 S3 A1 A2 Bi RAZON

0 X2 -1 1 0 -1 0 0 1 3

0 S1 -2 0 1 -1 0 -1 1 1

0 S3 4 0 0 3 1 0 -3 3

Zj 0 0 0 0 0 0 0 0

Cj - Zj 0 0 0 0 0 1 1

Se pudo observar que a medida que se iban haciendo las tablas el Z iba disminuyendo. Ahora como el Z óptimo es igual a cero procedemos a la FASE 2:

FASE 2

En la FASE 2, cambiaremos la fila de la función objetivo y dejamos la de la función original, pero como en la fase 1 nos aseguramos de eliminar las variables artificiales, en la fase 2, las podemos eliminar también, como es lógico, las borramos de las restricciones. Ahora, sin estorbos, sin constantes M, o variables artificiales resolvemos por el método simplex tradicional.

Cj 1 2 0 0 0

CB VB X1 X2 S1 S2 S3 Bi RAZON

2 X2 -1 1 0 -1 0 3

0 S1 -2 0 1 -1 0 1

0 S3 4 0 0 3 1 3

Zj -2 2 0 -2 0 6

Cj - Zj 3 0 0 2 0

Como estamos minimizando, en la fila Cj - Zj no deben existir números negativos y efectivamente, no hay; Por tal motivo nos encontramos en la tabla optima, así nuestro Z = 6 con X1 =0 y X2 = 3.

Si resolvemos este problema de PL por el método de la gran M obtendremos el mismo resultado, Para corroborar anexaremos la salida del programa winQSB el cual resolverá el problema por el método de la gran M.

Se observa que el Z es el mismo.

EJEMPLO 2

Min Z = 5X1 + 4X2 + 7X3

Sujeto a:

4X1 + 5X2 + 3X3 = 100

3X1 + 7X2 + X3 ≤ 150

2X1 + 4X2 +

...