Tc20100714Pistas

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) 14 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) Una profesora va a pasar un semestre en la Universidad de Islandia y quiere llevar consigo toda la ropa que 
necesita. Después de organizar el material relacionado con el trabajo, se dio cuenta de que, debido a las 
restricciones de peso del equipaje que puede llevar, debe restringir la cantidad de ropa que puede incluir en el 
equipaje. Puede llevar hasta 4 kilos y 32 dm3 de ropa. La profesora va a llevar una campera y piensa comprar 
en Islandia un polar islandés (llamada camisa islandesa) . 
Ella tiene tres polleras (A, B y C), 3 pantalones (D, E y F), 4 camisas (G, H, I y J) y tres vestidos (K, L y M). De 
estas piezas quiere llevar aquellas que maximicen la cantidad de conjuntos que tendrá para vestir en Islandia, 
incluyendo el vestido que usará en el viaje. Un conjunto resulta de la combinación de una camisa con una 
pollera o con un pantalón. Un vestido también es considerado un conjunto. Algunas combinaciones, sin 
embargo no son viables porque van contra las reglas del buen gusto. En las siguientes tablas se muestran (con 
un punto) las combinaciones posibles de piezas de ropa, peso y volumen de cada pieza de ropa. 
 
¿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 Teresa Calandra plantea una heurística para resolver el problema: Llevar la pollera que combine con más 
camisas, el pantalón que combine con más camisas, la camisa que combine con más polleras y/o pantalones y 
los tres vestidos. 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) Una empresa fabrica P1 y P2 a partir de R1 y R2. Hay una demanda mensual mínima para P2 de 20 kg. 
Cuenta con un programa Lineal para su producción mensual. 2 X1 + 2 X2 < 160 (kg./mes) 
A continuación se muestran las ecuaciones iniciales y las tablas óptimas X1 + 2 X2 < 100 (kg./mes) 
directa y dual de dicho Programa Lineal: X2 > 20 (kg./mes) 
I) Se decide estudiar la posibilidad de la elaboración de un nuevo producto Z = 60 X1 + 40 X2 (MAX) 
 Ck Xk Bk A1 A2 A3 A4 A5 
 60 X1 60 1 0 1/2 0 1 
 40 X2 20 0 1 0 0 -1 
 0 X4 0 0 0 -1/2 1 1 
 Z = 4400 0 0 30 0 20 
 160 100 -20 
 Bk Yk Ck A1 A2 A3 A4 A5 
 160 Y1 30 1 1/2 0 -1/2 0 
 -20 Y3 20 0 -1 1 -1 1 
que consume 2 kg. de R1 y 1 kg. de R2. Su benef. 
es de $ 80 por unidad y no participa en la rest. de 
demanda mínima. Sin embargo, no se pueden 
fabricar más de 50 un. por mes de este producto 
¿Es conveniente?. 
II) Se presentan dos posibilidades luego de 
observar la sol. óptima (sólo se puede elegir una). 
a) Disminuir la demanda mínima de P2 a 10 
kg/mes. Eso cuesta $ 150 (en total). 
b) Comprar 10 kg. de R1 pagando $ 100 (en total) 
¿Qué posibilidad es más conveniente? Z = 4400 0 0* 0 -60 -20 
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 dos 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) Este problema es conocido como “problema de la mochila” porque hay un espacio limitado (en peso y 
volumen en este caso) y hay que definir qué se incluye en la “mochila” de los candidatos a entrar (como en el 
problema de la Guía 7.2, el del barco de las Naciones Unidas a Ruanda) 
 
El objetivo es determinar qué prendas va a llevar la profesora a su viaje, de modo de maximizar la cantidad de 
conjuntos que se pueden formar (cumpliendo con las restricciones de peso y volumen) 
 
Las variables (una por cada artículo o prenda de vestir) son bivalentes y valen 1 si la profesora lo va a llevar en 
el viaje y cero sino. 
 
Se deb en plantear restricciones para controlar el máximo peso y el máximo volumen (con los datos de la 
segunda tabla del enunciado, multiplicando cada uno por la bivalente que corresponda). 
 
Como hay que maximizar la cantidad de conjuntos, hay que plantear variables bivalentes con restricciones de 
AND para cada posible conjunto (intersección fila-columna de la primera tabla que tiene un punto). Por ejemplo, 
si lleva la pollera A y la camisa G se produce un conjunto AG, es decir que el and de YA con YG da YAG que es 
un conjunto (recordar que los vestidos se consideran conjuntos). 
 
En Z se maximiza la suma de las variables de conjuntos. 
 
A2) Esta heurística no dice que hacer en caso de empates (hay varios), no controla el peso ni el volumen y sólo 
lleva una camisa, una pollera y una blusa. Por otra parte, tampoco se fija si la camisa combina con la pollera y el 
pantalón que está llevando. 
 
A3) Una alternativa es armar una tabla con los conjuntos (el peso total y el volumen total) y definir una relación 
peso-volumen que permita ordenar esta tabla. Después, como en el ejercicio 7.2 de la Guía, hay que ir poniendo 
los conjuntos y controlando que no se exceda el peso ni el volumen (si un conjunto no entra, pasar al siguiente, 
hasta que no queden más conjuntos para probar). 
 
 
Parte B) 
 
I) Primero hay que introducir el producto (ojo que a la columna de X5 hay que cambiarle el signo para armar la 
matriz inversa óptima porque la tercera restricción es de mayor e igual). Luego hay que verificar si se fabrican 
más de 50 unidades del producto nuevo. Si este es el caso, hay que pasar al dual esa tabla óptima (agregando 
en el dual una fila porque hay un producto nuevo, y una nueva variable slack Y6 que será el costo de 
oportunidad del nuevo producto X6) y armar la matriz inversa óptima del dual y agregar la nueva restricción. 
Finalmente, una vez que llegamos a la tabla óptima del dual, hay que comparar el valor del funcional con el que 
teníamos hasta el momento (4400) para ver si conviene o no este nuevo producto. 
 
II) 
a) Simplemente se puede reemplazar el -20 por -10 y se ve el valor del Z en la tabla dual óptima. Si el Z no 
aumenta, no conviene. Si aumenta, el aumento debe superar los 150 pesos que cuesta hacer esto para que 
convenga. 
 
b) No conviene, porque si aumentamos la disponibilidad de R1, entra Y2 a la base y sale Y1, con lo que deja de 
ser escaso R1, no ganamos nada y gastamos $100.