Tarea 7

Investigación de Operaciones
Fecha de entrega: 21/10/2019

1. Dibuja la red de la matriz y, asocia los costos de la matriz c, y obtén la ruta

más corta del nodo 1 al nodo 6 (si hay rutas alternas, determina todas las
rutas):

 0 2 4 3  
1 1 1 0 0 0 0 0 0 0 0   
   0 2  2 
1 0 0 1 1 0 1 0 0 0 0    0   1 
 0 0 
y
0 1 1 0 1 0 0 0 1
 c 
 0 1 0 0 1 1 0 1 1 0 0   4 1 0 5 2 
   
 0 0 0 0 0 0 1 1 0 0 1      0 1 
 0 0 0 0 0 0 0 0  1  1  1 
     0 
  

2. Utiliza el algoritmo de Bellman y determina la ruta más corta entre el nodo 1

y el nodo 8 de la siguiente red:

4
3 6
1 -2
-2 3

1 2 5 6 8
-1 5
[-
2,
1 2 3 -3 2]
1

2 4 7
5 1

3. Encuentra la ruta más corta del nodo 0 al nodo 7 utilizando el algoritmo de

Bellman.
a. Da las rutas más cortas desde el nodo 0 a los nodos intermedios.
 1

2 5
2 -2
3 3
-2
4 6 3
0 4 7

2 4
-1 3 -1 5
6

1 3 6
5 7

4. Aplica el algoritmo de Dijkstra para obtener las siguientes rutas:

a) Del nodo 1 al nodo 12.
b) Del nodo 3 al nodo 10.
c) Del nodo 4 al nodo 11.

4 6 3
1 4 7 10

2
3 2
3 2 5 2
4 2 4
2 5 8 11

1
0 2 1
2 3 0
5 5 3
3 6 9 12

5. Aplica el algoritmo de Dijkstra a la siguiente red y determina la ruta más

corta del nodo 1 a todos los demás nodos.
 6
2 5
5 3 2 4
1
3 5
1 4 7
6
7 4
2
2
3 6
5

6. La siguiente figura indica un cierto flujo x. Determine la divergencia y = div x

y cuáles son los nodos fuentes y los nodos sumideros con respecto a este
flujo.

2 2

8 6
5
11 10

1 8 3 7
7

15
7 4 6

4 3

7. Determina el flujo máximo en la siguiente red.

 s1 5 1 4 4 1 t1

2 2 ∞ 1

s2 4 2 2 5 5 t2

6
1 3 ∞

s3 9 3 1 6 8 t3

8. Aplica el algoritmo de Ford-Fulkerson con coloración y encuentra el flujo

máximo y el corte mínimo:

a.

[-6,8] [-5,7]
1 3 5
[-8,5]
[-8,12]
[-5,8]
[-4,4] [-2,8]

S [-2,6] S’
6
[-1,3]
[-1,8]
[-1,10]
[-3,7] [-3,8]

2 4 7
[-4,6] [-1,8]

b.
 [0,2]
[0,5] 1 S’
[-2,2] [0,4]
[0,3]
S 3 [-1,1]
[-4,2]
[0,2]
[0,6] [-5,1]

2 S’’
[0,1]

9. Resuelve utilizando el algoritmo de coloración de Ford-Fulkerson:

a. N+ = {S} y N- = {S’’, S’}

[-2,3] 3 [-3,3]
1
S’
[-3,1] [-1,1] [0,2]
[0,9] [0,2]
[-10,7]
[-2,8]
[-5,2]
S
4 [0,5]
[-2,5]
[-10,1]
[-9,2]
[-4,2]

[0,1] S”
[0,4]
2
[-8,0]
[0,4] 5

10. Define y explica el teorema de flujo máximo – corte mínimo (Ford y

Fulkerson)