El problema dual es una programación lineal definida en forma directa y sistemática a partir del modelo original (o primal) de programación lineal. Los dos problemas están relacionados en forma tan estrecha que la resolución óptima de un problema produce en forma automática la resolución óptima del otro.
En la mayor parte de las presentaciones de programación lineal, el dual se define para varias formas del primal, dependiendo del sentido de la optimización (maximización o minimización), tipos de restricciones ( o =), y la orientación de las variables (no negativa o no restringida). Este tipo de tratamiento puede confundir. Por esta razón presentaremos una sola definición que comprenda en forma automática a todas las formas del primal.
Nuestra definición del problema dual requiere expresar el problema primal en forma de ecuaciones, todas las restricciones son ecuaciones, con lado derecho no negativo y todas las variables son no negativos. Este requisito es consistente con el formato de la tabla de inicio símplex. En consecuencia, todo resultado obtenido a partir de la solución primal óptima se aplican en forma directa al problema dual asociado.
¿Cómo convertir un problema primal a dual?
Un problema dual se formula de un problema primal de la siguiente forma:
- Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.
- Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.
- Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.
- Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.
- Los signos de desigualdad del problema dual son contrarios a los del primal.
- Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables Xn del primal se convierte en nuevas variables Ym en el dual.
| PROBLEMA PRIMAL EN FORMA CANONICA: MAX Z= CX Sujeto a: AX £ b X ³ 0 | PROBLEMA DUAL EN FORMA CANONICA: MIN Z= BY Sujeto a: AY ³ C Y ³ 0 |
Ejemplo.
Si el problema primal es:
MAX Z= 45X1 + 17X2 + 55X3
Sujeto a:
X1 + X2 + X3 £ 200
9X1 + 8X2 + 10X3 £ 5000
10X1+ 7X2 + 21 X3 £ 4000
Xj ³ 0
El problema dual será:
MIN Z= 200Y1 + 5000Y2 + 4000Y3
Sujeto a:
Y1 + 9Y2 + 10Y3 ³ 45
Y1 + 8Y2 + 7Y3 ³ 17
Y1 + 10Y2 + 21Y3 ³ 55
Yj ³ 0
