Investigación operativa

“AÑO DE LA UNIDAD, LA PAZ Y EL DESARROLLO”

[pic 1]

INVESTIGACIÓN OPERATIVA

TAREA ACADÉMICA 4

PROFESOR: VICTOR MANUEL GOMEZ CASTILLO

INTEGRANTES:

• Camila Graciela Ninachoque Pérez          U19203253
• Melani Anjela Paucar Salinas                    U18308728
• Maryorit Nicoll Quinto Quistan                U21227101
• Jesús Ángel Teodoro Aranda Castillo       U21314536
• Angella Amunategui Paz                             1635877
• Alexis yoel de la cruz Doria                        1631849
• Santisteban Morales Luis Enrique            U20100365

2023

TRABAJO DE APLICACIÓN NRO 04

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

[pic 2]

La solución consiste en emplear el enfoque del Algoritmo de Dijkstra para resolver problemas de rutas más cortas. Se inicia desde el punto de origen (O) con el objetivo de alcanzar el destino (T) a través del camino más corto. Es esencial optimizar y minimizar los costos de envío desde el nodo origen al nodo destino.

Se identifica una red que consta de 11 nodos:

- Al salir del Nodo O, se pueden alcanzar los nodos A, B y C. Es importante notar que se pueden alcanzar con diferentes costos: 4, 3 y 6 respectivamente. Estos costos se indican mediante cuadrados rojos sobre los nodos alcanzados o conocidos: OA=4, OB=3, OC=6.

[pic 3]

Ahora, al dirigirnos hacia el Nodo D, notamos que los nodos más cercanos previamente conocidos son A y C. Por lo tanto, el acceso a D desde A tiene un costo de 4+3=7, mientras que desde C es de 6+2=8. Dado que buscamos la ruta más corta, seleccionamos la conexión AD con un costo de 7.

Siguiendo con la ruta hacia el Nodo E, observamos que los nodos conocidos más próximos son B y C. Desde B, el costo para llegar a E es de 3+6=9, mientras que desde C es de 6+5=11. Optamos por la ruta BE con un costo de 9, ya que buscamos el camino más corto disponible.

Ahora, al dirigirnos hacia el Nodo F, podemos observar que los nodos más cercanos previamente conocidos son C, D y E. Desde C, el costo para llegar a F es de 6 + 2 = 8; desde D es de 7 + 2 = 9; y desde E es de 9 + 1 = 10. El camino más corto de los tres es el de 8, por lo que elegimos la conexión CF para alcanzar el Nodo F.

[pic 4]

Ahora, avanzamos para alcanzar el Nodo G desde los nodos conocidos más cercanos, D y F. Desde D, el costo para llegar a G es de 7+4=11, mientras que desde F es de 8+2=10. Es menos costoso llegar desde F, por lo que seleccionamos la conexión FD para llegar a G.

Posteriormente, podemos alcanzar el Nodo H desde los nodos conocidos más cercanos, E, F y G. Desde E, el costo para llegar a H es de 9+2=11, desde F es de 8+5=13, y desde G es de 10+2=12. La opción menos costosa es la conexión EH con un costo de 11.

Prosiguiendo, buscamos alcanzar el Nodo I desde los nodos conocidos más cercanos, E y H. Desde E, el costo para llegar a I es de 9+5=14, y desde H es de 11+3=14. Los costos son iguales desde E o desde H, por lo que existen dos opciones posibles: HI y EI.

[pic 5]

Ahora, nos dirigimos hacia el nodo destino T desde los nodos conocidos más cercanos, G, H e I. Desde G, el costo para llegar a T es de 10+7=17, desde H es de 11+8=19, y desde I es de 14+4=18. Entre las tres opciones, el costo más bajo es de 17 desde GT.

[pic 6]

La ruta óptima resultante es: OC-CF-FG-GT, o expresado de otra manera, O-C-F-G-T, con un costo total de 17. Esta ruta representa el camino más corto desde el nodo inicial (O) hasta el nodo destino (T) dentro de la red analizada.

[pic 7]

        3            4[pic 8][pic 9][pic 10][pic 11][pic 12]

        4                7[pic 13][pic 14][pic 15][pic 16][pic 17][pic 18]

        5        2        2        2        2[pic 19][pic 20]

        6        2        5        8[pic 21][pic 22][pic 23][pic 24][pic 25][pic 26]

(Origen)        5        (Destino)[pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33]

        4        1        2        3[pic 34][pic 35][pic 36][pic 37][pic 38]

        3        6        4[pic 39][pic 40][pic 41]

        5[pic 42][pic 43]

1. 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).

4

[pic 44]

        [pic 45]

        [pic 46]

        [pic 47]

[pic 48]

Respuesta:

...