Tc20100728Pistas

Vista previa del material en texto

Nota de este examen: 
 
Nota de Cursada: Nota en la libreta: 
 
Coloquio de Modelos y Optimización I (71.14) 28 de julio de 2010 
Apellido y nombre:........................................................................... Nro.de Padrón:....... .................... 
Cursó en el cuatrimestre del año 
Turno de T.P.: (día y horario) ................................................... Ayudante/s:....................................... 
Oportunidad en la cual rinde (1ra, 2da, 3ra) Rinde como: Regular: Libre: 
 
 
A) Los residentes de Hometown viven mayoritariamente en 5 torres representadas en el dibujo adjunto por las 
letras “A” a “E”. Enfrente de Hometown hay una isla, llamada Worktown, donde están los edificios de oficinas P, 
Q, R, S y T. 
 
Como hay un río entre Hometown y Worktown, a menos 
que se construyan puentes, los habitantes de Hometown 
no pueden ir a trabajar a Worktown. El presupuesto 
comunal prevé construir dos puentes y los lugares 
candidatos son los que se indican como “One”, “Two”, 
“Three” y “Four”. Se conocen las constantes Pij que 
representan la cantidad de personas que viven en la torre 
i y que trabajan en el edificio de oficinas j. 
Para indicar la distancia que se debe recorrer entre cada 
torre y el puente y entre el puente y cada edificio de 
oficinas se toma la distancia más corta considerando 
cada cuadrito de la cuadrícula como una cuadra y 
teniendo en cuenta que no se puede ir en diagonal, 
considerando que cada cuadrito es un kilómetro. Por 
ejemplo, ir de la torre E a la oficina T si se construyera el 
puente “Four” implicaría recorrer 9 kilómetros (5 desde el 
edificio E hasta el puente, 3 en el puente y 1 desde el 
puente hasta T). 
¿Qué es lo mejor que se puede hacer con la información disponible? Se pide: 
A1 Análisis del problema, Objetivo completo y claro. Hipótesis necesarias para su resolución, definición de 
variables. Modelo matemático para su resolución por Programación Lineal. 
A2 Donald Trump plantea una heurística de construcción: Calcular para cada torre la cantidad de personas que 
viven en la misma (independientemente del edificio de oficinas en el cual trabajan) y construir los dos puentes 
que queden más cerca de la mayor cantidad de personas posible. Indique qué inconvenientes tiene la 
heurística propuesta, si es que los tiene. 
A3 Plantee una heurística de construcción para resolver el problema. Recuerde que su heurística debe tender al 
mejor resultado y que no debe tener los problemas que Ud. criticó en el punto A2. 
 
B) Supongamos que tenemos una empresa que fabrica P1 y P2 a partir de 2 X1 + 3 X2 < 90 (kg. R1/mes) 
dos recursos, R1 y R2. Además tenemos una demanda mensual máxima 2 X1 + X2 < 50 (kg. R2/mes) 
para P1 de 15 unidades. Contamos con un programa Lineal para la X1 < 15 (un/mes) 
producción mensual. A continuación se muestran las ecuaciones iniciales Z = 120 X1 + 100 X2 (MAX) 
y las tablas óptimas directa y dual de este problema. (120 y 100 son los precios de venta) 
 Ck Xk Bk A1 A2 A3 A4 A5 
 100 X2 20 0 1 1/2 -1/2 0 
 120 X1 15 1 0 -1/4 3/4 0 
 0 X5 0 0 0 1/4 -3/4 1 
 Z = 3800 0 0 20 40 0 
 90 50 15 
 Bk Yk Ck A1 A2 A3 A4 A5 
 90 Y1 20 1 0 -1/4 1/4 -1/2 
 50 Y2 40 0 1 3/4 -3/4 1/2 
I) Una empresa amiga nos ofrece el siguiente 
negocio: nos vende 5 unidades de P1, pero con la 
condición de que utilicemos esas 5 unidades para 
satisfacer la demanda máxima de P1, es decir, que 
efectivamente las vendamos. ¿A qué precio (como 
máximo) les debemos pagar las 5 unidades para que 
el negocio sea conveniente para nosotros?. 
II) Se presentan dos posibilidades luego de observar 
la solución óptima (sólo se puede elegir una): 
a) Comprar 20 kilos de R1 pagando $200 (en total) 
b) Vender 10 kilos de R2 cobrando $700 (en total) Z = 3800 0 0 0* -15 -20 
 
Los puntos BI y BII son independientes entre sí y se deben resolver refiriéndose al enunciado original. 
 
Para aprobar debe tener Bien dos puntos de A y dos de B (considerando que BII está integrado por dos 
puntos). Además, A1 no puede estar Mal. 
 
 
USO 
INTERNO 
Algunas pistas para la resolución. 
 
Atención: este documento no contiene el resuelto del examen, sino algunas pistas para ayudar a su resolución. 
 
Parte A: 
 
A1) Es un problema de distancias mínimas en el cual hay que seleccionar cuáles son los dos puentes que se van 
a construir para que los habitantes de Hometown que tienen que recorrer más distancia para ir a trabajar tengan 
que recorrer la menor distancia posible (si lo que se minimiza fuera la suma de las distancias a recorrer, el 
modelo podría compensar algunos que están a mucha distancia con otros que están a corta distancia). 
 
En primer lugar hay que definir variables bivalentes Yk para cada puente, que valdrán 1 si se construye ese 
puente y cero sino. 
 
Luego hay que definir la distancia que tiene que recorrer la gente que va desde una torre i hasta un edificio de 
oficinas j por el puente k. Como la cantidad de gente que va de i a j es constante (Pij) y la distancia entre i y j 
pasando por el puente k también es una constante que se puede sacar del dibujo (llamémosla Dijk), solamente 
basta con multiplicar Pij por Dijk y por la bivalente Yk del puente (si no se construye el puente, nadie pasará de i 
a j por ese puente. Luego, de esas dos variables, hay que calcular verdadera distancia que recorrerá la gente 
entre i y j que es la menor de las cuatro variables de los puentes para esa combinación (i,j) que sea distinta de 
cero (porque la gente va a ir de i a j por uno solo de los puentes, el que le quede más cerca). Ojo, si al sacar el 
mínimo, no anulamos las restricciones de las que son iguales a cero (se puede hacer usando 1 menos la 
bivalente) tomará que el menor es cero. 
 
También se podría suponer que, como van a ir por el camino más corto, si se sabe qué par de puentes se 
construye (haciendo restricciones de AND para cada par de puentes) se pone en la distancia el total de personas 
de una torre a un edificio multiplicado por la variable AND que corresponde y por la constante distancia del 
puente construido que queda a menor distancia entre i y j. 
 
Luego, para el funcional calculamos cuál de las variables de verdadera distancia entre i y j es mayor y 
minimizamos esa variable. 
 
A2) Esta heurística no tiene en cuenta a qué edificio tienen que ir a trabajar las personas, entonces va a enviar a 
la gente al edificio de oficina que quede más cerca, que no es exactamente adonde tienen que ir. Tampoco 
determina qué hacer en caso de empate. 
 
A3) Una opción sería armar para cada par torre-edificio, un orden de los puentes, del más cercano al menos 
cercano a ese par de edificios. Luego, se revisa cuáles son los puentes que quedan más cerca de la mayor 
cantidad de pares. Si las cantidades Pij son muy diferentes entre sí, hay que incorporarlas al cálculo para tratar 
de construir los puentes más cercanos a la mayor cantidad de personas posible, 
 
Parte B) 
BI) Si compramos las 5 unidades, hay que bajar nuestra demanda máxima de X1 en 5 unidades, porque las 5 
que compramos las tenemos que vender. Si bajamos la demanda máxima a 10 unidades (en 5 unidades) vamos 
a ganar menos dinero que ahora. Considerando que las 5 unidades las vamos a vender, como el precio de 
venta es de 12 unidades vamos a ganar 60 pesos. Si la baja del funcional es menor que 60 pesos, la diferencia 
entre 60 pesos y la baja del funcional nos dice a cuánto tenemos que pagar las 5 unidades como máximo. Si la 
baja del funcional es mayor que 60 pesos, el negocio no conviene y no podemos comprar las 5 unidades. 
 
BII) 
 
En los dos casos, podemos reemplazar la disponibilidad de recursos por la nueva que quedaría cuando 
compramos o vendemos recurso y ver cómo se modifica el funcional. Para que convenga, en el punto a) lo que 
aumenta el funcional debe ser mayor que $200, y en el punto b) lo que disminuye el funcional debe ser menor 
que$700. Al haber dos tablas duales alternativas, es probable que tengamos que cambiar de tabla para analizar 
alguno de los dos negocios.