INSTITUTO TECNOLOGICO DE CD.

VALLES
MATERIA: INVESTIGACION DE OPERACIONES CARRERA: INGENIERIA INDUSTRIAL IV SEMESTRE GRUPO D

EQUPO NO 3 INTEGRANTES: ALTAMIRANO MORQUECHO JUAN PABLO CARPIO CHAVEZ VICTOR HUGO GARCIA RODRIGUEZ JUAN CARLOS PEREZ LOPEZ OZIEL RAMIREZ SANCHEZ RICARDO TORRES AVILA KEVIN VEGA LARA DAVID

METODO DE LAS DOS FASES

Fase Uno:

Minimizar la suma de las variables artificiales del modelo. Si el valor de la Z ptima es cero, se puede proseguir a la Fase Dos, de lo contrario el problema no tiene solucin.

Fase Dos: Con base en la tabla ptima de la fase uno, se elimina de las restricciones las variables artificiales, y se reemplaza la funcin objetivo, por la funcin objetivo original y se resuelve a partir de ah, con el mtodo Simplex tradicional.

Porque existe el mtodo Simplex de 2 fases?

La desventaja de la tcnica M es el posible error de cmputo que podra resultar de asignar un valor muy grande a la constante M. Esta situacin podra presentar errores de redondeo en las operaciones de la computadora digital. Para evitar esta dificultad el problema se puede resolver en 2 fases. ste mtodo difiere del Simplex en que primero hay que resolver un problema auxiliar que trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar el mtodo Simplex normal.

Algoritmo para la aplicacin del mtodo de 2 fases

SI

Aparecen Var. Art? Mtodo Simplex Mtodo 2 Fases

Construimos Primera Tabla

SI

Cumple Parada
NO SI SI NO

Elegir Variable Entrante

Cumple Parada
NO

F.Objetivo=0

Eliminar Columnas de Var. Artificiales

Elegir Variable Entrante No existe Solucin

Elegir Variable que Sale Dar resultado Actualizar Tabla

Actualizar Tabla

Reglas:

- Construccin de la primera tabla: Se hace de la misma forma que la tabla inicial del mtodo Simplex, pero con algunas diferencias. La fila de la funcin objetivo cambia para la primera fase, ya que cambia la funcin objetivo, por lo tanto aparecern todos los trminos a cero excepto aquellos que sean variables artificiales, que tendrn valor "-1" debido a que se est minimizando la suma de dichas variables (recuerde que minimizar F es igual que maximizar F(-1)). La otra diferencia para la primera tabla radica en la forma de calcular la fila Z. Ahora tendremos que hacer el clculo de la siguiente forma: Se sumarn los productos CbPj para todas las filas y al resultado se le restar el valor que aparezca (segn la columna que se ste haciendo) en la fila de la funcin objetivo.

- Condicin de parada: La condicin de parada es la misma que en el mtodo Simplex normal. La diferencia estriba en que pueden ocurrir dos casos cuando se produce la parada: la funcin toma un valor 0, que significa que el problema original tiene solucin, o que tome un valor distinto, indicando que nuestro modelo no tiene solucin.

- Eliminar Columna de variables artificiales: Si hemos llegado a la conclusin de que el problema original tiene solucin, debemos preparar nuestra tabla para la segunda fase. Deberemos eliminar las columnas de las variables artificiales, modificar la fila de la funcin objetivo por la original, y calcular la fila Z de la misma forma que en la primera tabla de la fase 1.

Identificacin de Casos Anmalos y Soluciones

- Infinitas soluciones: Cumplida la condicin de parada, si se observa que alguna variable que no est en la base, tiene un 0 en la fila Z, quiere decir que existe otra solucin que da el mismo valor ptimo para la funcin objetivo. Si estamos ante este caso, estamos ante un problema que admite infinitas soluciones, todas ellas comprendidas dentro del segmento (o porcin del plano, o regin del espacio, dependiendo del nmero de variables del problema) que define Ax+By=Z0. Si se desea se puede hacer otra iteracin haciendo entrar en la base a la variable que tiene el 0 en la fila Z, y se obtendr otra solucin. -

 - Empate de variable entrante: Se puede optar por

cualquiera de ellas, sin que afecte a la solucin final, el inconveniente que presenta es que segn por cual se opte se harn ms o menos iteraciones. Se aconseja que se opte a favor de las variables bsicas, ya que son aquellas las que quedarn en la base cuando se alcance la solucin con estos mtodos.

- Solucin ilimitada: Si al intentar buscar la variable que debe abandonar la base, nos encontramos que toda la columna de la variable entrante tiene todos sus elementos negativos o nulos, estamos ante un problema que tiene solucin ilimitada. No hay valor ptimo concreto, ya que al aumentar el valor de las variables se aumenta el valor de la funcin objetivo, y no viola ninguna restriccin.
- No existe solucin: En el caso de que no exista solucin, seguro que no tendremos que realizar las dos fases, por lo que al trmino de la primera sabremos si estamos en tal situacin.

- Empate de variable saliente: Se puede nuevamente optar por cualquiera de ellas, aunque se puede dar el caso degenerado y entrar en ciclos perpetuos. Para evitarlos en la medida de lo posible, discriminaremos a favor de las variables bsicas haciendo que se queden en la base. Ante el caso de estar en la primera fase (del mtodo de las Dos Fases), se optar por sacar en caso de empate las variables artificiales.

Ejemplo Simplex de 2 Fases

Considere el siguiente modelo de Programacin Lineal:

FASE 1: Al agregar S1 como variable de exceso en la restriccin 1 resulta evidente que no se dispone de una solucin bsica factible inicial, por tanto utilizaremos una variable auxiliar "y" que incluiremos en el lado izquierdo de la restriccin y que servir como variable bsica inicial. Esto define el problema inicial de la Fase 1 junto a su tabla.

Luego la variable X2 entra a la base (costo reducido negativo) y claramente "y" deja la base. Se actualiza la tabla utilizando el mtodo simplex:

Con esta tabla finaliza la Fase 1. Notar que el valor de la funcin objetivo al finalizar la Fase 1 es cero, por tanto podemos continuar la Fase 2.

FASE 2: Se elimina la columna asociada a la variable artificial "y" y se actualiza el vector de costos reducidos considerando la funcin objetivo original. De esta forma se obtiene la tabla inicial de la Fase 2.

Dado que X2 es variable bsica al finalizar la Fase 1 buscamos dejar esta misma variable como bsica al iniciar la Fase 2. Para ello multiplicamos por -3 la fila 1 y luego la sumamos a la fila 2.

En este sencillo ejemplo se llega inmediatamente a la tabla final de la Fase 2, con solucin ptima X1=0 y X2=10. El valor ptimo V(P)=-30.