Dualidad

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

1

Esta 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´on1.

Pag. 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´asaber 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 u
´tiles
de dualidad y elconcepto 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, paraencontrar 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 tablade relaciones
primal-dual.
2
3

Suponemos restricciones l.i
O 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 formabastante
algor´ıtmica, tanto para problemas de minimizaci´on como de maximizaci´on.
´
´
PROBLEMA DE MINIMIZACION
PROBLEMA DE MAXIMIZACION
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
t
s.a A · y ≤ c
yi ≥ 0

TeoremaD´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


α1·
 α2· 


Sea β·1 β·2 · · · β·n =  ..  una matriz dem filas y n columnas.
 . 
αm·
Sea el par primal-dual siguiente:
4

Tambi´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 ) · y¯i = 0

i=1,...,m.

ii) (cj...