-
7/31/2019 capisclave
1/14
Ing. Miguel Jimnez C. M.Sc.
2
SOLUCIONARIO"Los que mandan generalmente mueven las manos y
dicen 'He considerado todas las alternativas'. Pero
eso es casi siempre basura. Lo ms probable es que no
pudiesen estudiar todas las combinaciones."
Sobre Redespor
Ing. Miguel Jimnez Carrin M.Sc George B. Dantzig , el creador de
laprogramacin lineal, en una entrevista
publicada en The College Mathematical
Journal, marzo de 1986.
Ruta ms cortarbol de Extensin Mnimo
Flujo Mximo
2004
-
7/31/2019 capisclave
2/14
-
7/31/2019 capisclave
3/14
-
7/31/2019 capisclave
4/14
-
7/31/2019 capisclave
5/14
-
7/31/2019 capisclave
6/14
Redes Solucionario
Nodos conectados
(1) (4) con 19.1(2) (3) con 8.3 se elige el menor. O sea se
conecta (2) con (3)
(1) (2) (3) 7.1 + 8.3 = 15.4
(1)(4) con 19.1(2)(5) con 13.2(3)(5) con 5.2 se elige el menor.
O sea se conecta (3) con (5)
(1) (2) (3) (5) 15.4 + 5.2 = 20.6
Como solo falta conectar (4) se toma ese nodo como punto de
partida y se conecta con elnodo cuya rama es la de menor costo y se
conecta.
(4)(2) con 16.2 el rbol quedara como:
(1) (2) (3) (5) 20.6 + 16.2 = 36.8I
(4)
Los caminos deben construirse conectando la Entrada al Parque
con Cascada y esta conFormacin Rocosa, y desde all con Pradera y
finalmente hacer el tramo Cascada Mirador,con un recorrido total de
36.8 Km.
4) Verifique que el rbol mnimo de la red, es el que se muestra
en lneas gruesas. Construyael modelo matemtico de esta red y
utilice QBS para resolver el modelo matemtico, si sus
respuesta es coincidente (29 unidades) su modelo est bien
formulado, de lo contrarioreformlelo.
4
9
9
2
7
7
23
6
3
5
8
47
3
8
4
5
72
91
38
6
Ing. Miguel Jimnez C. M.Sc.
12
3. MODELO DE FLUJO MXIMO
a) Red.
El modelo matemtico
6
4
65
6
2
5
9
4
9
7
7
8
4
3
6
7
5
3
9
1
2
3
4
5
6
NodoOri en
7 Nododestino
Max F = x67 + x57
s.a x12 + x13 = x67 + x57x12 + x32 + x42 = x21 + x23 + x24x13 +
x23 + x43 + x53 =x31 + x32 + x34 + x35x24 + x34 + x54 + x64 = x42 +
x43 + x45 + x46x35 + x45 + x75 = x53 + x54 + x57x46+ x76 = x64 +
x67
x12
-
7/31/2019 capisclave
7/14
-
7/31/2019 capisclave
8/14
Redes Solucionario
15
O F2 J3 D con un flujo de 80
O F3 J4 D con un flujo de 300
O F4 J3 D con un flujo de 50
El flujo mximo es de 200 + 50 + 100 + 80 + 300 + 50 = 780. El
programa de embarque se
obtiene por diferencia de esta ltima red y la primera, se deja
al alumno que determine elprograma de embarque.
50
50
100180
50
200
200
300
270
0
0
50
300
50
300
300
0
0
D
50
180
80
250
200
50
F1
F2
F3
F4
J1
J2
J3
J4
250
150
50
80
0300
100180
50
200
200
270
0
0
50
0
50
300
0
0
0
O D
50
180
80
250
200
50
F1
F2
F3
F4
J1
J2
J3
J4
250
150
50
80300
300
0300
100180
50
200
200
220
0
0
0
0
0
300
0
0
0
O D
50
180
80
250
200
50
F1
F2
F3
F4
J1
J2
J3
J4
250
150
50
130300
300
Ing. Miguel Jimnez C. M.Sc.
16
3) Caso oleoducto
Una compaa es propietaria de una red de oleoductos que se
utiliza para transportar petrleodesde el pozo hasta diversos
lugares de almacenamiento. En la siguiente tabla se indica elpozo,
6 lugares de almacenamiento y la cantidad de metros cbicos de
petrleo que fluyen
por hora por los conductos:
Pozo Alm.1 Alm.2 Alm.3 Alm.4 Alm.5 Alm.6
Pozo 6000 0 6000 0 0 0Alm.1 0 2000 0 3000 0 0Alm.2 0 2000 3000
2000 2000 0Alm.3 0 0 3000 0 1000 2000Alm.4 0 3000 2000 0 0
5000Alm.5 0 0 2000 1000 0 5000Alm.6 0 0 0 0 0 0
Debido a los diversos dimetros de los caos, tambin son variables
las capacidades de flujo.Al abrir y cerrar selectivamente las
diversas secciones de la red de oleoductos, la empresapuede
abastecer cualquiera de los puntos de almacenamiento.
a) Si la empresa desea abastecer el punto de almacenamiento 6 y
utilizar en forma completala capacidad del sistema, cunto tiempo se
necesitar para satisfacer la demanda de 100000metros cbicos de este
punto? cul es el flujo mximo para este sistema de oleoductos?
b) Si se presenta una ruptura entre los puntos de almacenamiento
1 y 2 y se cierra en amboslados, cul es el flujo mximo para el
sistema? cunto tiempo se requerir para abasteceral punto 6 de
almacenamiento?
Solucin:
Red
a) Lo primero que debe hacerse es calcular el flujo mximo de la
red tomando como nodoorigen el pozo y como nodo destino el tanque
de almacenamiento nmero 6; luego el flujomximo ser el caudal que
entra al tanque de almacenamiento N 6; y para determinar eltiempo
en atender la demanda de ste tanque se divide la demanda (100000),
entre elcaudal que ingresa, el resultado ser el tiempo necesario en
horas. Los clculos se aprecian acontinuacin:
0
00
5
1
2
52
3
2
13
2
3
2
3
2
0
6
6
A1
A2
A3
A4
A52
0
P A6
-
7/31/2019 capisclave
9/14
Redes Solucionario
17
P A1 A4 A6 con un flujo de 3000 m3/h
P A1 A2 A4 A6 con un flujo de 2000 m3/h
P A3 A2 A5 A6 con un flujo de 2000 m3/h
P A3 A5 A6 con un flujo de 1000 m3
/h
0
0 35
12
22
6
2
13
2
3
2
0
2
0
3
6
A1
A2
A3
A4
A5 A6P
3
2
0
05
5
12
0
4
6
2
13
0
3
4
0
0
0
1
6
A1
A2
A3
A4
A5 A6P
5
2
0
25
3
14
046
2
11
0
5
4
0
0
2
1
4
A1
A2
A3
A4
A5 A6P
5
0
0
35
2
24
04
6
2
01
0
5
4
0
0
3
1
3
A1
A2
A3
A4
A5 A6P
5
0
Ing. Miguel Jimnez C. M.Sc.
18
P A3 A6 con un flujo de 2000 m3/h
Ya no existe ningn otro camino de flujo positivo del origen P al
destino A6, en consecuenciael flujo mximo es de 10000 m3/h. (3000 +
2000 + 2000 + 1000 + 2000).
El tiempo que demanda en atender la demanda del Tanque de
almacenamiento A6 es:100000 10000 = 10 horas.
El programa de embarque que permite el flujo mximo de 10000 m3
/h es el siguiente:
Enviar del pozo al tanque de almacenamiento A1 5000 m3/hEnviar
del pozo al tanque de almacenamiento A3 5000 m3/hEnviar del tanque
de almacenamiento A1 al A4 3000 m3/hEnviar del tanque de
almacenamiento A1 al A2 2000 m3/hEnviar del tanque de
almacenamiento A2 al A4 2000 m3/hEnviar del tanque de
almacenamiento A4 al A6 5000 m3/hEnviar del tanque de
almacenamiento A3 al A2 2000 m3/hEnviar del tanque de
almacenamiento A2 al A5 2000 m3/hEnviar del tanque de
almacenamiento A3 al A5 1000 m3/hEnviar del tanque de
almacenamiento A5 al A6 3000 m3/hEnviar del tanque de
almacenamiento A3 al A6 2000 m3/h
b) si se rompe el tramo de A1 a A2 entonces el arco A1 A2 se
elimina de la red, en estecaso se vuelve a calcular el flujo mximo
de la red, procedindose de la misma manera queen el caso a), tal
como se indica:
2
3 52
24
04
6
0
01
0
5
4
0
0
5
1
1
A1
A2
A3
A4
A50
5
P A6
20
00
5
12
52
3
2
13
2
3
3
0
6
6
A1
A2
A3
A4
A5
0
P A6
-
7/31/2019 capisclave
10/14
Redes Solucionario
19
P A3 A6 con un flujo de 2000 m3/h
P A3 A5 A6 con un flujo de 1000 m3/h
P A3 A2 A5 A6 con un flujo de 2000 m3/h
P A1 A4 A6 con un flujo de 3000 m3/h
22
00
5
12
52
3
0
13
2
3
3
2
6
4
A1
A2
A3
A4
A5 A6P
0
22
10
4
22
5
2
3
0
03
2
3
3
3
6
3
A1
A2
A3
A4
A5 A6P
0
02
30
2
24
523
0
01
2
5
3
5
6
1
A1
A2
A3
A4
A5 A6P
0
02
33
2
24
22
6
0
01
2
5
0
5
3
1
A1
A2
A3
A4
A5 A6P
3
Ing. Miguel Jimnez C. M.Sc.
20
P A3 A2 A4 A6 con un flujo de 1000 m3/h
El flujo mximo que se logra en estas condiciones es 9000 m3/h,
lo cual disminuye en 10%respecto al anterior y el tiempo que se
tardara sera: 100000/9000 = 11hrs. 60 min., 40 seg.
Se deja al estudiante para que realice el programa de embarque
bajo estas condiciones:4) Un padre de familia tiene cinco hijos
(adolescentes) y les quiere asignar cinco tareasdomsticas. La
experiencia pasada le ha enseado al padre que resulta
contraproducenteimponerle obligaciones a un hijo. Teniendo esto en
mente, les pide a sus hijos que hagan unalista de sus preferencias
entre las cinco tareas, como lo muestra la siguiente tabla.
Ahora, la modesta meta del padre es determinar tantas tareascomo
sea posible, respetando al mismo tiempo las preferenciasde sus
hijos. Determine el nmero mximo de tareas que sepueden terminar y
la asignacin de las tareas a los hijos.
Solucin:
La red
Del nodo auxiliar O origen, todas las ramas tienen una capacidad
mxima de 1, lo quesignifica que cada hijo debe hacer solo una
tarea, ya que son 5 tareas; y adems el padredesea asignar las
tareas de acuerdo a sus preferencias sin imponer una tarea a ningn
hijoque no le gusta hacer, esta condicin estn representadas por las
ramas Hi Tj (i = j =1,2,3,4,5). Finalmente la red hace uso del nodo
auxiliar D para mostrar el final, cuando todaslas tareas han sido
representadas. Aplicando el algoritmo de flujo mximo el padre solo
puedeasignar 4 tareas de las cinco. Se deja al alumnos determinar
las posibles alternativas que
tiene el padre en la asignacin de tareas.
No Hijo Tarea preferida
1 Juan 12 Andrs 3, 4 o 53 Luis 24 Carlos 1, 2, o 35 Jorge 1 o
2
02
34
2
24
13
6
0
00
1
6
0
6
3
0
A1
A2
A3
A4
A5
3
P A6
1
1
1
1
1
1
1
1
11
D
1
1O
1
1
1
1
1
1
1T5
T4
T1H5
H3
H1 T2
H4 T3
1
H2
-
7/31/2019 capisclave
11/14
-
7/31/2019 capisclave
12/14
Redes Solucionario
23
O 1 4 5 8 D con un flujo de 20 MDB
O 2 6 6-1 8 D con un flujo de 5 MDB
O 3 5 8 D con un flujo de 10 MDB
El flujo mximo que circula en la red es de 95 MBD. El programa
de embarque se obtiene pordiferencia, el cual se deja al alumno
para que lo determine.
100
20
30
2010
20
2020
0
10
60
30
10 60
50
5050
0
20
05
0
0
0
15
20
10
15
30
1
2
5
6
7
8
O6-1 D
25
10
0
25
25
2010
20
2020
0
10
65
30
1060
50
5555
0
15
00
0
0
0
15
20
5
15
25
1
3
4
5
7
8
O6-1 D
10
510
5
25
10
0
35
15
300
20
2020
0
10
65
30
10 60
50
5555
0
15
00
0
0
0
20
525
1
2
3
4
5
6
7
8
O6-1 D
Ing. Miguel Jimnez C. M.Sc.
24
b) Si disminuye la produccin en la refinera 2 en 40%, significa
que la produccin mxima desta refinera ser de 54 MDB. (0.60 x 90).
La red que habra que analizar ser:
Aplicando el algoritmo de flujo mximo se obtiene que este
alcanza a 85 MDB lo que significaun decremento del abastecimiento
normal de 10.53% aproximadamente. El alumno deberdeterminar este
nuevo flujo mximo con su respectivo programa de embarque.
PROBLEMAS PROPUESTOS
1) Una compaa constructora ha reunido los datos (en dlares)
referentes a camiones devolteo que se muestran en la tabla
siguiente:Ningn camin de volteo se conserva ms de 5 aos. Determnese
una poltica de reemplazo
para un camin, que actualmentetiene 2 aos, minimice el
costototal de operacin durante losprximos 9 aos. Considreseque los
camiones nuevoscuestan $21000 dlares y queslo se compran
camionesnuevos para reemplazar a losviejos.(Sugerencia: Tmese Y0
como
inicio del perodo. Entonces, Y1 a Y9 son los inicios de los
prximos 9 aos y Y-2 representa elda en que el camin actual fue
comparado y Y-1 no es necesaria).
2) En fecha reciente se ha reservado el parque "EL ANGOLO" para
pasear y acampar. No sepermite la entrada de los automviles al
parque, pero existe un sistema de caminos angostospara Tranvas y
Jeeps conducidos por los guardabosques. En la Figura que sigue, se
muestraeste sistema de caminos (sin las curvas), en donde O es la
localizacin de la entrada alparque; las otras letras designan la
localizacin de estaciones de guardabosques (y otrasinstalaciones).
Los nmeros dan las distancias de esos caminos sinuosos en Km.
Edad en aos0 -1 1 - 2 2 - 3 3 - 4 4 - 5
Costo deMantenimiento
7000 7500 9700 7700 9000
Ingreso perdidopor descompostura 500 800 1200 800 1000
Valor de venta alfinal del ao 16000 6000 9000 3500 2500
50
60
20
5055
3030
1010
20
20
15
20
60
10
15
54
20
1
3
4
7
8
O6-1 D
-
7/31/2019 capisclave
13/14
-
7/31/2019 capisclave
14/14
Ing. Miguel Jimnez C. M.Sc.
28
Redes Solucionario
10) Modelo matemtico general del rbol de extensin mnimo para
esta red.
Restricciones quegarantizan la
conectividad decada nodo
Restricciones quegarantizan la noexistencia deciclos
Restriccinque
garantizaque el rbol
estecompuesto
por n-1ramas
Min Ct = 2x12 + 9x13 + 6x23 + 8x24 + 1x34 + 3x35 + 4x45 + 3x46 +
2x57 + 5x67s.a
x12 + x13 >= 1x12 + x23 + x24 >= 1
x13 + x23 + x34 + x35 >= 1x24 + x34 + x45 + x46 >= 1
x35 + x45 + x57 >= 1x46 + x67 >= 1x57 + x67 >= 1
x12 + x13 + x23 + x24 + x34 + x35 + x45 + x46 + x57 + x67 = 6x12
+ x13 + x23
