Tema
Programación lineal y dualidad
- Algoritmos
- Nivel avanzado
Un programa lineal optimiza una función lineal sujeta a restricciones lineales, y su dual proporciona una cota que en el óptimo coincide con el valor del problema original.
Nombre en inglés
Linear programming and duality
Intuición
La región admisible es un poliedro y el óptimo, cuando existe, se alcanza en un vértice, razón por la que el método símplex recorre vértices vecinos mejorando el objetivo. El dual se lee como el precio de cada recurso: Cuánto valdría relajar una restricción en una unidad. El teorema de flujo máximo y corte mínimo es un caso particular de esa dualidad.
Fórmula
primal: max c^T x sujeto a A x <= b y x >= 0 ; dual: min b^T y sujeto a A^T y >= c y y >= 0
Ejemplo resuelto
Se maximiza 3 x más 2 y con las restricciones x más y como mucho 4, x como mucho 3 y ambas variables no negativas. Los vértices de la región son (0, 0), (3, 0), (3, 1) y (0, 4), con valores 0, 9, 11 y 8. El máximo vale 11 y se alcanza en el vértice (3, 1).
Errores frecuentes
- Suponer que el óptimo siempre existe: Un programa lineal puede no tener solución admisible o no estar acotado, y el examen pide distinguir los dos casos.
- Exigir variables enteras sin advertirlo: Al añadir esa condición el problema pasa a ser de programación entera y deja de resolverse en tiempo polinómico conocido.
- Equivocar el sentido de las desigualdades al construir el dual: Cada restricción del primal se convierte en una variable del dual y cada variable en una restricción, y los sentidos se invierten según el tipo de problema.
Ejercicio
Maximice x más y con las restricciones x más 2 y como mucho 6, x como mucho 4 y ambas variables no negativas. ¿Cuál es el valor óptimo?
Ver la solución
Los vértices son (0, 0), (4, 0), (4, 1) y (0, 3), con valores 0, 4, 5 y 3. El mejor de todos es el vértice (4, 1).
Respuesta: 5