Cada
uno de los problemas abordados hasta entonces en los módulos anteriores se
consideran problemas primales dado que tienen una relación directa
con la necesidad del planteamiento, y sus resultados responden a la formulación
del problema original; sin embargo cada vez que se plantea y resuelve un problema lineal, existe otro problema
ínsitamente planteado y que puede ser resuelto, es el considerado
problema dual, el cual tiene unas importantes relaciones y
propiedades respecto al problema primal que pueden ser de gran beneficio para
la toma de decisiones.
Cada
problema de programación lineal (Primal) 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. La dualidad en programación lineal provee de resultados teóricos
interesantes que justifican su uso como herramienta alternativa y
complementaria de resolución.
Dado
un modelo lineal determinado, podemos definir otro modelo lineal que nos
permitirá obtener propiedades interesantes del primero y que será su dual. La
solución del modelo dual permite obtener interesantes resultados, relativos al
análisis de sensibilidad de los términos independientes.
Relación
entre el método primal y dual
§ El dual tiene la matriz D transpuesta, es decir, si suponemos que D es
de orden sx r, entonces Dt es de orden r x s. Además las variables del primal y
el dual son diferentes, ya que X será un vector de r-componentes mientras que
el vector Y tendrá s-componentes.
§ Los términos independientes del conjunto de las restricciones del
problema primal forman los coeficientes de la función objetivo del dual.
§ Los coeficientes de la función objetivo del primal forman los términos
independientes de las restricciones del dual.
§ Las restricciones del dual cambian su sentido al igual que el criterio
de optimización en términos de mínimo o máximo.
§ A cada restricción del problema primal le corresponde una variable dual
y análogamente a cada restricción del dual le corresponde una variable del
primal.
§ Si se halla el dual del problema dual, obtendremos el problema primal.
Ventajas y Desventajas de la Dualidad.
Ventajas:
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.
Desventajas:
Una desventaja de este método, es que se
requiere para empezar a iterar la condición de factibilidad dual.
Características de la Solución del Dual.
- 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 ,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.
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ín G (λ) = λ b
S. A:
λ A ≥ c
λ ≥ 0
Dual Asimétrico
Son los
restantes tipos de combinaciones de problema. Como por ejemplo:
Máx Z(x) = ct x
S. A:
A x = b
X ≥ 0
El problema dual (dual asimétrico) es:
Mín G (λ) = λ b
S. A:
λ A ≥ c
λ >< 0, es decir, variables libres.
Tabla
de Tucker
Problema dual (minimizar)
Problema dual (maximizar)
Haz click en los siguientes enlaces para mas información relacionada al tema:
No hay comentarios:
Publicar un comentario