Dualidad Investigación de Operaciones

[pic 1]REPUBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA

EDUCACION UNIVERSITARIA

CIENCIA Y TECNOLOGIA

INSTITUTO UNIVERSITARIO POLITECNICO

“SANTIAGO MARIÑO”

EXTENSION COL – SEDE “CIUDAD OJEDA”

PRACTICA Nº 2 Dualidad

Autores:

                 Elibregan Colina C.I 27.082.126

Victor Correa C.I 25.492.290

Andrés Castellanos C.I 26.653.181

Ángel Arrieta C.I 26.653.223

Ciudad Ojeda, agosto 2019

PARTE A

PROBLEMA PRIMAL A DUAL

     El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de modelamiento matemático que nos permite rescatar la información del problema original conocido comúnmente como modelo primal. En consecuencia es suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución óptima y valor óptimo del problema equivalente (primal o dual según sea el caso). Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el Teorema de Holguras Complementarias.

Las relaciones de dualidad se pueden resumir en el siguiente cuadro:[pic 2]

     La tabla anterior se puede interpretar tanto de izquierda a derecha como de derecha a izquierda.

Por ejemplo: [pic 3]

     Si se desea pasar el problema primal planteado a problema dual, se sigue el siguiente procedimiento.

     Como en este caso el problema primal es de minimización, para definir su respectivo problema dual leeremos la tabla que resume las relaciones de dualidad desde izquierda a derecha. En consecuencia, el problema dual será uno de maximización. Adicionalmente la primera y segunda restricción del problema primal definirán las variables de decisiones (variables duales) en el problema dual (Y1 e Y2, respectivamente), siendo los coeficientes en la función objetivo los actuales valores de los lados derechos de las restricciones del problema primal.

     De esta forma la función objetivo del problema dual queda definida por la siguiente expresión:[pic 4]

     Luego por cada variable en el problema primal vamos a tener la misma cantidad de restricciones en el problema dual. En este caso las variables X1, X2 y X3 definirán la estructura de las restricciones 1, 2 y 3 en nuestro problema dual. Por ejemplo la primera restricción del problema dual (asociada a la variable primal X1) sería 2Y1+2Y2 <= 160.

     Notar que los coeficientes que ponderan a las variables duales son los parámetros asociados a la variable X1 en el primal en la primera y segunda restricción, respectivamente. La restricción en el dual es del tipo “<=” debido a que la variable X1 en el problema primal de minimización tiene la condición de no negatividad (“>=0”). Por último el lado derecho de la restricción es el coeficiente que tiene la variable X1 en la función objetivo del problema primal.

     Siguiendo el procedimiento las restricciones del problema dual serían:[pic 5]

     Finalmente como las 2 primeras restricciones del problema primal son del tipo “>=” en el problema primal de minimización, las respectivas variables duales asociadas en el problema de maximización serán no negativas. De esta forma el problema dual es:

[pic 6]

CONDICIÓN DE KARUSH–KUHN–TUCKER

     Las condiciones de optimalidad establecidas en el Teorema de Karush Kuhn Tucker (KKT) permiten abordar la resolución de modelos de Programación No Lineal que consideran tanto restricciones de igualdad (ecuaciones) como desigualdad (inecuaciones). En términos comparativos las condiciones de KKT son más generales que el Método de Lagrange el cual se puede aplicar a problemas no lineales que consideran exclusivamente restricciones de igualdad.

     Básicamente el procedimiento consiste en resolver el problema no lineal como uno sin restricciones, luego si la solución óptima de dicho problema no cumple la totalidad o parte de las restricciones del problema se activan dichas restricciones (en conjunto y/o secuencialmente) y se resuelve nuevamente. Esto se repite hasta llegar a un conjunto de restricciones activas cuya solución también satisface las restricciones omitidas. Notar que si se han activado la totalidad de restricciones sin encontrar una solución factible, entonces el problema es infactible.

Programación lineal y condiciones KKT: Un Ejemplo

     Considere el siguiente problema de programación lineal:

[pic 7]

     Las restricciones y el objetivo son todos cóncavos (y convexos) ya que son lineales. Por lo tanto, es suficiente encontrar un punto KKT y este punto debe ser óptimo. Podemos reescribir el problema P en forma:

[pic 8]

     Para escribir las condiciones KKT, observe lo siguiente:

[pic 9]

     Ahora podemos escribir las condiciones de KKT para este problema como:

     Viabilidad Primaria:  [pic 10]

     Viabilidad Dual: [pic 11]

     Holgura complementaria: [pic 12]

     Considere la doble viabilidad por un momento. Puedo expandir las matrices para obtener un sistema de ecuaciones:

1 − λ1 − 2λ2 + λ3 = 0

1 − 2λ1 − λ2 + λ4 = 0

λ1, λ2, λ3, λ4 ≥ 0

O:

λ1 + 2λ2 − λ3 = 1 2λ1 + λ2 − λ4 = 1

λ1, λ2, λ3, λ4 ≥ 0

     Como λ3, λ4 ≥ 0, actúan como variables excedentes y podemos escribir la viabilidad dual como:

[pic 13]

     Ahora sería suficiente encontrar valores para x1, x2, λ1, λ2, λ3 y λ4 que satisfagan las condiciones de KKT y podríamos resolver el problema de programación lineal P. Podemos demostrar que el punto óptimo para este problema es x = 8/3 y y = 2/3 usando un método gráfico. La Figura 1 (a) muestra la región factible del problema, así como las curvas de nivel de la función objetivo (curvas para las cuales x1 + x2 = k, donde k es una constante fija). El valor k aumenta yendo de izquierda a derecha y de abajo hacia arriba, por lo que la solución óptima debe ocurrir en la intersección de las líneas x1 + 2x2 = 4 y 2x1 + x2 = 6. Puede comparar el valor del objetivo en la propuesta del punto óptimo x = 8/3 y y = 2/3 al valor del objetivo en los otros puntos extremos. Por ejemplo, en el punto extremo X = 3, Y = 0, vemos que el valor del objetivo es solo 3, en comparación a 10/3 en el punto de optimación. Ahora podemos ver que para que se cumplan las condiciones de KKT, debemos tener λ3 = λ4 = 0 porque x1> 0 y x2> 0 en la optimización y la holgura complementaria requiere que: λ3 (−x1) = 0 y λ4 (−x2) = 0 en la optimización. Esto deja λ1 y λ2. Sabemos que estos deben satisfacer las ecuaciones en la Expresión 2. Por lo tanto, vemos que cuando λ1 = λ2 = 1/3, la Expresión 2 es correcta. Así: hemos escrito:

...