Tc20100721Pistas

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) 21 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) La compañía de aviación VoyageVoyage quiere armar el itinerario que seguirá cada una de las tres 
tripulaciones que trabajan en la misma. Con esas tres tripulaciones (que tienen base en San Francisco, es decir 
que cuando terminan de trabajar tienen que estar de vuelta en esa ciudad) tiene que realizar sí o sí once vuelos, 
que se ven en la tabla siguiente (en la primera columna, que dice “Vuelos”). En las restantes 12 columnas se 
muestran las secuencias posibles de vuelos que considera la compañía (una secuencia es una forma posible de 
hacer determinados vuelos). Los números de cada columna indican el orden de los vuelos dentro de la 
secuencia, por ejemplo en la columna 12 se lee (de arriba abajo): 1, 3, 4, 5 y 2. Eso significa que la secuencia 
tiene como inicio el vuelo “S. Francisco-Seattle” (1), luego “Seattle-Los Angeles” (2), a continuación “Los 
Angeles-Chicago” (3), prosigue con “Chicago-Seattle” (4) y finaliza con “Seattle-San Francisco” (5). El costo de 
asignar a una tripulación a una secuencia determinada de vuelos está en la última fila de la tabla (en miles de 
dólares). 
 
¿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 Mariano Recalde plantea una heurística de construcción: Ordenar las secuencias por costo y elegir la más 
barata, luego la que le sigue si permite hacer vuelos que la anterior no hacía y así sucesivamente seguir 
eligiendo por costo creciente, salteando las que no agregan más vuelos a los ya cubiertos. 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 10 un. 
Cuenta con un programa Lineal para su producción mensual. 2 X1 + 2 X2 < 80 (kg.R1/mes) 
A continuación se muestran las ecuaciones iniciales y las tablas óptimas X1 + 2 X2 < 50 (kg.R2/mes) 
directa y dual de dicho Programa Lineal: X2 > 10 (un./mes) 
Se presentan tres posibilidades luego de observar la solución óptima Z = 60 X1 + 40 X2 (MAX) 
Ck Xk Bk A1 A2 A3 A4 A5 
60 X1 30 1 0 1/2 0 1 
0 X4 0 0 0 -1/2 1 1 
40 X2 10 0 1 0 0 -1 
 Z = 2200 0 0 30 0 20 
 80 50 -10 
Bk Yk Ck A1 A2 A3 A4 A5 
80 Y1 30 1 1/2 0 -1/2 0 
-10 Y3 20 0 -1 1 -1 1 
(sólo se puede elegir una): 
a) Comprar 20 kg. de R1 pagando $ 200 (en total) 
b) Vender 10 kg. de R2 cobrando $ 700 (en total) 
c) Comprar 5 un. de P2 (para reducir en 5 la de- 
manda mínima), pagando $ 5 por unidad. 
¿Cuál de las tres posibilidades es más 
conveniente? 
 
NOTA: Detalle los cálculos efectuados en la 
parte B. 
 Z = 2200 0 0* 0 -30 -10 
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 hay que seleccionar secuencias para que todos los 
vuelos sean cubiertos con el menor costo de tripulación posible (en este caso es similar a lo que se plantea en la 
clase teórica por página web – la cual esperamos hayan leído cuando la recomendamos – que plantea ciudades 
a cubrir con vuelos. 
 
Como no se aclara si se permite o no que un vuelo sea cubierto por más de una secuencia, depende de las 
hipótesis que se tomen. 
El orden que se menciona en el enunciado (orden en el cual se hacen los vuelos dentro de una secuencia) es 
irrelevante, porque todas las secuencias comienzan y terminan en San Francisco (si alguna secuencia no 
empezara o no terminara en San Francisco no se puede hacer sin engancharla con otra porque el enunciado 
dice que todas las tripulaciones tienen que volver a San Francisco. El tema de las tres tripulaciones depende de 
si se supone que una tripulación no puede hacer más de una secuencia (entonces solamente tres secuencias se 
pueden hacer) o si cada tripulación puede hacer más de una secuencia (entonces no importa qué tripulación 
hace cada secuencia sino solamente si se hace o no). 
 
Las variables (una por secuencia) son bivalentes y valen 1 si se hace esa secuencia y cero sino. 
 
Para cada vuelo hay que plantear que la suma de las bivalentes de las secuencias que incluyen ese vuelo debe 
ser mayor o igual que 1 (o igual a 1, depende de la hipótesis que se haya tomado). Si no se plantea esto (un 
error común es igualar este valor a una bivalente, con lo que el vuelo puede no cubrirse si la bivalente vale cero) 
no se asegura que haga todos los vuelos, con lo que el modelo, en su afán de minimizar los costos, no hace 
ninguna secuencia porque no está obligado a cubrir ningún vuelo y lo más económico es no hacer nada. 
 
En Z se minimiza el costo de hacer las secuencias (se calcula multiplicando cada bivalente de cada secuencia 
por el costo que se indica de la misma). 
 
A2) Esta heurística no dice que hacer en caso de empates (hay varios). Tampoco el elegir secuencias baratas 
asegura que se hagan todos los vuelos con el menor costo, porque las secuencias más baratas cubren pocos 
vuelos. 
 
A3) Como en todo caso de cobertura, hay que tener en cuenta cuáles son los elementos (vuelos) que tienen 
menos posibilidades de ser cubiertos y tratar de cubrirlos con secuencias que cubran a la mayor cantidad de 
otros vuelos posibles (es decir, no pesa solamente el costo sino el costo en función de los vuelos cubiertos, una 
secuencia barata que cubre vuelos que son cubiertos por otra secuencia que por poco dinero más cubre esos 
vuelos y más, no debe elegirse como primera opción). 
 
Parte B) 
 
a) 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 $200. 
 
b) La venta de R2 debe ser analizada en la otra solución alternativa que tiene el dual de este problema. Eso se 
puede ver fácilmente porque si en la alternativa óptima dual que figura en el enunciado bajamos la 
disponibilidad de R2 a 40, la tabla deja de ser óptima, entra Y2 a la base, sale Y1 y pasamos a una tabla en 
la cual el valor marginal del R2 es 60, es decir conviene comenzar a analizar el negocio (si en esta tabla 
pudiéramos vender 10 kilos, cobraríamos $700 y el funcional bajaría en $600). De igual manera, en la tabla 
que corresponde hay que analizar el rango de variación para ver si podemos bajar en 10 kilos la 
disponibilidad y conseguir que la tabla siga siendo óptima. 
 
c) Si cambiamos el coeficiente de la demanda mínima (-10) por -5, en la tabla óptima del dual veremos que la 
tabla sigue siendo óptima y que el funcional aumenta en $100. Además hay que considerar, para analizar 
esta situación, que las 5 unidades que se compran deben ser pagadas (a $5 cada una) y deben ser vendidas 
(ya que es producto terminado y lo compramos para suplir la demanda mínima que tenemos de las unidades 
que fabricaba la empresa, aunque no le conviniera hacerlo). Para poder calcular esto necesitamos el precio 
de venta de P2, que puede ser el que figura en el funcional ($40). Es un error lamentablementecomún 
olvidar la ganancia por venta del producto comprado (como no forma parte del modelo es un cálculo que hay 
que hacer “por afuera” del modelo, al igual que el costo de comprarlas)