prueba

PROBLEMAS RESUELTOS DE INVESTIGACIÓN DE OPERACIONES
Enero 2013

TEMA 1: REDES
1. Encuentre la ruta más corta de la siguiente red. Los números representan las distancias
correspondientes reales entre los nodos.

Solución: Para resolver problemas de ruta más corta se debe proceder con el criterio del
Algortimo de Dijktra. Esto es demos partir del origen (O) y debemos llegar al Destino (T) ylo
debemos hacer por el camino o ruta más corta. Es decir tenemos que optimizar, minimizando
costos de envío del nodo Origen al Nodo destino.
Vea la red tenemos tiene 11 nodos:


Al salir del Nodo O se puede llegar a los Nodos A,B y C. pero fíjese que se puede hacer a
distintos costos 4,3 y 6. Respectivamente. Lo cual mostramos con cuadrados rojos sobre
los nodos alcanzados o conocidos.OA=4, OB=3,OC=6
4

6

3




Ahora vamos a llegar al Nodo D; puede ver que los nodos conocidos más cercanos son A y
C. por lo tanto se puede llegar a D desde A con 4+3=7; pero se puede llegar a D dese C con
6+2=8, como nos interesa el camino más corto elegimos AD para un costo de 7.
Ahora vamos a llegar a E; puede ver que los nodos conocidos más cercanos son B y C. por
tanto sepuede llegar a E desde B con 3+6= 9; pero se puede llegar a E desde C con 6+5=11
como nos interesa el camino más corto elegimos BE con un costo de 9.



Ahora vamos a llegar a F; puede verse que los nodos conocidos más cercanos son C,D y E,
por tanto se puede llegar a F desde C con 6 + 2= 8; pero se puede llegar a F desde D con
7+2=9; pero también se puede llegar a F desde E con 9+1=10; puedeverse que el más
corto de los tres es 8 por lo que elegimos CF.

7

8

9






Ahora podemos alcanzar G desde los nodos conocidos más cercanos D y F. por tanto se
puede llegar a G desde D con 7+4=11; pero se puede llegar a G desde F con 8+2=10;
puede verse que es menos costoso llegar desde F por lo que elegimos FD.
Ahora podemos alcanzar H desde los nodos conocidos máscercanos E,F y G. Por tanto se
puede llegar H desde E con 9+2= 11; pero se puede llegar a H desde F con 8+5=13; pero se
puede llegar a H desde G 10+2=12; puede verse que el menos costoso es de EH con 11.
Ahora podemos alcanzar I desde los nodos conocidos más cercanos E y H. Por lo tanto se
puede llegar a I desde E con 9 + 5=14; pero puedo llegar I desde H con 11+3=14; vemos
que los costos soniguales desde E o desde H, por lo que hay dos opciones posibles. HI y EI

10

11

14


Ahora podemos alcanzar el nodo destino T desde los nodos conocidos más cercanos G,H e
I. Por tanto puedo alcanzar T desde G con 10+7=17; pero puedo alcanzar T desde H con
11+8=29 o puede alcanzar T desde I con 14+4=18, puede verse que de los tres el menos
costoso es 17 desde GT

10

17
8

6Resultando la ruta óptima: OC-CF-FG-GT o lo que es lo mismo O-C-F-G-T = 17

N

Nodos resueltos,
conectados
directamente a
nodos no
resueltos

1
2
3

O
O
O
A
B
A
C
B
C
C
D
E
D
F
E
F
G
E
H
G
H
I

4
5
6

7
8

9
10

Nodos no
Distancia
resueltos
total
más
involucrada
cercanos
conectados
A
B
C
C
C
D
D
E
E
F
F
F
G
G
H
H
H
I
I
T
T
T4
3
6
4+5
3+6
4+3
6+5
3+6
6+5
6+2
7+2
9+1
7+4
8+2
9+2
8+5
10+2
9+5
11+3
10+7
11+8
14+4

N-ésimo
nodo más
cercano

Distancia
mínima

Última
conexión

A
B
C
C
C
D
D
E

4
3
6

OA
OB
OC

7
11
9

AD

F

8

CF

G
H

10
11

FG
EH

I
I
17

14

EI
HI
GT

T

BE

2. Encuentre el flujo máximo de la red que se le muestra acontinuación, donde el nodo
inicial es (AI) y el terminal es (GT).

Solución: Los problemas de flujos máximos consisten en tratar de llevar desde el Nodo AI
la mayor cantidad flujo posible al Nodo destino GT. Tomando en cuenta que los arcos o
aristas tienen capacidades diferentes. Ejemplo BE tiene capacidad de 4; CE tiene capacidad
de 1; etc.
Este problema se resuelve por pasos o...