historia

La solución de cualquiera de los dos problemas anteriores por el procedimiento del simplex proporciona determinada información relativa al otro. Así, a la luz de la formulación que hagamos delproblema de programación lineal, se resolverá éste y podremos utilizar la información contenida en la última tabla del simplex para deducir la solución del otro.
Conocer la relación entre un problema deprogramación lineal y su dual es vital para entender temas avanzados en programación lineal y no-lineal.
Si el PRIMAL es un problema de minimización su DUAL será un problema de maximización yviceversa. Por conveniencia las variables del PRIMAL serán z (función objetivo) y sus variables xi y las variables para el problema de minimización serán z (función objetivo) y sus variables j. Veremos comoencontrar el DUAL de un problema PRIMAL de maximización, con todas sus variables no-negativas y cuyas restricciones son todas del tipo mayor o igual (Problema estándar de maximización)
En estecapítulo se desarrollarán algunos teoremas y propiedades relativas a los problemas duales, así como las relaciones existentes entre los problemas PRIMAL-DUAL.
En el capítulo anterior vimos que, para resolverun problema de Programación Lineal, transformábamos éste a su formulación estándar, es decir, transformábamos las desigualdades en igualdades. Ahora trabajaremos con los problemas con lasdesigualdades puestas todas en el mismo sentido.
Vamos a ver un ejemplo que nos ayude a situarnos frete al problema PRIMA-DUAL. Una granja compra, para el engorde de animales, dos tipos de alimento los cualesdeben cumplir una serie de requisitos para cubrir sus objetivos según se recoge en la tabla siguiente:
Si se compara los dos planteamientos se puede observar lo siguiente:
-
Los primeros miembrosdel primer problema son coeficientes de la función objetivo del segundo y viceversa.
-
La matriz de coeficientes de un problema es la transpuesta de la matriz de coeficientes del otro problema.
-...