viernes, 15 de febrero de 2013

Dualidad


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.