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)

...