METODO SIMPLEX EN DOS FASES

METODO SIMPLEX EN DOS FASES

El procedimiento consiste en resolver el modelo en dos etapas o fases. En la primera, se busca obtener una SBF del modelo aumentado, que no incluya variables artificiales. Cuando en esta solución básica factible del MA, todas las variables artificiales valen cero, ella es una solución básica factible inicial del Modelo original y a partir de ahí se inicia la segunda fase del método simplex. Pero puede ocurrir que en la fase 1 no sea posible extraer todas las variables artificiales de la solución básica, presentándose los casos de: restricción redundante analíticamente, solución infactible, inexistencia de solución; situaciones que discutiremos más adelante.

Veamos cual es el procedimiento en cada fase del algoritmo.

Fase 1

Empieza con una solución básica factible inicial artificial y equivale al paso inicial del método simplex que conocemos, ya que en ella se trata de hallar una SBFI del modelo original.

Para propiciar que las variables artificiales tomen el valor de cero, se construya una función objetivo que reemplaza provisionalmente a la del modelo original. Esta nueva función se forma con la suma de las variables artificiales y el objetivo es minimizar la suma de ellas. Es importante aclarar que el objetivo de la fase 1, siempre es minimizar la suma de las variables artificiales, aunque el objetivo del modelo original sea maximizar o minimizar.

Fase 2

Consiste en buscar la solución óptima del modelo original partiendo de la SBFI hallada en la Fase 1. Equivale a los pasos 1 y 2 del método simplex.

Para iniciar la Fase 2 se toma el tablero final de la Fase 1 y se le escribe la función objetivo original del problema, en lugar de la provisional que habíamos escrito para iniciar la Fase 1. Enseguida se actualizan la fila Cj y la columna CB, para luego recalcular los valores Zj y Ej, asi como el valor Z. A partir de esta tablero se continúa el Método Simplex para la búsqueda de la solución óptima, considerando el objetivo del problema original.

Ejemplo de aplicacion del modelo de las dos faces

Supóngase que deseamos hallar la solución óptima del modelo:

Maximizar:Z =

100X1 + 90X2

sujeta a: 6X1 + 4X2 24

20X1+ 8X2 160

3X1 + 2X2 15

1X2 5

Con

X1, X2 0

Escribimos el modelo en formato estándar y le agregamos las variables artificiales necesarias, para obtener el siguiente modelo ampliado:

Maximizar: Z = 100X1+ 90X2+ 0E1+ 0H2+ 0E3+ 0H4

sujeta a: 6X1 + 4X2 – 1E1 + 1A1 = 24

20X1 + 8X2 + 1H2 = 160

3X1 + 2X2 - 1E3 +1A3 = 15

1X2 + 1H4 = 5

Con X1, X2 0 ; Hi 0 ; Ei 0 ; Ai 0

Fase 1 de la solucion

Vamos a determinar la solución óptima del Modelo Aumentado, la cual será la SBFI del modelo original. Para ello planteamos la nueva función objetivo, así:

Z1= A1 + A2 ; que vamos a minimizar.

Por lo tanto el modelo por resolver queda:

Minimizar:Z1 = A1 + A2

sujeta a: 6X1 + 4X2 – 1E1 + 1A1 = 24

20X1 +8X2 + H2 = 160

3X1 + 5X2 - 1E3 +1A3 = 15

1X2 + 1H4 = 5

Con

X1, X2 0 ; Hi 0 ; Ei 0 ; Ai 0

La tabla inicial para resolver este modelo es:

Tabla 0 Fase I

Cj 0 0 0 0 0 0 1 1

CB X1 X2 E1 H2 E3 H4 A1 A3 Solucion XB

1 6 4 -1 0 0 0 1 0 24 A1

0 20 8 0 1 0 0 0 0 160 H2

1 3 5 0 0 -1 0 0 1 15 A3

0 0 1 0 0 0 1 0 0 5 H4

Zj 9 9 -1 0 -1 0 0 0 0 Z1

Ej -9 -9 1 0 1 0 0 0

Ahora procedamos con el Simplex, para buscar la solución óptima del modelo aumentado. Como el objetivo es minimizar, la variable de entrada puede ser X1 ó X2 pues ambas tienen el efecto neto más negativo. Seleccionamos arbitrariamente a X1 como variable de entrada. La variable de salida será A1 como se indica a la derecha de la tabla 0.

La nueva tabla es:

Tabla 1 Fase I

Cj 0 0 0 0 0 0 1 1

CB X1 X2 E1 H2 E3 H4 A1 A3 Solucion XB

0 1 2/3 -1/6 0 0 0 1/6 0 4 X1

0 0 -16/3 10/3 1 0 0 -10/3 0 80 H2

1 0 3 1/2 0 -1 0 -1/2 1 3 A3

0 0 1 0 0 0 1 0 0 5 H4

Zj 0 3 1/2 0 -1 0 -1/2 1 3 Z1

Ej 0 -3 -1/2 0 1 0 3/2 0

Esta solución es mejorable entrando a X2 y sacando a A3, con lo cual se obtiene la tabla siguiente:

Tabla 2 Fase I

Cj 0 0 0 0 0 0 1 1

CB X1 X2 E1 H2 E3 H4 A1 A3 Solucion XB

0 1 0 -5/18 0 2/9 0 5/18 -2/9 10/3 X1

0 0 0 38/9 1 -16/9 0 -38/9 16/9 256/3 H2

0 0 1 1/16 0 -1/3 0 -1/6 1/3 1 X2

0 0 0 -1/6 0 1/3 1 1/6 -1/3 4 H4

Zj 0 0 0 0 0 0 0 0 0 Z1

Ej 0 0 0 0 0 0 1 1

La tabla actual representa la solución óptima de la fase 1 del Modelo Aumentado, ya que todos los evaluadores de la fila cero son no positivos (además, el valor de Z1 es cero). Como todas las variables artificiales están fuera de la base, esta solución es una SBFI para el modelo original y podemos continuar con la fase siguiente.

Antes de proceder notemos que en las tablas de la fase 1, se observa la misma característica llamada efecto espejo que mencionamos al estudiar el método de las M’s

Obviamente la eliminación no debe efectuarse cuando la variable artificial, corresponde a una restricción de igualdad, pues en ese caso no hay variable de holgura.

Actualizando el renglón de Cj y la columna CB, para luego recalcular los valores Zj y Ej; así como el valor de Z ; y eliminando las columnas de A1 y A2 obtenemos la nueva tabla, así:

Fase 2 de la Solucion

Tabla 3 (Max )

Cj 100 90 0 0 0 0

CB X1 X2 E1 H2 E3 H4 Solucion XB

100 1 0 -5/18 0 2/9 0 10/3 A1

0 0 0 38/9 1 -16/9 0 256/3 H2

...