Ruta mas corta IO

Bueno mis estimados pues esto sería todo con respecto a los problemas de Transporte, Asignación y Transbordo. Cabe mencionar que el método Húngaro está diseñado para un problema de minimización. Para un problema de maximización, yo les recomiendo que lo conviertan a uno de minimización. Pero si alguno de ustedes tiene la capacidad de modificar el método Húngaro para un problema de maximización adelante no lo limito.

Ahora veamos en lo poco que nos resta de tiempo algo de modelos de redes.

MODELOS DE REDES

Definiciones Básicas:

      Se define un grafo o una red por medio de dos conjuntos de símbolos: el conjunto de nodos y el conjunto de arcos.

Primero definimos el conjunto de nodos o vértices, el cual denotaremos por V.

      Los vértices de un grafo o una red sirven para representar puntos en un mapa que dependiendo de la situación particular, estos pueden representar cosas diferentes.

      Posteriormente se define el conjunto de arcos, el cual denotaremos por medio de A

Definición: Un arco está formado por un par ordenado de vértices y representa una dirección posible de movimiento que puede ocurrir entre vértices.

     Para una red particular, el conjunto de arcos los denotaremos por medio de A.

     Si una red contiene un arco (i, j), es posible que exista movimiento desde el nodo i al nodo j, en cuyo caso diremos que i es el nodo inicial del arco y j es el nodo terminal.

Por ejemplo, supongamos que los nodos 1, 2, 3, 4 de la figura siguiente representan ciudades y que cada arco representa una carretera (de un solo sentido) que comunica dos ciudades      

[pic 1]                          Para esta red, V= {1, 2, 3, 4} y  A = {(1,2), (2,3), (3,4), (4,3), (4,1)}[pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8]

                              Si una red contiene un arco (j, k), el nodo j es el nodo inicial del arco,  

                                   y el nodo k es el nodo final del arco. Se dice que el arco (j, k) va del  [pic 9][pic 10]

                                   nodo j al nodo k.   [pic 11]

Definición: Una sucesión de arcos en la cual cada arco tiene exactamente un vértice en común con el arco anterior, se llama cadena.

Definición: Una ruta, es una cadena en la cual el nodo final de cada arco es idéntico al nodo inicial del siguiente arco.

Por ejemplo, en la figura anterior, los arcos (1, 2), (2, 3) y (4, 3) forman una cadena pero no una ruta; y los arcos (1,2), (2, 3) y (3, 4) forman una cadena y una ruta: la ruta. La ruta (1,2), (2, 3) y (3, 4) representa un camino para viajar del nodo 1 al nodo 4.

PROBLEMA DE LA RUTA MÁS CORTA

     En este caso suponemos que se asocia a cada arco una longitud en la red. Suponga que empezamos en un nodo en particular (por ejemplo el nodo 1). El problema de encontrar el camino más corto (el camino de longitud mínima) desde el nodo 1 hacia cualquier otro nodo en la red se llama problema de la ruta (camino) más corta.

Por ejemplo, consideremos el caso de una compañía, la cual desea mandar la energía desde la central 1 hacia la ciudad 1. Suponga que la energía tiene que pasar por subestaciones relevadoras, como se muestra en la figura siguiente:

                             [pic 12][pic 13][pic 14]

[pic 15][pic 16][pic 17][pic 18][pic 19]

[pic 20]

Central 1                                                                                         Ciudad1[pic 21][pic 22]

       [pic 23]

[pic 24][pic 25][pic 26][pic 27]

[pic 28][pic 29][pic 30][pic 31]

En esta figura se dan las distancias (en millas) para cualquier par de nodos, entre los cuales se puede transportar la energía.

     La compañía quiere que la energía que se mande desde la centra 1 hacia la ciudad 1, viaje la menor distancia posible; por lo tanto, se tiene que encontrar el camino más corto que une los nodos 1 y 6.

ALGORITMO DE DIJKSTRA

        Al suponer que todas las longitudes de los arcos son no negativas, se puede usar este algoritmo para obtener el camino más corto desde un nodo en particular (por ejemplo el nodo 1) a todos los demás nodos.

        Para iniciar, ponemos al nodo 1 la etiqueta permanente de 0. Después, ponemos a cada nodo i conectado al nodo 1 mediante un solo arco una etiqueta temporal igual a la longitud  del arco que une al nodo 1 con el nodo i. El resto de los nodos (menos el nodo 1) tendrán una etiqueta temporal de ∞.

        Escoja el nodo con la etiqueta temporal más pequeña y convierta esta en etiqueta permanente.

        Ahora suponga que el nodo i se ha convertido justamente en el (k+1) – ésimo nodo que recibirá una etiqueta permanente. Entonces, el nodo i es el k- ésimo nodo más cercano al nodo 1. En este momento, la etiqueta temporal de cualquier nodo (digamos el nodo i´) es la longitud del camino más corto del nodo 1 al nodo i´  que pasa solamente por los nodos incluidos en los (k – 1) nodos más cercanos al nodo 1.

        Para cada nodo j que ahora tiene una etiqueta temporal y que está conectado al nodo i mediante un solo arco, reemplazaremos la etiqueta temporal del nodo j por:

Min{etiqueta temporal del nodo j , etiqueta permanente del nodo i + longitud del arco (i,j)}

        La nueva etiqueta temporal para el nodo j es la longitud del camino más corto del nodo 1 al nodo j que pasa por los nodos incluidos en los k nodos más cercanos al nodo 1 . Ahora hay que convertir la etiqueta temporal más pequeña en una etiqueta permanente. El nodo con esta etiqueta será el k+1 –ésimo nodo más cercano al nodo 1. Continuar con este proceso hasta que todos los nodos tengan una etiqueta permanente.

...