Tc20100203Pistas

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) 3 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 FibraTul tiene que decidir dónde instalar puntos de acceso para Internet inalámbrico (Wi-Fi), entre un conjunto 
J = {1,2, . . . ,n} de posibles localizaciones. Para cada localización j, se conoce el costo correspondiente de 
instalación, dado por la constante conocida Cj. 
Una ley recientemente aprobada obliga a FibraTul a instalar puntos de acceso de manera que todos los barrios 
de la ciudad tengan cobertura Wi-Fi. 
Se ha dividido a la ciudad en m barrios, cada uno con un número de 1 a m. La Comisión Nacional de 
Comunicaciones le ha proporcionado a FibraTul una matriz de nxm en la cual cada fila representa una posible 
localización para un punto de acceso y cada columna j representa un barrio de la ciudad. Los elementos aij de 
la matriz son unos y ceros. Cuando aij=1 significa que si se instala un punto de acceso en la localización i, ese 
punto de acceso dará cobertura Wi-Fi al barrio j. Cuando aij=0 significa que si se instala un punto de acceso en 
la localización i, ese punto de acceso NO dará cobertura Wi-Fi al barrio j. 
¿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 Ceferino Namuncurá plantea una heurística para resolver el problema. Para cada fila i, calcula cuántos unos 
tiene esa fila y las ordena por la cantidad de unos que tiene la fila, desde la que tiene más unos hasta la que 
tiene menos. Hasta que todos los barrios estén cubiertos, instala un punto de acceso en cada localización 
correspondiente a la fila i, recorriéndolas en el orden dado por la cantidad de unos. 
Indique qué inconvenientes tiene la heurística propuesta, si es que los tiene. ¿Qué condiciones se deberían dar 
para que funcione bien? 
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 los productos X1 y X2 a partir de los recursos R1, R2 y R3. Aquí vemos el planteo: 
2 X1 + 3 X2 <= 240 (kilos de R1/mes) 
2 X1 + 2 X2 <= 180 (kilos de R2/mes) 
 X1 + 2 X2 <= 150 (kilos de R3/mes) 
Z = 20 X1 + 35 X2 (MAXIMO) (20 es el beneficio unitario de X1 y 35 es el beneficio unitario de X2) 
Sin embargo, el que escribió las tablas óptimas para el problema no completó todos los datos. A continuación 
presentamos las dos tablas óptimas incompletas. 
Optima Directo 20 35 Optima Dual 240 180 150 
Ck Xk Bk A1 A2 A3 A4 A5 Bk Yk Ck A1 A2 A3 A4 A5 
20 X1 1 0 2 0 -3 240 Y1 5 1 2 0 -2 1 
0 X4 0 0 -2 1 2 150 Y3 10 0 1 
35 X2 0 1 -1 0 2 Z= 2700 0 0 
 Z= 0 0 5 0 10 
1) Se sabe que la tabla óptima dual tiene una alternativa (es decir que además hay otra tabla óptima del 
dual). Sin embargo, lo que nosotros te pedimos es que completes las dos tablas óptimas que te presentamos 
anteriormente, justificando la inclusión de los números (es decir, por qué la completás de ese modo). Indicá la 
relación entre las variables del directo y las del dual y la definición de las mismas. 
2) 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 R3 y tiene un beneficio de $15. Además, por imposiciones 
del mercado, se incorpora una demanda máxima de 25 unidades para X1. ¿Cuál será el nuevo plan de 
producción? 
3) Una empresa ofrece la posibilidad de comprar recurso R1 a $10/kg. Además esta empresa vende 
recurso R3 a $5/kg. Lo que exige la empresa para comprarnos R1 es que todo lo obtenido en la compra de R1 
lo gastemos comprándole a esa misma empresa R3. Como el negocio de venderle R1 y comprarle R3 parece 
que viene “enganchado” pero no nos exige nada acerca de las cantidades a venderle de R1 y a comprarle de R3 
queremos que determines cuánto conviene venderle a esta empresa de R1 y cuánto conviene comprarle de R3. 
Se quiere saber cuál es la estructura óptima de producción luego de analizar esta posibilidad. 
NOTA: Detalle los cálculos efectuados en la parte B. B2 y B3 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) Es un problema de cobertura de conjuntos, en el cual cada localización cubre determinados barrios y se 
debe determinar en qué localizaciones instalar un punto de acceso de Internet Wi-Fi para minimizar el costo total 
de instalación, cubriendo todos los barrios. Haciendo un paralelo con el problema de cobertura de conjuntos que 
aparece en las teóricas (en una de las clases a través de la web) las localizaciones serían los vuelos y los barrios 
serían las ciudades. 
Para resolverlo se define una variable bivalente por cada localización (Yj, con j=1…n) que vale 1 si se instala un 
punto de acceso en esa localización. 
El funcional del problema consiste en minimizar la sumatoria con j desde 1 hasta n de (Yj . Cj) 
Para cada barrio hay que asegurar que esté cubierto por alguna (o más de una, esto es hipótesis) de los puntos 
de acceso instaladas: 
Para cada barrio i la sumatoria con j desde 1 hasta n de aij . Yj debe ser mayor o igual que 1. 
Si se supone que un barrio no puede ser cubierto por más de un punto de acceso las restricciones que se 
indican arriba deben ser de igual a 1. 
 
A2) Una crítica que se le puede hacer tiene que ver con priorizar las localizaciones que cubren más cuando lo 
que hay que priorizar es a aquellos barrios que son cubiertos por pocas localizaciones, para instalar en alguna 
de ellas un punto de acceso. Tampoco se fija cuando pasa a la siguiente localización, si los barrios que cubre 
esa localización ya están cubiertos porque si así fuera ¿para qué instalar un punto de acceso en esa 
localización?. Otra crítica es que no tiene en cuenta los costos y que no tiene en cuenta los empates. 
Esta heurística funcionaría bien si las localizaciones que más barrios cubren justamente cubren barrios distintos. 
Funcionaría mal si las localizaciones que más cubren, lo hacen todas en los mismos barrios. 
 
A3) Para plantear una heurística hay que enfocarse en los barrios (ordenados por la cantidad de localizaciones 
que los cubren de menor a mayor), para cada barrio asignar un punto de acceso en la localización que lo cubre 
que cubra más barrios (siempre que esos barrios no estén cubiertos, sino no hay que sumar ese barrio en la 
cuenta de la localización). 
 
Parte B) 
 
Optima Directo 20 35 Optima Dual 240 180 150 
Ck Xk Bk A1 A2 A3 A4 A5 Bk Yk Ck A1 A2 A3 A4 A5 
20 X1 30 1 0 2 0 -3 240 Y1 5 1 2 0 -2 1 
0 X4 0 0 0 -2 1 2 150 Y3 10 0 -2 1 3 -2 
35 X2 60 0 1 -1 0 2 Z= 2700 0 0 0 -30 -60 
 Z= 2700 0 0 5 0 10 
 
 
B2) Se debe incorporar el nuevo producto en la tabla óptima utilizando la matriz inversa óptima del directo. Si al 
incorporarlo se fabrican menos de 25 unidades no hay que incorporar una nueva restricción. De lo contrario hay 
que pasar al dual e incorporar la restricción. Cuando se incorpora el producto podemos ver que el funcional 
sigue teniendo el mismo valor(no aumenta) aunque se fabrica el nuevo producto. Como al agregar una 
restricción nunca mejora el funcional y la nueva restricción nos va a bajar la producción de X1, ya podemos ver 
que no conviene incorporar el nuevo producto. 
 
B3) Es una variación simultánea. Para las variaciones simultáneas sacar los rangos de cada restricción es un 
error porque los rangos son válidos si cambia solamente un recurso.