normalizacion

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION
Año 2003

Modelo de Redes

Práctico 5
Modelo de Redes
5.1

Ruta Más Corta

Encontrar la Ruta más Corta desde el Nodo (1) hacia los otros nodos en la Red
siguiente :
5

5

2
4
7

1
5

6

2

3
3

7

3
6

1

2
8

4

6

SOLUCION

Después de 5 Iteraciones se llega a la solución :
(Donde [d,n] : indica d= distancia directa desde el nodo 1, y n = nodo precedente
en la ruta desde el nodo 1)
[8,3]

[4,1]

5

2

[13,6]

[6,4]
[0,S]

1

7

3

4

6

[5,1]

[11,5]

La Ruta más Corta desde cada nodo hacia atrás puede ser resumida de la manera
siguiente :
NODO
2
3
4
5
6
7

Practico 5

Distancia
Mínima
4
6
5
8
11
13

Ruta más
Corta
1-2
1-4-3
1-41-4-3-5
1-4-3-5-6
1-4-3-5-6-7

-1 -

H. Roche

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION
Año 2003

Modelo de Redes

5.2

Ruta Más Corta
Una persona X debe estar en la ciudad (6) para un evento de la empresa en la
noche del mismo día. Tiene varias rutas alternativas para llegar a (6)
F

2
A

5
L

B

K
G

1

6

C
D
E

J
3

I

H

M
4

saliendo de(1). La Red siguiente resume las rutas alternativas.
La Tabla siguiente indica el modo de transporte, el tiempo de viaje, y el costo
Ruta
A
B
C
D
E
F
G
H
I
J
K
L
M

Modo de
Transporte
tren
avión
taxi
omnibus
tren
omnibus
omnibus
taxi
tren
omnibus
taxi
tren
omnibus

Tiempo
(horas)
4
1
6
2
3.333
3
4.667
1
2.333
6.333
3.333
1.333
4.667

Boleto
20115
90
10
30
15
20
15
15
25
50
10
20

asociado en cada una de las ramas de la red.
Si esa persona X gana una salario de $15 por hora, ¿cual será la ruta que
deberá escoger para minimizar el costo total de viaje?
Se Pide
1. Determinar los costos asociados a cada Arco.
Costo del Arco = $15x
60
2
+ Costo del Viaje
80
1

Tiempo de Viaje(en horas)
5
30

130

100
90

1806

40
80

120
3

50

30

90
4

Practico 5

-2 -

H. Roche

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION
Año 2003

Modelo de Redes

2. El Costo Mínimo es $150. La ruta de mínimo costo es 1-3-4-5-6.
[120,4]

[80,1]
60

2

30

80
[0,S]

5

130

1

100
90

180

6

[40,1]

40

[150,5]

120

3
80

50

30

90
4
(70,3)

5.3Arbol de Expansión Mínima

Encontrar el Arbol de Expansión Mínimo en la Red siguiente .

60

3

45

20

50

1

9
30

45

6

4

40

35

40
5

30

15

25

10

20
35

7
30

2

25
8

50

SOLUCION

60

3

45

20
50

1

45

6

4

40

35

40
5

30

15

25

10

20
35

7
30

2
50

Practico 5

9

30

-3-

25
8

H. Roche

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION
Año 2003

Modelo de Redes

5.4

Ejemplo- Modelo de Flujo Máximo (Aguas del Estado)
La empresa “Aguas del Estado” cuenta con una red de cañerías muy
heterogénea en cuanto a años de servicio, y quiere llevar agua del barrio A al
barrio G, abasteciendo en el camino a todos los demás. Pretende que el
caudalmedido en decenas de litros por segundo sea máximo, pero debido a la
edad avanzada de algunos tramos debió confeccionar un croquis de la ciudad
en el cual consta el flujo máximo que soporta cada tramo. El mismo se
muestra a continuación:
2
0

0

B
2

7

8
0
0

0
6

A

E

0

0

D

5

3

G
2

4

0
2
0

0

C

0

F
5

5

0

Se pide:
a) Identifiqueel flujo máximo a asignar en total y en cada tramo, usando el
algoritmo de trayectorias aumentadas, de modo tal que la solución sea óptima.
b) Verifique el resultado obtenido por medio del teorema del flujo máximo –
2
cortadura mínima.
0 E
8
0

B

0

2

SOLUCIÓN

7
4 ==>

0

0
6

A

0
3

0

D

5

G
4

0
4

2

0

B

7
1
2

8
0
0

0
5

E...