¿Cuáles son las ventajas de estudiar el problema dual en la programación lineal?

Question

Estoy estudiando programación lineal y me encontré con primal-dual algoritmo en Linear Programming . Lo he entendido, pero no consigo comprender por qué hay que calcular un dual, si el problema se puede resolver en el espacio primario. ¿Hay alguna ventaja inherente?

Estoy de acuerdo con las pruebas de la dualidad débil y la dualidad fuerte, pero me pregunto cuál es la razón.

Se agradece cualquier ayuda.

Answer 1

He aquí algunos usos del problema dual.

1. La comprensión del problema dual conduce a algoritmos especializados para algunas clases importantes de problemas de programación lineal. Algunos ejemplos son el método simplex de transporte, el algoritmo húngaro para el problema de asignación y el método simplex de red. Incluso la generación de columnas se basa en parte en la dualidad.
2. El doble puede ser útil para el análisis de sensibilidad. Cambiar el vector de restricciones del lado derecho de la primal o añadirle una nueva restricción puede hacer que la solución óptima original de la primal sea inviable. Sin embargo, esto sólo cambia la función objetivo o añade una nueva variable al dual, respectivamente, por lo que la solución óptima dual original sigue siendo factible (y no suele estar lejos de la nueva solución óptima dual).
3. A veces, encontrar una solución inicial factible para el dual es mucho más fácil que encontrar una para el primal. Por ejemplo, si el primal es un problema de minimización, las restricciones suelen ser de la forma $A {\bf x} \geq {\bf b}$ , ${\bf x} \geq {\bf 0}$ , para ${\bf b} \geq {\bf 0}$ . Las restricciones duales serían entonces probablemente de la forma $A^T {\bf y} \leq {\bf c}$ , ${\bf y} \geq {\bf 0}$ , para ${\bf c} \geq {\bf 0}$ . El origen es factible para este último problema pero no para el primero.
4. Las variables duales dan los precios sombra para las restricciones primarias. Suponga que tiene un problema de maximización de beneficios con una restricción de recursos $i$ . Entonces el valor $y_i$ de la variable dual correspondiente en la solución óptima le dice que obtiene un aumento de $y_i$ en el beneficio máximo por cada aumento unitario de la cantidad de recursos $i$ (en ausencia de degeneración y para pequeños aumentos de recursos $i$ ).
5. A veces lo dual es más fácil de resolver. Aseem Dua lo menciona: Un problema con muchas restricciones y pocas variables puede convertirse en uno con pocas restricciones y muchas variables.

Answer 2

La dualidad proporciona una gran ventaja computacional en un problema con menor número de variables y multitud de restricciones.

Si tomamos el ejemplo de simplex, nos daremos cuenta de que es mucho más fácil tratar con variables básicas menores.

Los economistas tienen una interpretación (el artículo de la wiki tiene una sección) que define muy bien las variables duales. Por otra parte, la dualidad permite comprender mejor la situación y puede ofrecer algunas perspectivas más.