Tc20100217Pistas

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) 17 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 A la derecha vemos el plano de una planificación urbana que consta de 36 lotes. 
En cada lote se pueden construir una fábrica, un edificio de oficinas, un edificio de 
viviendas, un shopping, una plaza o un depósito (también puede dejarse el lote 
vacío, pero para que la urbanización sea considerada exitosa debe tener pocos 
lotes vacíos y también la menor cantidad posible de plazas porque no dan 
ganancia). Cada fábrica debe estar alejada al menos 6 lotes de cada edificio de 
viviendas. Cada edificio de viviendas debe estar a no más de 2 lotes de un 
shopping. Cada depósito debe estar a menos de 6 lotes de alguna fábrica. Cada 
 
edificio de viviendas debe tener una plaza a no más de 1 lot e. Se deben construir al menos 5 edificios de 
viviendas, a lo sumo 6 edificios de oficina, no más de 2 depósitos y no más de 2 shopping. 
¿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 Abel Fatala propone la siguiente heurística de construcción: Colocar 6 edificios de viviendas en la primera fila 
y 6 fábricas en la última fila. Luego, por cada edificio de viviendas construir una plaza en un lote de la segunda 
fila. Completar el resto con edificios de oficina. 
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. 
 
BI) Una empresa nos solicitó que analicemos su plan de producción, que está representado en un modelo de 
PL. Tienen tres productos que piensan lanzar al mercado y para fabricarlos utilizan 3 recursos. Uno de los 
productos tiene una demanda mínima. El funcional maximiza la ganancia por ventas. Como los dueños no 
entienden la resolución del problema por medio del método simplex les comentamos que resultados obtuvimos: 
los tres productos se fabrican, y no hay sobrantes de ningún recurso, aunque si deciden aumentar la cantidad de 
alguno de los recursos solo les convendría comprar dos de los tres, explicándoles cuanto podían comprar y 
hasta qué precio de cada uno de los recursos (les aclaramos hasta qué precio porque ellos no tienen un precio 
sugerido para la compra de ninguno de los recursos, así que teóricamente podrían pedir el precio que quisieran). 
Entonces uno de los dueños nos hizo la siguiente pregunta: ¿qué pasa si la demanda mínima que les dije es 
incorrecta?, Porque en realidad podemos llegar a cumplir parte o toda la demanda consiguiendo producto 
terminado de otro fabricante a igual calidad pero a un costo superior a nuestro precio de fabricación. Te pedimos 
que nos digas bajo qué condiciones les conviene comprar el producto o no. Justificá tu respuesta y aclará qué 
hipótesis utilizaste. 
BII) Una empresa fabrica P1 y P2 a partir de R1 y R2. Hay una demanda mensual mínima para P2 
de 10 unidades. Cuenta con un programa Lineal para su producción mensual. 
A continuación se muestran las ecuaciones iniciales y las tablas óptimas directa y dual de dicho Programa 
Lineal: 2 X1 + 2 X2 < 80 (kg. de R1); X1 + 2 X2 < 50 (kg. de R2); X2 > 10 (un. de P2); 
Z = 60 X1 + 40 X2 (MAX) 
 Ck Xk Bk A1 A2 A3 A4 A5 
Se presentan tres posibilidades luego de ob- 60 X1 30 1 0 1/2 0 1 
servar la sol. óptima (sólo se puede elegir una) 0 X4 0 0 0 -1/2 1 1 
a)Comprar 20 kg. de R1 pagando $ 200 (en total) 40 X2 10 0 1 0 0 -1 
b) Vender 10 kg. de R2 cobrando $ 700 (en total) Z = 2200 0 0 30 0 20 
c) Comprar 5 un. de P2 (para reducir en 5 la de- 80 50 -10 
manda mínima, pagando $ 5 por unidad. Bk Yk Ck A1 A2 A3 A4 A5 
¿Cuál de las tres posibilidades es más 80 Y1 30 1 1/2 0 -1/2 0 
conveniente? -10 Y3 20 0 -1 1 -1 1 
 Z = 2200 0 0* 0 -30 -10 
 
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) Este es un problema de asignación en el cual hay que determinar (en algunos casos) cuántos elementos de 
cada tipo asignar, en qué lote asignar cada elemento de cada tipo para minimizar la cantidad de lotes en los 
cuales no se asigna ningún elemento o tienen construidas plazas. 
Una hipótesis importante para resolver el problema es cómo se cuenta la cantidad de lotes (o cuadras) de 
distancia. 
Para cada lote se deben tener 6 variables bivalentes, una por cada tipo de cosa que se puede construir. La 
suma de las seis variables de un mismo lote es menor o igual que 1 (si vale cero el lote está vacío). Si se quiere 
se puede poner una séptima variable, que vale 1 si no se construye nada (lote vacío) En este caso la suma de 
variables para un mismo lote vale 1. 
Luego hay que asegurar, para cada lote donde hay un edificio de viviendas, que valga 1 al menos una de las 
variables que indican que hay una plaza para los lotes que están contiguos. Asimismo, para cada lote donde hay 
un edificio de viviendas, hay que asegurar, 6 lotes a la redonda, que valgan cero las variables que indican que 
hay una fábrica (la suma debe ser menor o igual que 1). Para cada edificio de viviendas, se asegura que valga 1 
al menos una de las variables que indican que hay un shopping para los lotes que están a 2 lotes o menos. 
Esto se puede hacer con un ejemplo y después generalizándolo, o se puede hacer con subíndices (lo cual es 
más difícil y hay que estar muy seguro de lo que se quiere decir y cómo decirlo). Un error que hemos visto es 
contar la diferencia de distancia haciendo el valor absoluto de la resta entre las distancias de dos ubicaciones. El 
signo de valor absoluto no existe en programación lineal, para salvar estos casos se debe usar programación de 
metas con exceso y defecto. 
Luego se suman las bivalentes por cada tipo de construcción que tiene restricciones y así se asegura que no se 
construyan más edificios, shopping, etc. de lo que indica el enunciado. 
 
A2) La heurística no tiene en cuenta los límites de cantidad de cada tipo de cosa que se puede construir, no 
respeta distancias entre viviendas y fábricas, construye plazas de más (si se pusieran tres plazas en la segunda 
fila, separadas por un lote, alcanzaría para cumplir la restricción), no construye shopping como se exige para 
cada edificio de viviendas, ni depósitos para las fábricas. 
 
 
Parte B) 
 
 
B1) Si fabrican los tres productos y no tienen sobrante de ningún recurso, como hay 4 restricciones, parecería 
que se fabrica más de la demanda mínima y esa restricción tiene la slack distinta de cero. Pero como dice que 
de los tres recursos conviene comprar dos, la slack del tercer recurso debe de estar en la base valiendo cero 
(por eso no conviene comprarlo). Así que se fabrica exactamente la demanda mínima. Para comprar producto 
terminado y venderlo posteriormente no importa si el precio de compra es menor o no que el costo propio de 
fabricación. Lo que importa es que el precio de compra sea menor o igual que el precio de venta + el valor 
marginal de la restricción de demanda mínima (si el producto no tuviera demanda el preciode compra debería 
ser menor o igual que el precio de venta). 
 
B2) Basta con analizar las tres posibilidades cambiando los coeficientes de las variables del dual en el Z. 
Trabajando en la tabla óptima dual cambiamos b1 (que actualmente vale 80) por 100, luego cambiamos b2 (que 
actualmente vale 50) por 40 y finalmente cambiamos b3 (que actualmente vale -10) por -5. Hay que tener en 
cuenta que, como la tabla óptima del dual es una solución alternativa, eso significa que cada recurso tiene dos 
valores marginales (porque hay dos tablas óptimas del dual) y que eso corresponde a una solución óptima que 
es un punto degenerado (como podemos ver en la tabla óptima del directo). En la otra tabla óptima del dual 
estarán en la base Y1 e Y2. Sabemos que de las dos tablas la tabla que tiene el menor valor marginal para un 
determinado recurso es aquella en la cual el rango permite comprar el recurso y la tabla que tiene el mayor valor 
marginal para un determinado recurso es aquella en la cual el rango permite vender el recurso y eso debemos 
tenerlo en cuenta para ver en qué tabla probar para R1 y R2. De aquellas soluciones que den ganancia 
(comparando el nuevo funcional menos el costo o más la ganancia de la operación con el funcional actual) se 
elegirá la más conveniente por mayor ganancia o por rendimiento por peso invertido.