Ir al Principio                                         Regresar al Menú Principal

MÉTODO DE LAS DOS FASES

El problema del ejemplo anterior fue manejado en la forma regular después de que las variables artificiales habían sido añadidas. Existe una complicación en el método de la M, en el cual se debe asignar un valor M sin especificar exactamente que valor es. Si un valor numérico especifico fuera asignado a la M, este deberá ser mucho mayor que cualquier otro numero que aparece en la función objetivo y probablemente no satisfaga todas las condiciones. Su propósito seria el de proveer una penalización para eliminar las variables artificiales de la base, ya que ellas realmente no pueden formar parte de  la solución en un problema de la vida real. Un enfoque para evitar estas dificultades está incorporado o considerado en el método de dos fases.

La primera fase consiste en convertir todas las variables artificiales en cero, para obtener una solución básica factible para las variables reales del problema.

La segunda fase consiste en optimizar la función objetivo actual Z, iniciando de una solución básica factible que puede o no contener variables artificiales a nivel cero.

FASE I

Se inicia con una solución básica factible formada con algunas variables artificiales y con la finalidad de eliminar las variables artificiales.

Se asigna a cada coeficiente de la variable artificial en la función objetivo un valor de la unidad (positiva o negativa, dependiendo de si es un problema de Minimización o de Maximización respectivamente) en lugar del valor M. A todas las variables restantes se les asigna un coeficiente cero (sin importar los coeficientes actuales del problema). Entonces en lugar de considerar la función objetivo actual.

Se optimiza la función :

Z = å _i^s ₌₁(± 1) X_Ai = (±X_A1 ±X_A2 ± X_A3......±X_As)

donde X_A son las s variables artificiales (X_A ³ 0)

La fase I termina después de haber aplicado el Método Simplex, cuando :

1).- Z* = 0

Una o mas variables están en la base a un nivel positivo. El problema original tiene una solución no factible.

2).- Z* = 0

Ninguna variable artificial está en la base. Se ha encontrado una solución básica factible al problema original.

3).- Z* ¹ 0

Una o mas variables artificiales están en la base a un nivel cero ( es decir que la b correspondiente a la variable artificial es igual a cero). Se ha encontrado una solución factible a el problema original. Debido a que algunas variables artificiales están en la base a un nivel cero, posiblemente haya redundancia en las ecuaciones restrictivas.

La fase I termina cuando los elementos zj - cj son ³ 0 para un problema de Maximización y £ para un problema de Minimización.

ANTES DE INICIAR LA FASE II

a)   Elimine todas las columnas correspondientes a las variables artificiales no básicas.

b)   Cheque redundancia (ecuaciones redundantes) en el problema original. El sistema de ecuaciones original es Ax = b. Si una restricción (ecuación) puede ser obtenida como una combinación lineal de las otras, la restricción es redundante. Para localizar la existencia de ecuaciones redundantes observe en la tabla final de la fase I (después de haber eliminado las columnas correspondientes a las variables artificiales no básicas) si existe alguna fila cuyos elementos sean todos cero a excepción de un elemento 1 que corresponda a la columna de una variable artificial básica, entonces esto indicará que la fila es redundante, por lo tanto elimine la fila y la columna.

c)   Elimine las variables artificiales en la base, en la tabla final de la fase I, estas variables estarán representadas por columnas que tienen elementos cero a excepción de un uno en la fila donde b=0. Seleccione uno de los elementos diferentes de cero en esta fila (debe de existir alguno, de otra forma esta fila se hubiera eliminado en el paso b). Este elemento elíjalo como pivote, transformando su columna correspondiente a tener el elemento 1 en el pivote, y cero en el resto de la columna (es decir, se genera en esa columna el vector necesario para eliminar la variable artificial de la solución.)

FASE II

La primera tabla de la fase II, es la ultima tabla de la fase I, sufriendo los siguientes cambios;  se reemplazan los coeficientes de la función objetivo por los coeficientes originales de las variables reales y después se calculan las filas z_j y z_j-c_j. Una vez que se han realizado estos cambios, se aplica el Método Simplex nuevamente para optimizar la función objetivo Z.

Ejemplo :

Minimizar Z = -X₁

sujeto a :

                        X₁ + X₂ - X₃ + X₄ - X₅ +2X₆ = 2

                        2X₁ - X₂ - X₃ - 2X₄ + X₅ - X₆            = 3

                        3X₁        - 2X₃ - X₄          +X₆            = 5

                        X₁,X₂,X₃,X₄,X₅,X₆ ³ 0

Expresándolo en la forma estándar, tenemos :

Minimizar Z = -X₁

sujeto a :

                        X₁ + X₂ - X₃ + X₄ - X₅ +2X₆ +X₇                      = 2

                        2X₁ - X₂ - X₃ - 2X₄ + X₅ - X₆          + X₈                  = 3

                        3X₁        - 2X₃ - X₄          +X₆                            + X₉ = 5

                                                                                  X´s ³ 0, para toda X.

Donde X₇, X₈ Y X₉ son variables artificiales.

FASE I

Tabla 1

Tabla 2

Tabla 3

Como todos los elementos en Zj-Cj son £ 0, la fase I esta terminada. El valor mínimo de la fase I es cero y por esto el problema es factible. Una solución factible para el problema original es (1.6, 0, 0, 0, 0, .2). Para establecer la tabla de la fase II; elimine las columnas 7 y 8, asigne los coeficientes originales en la función objetivo y calcule las entradas de la fila Zj-Cj (en la variable artificial cero).

Como todos los elementos en la tercera fila son cero, excepto por un 1 que representa la variable artificial X₉, la fila es eliminada por ser redundante. Cheque en el problema original y encontrará que la tercera ecuación es la suma de las dos primeras ecuaciones. Se elimina la fila 3 y la columna 7 (X₉).

FASE II

La columna muestra que el problema es ilimitado (los elementos en la columna correspondiente a la variable entrante son £ 0,  y_rj £ 0 ), por tanto la solución es ilimitada ( Z = -a ).

    Ir al Principio                                         Regresar al Menú Principal