dual simplex
Cada problema de programación lineal tiene un segundo problema asociado a él. Uno se
denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas, de talmanera que la
solución óptima a un problema proporciona información completa sobre la solución óptima para el
otro.
Las relaciones entre el primal y el dual se utilizan para reducir elesfuerzo de cómputo en ciertos
problemas y para obtener información adicional sobre las variaciones en la solución óptima
debidas a ciertos cambios en los coeficientes y en la formulación delproblema.
DEFINICION DEL PROBLEMA DUAL.
Para poder elaborar el problema dual a partir del primal, este se debe presentar en su forma
canónica de la siguiente forma:
Maximizar
Sujeto a:
Elproblema dual se puede obtener a partir del problema primal y viceversa de la siguiente
manera:
1. Cada restricción de un problema corresponde a una variable en el otro.
2. Los elementos dellado derecho de las restricciones en un problema son iguales a los
coeficientes respectivos de la función objetivo en el otro.
3. Un problema busca maximizar y el otro minimizar.
4. Elproblema de maximización tiene restricciones
restricciones que.
5. Las variables en ambos casos son no negativas.
que y el problema de minimización tiene
EJEMPLO:
Considere el problemaprimal siguiente:
Maximizar
Sujeto a:
Elaborar el dual a partir del primal.
Minimizar
Sujeto a:
Cuando el problema primal no está en forma canónica, es necesario hacer ajustes para poderpresentarlo así. Los cambios más frecuentes son:
1. Si la función objetivo es minimizar, se puede transformar a una función objetivo de maximizar
de la siguiente forma:
MinimizarMaximizar
2. Una restricción mayor o igual que se transforma en una restricción menor o igual que de la
siguiente manera:
3. Una restricción de igualdad se transforma en 2 inecuaciones.
Regístrate para leer el documento completo.