MÉTODO DUAL SIMPLEX

METODO DUAL SIMPLEX

 
TEORIA DE LA DUALIDAD.
 
Cada problema de programación lineal tiene un segundo problema asociado con el. Uno se denomina primal y el otro dual. Los 2 poseen propiedadesmuy relacionadas, de tal manera 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 utilizanpara reducir el esfuerzo de computo 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óndel problema. Esto se conoce como análisis de sensibilidad o post-optimidad.
 
DEFINICION DEL PROBLEMA DUAL.
 
Para poder elaborar el problema dual a partir del primal, este se debe presentar ensu forma canónica de la siguiente forma:
 
Maximizar
 
Sujeto a:
 


 

 
El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera:
 
1. Cadarestricción de un problema corresponde a una variable en el otro.
 
2. Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la funciónobjetivo en el otro.
 
3. Un problema busca maximizar y el otro minimizar.
 
4. El problema de maximización tiene restricciones  que y el problema de minimización tiene restricciones  que.
 
5. Lasvariables en ambos casos son no negativas.
 
EJEMPLO:
 
Considere el problema primal siguiente:
 
Maximizar
 
Sujeto a:
 

 
Elaborar el dual a partir del primal.
 
Minimizar
 
Sujetoa:
 

 
Cuando el problema primal no está en forma canónica, es necesario hacer ajustes para poder presentarlo así. Los cambios más frecuentes son:
 
1. Si la función objetivo es minimizar, sepuede transformar a una función objetivo de maximizar de la siguiente forma:
 
Minimizar
 

Maximizar
 
2. Una restricción mayor o igual que se transforma en una restricción menor o igual...