DUALIDAD EN PROGRAMACIÓN
LINEAL
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 más
concretamente, para los rangos de valores
de los términos independientes para los que se mantiene la base optima
(que podemos conocer mediante el análisis de sensibilidad). La solución del
dual nos permite conocer el precio sombra de la restricción, que será la
variación de la función objetivo por unidad incrementada del termino
independiente de la restricción.
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 algunas de las
variables resultantes es no negativa o no restringida en signo) del mismo modo
que el primal. Sin embargo, en general puede obtenerse la solución del dual
resolviendo el primal.
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.
CARACTERÍSTICAS
DE LAS SOLUCIONES DEL DUAL Y DEL 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 optimo no acotado, el otro no tendrá solución (la región factible será un conjunto vacío)
- Si uno de los dos problemas no tiene solución, el otro puede tener optimo no acotado o no tener tampoco solución.
IMPORTANCIA DE
DUALIDAD DE PROGRACMACION LINEAL
La dualidad permite realizar importantes
interpretaciones económicas de los problemas de programación lineal y así como
también generar métodos como el método dual del simplex de gran importancia en
el análisis de post-optimización y en la programación lineal paramétrica.
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.
Otra
de las ventajas que presenta es que dado al 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.
Sin embargo cada vez que se plantea y resuelve un problema lineal, existe otro
problema incitante 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.
DEFINICIÓN DE
ANALISIS 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.
El análisis de sensibilidad propiamente dicho
estudia los intervalos para los cuales la modificación de un valor (coeficiente
de la función objetivo o término independiente) en el programa lineal, de forma
individualizada, no cambia las variables que componen la base de nuestra
solución. Hallando, para el rango de valores definido en el intervalo, la
evolución de la función objetivo (expresado a través de los precios sombra).
OBJETIVO DE
ANALISIS DE SENSIBILIDAD
El objetivo fundamental del análisis de sensibilidad
es identificar los parámetros sensibles, (por ejemplo, los parámetros cuyos
valores no pueden cambiar sin que cambie la solución óptica). Para ciertos
parámetros que no están clasificados como sensibles, también puede resultar de
gran utilidad determinar el intervalo de valores del parámetro para el que la
solución óptima no cambie. Este intervalo de valores se conoce como intervalo
permisible para permanecer óptimo. En algunos casos cambiar el valor de un
parámetro puede afectar la factibilidad de la solución BF óptima con los
valores ajustados de las variables básicas seguirá siendo factible.
CARACTERISTICAS
DEL ANALISIS DE SENCIBILIDAD
·
El
análisis de sensibilidad prácticamente elimina el esfuerzo computacional.
·
Los
problemas reales ocurren en un medio ambiente dinámico
Identifica los parámetros sensibles.
ANÁLISIS DE
SENSIBILIDAD MEDIANTE PROGRAMAS INFORMÁTICOS
Los programas informáticos que resuelven
modelos de programación lineal, como el LINDO, suelen incorporar la posibilidad
de realizar el análisis de sensibilidad de los coeficientes de coste c y de los términos independientes de las restricciones b, el resultado de este análisis es el
intervalo de valores de estos parámetros para el que se mantiene la base.