• Author / Uploaded
• Ewduar

Citation preview

República Bolivariana de Venezuela Instituto Universitario Politécnico “Santiago Mariño” Escuela de Ingeniería Industrial Extensión Maturín

DUALIDAD

Profesora:

Bachiller:

Ing. Stefanía D’Andrea Vega

Ewduar Campos C.I. 19.782.591

Sec. H

Maturín, mayo de 2015

Índice

Introducción ........................................................................................................... 3 Dualidad .................................................................................................................. 4 Relaciones entre los Modelos Primal y Dual ..................................................... 4 Esencia de la Teoría de Dualidad ........................................................................ 5 Importancia de la Teoría de Dualidad ................................................................. 6 Tabla Prima-Dual ................................................................................................... 6 Origen del Problema Dual .................................................................................. 10 Elementos de los Problemas Primal Dual ........................................................ 10 Establecimientos de las Propiedades Débil .................................................... 16 Propiedades de Soluciones Complementarias ............................................... 19 Desarrollo de las Relaciones entre Primal y Dual ........................................... 19 Conclusión ........................................................................................................... 21 Bibliografía ........................................................................................................... 22

Introducción

Uno de los descubrimientos más importantes durante el desarrollo inicial de la programación lineal fue el concepto de dualidad y sus muchas e importantes ramificaciones. Este descubrimiento revelo que asociado a todo problema de programación lineal existe otro problema lineal llamado dual. Las relaciones entre el dual y su original (llamado primal) son extremadamente útiles en una gran variedad de situaciones. Por ejemplo, se vera que de hecho la solución optima del problema dual es la que proporciona los precios sombra descritos en las practicas al introducir el análisis de sensibilidad. Uno de los papeles clave que juega la teoría de la dualidad es la interpretación y realización del análisis de sensibilidad. De hecho la dualidad nos permitirá tratar dicho análisis desde el punto de vista algebraico pudiendo así generalizarlo y aplicarlo a cualquier problema de programación lineal, independientemente de cual sea su tamaño, numero de variables y/o restricciones. Los orígenes de la dualidad, tal y como hoy se conoce, son, en boca del propio Dantzig, atribuibles al celebre matemático John Von Neumann, quien, en octubre de 1947, conjeturo por primera vez la existencia de un problema dual asociado al modelo de programación lineal.

3

Dualidad

La dualidad es la propiedad o el carácter de lo que es doble o contiene en sí dos naturalezas, dos sustancias o dos principios, por ejemplo. En programación lineal, dualidad significa que existe otro problema de PL asociado con cada problema de PL, que se designa como problema dual (D). En esta relación con el problema dual, el problema original se designa como problema primario (P). El concepto de dualidad desempeña importantes papeles dentro de la programación lineal (también en la no lineal), tanto desde un punto de vista teórico como práctico. Una de las ventajas de la existencia del problema dual es la posibilidad de reducir el esfuerzo computacional al resolver ciertos modelos de programación lineal. La teoría de dualidad parte de que asociado a todo problema de programación lineal (pl), existe otro problema lineal llamado dual. Las relaciones entre el problema dual y el problema original o (primal) son en extremos útiles en una gran variedad de situaciones. Uno de los aspectos más importantes de la teoría de dualidad es la interpretación y realización del análisis de sensibilidad. Relaciones entre los Modelos Primal y Dual

Observando la estructura de ambos modelos podemos citar las siguientes relaciones entre ellos: 1. Los coeficientes objetivos de uno son los coeficientes recurso del otro. 2. Los coeficientes recurso de uno son los coeficientes objetivo del otro. 3. La matriz de coeficientes tecnológicos de uno es la transpuesta de la matriz de coeficientes tecnológicos del otro.

4

4. Ambos problemas están en formato canónico, como lo comprueban más en detalle las siguientes características 4.1. El objetivo del primo es maximizar en cambio el objetivo del dual es minimizar. 4.2. Las restricciones del Primo son del tipo =, mientras que las del dual son del tipo =. 4.3. Las variables de ambos problemas están restringidas a ser mayores o iguales que cero.

Esencia de la Teoría de Dualidad

La esencia de la Teoría de la Dualidad viene dada a través de la forma estándar para el problema primal (izquierda), y su problema dual tiene la forma que se muestra a la derecha.

Entonces podemos decir que el problema dual usa exactamente los mismos parámetros que el problema primal, pero en diferentes lugares. Para recalcar esta comparación, observamos ahora estos mismos problemas en la notación matricial, Donde c y y son vectores fila y b y x son vectores columna.

5

Importancia de la Teoría de Dualidad

Permite resolver problemas de programación lineal de forma sencilla y rápida. Es otra vía para resolver un problema de programación lineal. Facilita profundizar en el contenido económico del problema original (primal). Puede ser utilizada para resolver el caso que se debe considerar la introducción de una nueva variable.

Tabla Prima-Dual

El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de modelamiento 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 las condiciones del Teorema de Holguras Complementarias:

6

Una restricción de igualdad en el programa primal hace que la correspondiente variable dual pueda tener cualquier signo. En cambio, una restricción de desigualdad del tipo >= en el primal implica que la variable dual sea mayor o igual que cero. Si las variables del primal son mayores o iguales que cero, las restricciones del dual son del tipo = 3 x1-x3 = 2 x3 >= 0

Programa dual max 3z1+2z2 2z1+z2 = 1 z1 = 1 -z2 = 0

Las relaciones de dualidad se pueden observar en el siguiente cuadro:

La tabla anterior se puede interpretar tanto de izquierda a derecha como de derecha a izquierda. A continuación se presenta un modelo de optimización que se considera como el problema primal y que en un artículo previo fue resuelto a través del Método Simplex de 2 Fases.

7

Modelo de optimización:

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:

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=” 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:

Tabla Prima Dual:

9

Origen del Problema Dual La teoría de dualidad se basa directamente en la idea fundamental (en particular con respecto al renglón 0). Entonces, en cualquier iteración dada del método simplex para el problema primal los números actuales del renglón 0 se denotan como se muestra en la tabla (parcial) dada en la tabla 6.4.

La idea fundamental conducía a las siguientes relaciones entre las cantidades y los parámetros del modelo original:

Elementos de los Problemas Primal Dual Elementos Primal

10

Elementos Dual

Problema primal y su dual mediante método simplex utilizando variables de holgura, exceso y artificiales; además resolveremos el primal utilizando Simplex maximizando y el dual minimizando. Dado el siguiente modelo primal: ZMAX = 40X1 + 18X2 16X1 + 2X2 ≤ 700 6X1 + 3X2 ≤ 612 X1 ≤ 80 X2 ≤ 120

11

Cuya respuesta es: X1 = 28,75 X2 = 120 S1 = 79.5 S3 = 51.25 Función objetivo = 3310 Solución del problema dual:

12

Este paso se lleva a cabo teniendo en cuenta las relaciones que se expusieron en la definición de la dualidad. Ahora las variables en el dual las representaremos por "ʎ" y corresponden a cada restricción. El modelo queda de la siguiente forma: ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 + 120ʎ4 16ʎ1 + 6ʎ2 + ʎ3 ≥ 40 2ʎ1 + 3ʎ2 + ʎ4 ≥ 18 ʎ1;ʎ4 ≥ 0 Ahora preparamos el modelo para ser resuelto mediante método simplex, utilizaremos el procedimiento en el cual la función objetivo es multiplicada por (-1) y resolveremos el modelo mediante maximización. ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 + 120ʎ4 Lo que es igual (-Z)MAX = -700ʎ1 - 612ʎ2 - 80ʎ3 - 120ʎ4 Ahora dado que los signos de las inecuaciones son mayor o igual procedemos a volverlas ecuaciones agregando variables de exceso, recordemos que en este caso las variables de exceso se restan del lado izquierdo de la igualdad, por ende. 16ʎ1

+ 6ʎ2 + ʎ3

21ʎ1

+ 3ʎ2 + 0ʎ3 + ʎ4

+ 0ʎ4 - 1S1

+ 0S2 = 40

+ 0S1 - 1S2 = 18

ʎ1;ʎ4 ≥ 0 Recordemos que el método simplex solo es posible por la formación de la matriz identidad, sin embargo en una matriz identidad no pueden ir coeficientes negativos, el cual es el caso, por ende recurriremos al artificio denominado "Método de la M grande" utilizando variables artificiales, las cuales siempre se suman.

13

16ʎ1

+ 6ʎ2 + ʎ3

21ʎ1

+ 3ʎ2 + 0ʎ3 + ʎ4

+ 0ʎ4 - 1S1

+ 0S2 + 1A1 + 0A2 ≥ 40

+ 0S1 - 1S2

+ 0A1 + 1A2 ≥ 18

ʎ1;ʎ4 ≥ 0 Ahora si observamos la matriz identidad formada por las variables artificiales, nuestra función objetivo es la siguiente (varía dada la incorporación de las nuevas variables). (-Z)MAX = -700ʎ1 - 612ʎ2 - 80ʎ3 - 120ʎ4 + 0S1 + 0S2 - MA1 - MA2 Recordemos que el coeficiente de las variables de holgura y exceso es 0, además que los coeficientes de las variables artificiales es M, donde M corresponde a un número grande poco atractivo cuyo signo en la función objetivo depende del criterio de la misma, dado que la función es maximizar el signo es negativo. Dado que utilizaremos el método simplex y no un software para la resolución del modelo es necesario que m adquiera valor, en este caso será "-10000" un número bastante grande en el problema. Las iteraciones que utiliza el método simplex son las siguientes:

14

Podemos observar que todos los Cj - Zj son menores o iguales a 0, por ende hemos llegado a la solución óptima del problema, sin embargo recordemos que la función objetivo fue alterada en su signo al principio, por ende se hace necesario regresarle su signo original a Zj y a la fila Cj - Zj. (-Z)max = -3310 *

(-1)

Zmax = 3310 Podemos

cotejar

con

la

función

objetivo

del

modelo

primal

y

encontraremos que hallamos el mismo resultado. Ahora se hace necesario interpretar los resultados de la tabla dual respecto al modelo primal, y esta interpretación se realiza siguiendo los siguientes principios.

15

La interpretación del tabulado final del modelo dual es la siguiente:

Establecimientos de las Propiedades Débil En el contexto de las relaciones de dualidad en programación lineal, los teoremas de dualidad fuerte y dualidad débil constituyen importantes resultados teóricos que contribuyen a la comprensión y resolución de modelos de optimización lineales. Consideremos los siguientes problemas Primal (P) y Dual (D) en su formato matricial:

Lo anterior no constituye una pérdida de generalidad dado que el problema primal puede ser de maximización o de minimización con la consecuente incidencia en la interpretación de los resultados. El Teorema de Dualidad Débil establece que six є IRn, es una solución factible del problema Primal P) y ∏ є IRm, una solución factible del problema Dual D), entonces:

16

Es decir, en el formato descrito anteriormente, el valor que reporta una solución factible del problema dual de minimización al ser evaluada en su respectiva función objetivo, representa una cota superior del valor óptimo del problema primal de maximización. Análogamente, una solución factible del problema primal de maximización al ser evaluada en dicha función objetivo representa una cota inferior del valor óptimo del problema dual de minimización. En conclusión: V(P) 0) la restricción

dual es una igualdad, es decir, su correspondiente variable de holgura o excedente es nula en el óptimo.

-

Si una restricción primal es una desigualdad en el ´optimo, es decir, su

correspondiente variable de holgura o excedente es positiva en el ´optimo, la correspondiente variable dual es cero en el ´optimo.

-

Si una variable dual es positiva en el ´optimo (y ∗ j > 0) la restricción

primal es una igualdad, es decir, su correspondiente variable de holgura o excedente es nula en el ´optimo.

-

Si una restricción dual es una desigualdad en el ´optimo, es decir, su

correspondiente variable de holgura o excedente es positiva en el ´optimo, la correspondiente variable primal es cero en el ´optimo. Desarrollo de las Relaciones entre Primal y Dual

El número de variables que presenta el problema dual se ve determinado por el número de restricciones que presenta el problema primal. El número de restricciones que presenta el problema dual se ve determinado por el número de variables que presenta el problema primal.

19

Los coeficientes de la función objetivo en el problema dual corresponden a los términos independientes de las restricciones (RHS), que se ubican del otro lado de las variables. Los términos independientes de las restricciones (RHS) en el problema dual corresponden a los coeficientes de la función objetivo en el problema primal. La matriz que determina los coeficientes técnicos de cada variable en cada restricción corresponde a la transpuesta de la matriz de coeficientes técnicos del problema primal. El sentido de las igualdades y desigualdades se comporta según la tabla de TUCKER, presentada a continuación:

20

Conclusión

La dualidad consiste en resolver gráficamente algunos problemas lineales donde el número de restricciones es mayor que el número de variables. De acuerdo a las teorías de dualidad y elaboración de tablas se le podrá dar solución a problemas primal-dual. La dualidad permite realizar importantes interpretaciones de los problemas de programación lineal, además nos ayuda a generar métodos como el método dual de simplex de gran importancia de optimización y la programación lineal. En la dualidad débil, el valor de cualquier solución del problema de minimización, provee una cota superior del valor óptimo del problema de maximización. El óptimo valor de función objetivo del problema primal será igual al valor de la función objetivo del problema dual de una solución dual óptima.

21

Bibliografía

Frederick S. Hillier, Gerald J. Lieberman. Investigación de Operaciones. 7ma edición, México: Editorial, McGraw Hill, 2002.

http://www.significados.com/dualidad/ [Consultado: 19 de mayo de 2015, 17:49 am].

https://jrvargas.files.wordpress.com/2008/08/analisisdesensibilidad_2010.pdf/ [Consultado: 19 de mayo de 2015, 18:12 am].

http://www.gestiondeoperaciones.net/programacion_lineal/ [Consultado: de mayo de 2015, 20:12 pm].

http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingenieroindustrial/investigaci%C3%B3n-de-operaciones/dualidadenprograma ci%C3%B3n-lineal// [Consultado: 19 de mayo de 2015, 19:11 pm].

22

18