C1 Prim2014

Universidad de Chile
IN3701: Modelamiento y Optimizaci´on
Facultad de Cs. F´ısicas y Matem´aticas Profs: Daniel Espinoza, Fernando Ord´on
˜ez
Departamento de Ingenier´ıa Industrial Aux: B.Bahamondes, C. Bonet,
D. Fuentealba, C. Haye, P. Jofr´e,
H. Navarrete

Control 1 – Primavera 2014
P1 Considere un conjunto N1 de palomas mensajeras que deben llegar a un conjunto N2 de nidos, donde
no todas laspalomas pueden llegar a todos los nidos. Sea A el conjunto de pares ordenados que
indica si una paloma puede ocupar un nido. Es decir si (i, j) ∈ A entonces la paloma i ∈ N1 puede
ocupar el nido j ∈N2 . Se desea encontrar la asignaci´on de palomas a nidos que maximice el numero
de asignaciones hecho. Este problema se conoce como el problema de emparejamiento (matching) de
cardinalidad maxima enun grafo bipartito.
a) (2 ptos) Formule un problema de optimizaci´on con variables enteras que encuentre la asignaci´on
de palomas a nidos de mayor cardinalidad.
b) (2 ptos) Muestre que este problemase puede escribir como un problema de flujo en redes.
Explique que tipo de problema de flujo es, describa el grafo en que este problema ocurre y
explique el sentido de las variables.
c) (2 ptos)Demuestre que los dos problemas encontrados arriba son equivalentes.

P2 Dada la relajaci´on lineal del problema de la mochila
m´ax
s.a.

n
i=1 bi xi
n
i=1 wi xi

0 ≤ xi ≤ 1

≤W
i = 1...n

a) (1.5 ptos)Explique porque solo es necesario considerar items que tienen bi y wi del mismo signo.
b) (2.5 ptos) Muestre que asignar los items en orden decreciente del valor bi /wi hasta agotar la
capacidad Wentrega la soluci´on o´ptima de este problema.
c) (2 ptos) Caracterize los puntos extremos del poliedro de la relajaci´on lineal del problema de la
mochila.

P3 Considere el problema que enfrenta elCentro Despacho Econ´omico de Carga del sistema interconectado del norte grande (CDEC-sing) para la planificaci´on de la producci´on de energ´ıa el´ectrica cada
semana. El objetivo del CDEC-sing es...