top of page

TEORIA DE LA DUALIDAD

 

Cada problema de programación lineal  está estrechamente relacionado con otro problema simétrico a él, denominado problema dual.

El dualismo es una teoría que surge como consecuencia de una profundización en el estudio de la programación lineal porque la distribución de los recursos y la formación de los precios son dos aspectos del mismo problema. Entonces la doble formulación de la programación lineal no se debe considerar como un simple ejercicio matemático, sino que una y otra versión del problema vienen a explicar dos aspectos económicos distintos para una misma situación problémica. Una propiedad fundamental de la relación entre el primal y el dual es que la solución óptima de cualquiera de estos problemas proporciona la solución óptima para el otro.

 

IMPORTANCIA DE LA DUALIADA EN LA PROGRAMACION LINEAL

 

La resolución de los problemas duales respecto a los primales se justifica dada la facilidad que se presenta dados problemas donde el número de restricciones supere al número de variables. Además de tener gran aplicación en el análisis económico del problema.

 

Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables.

 

 

METODO DUAL SIMPLEX

 

Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.

El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.

 

CARACTERÍSTICAS DE LA SOLUCIÓN DEL DUAL Y DEL PRIMAL.

 

 Existen algunas de las propiedades de interés a cerca de las soluciones del dual y el primal.

  • Si el primal tiene solución óptima acotada x*, el dual también tendrá solución óptima acotada u*, ambas soluciones darán el mismo valor de la función objetivo. c´. x* = b´. u*

  • Si uno de los dos problemas tiene óptimo no acotado, el otro solo tendrá solución, la región factible será un conjunto vacio.

  • Si uno de los dos problemas no tiene solución, el otro puede obtener óptimo no acotado, o tampoco tener solución.

 

La dualidad es importante por el hecho de que es equivalente resolver un problema a resolver su dual. Ello es debido a que los precios sombra de dual son las soluciones de problemas y viceversa. Así, en ocasiones, puede resultar conveniente obtener las soluciones de problemas a partir de los precios sombra de dual en vez de resolver problemas directamente. 

La resolución de los problemas duales respecto a los primales se justifica dada la facilidad que se presenta dados problemas donde el número de restricciones supere al número de variables. Además de tener gran aplicación en el análisis económico del problema. 

 

 

 

VENTAJAS Y DESVENTAJAS DE LA DUALIDAD.

 

Una de las ventajas de la existencia del programa dual es la posibilidad de reducir el esfuerzo computacional  al resolver ciertos modelos de programación lineal.

  • Permite resolver problemas de programación lineal de forma más rápida y sencilla.

  • Es otra vía para resolver un problema de programación lineal.

  • Facilita profundizar en el contenido económico del problema original (primal).

  • Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una nueva variable en el primal una vez que ha de sido obtenida la solución óptima, sin tener que resolver completamente el problema.

  • Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables.

  • Una desventaja de este método, es que se requiere para empezar a iterar la condición de factibilidad dual.

 

 

bottom of page