Tc20100224Pistas

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) 24 de febrero 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 Una empresa de telecomunicaciones diseña instalaciones en sus clientes. Estas instalaciones consisten en 
un gran número de computadoras que deben estar interconectadas. Un diseño común es instalar las 
computadoras en determinada cantidad de anillos (rings). Las comunicaciones dentro de un mismo anillo son 
muy baratas y rápidas. Las comunicaciones entre anillos (entre dos computadoras que pertenecen a distintos 
anillos) es bastante cara. Desafortunadamente, hay límites en el tamaño de los anillos. 
Más formalmente, digamos que hay 14 computadoras, cada una tiene requerimientos diarios de comunicación 
que se han estimado en Ri mensajes. Entre cualquier par de computadoras i y j es necesario enviar Min(Ri,Rj) 
mensajes diarios. Los datos de la cantidad de los requerimientos de comunicación de cada computadora se 
muestran a continuación: 
Nombre de la computadora A B C D E F G H I J K L M N 
Requerimiento diario (Rj) 90 40 30 95 50 90 80 40 30 40 30 80 50 30 
Cada computadora debe instalarse en un anillo. Si dos computadoras están en el mismo anillo, los mensajes 
que se envíen entre ellas no tienen costo. Cuando dos computadoras están en distintos anillos, cada uno de los 
mensajes que se envíen de una a otra cuesta $1. Existen límites sobre la cantidad de mensajes que pueden 
circular dentro de cada anillo. Diariamente, no pueden intercambiarse menos de W1 mensajes ni más de W2 
mensajes. 
¿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 Angel Di Mazo plantea una heurística para resolver el problema. Ordena las computadoras de mayor a 
menor según la cantidad de mensajes a enviar (Rj). 
Mientras queden computadoras en la lista 
Mientras no se exceda el límite de mensajes (W2) del anillo 
Toma la primera y la última de la lista y la coloca en el mismo anillo. Luego las elimina de la lista. 
Fin mientras. 
Genera un nuevo anillo 
Fin mientras 
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 = 12 X1 + 10 X2 (MAX) 
y las tablas óptimas directa y dual de este problema. (12 y 10 son los precios de venta) 
 Ck Xk Bk A1 A2 A3 A4 A5 
 10 X2 20 0 1 1/2 -1/2 0 
 12 X1 15 1 0 -1/4 3/4 0 
 0 X5 0 0 0 1/4 -3/4 1 
 Z = 380 0 0 2 4 0 
 90 50 15 
 Bk Yk Ck A1 A2 A3 A4 A5 
 90 Y1 2 1 0 -1/4 1/4 -1/2 
 50 Y2 4 0 1 3/4 -3/4 1/2 
B1) 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? 
B2) Se quiere determinar la conveniencia de fabricar 
un nuevo producto al cual llamaremos X6. Este 
producto consume por unidad 1 kilo de R1 y 1 kilo de 
R2 y tiene un precio de venta de $15. Además, se Z = 380 0 0 0* -15 -20 
incorpora una demanda máxima de 25 unidades para X6. ¿Cuál será el nuevo plan de producción? 
NOTA: Detalle los cálculos efectuados en la parte B. B1 y B2 son independientes entre sí. 
 
Para aprobar debe tener Bien dos puntos de A y uno de B. 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) En este problema de asignación cuadrática hay que determinar cuántos anillos se forman y qué 
computadoras están en cada anillo. 
Si hay K computadoras a lo sumo habrá K (14) anillos (es importante que la variable que indica cantidad de 
anillos tenga un tope, no puede ser variable la cantidad de variables que tiene el problema). 
Se deben tener variables Yij que valen 1 si la computadora i se instala en el anillo j. 
La sumatoria de las Yij variando j de 1 a 14 debe ser igual a 1. 
El carácter de asignación cuadrática aparece en el funcional porque si las dos computadoras están en el mismo 
anillo el costo de comunicación es cero. 
Para cada par de computadoras se puede averiguar con un AND si pertenecen a un determinado anillo. 
Por ejemplo, en el caso de las computadoras A y B se puede hacer un AND para ver si ambas pertenecen al 
anillo 1 2 YAYB1 <= YA1 + YB1 <= 1 + YAB1 
Del mismo modo se puede hacer un AND cambiando el número de anillo para detectar si A y B están juntas en 
algún anillo. Luego, sumando todas las variables YABk, si la suma da 1 es porque están juntas en algún anillo, 
si la suma da cero es porque no están en el mismo anillo. Entonces igualamos la sumatoria de las YABk 
variando k de 1 a 14 a la variable YABjuntas que es una variable bivalente. En el funcional multiplicamos el 
costo de comunicación de A con B (40 mensajes a 1 peso el mensaje) por (1 – YABjuntas). 
Lo mismo se hace para todos los pares de computadoras. 
También hay que agregar restricciones para controlar la cantidad de mensajes de computadoras de un mismo 
anillo (para eso también sirven las variables YABjuntas, para multiplicarlas por la cantidad de mensajes 
intercambiados entre A y B y calcular cuántos mensajes se intercambian en un mismo anillo). 
 
A2) Una crítica que se le puede hacer es que al colocar el primero con el último van a quedar en el mismo anillo 
computadoras que intercambian pocos mensajes y las que intercambian muchos (por ejemplo, dos de 90) 
pueden quedar en anillos distintos y pagar mucho costo. Además no controla el mínimo de mensajes del anillo. 
Tampoco dice cómo ordenar en caso de empates (que en el problema se dan y mucho). 
 
A3) Una idea es mejorar la heurística propuesta tratando de que las computadoras que quedan en el mismo 
anillo tengan una cantidad similar de requerimientos diarios. 
 
Parte B) 
 
 
B1) Esto implica dejar de vender 5 de las 15 que vendíamos nosotros. Por eso a la cuenta que se saca siempre 
que hay una compraventa de producto terminado (Precio de Venta – Precio de Compra debe ser mayor o igual 
que cero) hay que agregarle un costo adicional que es el valor marginal de la restricción de producción máxima 
para X1. Para saber cuánto me jorobaría habría que convertir (en el dual) el límite de la tercera restricción, que 
actualmente es 15, en 10 y ver cuál es el funcional óptimo del dual. La diferencia entre el funcional actual de 
380 y ese nuevo funcional óptimo me dará el costo adicional de tener que vender las 5 unidades y dejar de 
vender 5 que fabricaba yo. Como venderé las 5 unidades a 12 pesos cada una, ganaré 60 pesos. 60 pesos 
menos el costo adicional de tener que vender las 5 unidades y dejar de vender 5 de las que fabricaba yo me 
dará el costo total que conviene pagar por esa 5 unidades.B2) Hay que incorporar el producto en el directo, usando la matriz inversa óptima para llevar el vector de la tabla 
inicial a la tabla óptima, ver cuánto se fabrica y ver si se fabrican más de 25 unidades. En este caso tendremos 
que agregar la restricción en la tabla dual.