Dualidad y An´alisis de Sensibilidad

Universidad de Chile

Facultad de Ciencias F´ısicas y Matem´aticas

Departamento de Ingenier´ıa Industrial

IN34A: Clase Auxiliar

Dualidad y An´alisis de Sensibilidad

Marcel Goic F.1

1Esta es una versi´on bastante preliminar por lo que puede contar con numerosas faltas de ortograf´ıa y

errores no forzados. Si encuentran alguno favor de denunciarlo a mgoic@ing.uchile.cl

IN34A: Optimizaci´on Pag. 1

1. Una brev´ısima introducci´on.

Encontrar el ´optimo de un problema de optimizaci´on, es solo una parte del proceso de

soluci´on. Muchas veces nos interesar´a saber como var´ıa la soluci´on si var´ıa alguno de los

par´ametros del problema que frecuentemente se asumen como determin´ısticos, pero que

tienen un caracter intr´ınsicamente aleatorio. M´as especificamente nos interesar´a saber para

que rango de los par´ametros que determinan el problema sigue siendo valida la soluci´on

encontrada.

Otro aspecto interesante es el tema de dualidad. Dualidad resulta de buscar relaciones que

permitan obtener informaci´on adicional de un problema de optimizaci´on general. Esto, traducido

a PL nos conduce a relaciones primal-dual. Adem´as veremos algunos teoremas ´utiles

de dualidad y el concepto de precio sombra.

2. Acerca de Dualidad

Todo problema de optimizaci´on (primal), tiene un problema asociado (dual) con numerosas

propiedades que los relacionan y nos permiten hacer un mejor an´alisis de los problemas. A

continuaci´on se describen los resultados que se ocupar´an en la resoluci´on de los problemas.

2.1. Construcci´on del problema dual

Bastante en general, para encontrar el dual de un problema lineal:

1. Si es problema de minimizaci´on el dual ser´a de maximizaci´on y viceversa.

2. En el dual habr´a tantas variables como restricciones 2 en el primal.

3. En el dual habra tantas restricciones como variables en el primal.

4. Los coeficientes de la funci´on objetivo del dual vendr´an dados por los coeficientes del

lado derecho de las restricciones del primal.

5. Los coeficientes del lado derecho del dual vendr´an dados por los coeficientes de la

funci´on objetivo del primal.

6. Los coeficientes que acompa˜nar´an a las variable en una restriccion del dual corresponder

´an a aquellos coeficientes que acompa˜nan a la variable primal correspondiente a la

restriccion dual 3.

7. Para saber si las restricciones duales son de , = ´o , se recurre a la tabla de relaciones

primal-dual.

2Suponemos restricciones l.i

3O si se prefiere, los coeficeintes ser´an el resultado de transponer la matriz A de coeficientes

IN34A: Optimizaci´on Pag. 2

8. Para saber si las variables duales son  0, = 0 ´o  0, se recurre a tabla de relaciones

primal dual.

Relaciones Primal-Dual

Estas relaciones nos permiten pasar de un problema de primal a su dual en forma bastante

algor´ıtmica, tanto para problemas de minimizaci´on como de maximizaci´on.

PROBLEMA DE MINIMIZACI ´ON PROBLEMA DE MAXIMIZACI ´ON

Restricciones Variables

  0

= Irrestricta

  0

Variables Restricciones

 0 

Irrestricta =

 0 

2.2. Algunos teoremas de dualidad

Consideremos el siguiente par primal-dual:

(P) m´ın z = c · x

s.a A · x  b

xi  0

(D) m´ax w = y · b

s.a At · y  c

yi  0

Teorema D´ebil de Dualidad

Si ¯x e ¯y son factibles para (P) y (D) respectivamente, entonces z(¯x)  w(¯y).

Teorema Fundamental de Dualidad4

Dados un par de problemas primal-dual, si uno de ellos admite soluci´on ´optima, entonces

el otro tambien la admite y los respectivos valores ´optimos son iguales.

Teorema de Holgura Complementaria

Sea



·1 ·2 · · · ·n



=

2

6664

1·

2·

...

m·

3

7775

una matriz de m filas y n columnas.

Sea el par primal-dual siguiente:

4Tambi´en conocido como teorema fuerte de dualidad

IN34A: Optimizaci´on Pag. 3

(P) m´ın z = c · x

s.a i · x  bi

xi  0

(D) m´ax w = y · b

s.a j · y  cj

yi  0

Sean ¯x e ¯y soluciones factibles para los problema (P) y (D) respectivamente. ¯x e ¯y son

´optimos si y solo si:

i) (i · ¯x − bi) · ¯yi = 0 i=1,...,m.

ii) (cj − ¯y · j) · ¯xj = 0 j=1,...,n.

Obs:Notar que (i · ¯x − bi) y (cj − ¯y · j) son las variable de holgura de los problemas

(P) y (D) respectivamente.

2.3. Acerca de los precios sombra

Los valores de las variables duales en el ´optimo tienen una interpretaci´on econ´omica interesante

en problemas de programaci´on lineal: Corresponde a las tasas marginales de variaci´on

del valor de la funci´on objetivo ante variaciones unitarias del lado derecho de una restricci´on.

Por este motivo se le llama precio sombra al vector de variables duales en el ´optimo.

3. Acerca de sensibilidad

Como ya se dijo, nos interesa ver como se ve afectada la soluci´on de un problema de optimizaci

´on si cambia alguno de los par´ametros del problema. En este ´ambito, podemos distinguir

2 tipos de an´alisis:

Analisis de sensibilidad: Consiste en determinar cual es el rango de variaci´on de los

par´ametros del problema de modo que la base ´optima encontrada siga siendo ´optima.

Analisis post optimal: Consiste en determinar como var´ıa la base ´optima si cambia

alguno de los par´ametros del problema.

En la presente sesi´on nos concentraremos en an´alisis de sensibilidad dejando el an´alisi post

optimal para un poco mas adelante.

Consideremos la forma estandar siguiente:

(P) m´ın z = c · x

s.a A · x = b

x  ~0

IN34A: Optimizaci´on Pag. 4

Sea B la base ´optima. Nos interesa estudiar el rango de variaci´on de los parametros c y b de

modo que B siga siendo ´optima 5.

Variaci´on en el parametro b.

Buscamos el rango en el que puede tomar valores b de modo que la base B siga siendo

´optima. Para ello debemos verificar:

1. Factibilidad: xB = B−1b  0

2. Optimalidad: ¯cR = cR − cBB−1R  0

Como en la ecuaci´on 2. no hay dependencia explicita de b, no impone condiciones y

por tanto solo debemos verificar 1.

Variaciones en el parametro c

Buscamos el rango en el que puede tomar valores c de modo que la base B siga siendo

´optima. Para ello debemos verificar:

1. Factibilidad: xB = B−1b  0

2. Optimalidad: ¯cR = cR − cBB−1R  0

Como en la ecuaci´on 1. no hay dependencia explicita de b, no impone condiciones y

por tanto solo debemos verificar 2. Notemos que al variar un coeficiente de cj a ˆcj e

imponer la condici´on 2. surgen dos casos:

• Caso 1: variable xj es no b´asica.

¯cj = ˆcj − cBB−1j cambia.

¯ck = ck − cBB−1k no cambia (i 6= j).

Por lo tanto s´olo tenemos que imponer 1 ecuaci´on: la de costo reducido asociado

a variable que cambi´o.

• Caso 2: variable xj es b´asica.

¯ck = ¯ck − ˆcBB−1k puede cambiar 8 k.

Por lo tanto, no basta con examinar una ´unica ecuaci´on y se debe inspeccionar

todas las ecuaciones de costo reducido. As´ı:

 Si cambia cj de variable no b´asica se impone ¯cj  0.

 Si cambia cj de variable b´asica se impone ¯ck  0 8 xk no b´asica.

5En rigor, tambien podr´ıa interesarnos estudiar otras situaciones como por ejemplo variaciones en los

coeficientes de la matriz A, o que pasar´ıa si agregamos una nueva variable, etc. Sin embargo, por el momento

s´olo estudiaremos estos 2 casos cl´asicos

IN34A: Optimizaci´on Pag. 5

4. Problemas

4.1. Problema 1

Una florista sabe hacer solo 2 tipos distintos de arreglos florales (x1 y x2) para los

cuales dispone de 3 tipos distintos de flores: rozas, tulipanes e ibizcos. Los requerimientos

de flores para cada arreglo, la disponibilidad de flores y los precios de cada arreglo vienen

dados por:

FLORES x1 x2 DISPONIBILIDAD

Rozas 3 1 300

Tulipanes 1 1 140

Ibizcos 1 3 300

PRECIO 2000 1000 -

1. Formule un PPL que resuelva el problema de maximizaci´on de ingresos por ventas

sujeto a la disponibilidad de recursos.

2. ¿Cual es el problema dual asociado? ¿Que situaci´on podr´ıa estar optimizando?

3. Usando el teorema de holgura complementaria, encuentre el ´optimo del problema dual

sabiendo que el ´optimo primal viene dado por (x1 = 80, x2 = 60).

4. Suponga que retorna frustrado despu´es que una bella dama le cerrara la puerta cuando

usted le llevaba amablemente una rosa, un tulip´an y un ibizco 6. Si se encuentra con

la florista, ¿Cuanto cree que estar´ıa dispuesta a pagar ella por sus flores?

Soluci´on

1. A estas alturas del curso, todos debieran de poder modelar un problema tan sencillo

como este por lo que ahorrar´e comentarios:

m´ax z = 2000x1 + 1000x2

s.a 3x1

...