Dualidad

UNIVERSIDAD NACIONAL DE INGENIERIA SEDE: UNI - NORTE Prueba del modelo y Evaluación de la solución.

Teoría de Dualidad y Análisis de Sensibilidad
Prof. :M.C. Ing. Julio Rito Vargas Avilés I.O. 2008

Dualidad y análisis de sensibilidad

Introducción.
• La asignación de probabilidades a los eventos es una tarea difícil que muchos gerentes pueden mostrarse difícil a hacer, por lo menos concierto grado de exactitud. En algunos casos prefieren decir “creo que la probabilidad de que este evento ocurra está entre 0.5 y 0.7”.

• Bajo estas circunstancias, como en cualquier aspecto de decisión gerencial, es útil realizar un análisis de sensibilidad para determinar cómo afecta a la decisión la asignación de probabilidades.
• El análisis de sensibilidad concierne el estudio de posiblescambios en la solución óptima disponible como resultado de hacer cambios en el modelo original.

Variaciones que podemos realizar en el modelo general:
Mediante el análisis de sensibilidad pueden existir diferentes tipos de cambios en el modelo original como: 1. Cambios en los coeficientes de la función objetivo, Cij

2. Cambios en los recursos, bi
3. Cambios en los coeficientestecnológicos, aij

4. Adición de una nueva variable y Xi
5. Adición de una nueva restricción. aij >= bi

Dualidad y análisis de sensibilidad
Teoría de dualidad: • La teoría de dualidad parte de que asociado a todo problema de 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 desituaciones.
• 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.

Dualidad y análisis de sensibilidad
Esencia de la teoría de dualidad: Dada la forma estándar para el problema primal (izquierda), su problema dual tiene la forma que se muestra a la derecha. Max Z   c j x j
j 1 n

Min

W   bi yi
i 1

m

sujetoa:

sujeto

a:

a
j 1

n

ij

x j  bi

a
j 1

n

ij

yi  c j

xj  0

yi  0

El problema dual usa exactamente los mismos parámetros que el problema primal, pero en diferentes lugares.

Dualidad y análisis de sensibilidad
Esencia de la teoría de dualidad: Dada la forma matricial del problema primal (izquierda), y del problema dual. Max Z  cx
sujeto Ax  bx0 a:

Min W  yb
sujeto yA  c y0 a:

Donde C y Y son vectores fila y b y x son vectores columna.

Dualidad y análisis de sensibilidad

Problema primal y dual para el ejemplo Wyndor Glass Co.
Max Z  3 x1  5 x2
sujeta x1  4 2 x2  12 3 x1  2 x2  18 x1  0 x2  0 a:

Min W  4 y1  12 y 2  18 y3
sujeta a: y1  3 y3  3 2 y 2  2 y3  5 y1  0 y2  0 y3  0

A la izquierdase muestra el problema primal en forma algebraica y a la derecha el problema dual en forma algebraica.

Problema primal y dual para el ejemplo Wyndor Glass Co.
Max
Z  3 sujeta  x1  5 x2    a:

Min

W   y1 sujeta

y2 a:

4 y3 12   18   0 2  3  2  0

0 1 4 0   x1   12  2       x2  3 18 2      x1  0   x   0     2

y1  y1

y2 y2

1 y3 0  3 

5

y3   0

0

A la izquierda se muestra el problema primal en forma matricial y a la derecha el problema dual en forma matricial.

Solución del P. dual, para el ejemplo Wyndor Glass Co.

La solución óptima es: Y1=0 , Y2=1.5, Y3=1 para z= 36

Solución del primal, para el ejemplo Wyndor Glass Co.

Precio sombra

La solución óptima es:x1=2 y x2=6 para z= 36

Comparando solución del Primal con el Dual

Problema primal

Problema Dual

Dualidad y análisis de sensibilidad
MAX Z= 3X1 + 4X2 – 2X3 S. a: 4X1 – 12X2 + 3X3 < 12 –2X1 + 3X2 + X3 < 6 –5X1 + X2 – 6X3 < -40 3X1 – 4X2 – 2X3 < 10 X1 > 0, Min W = 12Y1 + 6Y2 – 40Y3 + 10Y4 S. a: 4Y1 – 2Y2 – 5Y3 + 3Y4 >= 3 –12Y1 + 3Y2 + Y3 - 4Y4 >= 4 X2 < 0, X3 Variables duales Y1 Y2...