“METODO DUAL” “ANÁLISIS DE SENSIBILIDAD”

UNIVERSIDAD AUTONOMA DEL CARIBE

INVESTIGACION DE OPERACIONES

TEMA

“METODO DUAL”

“ANÁLISIS DE SENSIBILIDAD”

PRESENTADO POR:

JESÚS SOLANO

JUAN MALDONADO

PRESENTADO A:

NELSON ZÚÑIGA

BARRANQUILLA/ATLÁNTICO

2014

MÉTODO DEL DUAL (TEORIA DE DUALIDAD)

Todo problema de programación lineal tiene asociado con él otro problema de programación lineal llamado DUAL. El problema inicial es llamado PRIMO y el problema asociado (sombra) es llamado el problema PRIMO. Los dos juntos son llamados problemas duales ya que ambos están formados por el mismo conjunto de datos. La solución básica factible óptima de estos problemas es tal que una puede fácilmente ser usada para la solución de la otra. La dimensión del problema de programación lineal influencia la elección del cálculo del primo o del dual.

Si el primo tiene más ecuaciones que variables, es frecuentemente más fácil obtener la solución del dual ya que menor número de iteraciones son requeridas. Además si el primo tiene solución, el dual tendrá solución. Una vez que el problema dual es formulado, el procedimiento de solución es exactamente el mismo que para cualquier problema de programación lineal.

Mecánicamente el dual es formulado partiendo del problema primo en la siguiente forma:

Si el primo es un problema de Maximización, el dual es un problema de Minimización y viceversa.

1. Los coeficientes de la función objetivo del primo se convierten en las restricciones constantes de las ecuaciones del dual.

2. Las restricciones de las ecuaciones del primo se convierten en los coeficientes de la función objetivo del dual.

3. Los coeficientes de las variables del dual en las ecuaciones restrictivas son obtenidas sacando la transpuesta de la matriz de coeficientes del primo ( los arreglos de los coeficientes en las columnas del primo se convierten en los coeficientes de las filas en el dual y viceversa ).

4. Los signos de la desigualdad son invertidos.

5. Las Xn variables del primo son remplazadas por Wm variables en el dual.

Notación matemática:

Primo Contiene m ecuaciones y n variables.

Dual Contiene n ecuaciones y m variables.

La notación matricial del Primo es:

Max Z = CX

Sujeto a:

AX£ b x³ 0

La notación matricial del Dual es:

Min Z = bt W

Sujeto a:

AtW ³ Ct

W³ 0

RELACION DE LOS PROBLEMAS PRIMO Y DUAL

³ 0 £ 0

£ 0 ³ 0 no restringida

= 0

³ 0 ³ 0

£ 0 £ 0

= 0 no restringida.

Ejemplo:

Primo

Min Z = 3X1 - 2X2 + X3

Sujeto a

:

2X1 - 3X2 + X3 £ 1 2X1 - 3X2 + X3 £ 1

2X1 - 3X2 + X3 - ³ 1 - 2X1 + 3X2 - X3 £ -1

2X1 + 3X2 - X4 £ 8 2X1 + 3X2 - X4 £ 8

2X1 + 3X2 - X4 ³ 8 - 2X1 - 3X2 + X4 £ -8

x´s ³ 0

Dual

Max Z = W1 - W2 + 8W3 - 8W4

Sujeto a

:

2W1 - 3W2 + 2W3 - 2W4 £ 3

-3W1 + 3W2 + 3W3 - 3W4 £ -2

W1 - W2 £ 1

- W3 - W4 £ 0

w´s £ 0

Problema de Minimización

Restricciones

Variables

Problema de Maximización

Variables

Restricciones

Ejemplo:

Primo:

Min Z = 2X1 + 3X2

Sujeto a;

2X1 + X2􀀃􀂔 16

X1 + 3X2􀀃􀂕 20

X1 + X2 = 10

X´s³0

Dual:

Max Z=16W1 + 20W2+10W3

Sujeto a;

2W1 + W2 +W3 􀂔 2

W1 + 3W2 +W3􀂔 3

W1 􀂔0, ,W2 ³0, W3 no restringida

Ejemplo:

Primo:

Maximizar Z = 3X1 - X2

Sujeto a;

-X1 + 2X2􀀃􀂕 5

X1 + 3X2􀀃􀂔 -2

X´s³0

Dual:

Max Z=5W1 - 20W2

Sujeto a;

-W1 + W2􀀃􀂔 3

2W1 + 3W2􀀃􀂔 -1

W 1􀀃􀂔 0, ,W2 ³ 0

Ejemplo:

Primo:

Min Z = -2X1 +13X2 +3X3 - 2X4+ X5 + 5X6

Sujeto a;

X1 - X2 + 4X4 – X5+ X6 = 16

X1 + 7X4 - 2X5 + 3X6 􀂕 - 1

5X2 + X3 - X4+ 2X5 - X6 􀂔 5

Xi ³ 0, para 1=1, 2,3

X4 􀂔 0

X5, X6 No restringidas

Dual:

Max Z=16W1 - W2+ 5W3

Sujeto a;

W1 + W2 + 􀂔 -2

-W1 + + 5W3 􀂔 13

+ + W3 􀂔 3

4W1 + 7W2 - W3 ³ -2

W1 -2W2 +2W3 = 1

5W1 + 3W2 - W3 = 5

W1 no restringida,W2 ³ 0, W3􀀃􀂔 0

El valor óptimo en el primo, es siempre igual al valor óptimo del dual. Los valores absolutos de las variables del Dual (w`s) se encontraran en la tabla final (Optima) del primo en la fila Zj-Cj bajo las columnas de las variables que originalmente aportaron las columnas para formar la matriz identidad.

De manera similar el valor absoluto de las variables del primo (x´s) se encontrará en la tabla Optima del Dual en la fila Zj-Cj bajo las columnas de las variables que originalmente aportaron las columnas para formar la matriz identidad.

Interpretación Económica de las variables del Dual.

La solución del problema Dual representa la interpretación económica que es una forma de análisis marginal ( Que pasará si una entidad adicional del insumo es utilizada?). Las variables del Dual Wm en un problema Primo de Maximización de ganancias, son las ganancias marginales de cada insumo o producto adicional. Las variables del Dual son llamadas algunas veces costos marginales o precios sombra. Las variables del Dual Wm en un problema primo de Minimización de costos, son los costos marginales de cada insumo ó producto adicional. La limitación b en las ecuaciones del Primo determina si las variables del Dual se relacionan en insumos o productos marginales.

...