Teoremas de la Dualidad

            Teorema de existencia.

La condición necesaria y suficiente para que un problema de programación lineal tenga solución es que, tanto el conjunto de oportunidades del primal (S) como en conjunto de oportunidades del dual (S’) no sean vacíos, es decir, que ambos problemas sean factibles.

                                    ∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅

Una vez analizadas las condiciones que han de cumplirse para que exista solución óptima se muestra.

v  S ≠ ∅ ∧ S’ ≠ ∅                Ambos problemas tienen solución optima finita.

v  S = ∅ ∧ S’ ≠ ∅              El programa primal es infactible, y el programa dual es    no acotado.

v  S ≠ ∅ ∧ S’ = ∅ El programa dual es infactible, y el programa primal es no acotado.

v  S = ∅ ∧ S’ = ∅ Ambos problemas son infactibles.

Teorema de la Dualidad.

La condición necesaria y suficiente para que exista solución optima del primal ( x* ), es que exista una solución óptima para el dual ( λ* ) y que valor de la función objetivo de ambos programas sea igual, es decir Z(x*) = G(λ*).

                                   ∃ x* ←→ ∃ λ* / Z(x*) = G(λ*)

Teorema del Holgura complementaria.

La condición necesaria y suficiente para que (x*, λ*) sean soluciones óptimas del programa primal y dual, es que satisfagan las condiciones de holgura complementaria:

                                            ( c - λ* A ) x* = 0

                                           λ* ( b - A x* ) = 0

 

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.

Análisis de Sensibilidad.

            Es una herramienta útil cuando no tenemos una certeza absoluta sobre los valores que se han dado a los términos independientes de las restricciones o los coeficientes de la función objetivo, en este sentido el análisis de sensibilidad consiste en estudiar cómo evoluciona el optimo y el valor de la función objetivo del optimo ante variaciones de dichos términos independientes y coeficientes.

            Estudia los intervalos para los cuales la modificación de un valor 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 del Análisis de Sensibilidad.

Establecer un intervalo de números reales en el cual el dato que se analiza puede estar contenido, de tal manera que la solución sigue siendo óptimo siempre que el datopertenezca a dicho intervalo.

Investigar el cambio en la solución óptima del problema, cuando se producen cambios en los parámetros del modelo

Características del Análisis de Sensibilidad.

            El análisis de sensibilidad es una herramienta efectiva por dos razones fundamentales.

Ø  Los modelos de programación lineal son frecuencias grandes y costosas por lo tanto no es recomendable para usarlos en un solo caso.

Ø  Los elementos que se dan como datos para un problema de programación lineal la mayoría de las veces son estimaciones; por lo tanto es necesario investigar o tener en cuenta más de un conjunto de casos posibles. 

Análisis de Sensibilidad: Resolución Grafica.

            Para ilustrar de forma clara y sencilla en qué consiste el análisis de sensibilidad se utiliza nuevamente la metodología grafica. Ejemplo de ello.

Una compañía forestal tiene un predio de 100 hectáreas de bosques para explotar. Talar y dejar el suelo para uso agrícola tiene un costo inmediato de M$10 por hectárea y un retorno posterior de M$50 por hectárea. Una alternativa es talar y plantar pino que tiene un costo inmediato de M$50 por hectárea y un retorno posterior de M$120 por hectárea. De aquí que los beneficios netos de ambos planes sean de M$40 y M$70 por hectárea, respectivamente. Desafortunadamente, el segundo plan no puede ser aplicado a todo el terreno ya que sólo se dispone de recursos inmediatos por M$4.000.

·         Formule y resuelva gráficamente un modelo de Programación Lineal que provea el plan más eficiente de explotación, indicando claramente la solución óptima y valor óptimo.

·         Suponga que usted puede solicitar un préstamo por M$1.000 por el cual deberá retornar con posterioridad el monto de M$1.400 (una vez concluidos los proyectos). Sin reoptimizar, ¿tomaría usted estos recursos adicionales?

El Análisis de Sensibilidad para la parte b) y c) se puede hacer gráficamente siguiendo algunos criterios detallados. En cuanto a este caso particular se tiene:

Máxima variación: (0,100)

Mínima variación: (100,0)

Z(Max Var) = 40*0 + 70*100 = 7.000
Z(Min Var) = 40*100 + 70*0 = 4.000
R1(Max Var) = 10*0 + 50*100 = 5.000
R1(Min Var) = 10*100 + 50*0 = 1.000

Precio Sombra R1 = (7.000 – 4.000) / (5.000 – 1.000) = ¾

El aumento del lado derecho (1.000) se encuentra en el rango donde el precio sombra es válido (hasta 5.000)

Por tanto el aumento en el beneficio total es:
1000 * Precio Sombra = 1000 * 3/4 = 750

Es decir, nuevo V(P) =6.250 + 750 = 7.000

Donde el aumento (M$750) es claramente inferior al costo adicional (M$1.400) por tanto no se tomarían estos recursos adicionales.

Sin resolver nuevamente el problema, obtener la solución óptima de inversión que resulta al aumentar los retornos posteriores de la primera alternativa de M$50 a M$60.

Esta variación es equivalente a cambiar el coeficiente de X en la función objetivo de M$40 a M$50.

Luego, analizamos si esta variación está contenida en el intervalo de C1 que garantiza la actual solución óptima: (Para C2=70)

- 1 <= -C1/C2 <= -1/5

C1 puede variar entre {14, 70} y se conserva la actual solución óptima. Luego la variación propuesta no produce un cambio en la actual solución óptima.

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 los parámetros para el que se mantiene la base.