Pauta I3

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 13

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE Curso: ICS1113-Optimización

ESCUELA DE INGENIERÍA Semestre: 02-2012


Departamento de Ingenierı́a Industrial y de Sistemas Profesores: P. Álvarez, A. Cataldo
A. Lüer, G. Paredes

Pauta Interrogación 3
Duración: 2 horas 45 minutos.

Se debe contestar en cuadernillos independientes: Pregunta 1 Partes a), b) y c); Pregunta 1 Partes
d), e) y Bonus; Pregunta 2; y Pregunta 3. En cada uno de ellos debe colocar su nombre y número de
lista asignado. Si no cumple con las instrucciones se le descontarán automáticamente 5 puntos.
Está prohibido el uso de calculadoras y de celulares de cualquier tipo.

Pregunta 1 (20 puntos)

a) El sistema de puntos de la clasificatoria del mundial de fútbol Brasil 2014, establece que un
equipo de fútbol obtiene 0 puntos si pierde, 1 punto si empata, 3 puntos si gana un partido.
Se estima que un equipo clasifica al mundial con 25 puntos, de los cuales la selección chilena
ha ganado a la fecha 12 puntos. Dado que la selección chilena se encuentra en una situación
incómoda en la Tabla de Posiciones (“con la calculadora en la mano”), se desea saber cuál
es el número mı́nimo de partidos para que la selección pueda obtener exactamente 13 puntos
(y no más) para asistir al mundial Brasil 2014.
Modele el problema como un problema de flujo en redes. Explique detalladamente que repre-
sentan los nodos y arcos de la red, ası́ como los costos de los arcos.
Respuesta: El problema corresponde al problema de la ruta más corta. Considere una red
con nodos que van del 0 al 13, que corresponden a los puntajes obtenidos por la selección. Los
arcos de la red tienen costo igual a 1 y corresponden a una jugada factible, por lo que desde
cada nodo i salen dos arcos (excepto el nodo 11 y 12): un arco que avanza un nodo (1 punto)
y uno que avanza tres nodos (3 puntos). La red considerada se expone a continuación:

Se observa que la solución de la ruta más corta corresponde a 5 partidos (4 ganados y 1


empate) que son el mı́nimo necesario para alcanzar los 13 puntos requeridos.

b) Sea xi la solución óptima del siguiente problema de optimización:

(P E) mı́n Z = cT x
s.a.
Ax = b
x ∈ {0, 1}
El problema anterior se puede aproximar al siguiente problema relajado:

(P R) mı́n Z = cT x
s.a.
Ax = b
0≤x≤1

donde xr es la solución óptima del problema relajado. ¿Es posible asegurar que xr = xi ?
Fundamente su respuesta.
Respuesta: Lo que es posible afirmar es que el espacio de soluciones factibles de PE) es
sub-conjunto del espacio de soluciones factibles de PR), por lo que si xr es óptimo en P R) y
es entero, entonces xr es óptimo de P E). Sin embargo, no es posible asegurar que xr = xi ya
que PE) puede tener otros óptimos.
En otras palabras, si la matriz de A es totalmente unimodular, entonces sı́ es posible afirmar
que xr = xi .
c) Sea el siguiente problema de optimización entero:

(P R) máx Z = 6x1 + 2x2


s.a.
2x1 − x2 ≤ 4
5x1 + 3x2 ≤ 17
x1 , x2 ≥ 0, enteros

La solución del problema relajado es: x∗1 = 29


11 , x∗2 = 14
11 y Z∗ = 202
11

i) Encuentre un corte de Gomory para este problema de manera de obtener una formulación
más ajustada.
ii) Muestre que el corte obtenido de esta manera no incluirá la solución óptima del problema
relajado que se le ha entregado.

Algunas inversas:
     
−1 3/11 1/11 −1 0 1/5 −1 1/2 0
B(x 1 ,x2 )
= B(x 1 ,x3 )
= B(x 1 ,x4 )
=
−5/11 2/11 1 −2/5 −5/2 1
   
−1 0 1/3 −1 −1 0
B(x 2 ,x3 )
= B(x 2 ,x4 )
=
1 1/3 3 1

Respuesta:

i) Con la solución vemos que las variables básicas son x1 y x2 , y las no básicas x3 y x4 .
Esto permite calcular R̄:
    
3/11 1/11 1 0 3/11 1/11
R̄ = =
−5/11 2/11 0 1 −5/11 2/11
luego, se puede construir cualquiera de los siguientes dos cortes:
        
3 3 1 1 29 29
− x3 + − x4 ≥ − ⇔ 3x3 + x4 ≥ 7
11 11 11 11 11 11
        
−5 −5 2 2 14 14
− x3 + − x4 ≥ − ⇔ 6x3 + 2x4 ≥ 3
11 11 11 11 11 11
ii) Para verificar que la solución anterior no satisface ninguno de los dos cortes construidos
anteriormente, basta con verificar que x3 = x4 = 0 no cumple.

3x3 + x4 ≥ 7 ⇔ 0  7

6x3 + 2x4 ≥ 3 ⇔ 0  3

d) Sea G = (N, A) un grafo con capacidad ua ≥ 0 en cada arco a = (i, j) ∈ A. Se desea enviar el
mayor flujo posible desde una única fuente s ∈ N a un destino t ∈ N . Para ello, se considera
un arco de retorno r = (t, s) y se consideran los flujos factibles (fa )a∈A∪{r} que satisfacen
0 ≤ fa ≤ ua y permiten conservar flujo. Considere que el objetivo es maximizar el flujo fr en
este arco de retorno.
Se define que un s-t corte es un conjunto de nodos W ⊆ N con s ∈ W y t ∈
/ W , definiendo
su capacidad como la suma de las capacidades de los arcos que cruzan de W a W c . Esta
capacidad se denota como cap(W ).
Con la información anterior demuestre que todo flujo factible satisface fr ≤ cap(W ).
Respuesta: Definiendo el flujo neto a través de un conjunto de corte como:
X X
f (W, W c ) = fij − fij
a = (i, j) ∈ A ∪ {r} a = (i, j) ∈ A ∪ {r}
tal que i ∈ W, j ∈ W c tal que i ∈ W c , j ∈ W

ahora, como el flujo neto debe ser factible debe satisfacer las condiciones de conservación de
flujo. Entonces, sumando todas las ecuaciones correspondientes a nodos en W se tiene:
X X
fij − fij − F = 0 ⇔ f (W, W c ) = F
a = (i, j) ∈ A ∪ {r} a = (i, j) ∈ A ∪ {r}
tal que i ∈ W, j ∈ W c tal que i ∈ W c , j ∈ W

finalmente, como 0 ≤ fa=(i,j) ≤ ua para todo (i, j) ∈ A se tiene:


X X
uij − lij ≥ F
a = (i, j) ∈ A ∪ {r} a = (i, j) ∈ A ∪ {r}
tal que i ∈ W, j ∈ W c tal que i ∈ W c , j ∈ W

como en este caso lij = 0 para todo (i, j) ∈ A:


X
uij ≥ F = fr
a = (i, j) ∈ A ∪ {r}
tal que i ∈ W, j ∈ W c

e) Suponga que está resolviendo con el método de Branch and Bound el siguiente problema lineal
entero:

mı́n Z = xn+1
s.a. n 
P
2· xi + xn+1 = n
i=1
xi ∈ {0, 1} ∀i = 1, . . . , n.
i) ¿Qué se puede decir del número de nodos del árbol de Branch and Bound en este caso?
ii) ¿Qué ocurre si agrega las restricciones xi ≥ xi+1 , ∀i = 1, . . . , n − 1? ¿Cambia la solución
óptima entera? ¿Cuántos nodos posee el árbol?

Respuesta:

i) Primero debemos notar que la variable xn+1 ∈ R, luego, y que se está minimizando el
valor de esta variable. Como las variables xi ∈ {0, 1} para i = 1, . . . , n, la restricción del
problema se puede ver como:
n
!
X
xn+1 = n − 2 · xi
i=1

que dada la dirección de minimización se desea que xn+1 tome el valor más pequeño
posible, entonces la condición anterior queda:
n
!
X
xn+1 = n − 2 · 1 = n − 2n = −n
i=1

Luego, se puede afirmar que la relajación lineal del problema entero entregará una solución
que satisface las condiciones de integralidad del problema entero, por lo tanto, el árbol
de Branch and Bound tendrá solamente el nodo inicial asociado a la relajación lineal del
problema.
ii) Agregar ese grupo de restricciones no altera en nada la resolución del problema pues
ninguna de ella corta la solución relajada de la región factible del problema.

Bonus (5 puntos)

Muestre que un problema de flujo en redes con cotas inferiores nulas (0) y cotas inferiores
finitas puede convertirse en uno sin cotas superiores, mediante la siguiente transformación de
los arcos de la red.

Donde, para un nodo i, bi es su demanda generalizada; y para un arco (i, j), cij denota el costo
unitario de flujo y uij es su cota superior de flujo.
Solución
La validez de esta conversión se ve por casos.

 Si en el arco original el arco es nulo, es evidente que la conversión es válida en este caso,
ya que sólo habrá un flujo de uij unidades desde el nodo j al k, sin costo.
 Si el flujo f , que está entre las cotas (sin tocarlas), circula un flujo de f unidades entre
los nodos i y k, con costo unitario cij , y un flujo uij − f desde el nodo j al k, que no tiene
costo, para satisfacer la demanda en este último.
 Si el flujo es de uij unidades, entonces sólo existe un flujo desde el nodo i al k, que es el
único que se cobra.
 Un flujo de más de uij unidades no es factible en la conversión, porque implicarı́a un
“reflujo” en el arco (j, k).
Una alternativa era plantear las ecuaciones de conservación y la restricción correspondiente a
la cota superior, y ver ésta como una ecuación de conservación más, considerando la holgura
como una nueva variable (de flujo).

Pregunta 2

(20 puntos)
Debe responder solamente dos de las siguientes tres partes.

Parte a) (10 puntos)

Para el siguiente grafo,

i) (8 puntos) Resolver mediante el algoritmo simplex para redes, partiendo del siguiente flujo
factible: 10 unidades de flujo desde el nodo 1 al 4; 15 unidades de flujo desde el nodo 2 al 5;
y 5 unidades de flujo del nodo 2 al 3, y de ahı́ al nodo 4.

ii) (1 punto) ¿Qué costo deberı́a tener un nuevo arco (1, 5) para que la solución obtenida obtenida
en (a) siga siendo óptima?

iii) (1 punto) ¿Para qué valor(es) del costo del arco (5, 4) el problema tendrı́a múltiples bases
óptimas?

Solución

i) El desarrollo es como sigue,


Iteración 1 El árbol generador asociado a la solución básica anterior es,

Las variables básicas entregan el siguiente sistema de ecuaciones, para obtener los valores de
los potenciales,

π1 − π4 =5
π3 − π4 =2
π2 − π3 =3
π2 − π5 =8
Haciendo π1 = 0 se obtiene que,

π1 = 0, π2 = 0, π3 = −3, π4 = −5, π5 = −8

Los costos reducidos de las variables no básicas son,

c̄12 = c12 − π1 + π2 = 2−0+0=2


c̄13 = c13 − π1 + π3 = 1 − 0 + (−3) = −2
c̄35 = c35 − π3 + π5 = 2 − (−3) + (−8) = −3
c̄54 = c54 − π5 + π4 = 3 − (−8) + (−5) = 6

Con lo que entra f35 a la base. El ciclo que se forma es el siguiente,

Con lo que ∆ = 15 y f25 sale de la base.


Iteración 2 El árbol generador asociado a la nueva solución básica es,

Las variables básicas entregan el siguiente sistema de ecuaciones, para obtener los valores de
los potenciales,

π1 − π4 =5
π3 − π4 =2
π2 − π3 =3
π3 − π5 =2

Haciendo π1 = 0 se obtiene que,

π1 = 0, π2 = 0, π3 = −3, π4 = −5, π5 = −5

Los costos reducidos de las variables no básicas son,

c̄12 = c12 − π1 + π2 = 2−0+0=2


c̄13 = c13 − π1 + π3 = 1 − 0 + (−3) = −2
c̄25 = c25 − π2 + π5 = 8 − 0 + (−5) = 3
c̄54 = c54 − π5 + π4 = 3 − (−5) + (−5) = 3

Con lo que entra f13 a la base. El ciclo que se forma es el siguiente,


Con lo que ∆ = 10 y f14 sale de la base.
Iteración 3 El árbol generador asociado a la solución básica anterior es,

Las variables básicas entregan el siguiente sistema de ecuaciones, para obtener los valores de
los potenciales,

π1 − π3 =1
π3 − π4 =2
π2 − π3 =3
π3 − π5 =2

Haciendo π1 = 0 se obtiene que,

π1 = 0, π2 = 2, π3 = −1, π4 = −3, π5 = −3

Los costos reducidos de las variables no básicas son,

c̄12 = c12 − π1 + π2 = 2−0+2=4


c̄14 = c14 − π1 + π4 = 5 − 0 + (−3) = 2
c̄25 = c25 − π2 + π5 = 8 − 2 + (−3) = 3
c̄54 = c54 − π5 + π4 = 3 − (−3) + (−3) = 3

Por lo que la solución actuales óptima. Los flujos óptimos no nulos son,

∗ ∗ ∗ ∗
f13 = 10, f34 = 15, f23 = 20, f35 = 15

Con valor del objetivo Z = 130.

ii) El nuevo arco (1, 5) no cambiará la base actual si no es atractivo que entre, es decir c̄15 ≥ 0.
Esto equivale a decir que c15 − π1 + π5 ≥ 0 ⇒ c15 ≥ π1 − π5 , es decir si el arco (1, 5) tiene
costo c15 ≥ 3, la base actual no cambia.

iii) El problema tendrá múltiples bases óptimas si c̄54 = 0, lo que equivale a que c54 − π5 + π4 = 0,
es decir c54 = 0.
Parte b) (10 puntos)

Una empresa petrolera cuenta con tres pozos de extracción de crudo (los nodos 1, 2 y 3), en zonas
geográficamente distantes. El crudo se bombea desde los pozos hasta la planta, que se encuentra a
gran distancia de los pozos. Por esto, la empresa cuenta con dos estaciones de bombeo (los nodos 4
y 5), que permiten llevar el crudo hasta la planta de refinación (el nodo 6).
Existe una red de tuberı́as que conectan estas instalaciones, cuyas capacidades son conocidas y se
representan mediante el siguiente grafo, donde el atributo del arco (i, j) corresponde a la capacidad
de la tuberı́a que conecta las instalaciones en i y j.

La empresa está interesada en saber cuál es la cantidad máxima de crudo que podrı́a bombear desde
los pozos hasta la planta.

i) (2 puntos) Convierta el grafo en uno donde el problema de la empresa pueda resolverse como
uno de flujo máximo.

ii) (8 puntos) Ejecute el algoritmo de Ford y Fulkerson en el grafo obtenido en (a).

Solución

i) Debe agregarse un nodo común que haga las veces de origen. Se debe conectar con las fuentes
mediante arcos cuya capacidad no limite el flujo máximo de la red. Un criterio simple es
ponerle tanta capacidad como el máximo flujo que podrı́a salir de cada fuente. El nuevo grafo
es,

ii) Se ocupará el algoritmo de Ford y Fulkerson, considerando como origen el nodo 0 y como
destino el 6.
Iteración 1
El primer grafo residual es igual al original y sus capacidades. En el de flujos, todos son nulos.
R1 : F1 :

Se observa que pueden enviarse 6 unidades por 0-3-5-4-6.


Iteración 2
El nuevo residual y el grafo de flujos resultan ser,

R1 : F1 :

Ahora, pueden enviarse 2 unidades por 0-1-4-6.


Iteración 3
El nuevo residual y el grafo de flujos resultan ser,

R1 : F1 :

Ahora, pueden enviarse 3 unidades por 0-2-4-5-6.


Iteración 4
El nuevo residual y el grafo de flujos resultan ser,

R1 : F1 :

Como no pueden enviarse más unidades de flujo, se ha alcanzado el flujo máximo de la red.
El flujo total enviado es 6 + 2 + 3 = 11 unidades.
Parte c) (10 puntos)

Una agencia gubernamental busca determinar la forma más rápida de llegar desde su centro de
acopio a cinco (5) zonas afectadas por un frente de mal tiempo. La siguiente tabla muestra los
tiempos de viaje directo entre las zonas. De no existir un valor en la tabla, significa que no existe
un camino directo que las comunique.

Desde - Hacia Zona 1 Zona 2 Zona 3 Zona 4 Zona 5


Centro de Acopio 5 2 10 - -
Zona 1 - 3 - - 6
Zona 2 - - 3 - -
Zona 3 - - - 1 5
Zona 4 - - - - 4

i) (1.5 puntos) Construya el grafo asociado a este problema.


ii) (4.5 puntos) Resuelva usando el algoritmo de Dijkstra. Entregue el árbol de rutas más cortas,
ası́ como el tiempo de dichas rutas.
iii) (4.0 puntos) Construya el dual de este problema y demuestre utilizando el teorema fuerte de
dualidad que la solución encontrada es efectivamente la solución óptima del problema.

Solución

i) El grafo asociado es,

ii) Las iteraciones se encuentran sintetizadas en la siguiente tabla,

Nodo Iteración 1 2 3 4 5 6
C.A. (0, −)P (0, −)P (0, −)P (0, −)P (0, −)P (0, −)P
Z1 - (5, C.A.)T (5, C.A.)T (5, C.A.)P (5, C.A.)P (5, C.A.)P
Z2 - (2, C.A.)T (2, C.A.)P (2, C.A.)P (2, C.A.)P (2, C.A.)P
Z3 - (10, C.A.)T (5, Z2)T (5, Z2)T (5, Z2)P (5, Z2)P
Z4 - - - - (6, Z3)T (6, Z3)P
Z5 - - - (11, Z1)T (10, Z3)T (10, Z3)T

Donde se ha puesto en negrita los nodos que pasan a tener etiqueta permanente. La notación
de la etiqueta es (distancia al nodo raı́z, nodo predecesor).
El árbol de rutas mı́nimas, junto con las etiquetas que indican las distancias son,
Debe notarse que el arco (Z4, Z5), en reemplazo del (Z3, Z5), también podrı́a haber formado
parte del árbol de rutas mı́nimas, pero la ejecución del algoritmo llevo a la primera.

iii) El problema dual de este problema es (para el origen C.A. y el destino Zi , i ∈ {1, . . . , 5}) es,

max πCA − πZi


s.a. πCA − πZ1 ≤5
πCA − πZ2 ≤2
πCA − πZ3 ≤ 10
πZ1 − πZ2 ≤3
πZ1 − πZ5 ≤6
πZ2 − πZ3 ≤3
πZ3 − πZ4 ≤1
πZ3 − πZ5 ≤5
πZ4 − πZ5 ≤4

Por el árbol de rutas mı́nimas podemos rápidamente establecer valores duales: πCA = 0,
πZ1 = −5, πZ2 = −2, πZ3 = −5, πZ4 = −6, πZ5 = −10.
Por construcción de los valores π, éstos serán factibles para el conjunto de restricciones del
problema dual, sea cual sea el objetivo. Luego el problema admite una solución óptima.
Basta probar que los valores objetivos coinciden. Pensando en el problema de la ruta más
corta desde C.A. hasta Zi, i ∈ {1, . . . , 5}, se tiene que el objetivo serı́a,

max πCA − πZi

Asignamos los valores de las variables duales tales que son el negativo de la distancia de la
ruta mı́nima desde nodo C.A. hasta cada nodo Zi , el problema dual tendrá el mismo valor
óptimo que el problema primal.
Como el problema primal admite solución óptima, al igual que el problema dual, y sus valores
objetivo son iguales, la solución encontrada es la óptima.

Pregunta 3

Una empresa productora de muebles que posee N sucursales debe diseñar su red de distribución para
los próximos T años. Cada año debe ser capaz de abastecer sus sucursales con madera para fabricar
muebles. Esta madera puede provenir de M aserraderos con los cuales posee convenio. La cantidad
máxima de madera que puede entregar el aserradero i en el perı́odo t es Ait . El requerimiento
mı́nimo en el año t de cada sucursal k es Pkt . La empresa debe instalar bodegas donde se reciba
la madera proveniente de los aserraderos. Actualmente, no tiene bodegas instaladas y debe decidir
dónde localizarlas, estimándose que a lo más se deben instalar S bodegas, las cuales pueden ubicarse
en L lugares posibles (L ≥ S). Estas bodegas pueden ser instaladas en cualquier momento durante
los T años, y se asume inmediato su funcionamiento.
Las bodegas a instalar pueden ser de dos tipos; pequeñas o grandes, teniendo las pequeñas la opción
de ampliarse posteriormente a un costo de AMjt , correspondiente a una bodega en el lugar j en el
año t. Se considera que si la bodega es pequeña su capacidad máxima es de a y si es grande, su
capacidad es de b.
En cada sitio factible j puede instalarse a lo más una bodega de cualquier tipo y el costo de
instalación es de Fj . El costo de trasladar la madera desde i hasta j por la red de distribución es de
cij unidades monetarias. Por convenio con la compañı́a constructora encargada de las instalaciones
y ampliaciones, si en un perı́odo se realiza alguno de estos trabajos, entonces en los δ periodos
siguientes se deberá realizar al menos una ampliación. No asegurar esto hace que la empresa caiga
en una violación de contrato, lo que está asociado a una multa millonaria que la empresa no está en
condiciones de pagar.
Considerando la información anterior, formule un modelo de programación lineal entero mixto que
ayude a la empresa productora de muebles a tomar las decisiones de manera de minimizar el costo
total.

Pauta Pregunta 3

Variables de decisión

1, si se instala una bodega de capacidad a en el sitio j = 1, . . . , L en el perı́odo t = 1, . . . , T
 x1jt =
0, en otro caso

1, si se instala una bodega de capacidad b en el sitio j = 1, . . . , L en el perı́odo t = 1, . . . , T
 x2jt =
0, en otro caso

1, si una bodega de capacidad a en el sitio j = 1, . . . , L se amplia a capacidad b
 wjt =
0, en otro caso
 yijt : cantidad de madera a mover desde el aserradero i = 1, . . . , M a la bodega j = 1, . . . , L
en el perı́odo t = 1, . . . , T .

 zjkt : cantidad de madera a mover desde la bodega j = 1, . . . , L a la sucursal k = 1, . . . , N en


el perı́odo t = 1, . . . , T .

Función objetivo
!
T L L N P
L N P
L L
Fj x1jt Fj x2jt
P P P P P P
mı́n + + cij yijt + cjk zjkt + AMjt wjt
t=1 j=1 j=1 i=1 j=1 i=1 j=1 j=1

Restricciones

(a) Satisfacción de demanda.


L
X
zjkt = Pkt ∀k = 1, . . . , K; ∀t = 1, . . . , T.
j=1

(b) Balance de flujo en las bodegas.


M
X N
X
yijt = zjkt ∀j = 1, . . . , L; ∀t = 1, . . . , T.
i=1 k=1

(c) Cantidad máxima de bodegas.


T X
X L
x1jt + x2jt ≤ S

t=1 j=1
(d) Instalación de bodegas de una sola capacidad por perı́odo y sitio.

x1jt + x2jt ≤ 1 ∀j = 1, . . . , L; ∀t = 1, . . . , T.

(e) Instalación de bodegas en un sitio en un solo perı́odo.


T
X
x1jt ≤ 1 ∀j = 1, . . . , L.
t=1

T
X
x2jt ≤ 1 ∀j = 1, . . . , L.
t=1

(f ) Ampliación de bodegas solo si previamente hay una bodega pequeña instalada en ese sitio.
t−1
X
x1jt ≥ wjt ∀j = 1, . . . , L; ∀t = 1, . . . , T.
h=1

(g) Determinación de capacidad de bodega por perı́odo.


M
X t
X t
X t
X
yijt ≤ a · x1jt + b · x2jt + (b − a) · wjt ∀j = 1, . . . , L; ∀t = 1, . . . , T.
i=1 h=1 h=1 h=1

(h) Asegurar condición que evita la multa.


L
X t+δ X
X L
x1jt + x2jt + wjt ≤ 3 · L ·

wjh ∀t = 1, . . . , T.
j=1 h=t+1 j=1

(i) Naturaleza de las variables de decisión.

x1jt , x2jt , wjt ∈ {0, 1} , ∀j = 1, . . . , L; ∀t = 1, . . . , T.

yijt ≥ 0, ∀i = 1, . . . , M ; j = 1, . . . , L; ∀t = 1, . . . , T.

zjkt ≥ 0, ∀j = 1, . . . , L; k = 1, . . . , N ; ∀t = 1, . . . , T.

También podría gustarte