Metodo de las dos fases

Este método elimina el uso de la M y resuelve el problema en dos fases. En la fase I se utiliza el algoritmo simplex para suministrar a la fase II una forma factible de partida. Es decir, el producto final de la Fase I es una solución básica factible (en caso de que exista), en forma típica, para iniciar la Fase II del método. Los pasos de cada fase son lossiguientes:

Fase I
1. Utilice el algoritmo simplex para obtener la minimización de la suma de las variables artificiales, sujeta a las mismas restricciones del problema original, independientemente de si este problema original es de maximización o minimización.

2. Si la suma de las variables artificiales, X0, es mayor que cero, entonces no existe una solución básica factible y se termina el proceso. Si X0= 0, entonces inicie la Fase II del algoritmo.

Fase II
1. Utilice la solución óptima obtenida en la Fase I como solución de partida al problema 1. original, remplazando la función objetivo original Z por la de X0. Como es usual, la función objetivo original debe ser expresada en función de las variables no básicas. Si al final de la Fase I las variables artificiales son no básicas, se eliminan de la Fase II. Si alguna variable artificial es básica, pero a un nivel cero, esta variable se mantiene en el conjunto de variables básicas, pero debe garantizarse que su valor nunca será mayor que cero durante la ejecución de la Fase II. Ejemplo:

MIN W = 3 X1 + 4 X2

Resolver el anterior problema de Programación Lineal por el Método de las Dos Fases.
Solución analítica:

Fase I :
Paso 1 Se introducen las variables artificiales A1 y A2, las variables de exceso S1 y S2.

MIN X0 = A1 + A2

Con sus restricciones:

FASE I:
Puesto que A1 y A2 son variables básicas, sus coeficientes en la fila X0 deben ser cero (0); para ello sumamos las filas (1) y (1) a la fila (0). El tablero inicial para la aplicación del algoritmo simples es:

TABLERO 1 SIMPLEX
0
0
Cj
0
0
0
0
1
1
CB
VB
B
X1
X2
S1
S2
A1
A2
1
A1
20
2
3
-1
0
1
0
1
A2
30
1
5
0
-1
0
1
0
X0
50
3
8
-1
-1
1

1 Entra a la base X2 y sale de la base A2

VB
VNB

A1 = 20A2 = 30 X1 = 0X2 = 0S1 = 0S2 = 0 X0 = 50

TABLERO 2 SIMPLEX
CB
VB
b
X1
X2
S1
S2
A1
A2
1
A1
2
7/5
0
-1
3/5
1
-3/5
0
X2
6
1/5
1
0
-1/5
0
1/5
0
X0
2
7/5
0
-1
3/5
1

-3/5 Entra a la base X1 y sale de la base A1 VB VNB A1 = 2X2 = 6X1 = 0A2 = 0S1 = 0S2 = 0X0 = 2

TABLERO 3 SIMPLEX
CB
VB
b
X1
X2
S1
S2
A1
A2
0
X1
10/7
1
0
-5/7
3/7
5/7
-3/7
0
X2
40/7
0
1
1/7
-2/7
-1/7
2/7
0
X0
0
0
0
0
0
0
0

Al aplicar el método simplex a nuestro problema en la tercera etapa de la fase I se ha encontrado que mín X0 = 0 y no existen variables artificiales en la base. Por lo tanto, se ha encontrado una solución básica posible al problema original.FASE II:

Empleamos la función objetivo original W en lugar de X0 y eliminamos las variables artificiales A1 y A2, puesto que ya no son variables básicas, es decir, son variables no básicas. Como la función objetivo debe estar expresada en términos de las variables no básicas, entonces se deben realizar transformaciones para reducir a cero el coeficiente de X1 y X2 en la función objetivo.

TABLA