¿QUÉ ES?
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.
Una vez formulado el problema dual,
debemos encontrar su solución, el método a emplear será el denominado Método
Dual-Simplex el cuál empieza con una solución óptima o mejor que óptima, pero
no factible y se mueve hacia el óptimo mediante iteraciones que mejoran su
factibilidad conservando su optimalidad. Fíjese que es lo contrario al método
Simplex, en donde se empieza mediante una solución factible pero no óptima y
mediante iteraciones se mejora la optimalidad, conservando la factibilidad.
Esto se ilustra mediante la siguiente gráfica:
CONDICION 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).
CONDICION 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.
ALGORITMO PARA MAXIMIZAR
EN EL MÉTODO DUAL – SIMPLEX
Se requiere que el problema esté expresado en términos de Maximizar la
Función objetivo y todas sus restricciones con mayor ó igual ( > )
- Variable que sale de la Base: Aquella que tenga el valor menos factible ó sea la más negativa, matemáticamente: XB,r = Mínimo i XB,i , XB,i < 0 ; XB,i < 0 implica que la solución es NO factible.
- Variable que entra a la Base: Aquella variable que tenga el valor menos negativo en su expresión: ( Zj - Cj ) / ar,j , matemáticamente: (ZK - CK ) / ar,k = Máximo j (Zj - Cj ) / ar,j ; Siendo ar,j < 0 . El siguiente ejemplo ilustra un paralelo entre el Método Simplex y el Método Dual – Simplex en donde se resalta para cada iteración, la relación entre los dos (2) Métodos.
Hallar la solución óptima al problema siguiente:
CONCLUSION
Observe que en el
Dual – Simplex se hizo uso de la regla de equivalencia, multiplicando la
función objetiva por (-1), y al final, nuevamente se multiplicó el valor de Z
por (-1).
- En cada iteración del Método Simplex se muestra que:
1. Los Zj – Cj de las
variables de holgura X3, X4, X5 (Z3-C3 , Z4-C4 , Z5-C5) son los valores de las
variables reales del Dual (Y1,Y2,Y3).
2. Los Zj – Cj de las
variables reales X1,X2 (Z1-C1 , Z2-C2) son los valores de las variables de
holgura del Dual (Y4,Y5)
- En cada iteración del Método Dual – Simplex se muestra que:
1. Los Zj – Cj de las
variables de holgura Y4,Y5 (Z4-C4 , Z5-C5) son los valores de las variables
reales del problema principal (X1,X2)
2. Los Zj – Cj de las
variables reales Y1,Y2 ,Y3 (Z1-C1 , Z2-C2 , Z3-C3) son los valores de las
variables de holgura del problema principal (X3,X4,X5)
BIBLIOGRAFIA:
No hay comentarios.:
Publicar un comentario