Metodo de las dos fases

Solo disponible en BuenasTareas
  • Páginas : 5 (1208 palabras )
  • Descarga(s) : 0
  • Publicado : 26 de agosto de 2012
Leer documento completo
Vista previa del texto
2.3 MÉTODO DE LAS DOS FASES.
Este es otra variante del simplex que se aplica para resolver modelos de PL que requieren una matriz unitaria de base artificial para poder iniciar el algoritmo. El nombre indica que consiste de dos fases: En la 1ª, se reducen las artificiales Wi a cero y en tal caso se optimiza en la 2ª, o bien, se concluye que no hay solución factible para el problema porque Wi esdiferente de cero en fase 1, y por lo tanto no es necesaria la fase2.
Éste método 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 método Simplex normal.
FASE 1
Primera fase.- En estemétodo siempre se minimiza una función objetivo constituida por la suma de las variables artificiales utilizadas para completar la matriz I:
Minimo Z= Wi
Las variables artificiales son útiles para formar la primera base del simplex, pero si se logra que toda Wi=0, entonces Z=0 representa lo deseable u óptimo, pues lo contrario significa un problema que no tiene solución factible, en tal caso noaplica la segunda fase. Si todo va bien, las variables artificiales Wi deben salir de la base, excepto en algún caso degenerado en que Wi=cero, es básica.
En esta primera fase, se realiza todo de igual manera que en el método Simplex normal, excepto la construcción de la primera tabla, la condición de parada y la preparación de la tabla que pasará a la fase 2.
- Construcción de la primera tabla: Sehace de la misma forma que la tabla inicial del método Simplex, pero con algunas diferencias. La fila de la función objetivo cambia para la primera fase, ya que cambia la función objetivo, por lo tanto aparecerán todos los términos a cero excepto aquellos que sean variables artificiales, que tendrán valor "-1" debido a que se está minimizando la suma de dichas variables (recuerde que minimizar F esigual 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 cálculo de la siguiente forma: Se sumarán los productos Cb·Pj para todas las filas y al resultado se le restará el valor que aparezca (según la columna que se esté haciendo) en la fila de la función objetivo.
 
Tabla |
  |   | C0 | C1 | C2 | ... | Cn-k| ... | Cn |
Base | Cb | P0 | P1 | P2 | ... | Pn-k | ... | Pn |
Pi1 | Ci1 | bi1 | a11 | a12 | ... | a1n-k | ... | a1n |
Pi2 | Ci2 | bi2 | a21 | a22 | ... | a2n-k | ... | a2n |
... | ... | ... | ... | ... | ... | ... | ... | ... |
Pim | Cim | bim | am1 | am2 | ... | amn-k | ... | amn |
Z |   | Z0 | Z1 | Z2 | ... | Zn-k | ... | Zn |
Siendo Zj = Σ(Cb·Pj) - Cj y los Cj = 0 para todo jcomprendido entre 0 y n-k (variables de decisión, holgura y exceso), y Cj = -1 para todo j comprendido entre n-k y n (variables artificiales).
 - Condición de parada: La condición de parada es la misma que en el método Simplex normal. La diferencia estriba en que pueden ocurrir dos casos cuando se produce la parada: la función toma un valor 0, que significa que el problema original tiene solución,o que tome un valor distinto, indicando que nuestro modelo no tiene solución.
- Eliminar Columna de variables artificiales: Si hemos llegado a la conclusión de que el problema original tiene solución, debemos preparar nuestra tabla para la segunda fase. Deberemos eliminar las columnas de las variables artificiales, modificar la fila de la función objetivo por la original, y calcular la fila Z dela misma forma que en la primera tabla de la fase 1.
FASE 2.
Segunda fase.- Se continúa con ésta sólo si ocurre la optimización del problema en la fase anterior. Para ello sirve la tabla simplex óptima de la primera, que se ajusta eliminando las columnas de las variables artificiales Wi; además, el renglón Z se cambia a los coeficientes de la función Z original. El procedimiento continúa con...
tracking img