U N I V E R S I D A D N A C I O N A L J O R G E B A S A D R E G R O H M A N NF A C U L T A D D E C I E N C I A SE.A.P. de Ingeniería en Informática y Sistemas

By: CiBeRjOvIaL

Foto: Frontis de la Facultad de Ciencias UNJBG

Métodos de solución:Algoritmo de DijkstraVer video de muestra http://www.youtube.com/watch?v=6rl0ghgPfK0&feature=player_embedded

Algoritmo de FloydVer video de muestra http://www.youtube.com/watch?v=qdY4vK1V0Nk&feature=player_embedded

Ver video de muestra (cont)http://www.youtube.com/watch?v=mk62s7W0kN8&feature=player_embedded

Enunciado

Nota: El problema fue extraído del libro Investigación de Operaciones de Handy Taha.7ma edicion. Capítulo: Modelo con redes

Reescribimos la tabla del enunciado:

Y formulamos con los datos de la tabla nuestro grafo:

El nodo 7 y los caminos que conducen a el no son importantes en nuestro problema, puestoa que en el enunciado nos aclara que el horizonte de planeación es desde el inicio del 2001 (nodo 1) hasta fines del 2005 (implícitamente inicios del 2006) (nodo 6). Es por esto que lo coloreamos de plomo, y no lo tomaremos en cuenta en el algoritmo

algoritmodijkstraRedibujamos nuestro grafo, para que se note mejor los pasos del algoritmo.(Recordar no considerar el nodo 7)

Etiquetemos el nodo 1 con [0,--] puesto que existe 0 distancia acumulada y no procede de ningún nodo (--)

Nota: Si desean entender los pasos, porfavor ver el video de muestra que aparece en la diapositiva 2

iteración 1Seleccionamos el nodo1 y calculamos las etiquetas de los nodos que están conectadas a el (nodo3, nodo4 y nodo5)

Recordar:La etiqueta tiene la siguiente estructura:

[distancia acumulada , nodo del que precede ]

Al final se selecciona el nodo que contenga la etiqueta con menor distancia acumulada.En esta caso el nodo 3 [38,1]

iteración 2Seleccionamos el nodo3 y calculamos las etiquetas de los nodos que están conectadas a este (nodo6, nodo5 (la etiqueta del nodo 1 ya no se calcula puesto que ya fue un nodo seleccionado))

La etiqueta [80,3] del nodo 5 se elimina puesto a que su etiqueta anterior [68,1] tiene menos distancia acumulada.

Se elige el nodo con la etiqueta con menor distancia acumulada, en este caso el nodo 5 con etiqueta [68,1] .

[80,3]

iteración 3Seleccionamos el nodo5 y calculamos las etiquetas de los nodos que están conectadas a este (nodo 2, (las etiquetas del nodo1 y nodo3 no pueden calcularse puesto que sus nodos ya fueron seleccionados anteriormente)).

Asi que solo se calcula la etiqueta del nodo 2 [116,5], y seleccionamos este nodo por ser el único nodo al que le calculamos su etiqueta

iteración 4Seleccionamos el nodo2 y calculamos las etiquetas de los nodos que están conectadas a este (nodo 6, nodo 4, (la etiqueta del nodo5 no se calcula pues ese nodo ya fueron seleccionado anteriormente)).

La etiqueta [186,2] del nodo 6 se elimina pues su etiqueta anterior [91,3] tiene menos distancia acumulada.

La etiqueta [157,2] del nodo 4 se elimina pues su etiqueta anterior [41,1] tiene menos distancia acumulada.

Luego seleccionamos el nodo 4 [41,1] por tener menor distancia acumulada

[186,2]

[157,2]

iteración 5Seleccionamos el nodo4 y calculamos las etiquetas de los nodos que están conectadas a el (nodo 6, (las etiquetas del nodo1 y nodo2 no se calcula pues esos nodos ya fueron seleccionado anteriormente)).

La nueva etiqueta del nodo 6 [89,4] tiene menor distancia acumulada que su etiqueta anterior [91,3] por la etiqueta anterior de elimina.

Luego seleccionamos el nodo 6 por ser el único nodo al que le calculamos su etiqueta

iteración 6Finalmente seleccionamos el nodo6 y concluimos el algoritmo

La distancia del nodo 1 al nodo 6 es:d1-6 = 89La ruta es: 1 → 4 → 6

Interpretación:Se debe comprar el automóvil nuevo el 2001 y el 2004, y el automóvil se mantendrá hasta el 2006.El costo mantenimiento mínimo es de $ 8900