Mtodo de las dos fases

Captulo 6 Mtodo de las dos fases

Cj 4 1 M 0 M 0 V.B. b X1 X2 X3 X4 X5 X6 M X3 3 3 1 1 0 0 0 M X3 6 4 3 0 -1 1 0 0 X6 4 1 2 0 0 0 1 Zj - Cj 9M 7M-4 4M-1 0 -M 0 0

Cmo evitar usar la gran M Introduccin Como en el computador se usa la gran M, Un nmero muy grande, existe un efecto de error en los clculos, ya que la gran M tiende a infinito, para evitar usar la gran M, se diseo el Mtodo de las dos fases. Fase I Minimizar la suma de las variables de Super-Avit Artificiales, usadas en el problema. Si Z = 0 , proceder con la fase II Si Z es diferente de cero, el problema no tiene solucin Fase II Use la solucin de la fase I como solucin inicial factible de la fase II, teniendo en cuenta que todas las variables de Super-Avit Artificiales son iguales a cero.

101

Mtodo de las dos fases

Ejemplo

Fase I Min Z = 4X1 + X2 Min Z = 4X1 + X2 + MX3 + MX5 Min Z = X3 + X5 C.S.R. C.S.R. C.S.R.

3X1 + X2 = 3 3X1 + X2 + X3 = 3 3X1 + X2 + X3 = 3 4X1 + 3X2 > 6 4X1 + 3X2 X4 + X5 = 6 4X1 + 3X2 X4 + X5 = 6

X1 + 2X2 < 4 X1 + 2X2 + X6 = 4 X1 + 2X2 + X6 = 4 XJ > 0 ; J = 1,2 XJ > 0 ; J = 1,2,3,4,5,6 XJ > 0 ; J = 1,2,3,4,5,6

Fjese Que en la fase I , siempre ser Minimizar la suma de todas las variables Artificiales que tenga el problema. A continuacin procedemos a solucionar el problema planteado, usando el mtodo simplex, ya sea manualmente mediante el software Winqsb. De forma manual, los resultados son los siguientes:

Cj 0 0 1 0 1 0 V.B. b X1 X2 X3 X4 X5 X6 b/a 1 X3 3 3 1 1 0 0 0 1 (1/3) 1 X5 6 4 3 0 -1 1 0 3/2 0 X6 4 1 2 0 0 0 1 4 Zj - Cj 9 7 4 0 -1 0 0

Cj 0 0 1 0 1 0 V.B. b X1 X2 X3 X4 X5 X6 b/a 0 X1 1 1 1/3 1/3 0 0 0 3 (-4)(-1) 1 X5 2 0 5/3 -4/3 -1 1 0 6/5 (3/5) 0 X6 3 0 5/3 -1/3 0 0 1 9/5 Zj - Cj 2 0 5/3 -7/3 -1 0 0

Cj 0 0 1 0 1 0 V.B. b X1 X2 X3 X4 X5 X6 0 X1 3/5 1 0 3/5 1/5 -1/5 0 0 X2 6/5 0 1 -4/5 -3/5 3/5 0 (-1/3)(-5/3) 0 X6 1 0 0 1 1 -1 1 Zj - Cj 0 0 0 -1 0 -1 0

102

Mtodo de las dos fases

Fjese Que aqu Z* = 0 Fase II Con la solucin ptima de la fase I, planteamos el siguiente problema:

Min Z = 4X1 + X2 Min Z = 4X1 + X2 C.S.R. C.S.R. X1 + 3/5X3 + 1/5X4 1/5X5 = 3/5 X1 + 1/5X4 = 3/5

X2 4/5X3 3/5X4 + 3/5X5 = 6/5 X2 3/5X4 = 6/5 X3 + X4 X5 +X6 = 1 + X4 +X6 = 1

XJ > 0 ; J = 1,2,3,4,5,6

En la fase I, establecimos que X3 = X5 = 0 Luego las eliminamos de las restricciones XJ > 0 ; J = 1,2,4,6

Fjese que el nuevo problema no tiene la gran M, ya que han dejado de figurar las variables Artificiales, en atencin a que ya sabemos que efectivamente son iguales a cero. La solucin al nuevo problema se halla mediante el mtodo simplex. As:

Cj 4 1 0 0 V.B. b X1 X2 X4 X6 b/a 4 X1 3/5 1 0 1/5 0 3 1 X2 6/5 0 1 -3/5 0 NO 0 X6 1 0 0 1 1 1 (1) Zj - Cj 18/5 0 0 1/5 0

Cj 4 1 0 0 V.B. b X1 X2 X4 X6 4 X1 2/5 1 0 0 -1/5 1 X2 9/5 0 1 0 3/5 0 X4 1 0 0 1 1 (-1/5)(3/5) Zj - Cj 17/5 0 0 0 -1/5

Solucin X1* = 2/5 X2* = 9/5 Z * = 17/5

X4* = 1 X6* = 0

X3* = X5* = 0

103

Mtodo de las dos fases

Nota: El lector debe resolver el ejemplo, empleando el mtodo simplex con la gran M y comparar los tableros con los del mtodo de las dos fases, para observar que el mtodo de las dos fases, lo que hace es evitar los tableros en donde figura la gran M.

Ejercicios propuestos Resolver empleando el mtodo de las dos fases, todos los ejercicios resueltos y propuestos de los captulos 4 y 5 que usen la gran M.

104