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

...