En el apunte de la Programación Lineal se vio lo que se considera el problema primal, y su Análisis de Sensibilidad. También se puede plantear el mismo problema o modelo matemático como un problema dual: otra cara de la misma moneda en la que las restricciones y las variables de decisión intercambian lugares.
La solución óptima del problema de programación dual proporciona:
- Herramientas alternativas para comprobar la optimalidad de soluciones.
- Interpretaciones económicas de los problemas de programación lineal.
Se formula la función objetivo, variables, y coeficientes de manera sistemática a partir del modelo de programación lineal primal:
La matriz de coeficientes tecnológicos cambia: .
Los signos de las restricciones y de las variables se invierten. Un dual de minimización tiene todas sus restricciones de la forma , mientras que un dual de maximización las tiene de la forma .
Ejemplo:
El valor óptimo resultante de la función objetivo debería ser el mismo en ambos problemas.
Si se agrega una nueva restricción (no redundante) al modelo, de manera que empeore el valor óptimo actual, se puede determinar una nueva solución óptima mediante una iteración más del método Simplex dual.