DUALIDAD EN PROGRAMACIÓN LINEAL 

DEFINICIÓN:

El  concepto de dualidad desempeña importantes papeles dentro de la programación lineal (también en la no lineal), tanto desde un  punto de vista teórico como practico. Todo programa lineal lleva asociado otro programa lineal conocido como su programa dual; el programa inicial se conoce también como programa primal.

La dualidad en programación lineal provee de resultados teóricos interesantes que justifican su uso como herramienta alternativa y complementaria de resolución.

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

• TEOREMA DE DUALIDAD DÉBIL: En general, el valor de cualquier solución factible del problema de minimización, provee una cota superior del valor óptimo del problema de maximización. Análogamente, el valor de la función objetivo de cualquier solución factible del problema de maximización es una cota inferior del valor óptimo del problema de minimización.
• TEOREMA DE DUALIDAD FUERTE: En el óptimo el valor de la función objetivo del problema primal será igual al valor de la función objetivo del problema dual evaluada en la solución dual óptima. Si el problema primal es no acotado, entonces el dual es infactible. Alternativamente si el problema primal es infactible, entonces el dual es no acotado.
• TEOREMA DE HOLGURAS COMPLEMENTARIAS: Una variable en el primal esta asociada a una restricción en el dual (y viceversa). En este sentido si en el primal existe una variable no básica (valor igual a cero), en el dual la restricción asociado no está activa, es decir, no se cumple en igualdad. Análogamente, si la variable es básica en el primal, la restricción asociada en el dual se cumple en igualdad. Este resultado teórico es útil toda vez que simplifica la forma de obtener la solución óptima dado que como en un problema lineal la solución óptima (en caso de existir) esta en un vértice, esto implica resolver un sistema de ecuaciones (con restricciones de igualdad).

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.

a)    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*

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

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

d)    Permite resolver problemas lineales donde el numero de restricciones es mayor que el numero de variables. Gracias a los teoremas se pueden dar la solucion de unos de los problemas (primal o dual) nos proporciona de forma automatica la solucion del otro programa.

e)    La dualidad permite realizar importantes interpretaciones economicas de los problemas de programacion lineal.

f)     La dualidad permite generar metodos como el metodo dual del simplex de gran importancia en el analisis de post-optimizacion y en la programacion lineal parametrica.

IMPORTANCIA DE LA DUALIDAD EN PROGRAMACIÓN 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.

RELACIONES ENTRE PROBLEMAS PRIMALES Y DUALES

• El número de variables que presenta el problema dual se ve determinado por el número de restricciones que presenta el problema primal.
• El número de restricciones que presenta el problema dual se ve determinado por el número de variables que presenta el problema primal.
• Los coeficientes de la función objetivo en el problema dual corresponden a los términos independientes de las restricciones (RHS), que se ubican del otro lado de las variables.
• Los términos independientes de las restricciones (RHS) en el problema dual corresponden a los coeficientes de la función objetivo en el problema primal.
• La matriz que determina los coeficientes técnicos de cada variable en cada restricción corresponde a la transpuesta de la matriz de coeficientes técnicos del problema primal.

DUAL SIMÉTRICO Y ASIMÉTRICO:

Los problemas duales simétricos son los que se obtienen de un problema primal en forma canónica y ‘normalizada’, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades menores o igual para los problemas de maximización. Es decir, si el problema original es de la siguiente forma:

Máx Z(x) = ct x

s.a:

A x ≤ b

x≥ 0

El problema dual (dual simétrico) es:

MínG(λ) = λ b

s.a:

λA ≥ c

λ ≥ 0

Los restantes tipos de combinaciones de problemas, se conocen con el nombre de duales asimétricos. por ejemplo:

Máx Z(x) = ct x

s.a:

A x = b

x≥ 0

El problema dual (dual asimétrico) es

MínG(λ) = λ b

s.a:

λA ≥ c

λ >< 0, es decir, variables libres.

  

TABLA DE TUCKER

INTERPRETACIÓN DELA TABLA DE TUCKER  

VENTAJAS Y DESVENTAJAS DE LA INVESTIGACIÓN DE OPERACIONES:

Las ventajas de la investigación de operaciones son:

a)    permitir la toma de decisión más conveniente conforme a los recursos disponibles y a los objetivos que se tratan de conseguir;

b)    lograr la abstracción de los componentes en una situación para poder estructurarla como un modelo matemático;

c)    reducir el tiempo de búsqueda de una solución que se ajuste a los objetivos propuestos.

DESVENTAJAS DE LA IO

a)    No existe un conjunto de soluciones cerrado.

b)    Cada cambio en las variables de entrada requiere una solución separada o conjunto de ejecuciones.

c)    Los modelos de simulación complejos pueden requerir mucho tiempo para construirlos y ejecutarlos.

d)    Puede resultar dificultoso establecer la validez del modelo (es decir, la correspondencia con el sistema real).