• Author / Uploaded
• Hernán Huaynates

Citation preview

2.3. HACER EL ÁNALISI DE MÉTODO SIMPLEX DE DOS FASES MÉTODO DE DOS FASES El Método Simplex de Dos Fases permite abordar la resolución de aquellos modelos de Programación Lineal que luego de ser llevados a su forma estándar no permite obtener una solución básica factible inicial en las variables del modelo. EJEMPLO MÉTODO SIMPLEX DE DOS FASES: Considere el siguiente modelo de Programación Lineal usando el Método Simplex de Dos Fases.

Min z =160 X 1+120 X 2+280 X 3 S.a.:

2 X 1+ X 2+ 4 X 3 ≥ 1 2 X 1+ 2 X 2+2 X 3 ≥

3 2

X 1 , X 2, X 3 ≥ 0 FASE I (MÉTODO SIMPLEX DE DOS FASES) Formule un nuevo problema reemplazando la función objetivo por la suma de las variables artificiales. La nueva función objetivo se minimiza sujeta a las restricciones del problema original. Si el problema tiene un espacio factible el valor mínimo de la función objetivo óptima será cero, lo cual indica que todas las variables artificiales son cero. En este momento pasamos a la fase 2. * Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles. SOLUCIÓN: Para llevar el problema a la forma estándar agregamos las variables de exceso no negativas  X 4  y  X 5 para la primera y segunda restricción , también agregaremos 2 variables artificiales (o variables auxiliares) no negativas que llamaremos X6 y X7 (una para cada restricción) que nos permitirá tener una solución básica factible inicial. El problema queda como sigue:

Min z =160 X 1+120 X 2+280 X 3 S.a.:

2 X 1+ X 2+ 4 X 3−X 4 + X 6=1 2 X 1+ 2 X 2+2 X 3−X 5+ X 7= X i≥ 0 , i=1,2,3,4,5

3 2

Luego, el método en su Fase I minimiza la suma de las variables auxiliares (en este caso 2 variables artificiales). En consecuencia, el problema de la Fase I queda definido por:

Min z =X 6+ X 7 S.a.:

2 X 1+ X 2+ 4 X 3−X 4 + X 6=1 2 X 1+ 2 X 2+2 X 3−X 5+ X 7=

3 2

X i≥ 0 , i=1,2,3,4,5 Construimos la tabla inicial de la Fase 1: XB X6 X7  Z

X1 2 2 0

X2 1 2 0

X3 4 2 0

X4 -1 0 0

X5 0 -1 0

X6 1 0 1

X7 0 1 1

bi 1  3/2 0

Fila 1 Fila 2 Fila 3

Para utilizar X6 y X7 como variables básicas necesitamos llevar sus costos reducidos a cero. Para ello realizamos operaciones fila multiplicando la fila 1 por -1 y luego sumando a la fila 3. Repetimos el procedimiento multiplicando por -1 la fila 2 y sumando a la fila 3. La tabla actualizada corresponde a: XB X6 X7 Z

X1 2 2 -4

X2 1 2 -3

X3 4 2 -6

X4 -1 0 1

X5 0 -1 1

X6 1 0 0

X7 0 1 0

bi 1  3/2  -5/2

 θi  1/4  3/4  5/12

mín.

Valor más negativo

Continuando con las iteraciones del Método Simplex ingresamos la variable X3 a la base (criterio: variable no básica con costo reducido más negativo) y realizamos el mínimo cociente: 

Min{1/4 ; 3 /2 /2 }=1/4  ==> el pivote se encuentra en la fila 1 por tanto deja la base la variable básica X6 (variable básica asociada a la fila 1). Se realiza una iteración del Método Simplex y se actualiza la tabla: XB X3 X7 Z

X1  1/2 1 -1

X2 1/4   3/2 -3/2

X3 1 0  0

X4 -1/4   1/2  -1/2

X5 0 -1  1

X6 1/4  -1/2  3/2 

X7 0 1  0

bi 1/4  1 -1

 θi 1/4 1   1

F.G. Pivot

Ahora las variables no básicas con costo reducido negativo son X1 y X4. Hacemos entrar a la base a la variable X1 y calculamos el mínimo cociente:  Min{1/4 /1/2; 1/1 }=1 ==> el pivote esta en la fila 1 y por tanto la variable X3 deja la base. “es una situación inusual (pero no por ello incorrecto) que una variable que en una iteración previa haya ingresado a la base, deje ésta inmediatamente en la iteración posterior”. Si bien este es el caso al cual nos enfrentamos continuaremos con las iteraciones del Método Simplex. NOTA: la variable no básica con costo reducido más negativo en la tabla anterior es  X4  y por tanto dicha variable debería ser la que ingrese a la base. No obstante, de forma  involuntaria  se omitió dicha situación y se incorporó a la base la variable  X1. El efecto de esta decisión sólo tiene que ver con la rapidez de convergencia del  Método Simplex  y no afecta en absoluto los resultados finales. Sin embargo, cabe destacar que  no hay garantías  que incorporando la variable no básica con el costo reducido más negativo el Método Simplex alcance la solución óptima (de existir) de forma más rápida XB X1 X7 Z  

XB X1 X2 Z

X1 1 0 0

X2 1/2 1 -1

X3

X4 2 -1/2  -2 1 2 -1

X5 X6 0 1/2  -1 -1 1 2

X7

bi 0  1/2 1  1/2 0  -1/2

 θi 1  1/2   1/2

Para seguir con las iteraciones podemos seleccionar tanto la variable X2 como X4 como variables que ingresan a la base En este caso optaremos por la variable X2 y calculamos el mínimo cociente:  Min{1/2/1/2 ; 1/2/1}=1/2 ==> X7 deja la base. Actualizamos la tabla obteniendo lo siguiente: X1 1 0 0

X2 0 1 0

X3 3 -2 0

X4 X5 -1  1/2 1 -1 0 0

X6

X7 bi 1  -1/2   1/4 -1 1   1/2 1 1 0

Notar que ahora tenemos una solución básica factible con las variables  X 1=1 /4 y X 2=1/2 . Adicionalmente todas las variables no básicas ( X 3 , X 4 , X 5 , X 6 , X 7) tienen costos reducidos mayores o iguales a cero. Por último y muy importante el valor de la función objetivo al finalizar la Fase I es cero, condición indispensable para seguir a la Fase II del método. NOTA : Si el valor de la función objetivo al concluir la  Fase I  del  Método Simplex de 2 Fases  es  distinto a cero  el problema es   infactible, es decir, no tiene solución (su dominio de soluciones factibles es vacío).

FASE II. Para seguir con la Fase II eliminamos la(s) columna(s) asociadas a las variables artificiales y actualizamos el vector de costos reducidos considerando la función objetivo original. Se obtiene en consecuencia la siguiente tabla:

Min z =160 X 1+120 X 2+280 X 3 Función objetivo original XB X2 X1 Z

X1 1 0 160

X2 0 1 120

X3 3 -2 280

X4 -1 1 0

X5  1/2 -1 0

bi 1/4  1/2  0

Buscamos ahora llevar a cero el costo reducido a cero para las variables X1 y X2 (variables básicas al finalizar la Fase I). Para ello desarrollamos operaciones fila multiplicando la fila 1 por -1 y luego sumando a la fila 3 (también multiplicamos por -1 la fila 2 y sumando a la fila 3). XB X6 X7 Z

X1 1 0 0

X2 0 1 0

X3 3 -2 40

X4 -1 1 40

X5  1/2 -1 40

bi 1/4   1/2 -100

Finalmente se logra conservar la estructura de variables básicas para las variables X1 y X2 y las variables no básicas tienen costos reducidos mayores o iguales a cero. En consecuencia estamos frente a la solución óptima del problema con  X 1=1 /4 y X 2=1/2