Metodo de 2 fases

Método de 2 Fases

El Método de las Dos Fases es una variante del Algoritmo Simplex, que es usado como alternativa al Método de la M, donde se evita el uso de la constante M para las variables artificiales.

La desventaja de la técnica M es el posible error de cómputo que podría resultar de asignar un valor muy grande a la constante M. Esta situación podría presentar errores de redondeo enlas operaciones de la computadora digital. Para evitar esta dificultad el problema se puede resolver en 2 fases.

FASE 1. 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óptimo 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

Si hemos llegado a la conclusión de que el problema original tiene solución, debemos preparar nuestra tabla para la segundafase. Deberemos eliminar las columnas de las variables artificiales, modificar la fila de la función objetivo por la original, y calcular la fila Z de la misma forma que en la primera tabla de la fase 1.

FASE 2. Utilice la solución óptima de la fase 1 como solución de inicio para el problema original. En este caso, la función objetivo original se expresa en términos de las variables no básicasutilizando las eliminaciones usuales Gauss-Jordán.

EJEMPLO

P) Max 2X1 + X2
S.A 10X1 + 10X2 = 1
X1, X2 >= 0

Se debe agregar X3 como variable de holgura de la restricción 1, X4 como variable de
exceso de la restricción 2 y X5 variable auxiliar para poder comenzar la Fase 1.

F1) Min X5S.A 10X1 + 10X2 + X3= 9
10X1 + 5X2 - X4 + X5 = 1
X1, X2, X3, X4, X5 >= 0

La tabla inicial asociada a la Fase I queda en consecuencia definida de la siguiente forma:
X1 X2 X3 X4 X5
10 10 1 0 0 9
10 5 0 -1 1 1
0 0 0 0 1 0

Luego, se debe hacer 0 el costo reducido de X5,obteniendo la siguiente tabla inicial para hacer el uso de Simplex:
X1 X2 X3 X4 X5
10 10 1 0 0 9
10 5 0 -1 1 1
-10 -5 0 1 0 -1

Se escoge X1 como variable que entra a la base al tener el costo reducido más negativo. Posteriormente, mediante el criterio del mínimo coeficiente se selecciona la variable que sale de la base: Min {9/10; 1/10} = 1/10, X5 sale de la base.
X1X2 X3 X4 X5
0 5 1 1 -1 8
1 1/2 0 -1/10 1/10 1/10
0 0 0 0 1 0

Una vez obtenida la solución óptima de la Fase I, con valor óptimo cero, tomamos X1 y X3 como variables básicas iniciales para la Fase II.
X1 X2 X3 X4
0 5 1 1 8
1 1/2 0 -1/10 1/10
-2 -1 0 0 0

Hacemos cero los costos reducidos de las variables básicas:
X1 X2 X3 X4
0 5 11 8
1 1/2 0 -1/10 1/10
0 0 0 -1/5 1/5

X4 entra a la base. Por el criterio del mínimo coeficiente, el pivote se encuentra en la fila 1, por tanto X3 sale de la base.
X1 X2 X3 X4
0 5 1 1 8
1 1 1/10 0 9/10
0 1 1/5 0 9/5

Donde la solución óptima es: X1=9/10 X2=0 Con valor óptimo V (P) = 9/5

Método de la M

Definimos la letra M como un númeromuy grande pero finito para usarlo como coeficiente de las variables artificiales en la función objetivo y con sentido contrario a la misma para penalizar de manera muy grande la existencia de las mismas en la solución. Si el objetivo es minimizar las variables artificiales entraran con M positivo y si es maximizar las variables artificiales se usaran como -M.

El único problema serio que...