I.O 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. Se puede resumir así:
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 incluyavariables 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ónredundante 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 lasvariables 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 modelooriginal 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 seactualizan 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
A3Solucion
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...