Optimizacion-Redes

ING200 Optimizacio´n Tarea 3

Prof. A. Cubillos, E. Moreno, J. Pereira, L. Reus, S. Varas & W. Yushimito

Primer Semestre 2015, xx de xx de 2015

Instrucciones:

La tarea es individual.[pic 2]

La tarea debe estar escrita a mano. S´olo se permitir´a de forma impresa los c´odigos AMPL o resultados de este mismo que utilice.

La fecha de entrega es el Jueves xx de xx en hora de clase o hasta las 13:30 hrs en la secretar´ıa de Pregrado.

Cualquier infracci´on al C´odigo de Honor de la Universidad ser´a denunciada a Pregrado, donde ser´an aplicadas las sanciones correspondientes a la gravedad de la falta.

Si hay algo que usted considera que falta, haga un supuesto razonable e ind´ıquelo claramente en su respuesta.

Se evaluar´a el avance general en TODOS los ejercicios ([pic 3]de la nota), y se corregir´a un ejercicio de la tarea, escogido al azar, de forma exhaustiva ([pic 4]de la nota).

Ejercicios

1. (Modelos de redes)

La compaa de cerveza “Los Tres Mosqueteros” desea abastecer una ciudad con sus productos. La empresa posee su centro de distribucin en la ciudad a, y desea abastecer la ciudad b, contando con los caminos que se muestran en la figura.

[pic 5]

Est´a probado que en la ciudad b el consumo de alcohol es excesivo, por lo que la empresa est segura de poder vender todo lo que llegue a dicha ciudad, ganando P por cada tonelada de cerveza. El problema es que en cada camino existen inspectores que no permiten que se transporte ms de cij toneladas de cerveza (para evitar un consumo desmesurado), donde i y j son las ciudades que une un determinado camino.

1. Formule el problema que enfrenta la empresa al tratar de determinar la cantidad de cerveza que enva a la ciudad b (y por dnde), pero respetando las exigencias de los inspectores. Suponga que slo desea distribuir sus productos a la ciudad b, y no a los pueblos intermedios.

Figura 1: Modelo

[pic 6]

Figura 2: Datos

[pic 7]

1. Suponga ahora que se quiere construir una va directa entre a y b, que permita transportar toneladas de cerveza, pero para poder construirla le piden a la empresa que pague K por la construccin. Modifique el problema anterior, de manera que permita decidir si conviene pagar los K para la construccin del nuevo camino. Nota: la capacidad de la va directa es cab

Figura 3: Modelo

[pic 8]

Figura 4: Datos

[pic 9]

2. (Sensibilidad)

Considere un problema de transporte con dos or´ıgenes (almacenes) y tres destinos (clientes). Los almacenes pueden enviar a lo m´as 60 y 80 unidades respectivamente, mientras que la demanda es exactamente de 30 para el primer cliente, 50 para el segundo cliente, y 40 para el tercer cliente. El problema se puede formular entonces de la siguiente manera:

m´ın Z = 3x11 + 7x12 + 4x13 + 9x21 + 2x22 + 5x23

s.a.

x11 + x12 + x13 ≤ 60 x21 + x22 + x23 ≤ 80

(1)

x11 + x21 = 30 x12 + x22 = 50 x13 + x23 = 40

x11,x12,x13,x21,x22,x23 ≥ 0

Note que en la funciobjetivo queremos minimizar el costo total de env´ıo desde un almac´en i a un cliente j y que las variables xij indican la cantidad de unidades que se envdesde i hasta j. Sabiendo eso, responda:

1. Utilice AMPL y encuentre la soluci´on ´optima al problema e indique el plan de distribuci´on ´optimo y los costos asociados.
2. Explique sus resultados indicando si se distribuyeron todos los productos que hab´ıa en los almacenes.
3. ¿Qu´e hubiera pasado si el costo por unidad de env´ıo desde el origen 2 al origen 3 se incrementaba en $2. Explique su efecto en la soluci´on ´optima hallada en (a).
4. ¿Qu´e hubiera pasado si el costo por unidad de env´ıo desde el origen 2 al origen 3 se reduc´ıa en $2. Explique su efecto en la soluci´on ´optima hallada en (a).
5. ¿Qu´e hubiera pasado si el nu´mero de unidades disponibles en el primer almac´en se hubiera reducido en una unidad?
6. Si pudiera aumentar unidades en el primer almac´en ¿cu´antas comprar´ıa? y ¿a qu´e costo?
7. Un proveedor le ofrece enviarle unidades extras al segundo almac´en a un costo de $ 2 por unidad. ¿Le conviene aceptar la oferta?

(Nota: en todas las preguntas anteriores responda justificando num´ericamente su respuesta)

Soluci´on:

La soluci´on presenta los resultados usando los comandos de AMPL.

1. El primer almac´en no tiene holgura por tanto la soluci´on cambiar´ıa y la funci´on objetivo se reducir´ıa en 1 unidad de acuerdo al dual asociado con esa restricci´on si es que se tuviera una unidad m´as de inventario en el almac´en. Por tanto si es que se reduce en una unidad el costo se incrementar´ıa en 1, o sea el costo total ser´ıa de $361.
2. Lo m´as que se podr´ıa comprar ser´ıan 10 unidades porque el rango para el almac´en 1 es de b1 ∈ [40,70] y no se debiera pagar m´as de $1 porque esto es lo que se puede ahorrar.
3. Se debe declinar la oferta porque au´n quedan 20 unidades en ese almac´en y por tanto su dual es 0.

1. (Branch-Bound)

Dado el siguiente ´arbol del algoritmo Branch-Bound.

[pic 10]

Tomando en cuenta que en este problema la totalidad de las variables debe ser entera, responda:

1. Indique si el objetivo del problema es Maximizar o Minimizar, explicando la raz´on para ello.

Soluci´on:

Dado que se registra en decrecimiento de los valores de Z se concluye que el problema es de maximizaci´on. En el caso de la maximizaci´on la resoluci´on de cada problema relajado indica el mejor valor para los problema que de ah´ı se deduzca, es decir, cualquier ramificaci´on y acotamiento posterior implicar´a desmejorar el valor.

...