Sunday, February 17, 2013
Método Simplex Dual
Posted by Juan Francisco | Sunday, February 17, 2013 | Category:
INVESTIGACION DE OPERACIONES
|
Es un método genérico de solución de problemas lineales, desarrollado por George Dantzig en 1947.
A continuación veamos algunos conceptos de solución importantes.
El método simplex sólo revisa las soluciones FEV. Una de éstas soluciones FEV debe ser la óptima.
El método simplex es un algoritmo iterativo. Propone solución Prueba de estimabilidad NO SI. Siempre que es posible, el método simplex elige el origen (todas las variables de decisión iguales a cero) como la solución FEV inicial.
Si no es posible se requieren procedimientos especiales. Dada una solución FEV, es computacionalmente más rápido reunir información sobre sus soluciones FEV adyacentes que sobre otras soluciones FEV. Por tanto, siempre el algoritmo recorre las aristas de la región factible. Después de identificar la FEV actual, el algoritmo simplex identifica todas las aristas de la región factible que salen de esa solución.
Estas aristas llevan a una solución FEV adyacente en el otro punto terminal, pero el algoritmo ni siquiera se toma la molestia de obtener la solución FEV adyacente.
Solamente identifica la tasa de mejoramiento en Z que se obtendría al moverse por dicha arista. Entre las aristas con una tasa de mejoramiento en Z positiva, selecciona moverse por aquella con una tasa de mejoramiento en Z más grande.
Se escoge luego esta solución factible como la nueva solución actual.
MÉTODO DUAL SIMPLEX.
Este método se aplica a problemas óptimos pero infactibles. En este caso, las restricciones se expresan en forma canónica (restricciones <=).
La función objetivo puede estar en la forma de maximización o de minimización. Después de agregar las variables de holgura y de poner el problema en la tabla, si algún elemento de la parte derecha es negativo y si la condición de optimidad está satisfecha, el problema puede resolverse por el método dual simplex. Note que un elemento negativo en el lado derecho significa que el problema comienza óptimo pero infactible como se requiere en el método dual simplex. En la iteración donde la solución básica llega a ser factible esta será la solución óptima del problema.
CONDICIÓN DE FACTIBILIDAD.
La variable que sale es la variable básica que tiene el valor más negativo (los empates se rompen arbitrariamente si todas las variables básicas son negativas, el proceso termina y esta última tabla es la solución óptima factible).
CONDICIÓN DE OPTIMIDAD.
La variable que entra se elige entre las variables no básicas como sigue. Tome los cocientes de los coeficientes de la función objetivo entre los coeficientes correspondientes a la ecuación asociada a la variable que sale.
Ignore los cocientes asociados a denominadores positivos o cero.
La variable que entra es aquella con el cociente más pequeño si el problema es de minimizar o el valor absoluto más pequeño si el problema es de maximización (rompa los empates arbitrariamente). Si los denominadores son ceros o positivos el problema no tiene ninguna solución factible.
Subscribe to:
Post Comments (Atom)
Currently have 0 comentarios: