Definición:
Una programación lineal está formado por variables X1, X2, X3, DDD, Xn, a este programa PRIMARIO le corresponde otro programa lineal llamado DUAL formado por las variables W1, W2,
W3, DDD, Wm.
REGLAS
DE OBTENCIÓN DEL DUAL
Si el modelo está escrito en la forma canónica, el
dual resulta singularmente fácil de obtener. Por ejemplo, partiendo de la forma
canónica del modelo de máximo:
Primal Dual
[MIN] z= c'.x [MAX] w= b'.u
A.x ≥ b A'.u
≤ c
Xj ≥ 0 ui ≥ 0
OBTENCIÓN DE LA
SOLUCIÓN DEL DUAL
El
dual de un modelo lineal es otro modelo lineal, que puede solucionarse (después
de las oportunas transformaciones, si alguna de las variables resultantes es no
negativa o no restringida en signo) del mismo modo que el primal. En el ejemplo
siguiente veremos un modo de obtener la solución óptima del dual.
Dado un problema de minimización en forma canónica:
min
|
cTx
|
s.a
|
Ax≥ v
|
x≥ 0
|
su dual es el problema
max
|
wTb
|
s.a
|
wT A≤ cT
|
w≥ 0
|
Para un problema de programación lineal en forma estándar:
min
|
cTx
|
s.a
|
Ax=v
|
x≥ 0
|
el dual es
max
|
wTb
|
s.a
|
wT A≤ cT
|
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 menor 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
Los
restantes tipos de combinaciones de problemas, se conocen con el nombre de duales
asimétricos. 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.
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 representan 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.
ANÁLISIS
DE SENSIBILIDAD
El análisis de sensibilidad es una herramienta
especialmente útil cuando no tenemos una certeza absoluta sobre los valores que
se han dado a los términos independientes de las restricciones (en muchas
ocasiones asociados a la limitación de los recursos) o los coeficientes de la
función objetivo (coeficientes de coste). Para estos casos el análisis de
sensibilidad consiste en estudiar cómo evoluciona el óptimo y el valor de la
función objetivo en el óptimo ante variaciones de dichos términos
independientes y coeficientes.
Es importante visualizar qué variables tienen mayor
efecto en el resultado frente a distintos grados de error, en su estimación
permite decidir acerca de la necesidad de realizar estudios más profundos de
esas variables, para mejorar las estimaciones y reducir el grado de riesgo por
error.
Teoremas de Dualidad
- * Teorema Débil de Dualidad.
- * Teorema Fundamental de Dualidad.
- * Teorema de Holgura Complementaria.
A continuación tendremos un vídeo donde se explica un ejercicio de dualidad en programación lineal
