Ingeniero

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 se puede llegar a E desde B con3+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; puede verse que el más cortode 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ás cercanos E,F y G. Por tanto se puede llegar Hdesde 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 son iguales desde E o desde H, por lo que hay dosopciones 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 6 8 Nodos no Distancia resueltos total más involucradacercanos conectados A B C C C D D E E F F F G G H H H I I T T T 4 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 F 4 3 6 OA OB OC 7 11 9 8 AD BE CF G H 10 11 FG EH I I 17 14 T EI HI GT

Resultando 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 O O O A B A C B C C D E D F E F G E H G H I

1 2 3

4 5 6

7 8

9 10

2. Encuentre el flujo máximo de la red que se le muestra a continuació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 Iteraciones:

En cada paso o iteración elegimos un camino cualquiera y enviamos la cantidad que permite el arco con menor capacidad de ese camino y vamos reduciendo la capacidad de cada arco restando lo enviado. Iteración 1:...