Casos especiales - El Problema de Transporte

Para formular el problema de transporte que se presentó en la sección 7.1  como un problema de flujo de costo mínimo, se proporciona un nodo de recursos para cada origen y un nodo de demanda para cada destino pero no se incluyen nodos de trasbordo en la red. Todos los arcos son dirigidos, desde el nodo de recursos hacia el nodo de demanda, en donde distribuir xij unidades del origen i al destino j corresponde a un flujo de xij a través del arco i→j. El costo cij por unidad distribuida se convierte en el costo cij por unidad de flujo. Como el problema de transporte no impone restricciones de cota superior sobre las xij individuales, todas las uij = ∞ .

Utilizando esta formulación para el problema de transporte de la P&T Co. presentado en la sección 7.2 se llego a la red que se muestra en la figura 10.10

Propiedad de soluciones enteras (III)

Ahora obsérvese el patrón de coeficientes para  cada variable en el conjunto de cinco restricciones de arco. Cada variable tiene exactamente dos coeficientes distintos de cero, uno es +1 y el otro es -1. Este patrón aparece en todos los problemas de flujo de costo mínimo y es esta estructura especial la que lleva a la propiedad de soluciones enteras.

Otra consecuencia de esta estructura especial es que una (cualquiera) de las restricciones de arco es redundante. La razón es que si se suman todas estas ecuaciones sólo se obtienen ceros en ambos lados (suponiendo que existen soluciones factibles para que las bi sumen cero), por lo que el negativo de cualquier ecuación es igual a la suma de las demás. Con (n-1) restricciones de arco no redundantes, estas ecuaciones proporcionan exactamente (n-1) variables básicas para una solución básica factible. En la siguiente sección se verá que el método símplex de redes trata las restricciones xij ≤ uij como simétricas de las restricciones  de no negatividad; así, el número total de variables básicas es (n-1). Esto conduce a una correspondencia directa entre los (n-1) arcos de un árbol de expansión y las (n-1) variables básicas. Se hablará más sobre esto más adelante.

Pronto se resolverá este ejemplo aplicando el método simplex de transporte. Pero ahora se analizará la manera en que los cinco casos especiales mencionados se ajustan al formato del problema del flujo de costo mínimo. Para cada caso, se mostrará cómo formular su ejemplo prototipo en esta forma más general.

Propiedad de soluciones enteras (II)

Los valores de bi se muestran dentro de paréntesis cuadrados cerca de los nodos,entonces, los nodos origen (bi>0) son A y B,los nodos destino (bi<0
El modelo de programación lineal para este ejemplo es

Propiedad de soluciones enteras (I)

Para los problemas del flujo de costo mínimo en donde todo bi y uij tienen un valor entero, todas las variables básicas en cada solución factible (incluyendo la óptima) tendrán también valores enteros.

En la figura 10.9 se muestra un ejemplo del problema de flujo de costo mínimo. Esta es la misma que la de la figura 10.2, excepto que ahora se agregaron los valores de bi, cij, y uij.

Formulación (III)

Si los valores de bi que se dan en alguna aplicación violan esta condición, la interpretación más común es que los recursos  o las demandas (el que tenga exceso) representan en realidad cotas superiores y no cantidades exactas. Cuando esta situación surgió en el problema de transporte en la sección 7.1, se aumentaba un destino ficticio para recibir los recursos que sobraban o bien se aumentaba un origen ficticio par mandar en exceso de demanda. El paso análogo en este caso es que debe agregarse un nodo de demanda ficticio para absorber el exceso de recurso (agregando arcos con cij =0 desde todos los nodos de origen hasta este nodo), o bien debe agregarse un nodo de origen ficticio para generar un flujo equivalente al exceso de demanda (agregando arcos con cij=0 desde todos los nodos origen hasta este nodo), o bien debe agregarse un nodo origen ficticio para generar un flujo equivalente al exceso de demanda (agregando arcos con cij = 0 desde este nodo hasta todos los nodos de demanda).

En la práctica, con frecuencia las cantidades bi y uij tendrán valores enteros y la solución requerirá que las cantidades de flujo (las xij) sean también enteros. Por fortuna, igual que para el problema de transporte, este tipo de solución está garantizado sin tener que establecer restricciones enteras en forma explicita sobre las variables. Esto se debe a la siguiente propiedad.

Formulación (II)

La primera suma en las restricciones de los nodos representa el flujo total que sale del nodo i, mientras que la segunda suma representa el flujo total que entra al nodo i; así, la diferencia es el flujo neto generado en este nodo.

En algunas aplicaciones, es necesario tener una cota inferior Lij > 0 para el flujo por cada arco i→ j. Cuando esto ocurre se hace una traslación de variables , xij = xij - Lij, donde xij se sustituye por (x'ij + Lij) en todo el modelo, con el fin de ajustar el modelo al formato anterior con restricciones de no negatividad.

No se garantiza que el problema posea soluciones factibles; esto depende en parte de que arcos se tienen en la red y de sus capacidades. De cualquier manera, para una red diseñada razonablemente, la condición necesaria más importante es la siguiente:

Formulación (I)

Considérese una red conexa dirigida en la que los n nodos incluyen al menos un nodo origen y al menos un nodo destino. Las variables de decisión son:

Problema del flujo de costo mínimo

El problema del flujo de costo mínimo tiene una posición medular ente los modelos de optimización de redes; primero,  porque abarca una clase muy amplia de aplicaciones y segundo, porque su solución es en extremo eficiente. Al igual que el problema del flujo máximo, toma en cuenta un flujo a través de una red con capacidades limitadas en sus arcos. Al igual que el problema de la ruta más corta, considera un costo (o distancia) para el flujo a través de un arco. Al igual que el problema de transporte o el problema de asignación del capítulo 7, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demanda) para el flujo, también con costos asociados. Al igual que el problema de trasbordo del capítulo 7, puede considerar varios puntos de conexión (nodos de trasbordo) entre los orígenes y los destinos para este flujo. De hecho, estos cinco problemas estudiados son casos especiales del problema del flujo de costo mínimo, como se verá enseguida.

La razón por al que el problema del flujo de costo mínimo se puede resolver de manera tan eficiente es que se puede formular como un problema de programación lineal, y por tanto, se puede resolver mediante una versión simplificada del método símplex llamada método símplex de redes. En la siguiente sección se describirá este algoritmo.

Ejemplo Algoritmo para el problema del flujo máximo (V)

Aunque el procedimiento de la figura 10.7 es relativamente sencillo, será útil poder reconocer cuándo se tiene un patrón óptimo sin tener que buscar de manera exhaustiva una ruta que no existe. A veces es posible esto con el resultado de un teorema importante de teoría de redes, conocido como el teorema del flujo máximo cortadura mínima. Una cortadura se puede definir como cualquier conjunto de arcos dirigidos que contienen al menos un arco de cada tayectoria dirigida que va del nodo origen al nodo destino. El valor de la cortadura es la suma de las capacidades de los arcos (en las dirección específica) de la cortadura. El teorema del flujo máximo-cortadura mínima establece que para cualquier red con un solo nodo origen y un solo nodo destino, el flujo máximo factible del origen al destino es igual al valor de la cortadura mínima para todas las cortaduras de la red. Así, si F denota la cantidad de flujo del origen al destino para cualquier patrón de flujo factible, el valor de cualquier cortadura proporciona una cota superior para F, y el menor de los valores de las cortaduras es igual al máximo valor de F. Entonces, si se puede encontrar, en la red original, una cortadura cuyo valor sea igual al valor actual de F encontrado con el procedimiento de solución, el patrón de flujo actual debe ser óptimo. Eventualmente se alcanza la optimalidad siempre que exista una cortadura cuyo valor sea cero en la red residual.

Para ilustrar esto, considérese en la figura 10.5 la cortadura que se indica en la figura 10.8. Nótese que el valor de la cortadura es (3+4+1+6) =14 que, según se había encontrado , corresponde al máximo el valor de F, por lo que se tata de una cortadura mínima. Nótese también que en la red residual obtenida en la iteración 7, en donde  = 14, la cortadura correspondiente tiene el valor cero. Si estos se hubiera observado, no habría sido necesario buscar trayectorias aumentadas adicionales.

Ejemplo Algoritmo para el problema del flujo máximo (IV)

La parte más difícil de este algoritmo, cuando se trabaja con redes muy grandes, es encontrar una trayectoria aumentada. ESta tarea se puede simplificar con un procedimiento sistemático. Se comienza por determinar todos los nodos que se pueden alcanzar desde el origen con un sólo arco con capcidad residual positiva. Después, para caa uno de estos nodos alcanzados, se determinan todos los nuevos nodos (entre los que no han sidos alcanzados) a los que se puede llegar desde este nodo con un solo arco con capacidad residual positiva. Esto se repite con los nuevos nodos conforme se van alcanzando. El resultado será la identificación de un árbol con todos los nodos a los que se puede llegar desde el origen, a lo largo de una trayectoria con capcidad de flujo residual positiva. ESte procedimiento de abanico siempre identificará una trayectoria aumentada, si existe el origen al destino con una capacidad de flujo positivo. En la figura 10.7 se ilustra esto para la red que se obtiene en la iteración 6 del ejemplo anterior.

Ejemplo Algoritmo para el problema del flujo máximo (III)

Si se emplea este último método, existe un flujo a través de un arco si la capacidad residual final es mejor que la capacidad original. La magnitud de este flujo es igual a la diferencia entre estas capacidades. En la figura 10.6 se muestra el patrón de flujo óptimo que resulta al comparar la red que se obtuvo en la última iteración con la figura 10.5.

Este ejemplo ilustra en forma sencilla la razón para sustituir el arco i →j en la red residual y después aumentar en c* la capacidad residual de éste último cuando se asigna un flujo de c* al arco i →j. Sin este refinamiento, las primeras seis iteraciones no cambian, pero en ese momento pareceria que ya no quedan trayectorias aumentadas (ya que la capacidad de flujo real sin usar de E → B es cero). El refinamiento permite agregar la asignación de un flujo de 1 para O→C→E→B→D→T en la iteración 7. En efecto, esta asignación adicional cancela una unidad de flujo asignada en la iteración 1 (O→B→E→T) y la sustituye por las asignaciones de una unidad a las dos rutas O→B→D→T y O→C→E→T.

Ejemplo Algoritmo para el problema del flujo máximo (II)

El patrón de flujo actual se puede identificar ya sea al acumular las asignaciones de flujo o al comparar las capacidades residuales con las capacidades de flujo originales

Ejemplo Algoritmo para el problema del flujo máximo (I)

A continuación se resume la aplicación de este algoritmo al problema de Seervada Park (véase en la figura 10.5 la red original). En cada iteración se muestra la red residual después de completar los tres pasos, en donde se usa una sola línea para representar el par de arcos dirigidos en direcciones opuestas entre cada par de nodos. La capacidad residual del arco i→j se muestra junto al nodo i, mientas que la capacidad residual del arco j→i se muestra junto al nodo j. Utilizando este formato, la red que se muestra en la figura 10.5 es en realidad la red residual antes de asignar ningún flujo. Después de algunas iteraciones, se muestran en negritas (junto a los nodos O y T)la cantidad total del flujo que se logra.

Algoritmo para el problema del flujo máximo (II)

Al realizar el paso 1, con frecuencia habrá varias alternativas de trayectorias aumentadas entre las cuales se podrá escoger. Aunque la estrategia algorítmica para elegir tiene alguna importancia para la eficiencia en las aplicaciones a gran escala, no se profundizará en este tema relativamente especializado. (Más adelante en esta sección, se describe un procedimiento sistemático para encontrar una trayectoria aumentada.) Entonces, para el siguiente ejemplo (y los problemas al final del capítulo), la selección se hará en forma arbitraria.

Algoritmo para el problema del flujo máximo (I)

1. Se identifica una trayectoria aumentada encontrando alguna trayectoría dirigida del nodo origen al nodo destino en la red residual tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los flujos netos ya asignados constituyen un patrón de flujo óptimo).
2. Se identifica la capacidad residual c* de  esta trayectoria aumentada encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. SE aumenta en c* el flujo de esta trayectoria.
3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria aumentada. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa al paso 1.

Una trayectoria aumentada

Es una trayectoria dirigida del nodo fuente al nodo destino en la red residual, tal que todos los arcos en esta trayectoria tienen capacidad residual estrictamente positiva. El mínimo de estas capacidades residuales se llama capacidad residual de la trayectoria aumentada porque representa la cantidad de flujo que es factible aumentar en toda la trayectoria. Por lo tanto, cada trayectoria aumentada proporciona una oportunidad de aumentar más el flujo a través de la red original.

El algoritmo de la trayectoria aumentada selecciona repetidas veces algunas trayectoria aumentada y agrega un flujo igual a su capacidad residual en la red original. Este proceso continúa hasta que ya no hay trayectorias aumentadas, con lo que el flujo del nodo fuente al nodo destino no se puede aumentar. La clave para asegurar que la solución final es necesariamente óptima es el hecho de que las trayectorias aumentadas pueden cancelar flujos asignados con anterioridad en la red original; así, una selección indiscriminada de trayectorias para asignar flujos no puede evitar el uso de una combinación mejor de asignaciones de flujos.

Para resumir, cada iteración del algoritmo consiste en los tres pasos siguientes.

Problema del Flujo Máximo (III)

En principio, la red residual difiere de la red original sólo en que cada arco dirigido (i→ j) que no tiene arco dirigido en la dirección opuesta (j → i) ahora se le agrega con capacidad cero. Después, las capacidades de los arcos en la red residual (llamadas capacidades residuales) se ajustan de la siguiente manera. Cada vez que se agrega una cantidad de flujo Δ a un arco i → j en la red original, la capacidad residual del arco i→ j se disminuye en Δ, pero la capacidad residual de arco j →i se aumenta en Δ. Así, la capacidad residual representa la capacidad del arco que no se usa en la red original o la cantidad de flujo en la dirección opuesta en esta red que se puede cancelar (o una combinación de ambas, si la re original tiene arcos en las dos direcciones). Así, después de asignar los diferentes flujos a la red original, la red residual muestra que tanto más se puede hacer ya se aumentando más lo flujos o cancelado los que se asignaron antes.

Problema del Flujo Máximo (II)

Para hacer que el problema de Seervada Park se ajuste formalmente a este formato con una red dirigida, cada ligadura 10.5 con 0 en un punto terminal se sustituirá por un arco dirigido en la dirección factible. Por ejemplo, la ligadura entre los nodos O y A se sustituye por un arco dirigido del nodo O al nodo A con una capacidad de 5. Las dos ligaduras con un 1 en los extremos (AB y DE) se sustituyen por un par de arcos dirigidos en direcciones opuestas, cada uno con capacidad de 1. Considerando que estos cambios se llevan a cabo, se seguirá operando sobre la red que se muestra en la figura 10.5

Como el problema de flujo máximo se puede formular como un problema de programación lineal (véase el problema 11),se puede resolver con el método símplex. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficiente. Este algoritmo se basa en dos conceptos intuitivos, el de una red residual y el de una trayectoria aumentada.

Problema del Flujo Máximo (I)

Recuérdese que el tercer problema al que se enfrenta el administrador de Seervada Park (véase la sección 10.1) durante la temporada pico es determinar las rutas de algunos viajes de tranvía desde la entrada del parque (estación O en la figura 10.1) al mirador (estación T), de manera que el número de viajes diarios sea mínimo. (Cada tranvía regresará por la misma ruta que tomó de ida, por lo que el análisis se hará sólo sobre los viajes de ida.) Se impusieron límites superiores estrictos sobre el número de viajes de ida permitidos en cada dirección para cada ruta individual. Los límites se muestran en la figura 10.5, en la que los números que aparecen al lado de cada estación sobre los caminos dan el límite superior para ese camino en la dirección de salida de la estación. Por ejemplo, sólo se permite un viaje al día de la estación A a la estación B, pero también se permite otro de la estación B a la estación A. Dados los límites, una solución factible es mandar siete tranvias al día, cinco por la ruta O→ B→ E→ T, uno por la ruta O→ B→ C→ E→ T y otro por O→ B→ C→ E→ D→ T. Pero esta solución bloquea el uso de cualquier ruta que comience con O→ C (porque las capacidades de E→ T y E→ D están saturadas) Es sencillo encontrar mejores soluciones factibles. Es necesario considerar muchas combinaciones o rutas (y el número de viajes asignados a cada una) para encontrarla o las que maximicen.

Con la terminología que se introdujo en la sección 10.2, el problema del flujo máximo se puede describir formalmente como sigue. Considérese una red dirigida y conexa que tiene un solo nodo fuente y un solo nodo destino, y el resto son nodos de trasbordo. Dada la capacidad en los arcos, el objetivo es determinar el patrón factible que fluye a través de la red que maximiza el flujo total, desde el nodo fuente al nodo destino.

Ejemplo Algoritmo para el problema del árbol de mínima expansión (III)

Todos los nodos han quedado conectados, por lo que ésta es la solución (óptima) que se buscaba. La longitud total de las ramas es 14 millas.

Aunque con este procedimiento a primera vista puede parecer que la elección del nodo inicial afectaría la solución final (y la longitud total de las ligaduras), en realidad no es así. Se sugiere que se verifique este hecho en el ejemplo, aplicando de nuevo el algoritmo, pero iniciando en un nodo distinto de O.

Se considera que dentro de este capítulo el problema del árbol de expansión mínima es el que cae dentro de la amplia categoría de diseño de redes. En esta categoría, el objetivo es diseñar la red más apropiada para el problema dado (con frecuencia se trata de sistemas de transporte) y no analizar una red ya diseñada. La referencia selecta 10 proporciona una investigación en esta importante área.

Ejemplo Algoritmo para el problema del árbol de mínima expansión (II)

En forma arbitraria, se selecciona el nodo O para comenzar. El nodo no conectado más cercano a O es el nodo A. Se conecta el nodo A al nodo O.

Ejemplo Algoritmo para el problema del árbol de mínima expansión (I)

La administración de Seervada Park (véase la sección 10.1) necesita determinar los caminos bajo los cuales se deben tener líneas telefónicas para conectar todas las estaciones con una longitud total de cable mínima. Se describirá paso a paso la solución de este problema con base en los datos que se dan en la figura 10.1.

Los nodos y distancias para el problema se resumen enseguida, en donde las líneas delgadas ahora representan ligaduras potenciales.

Algoritmo para el problema del árbol de mínima expansión

1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir se pone una ligadura) al nodo más cercano distinto de éste.
2. Se identifica el nodo no conectado más cercano a un nodo conectado, y se conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que se hayan conectado todos los nodos.

Empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo todavía debe llevar a una solución óptima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden identificar si se buscan las demás formas de romper los empates hasta el final.

La manera más rápida de ejecutar este algoritmo en forma manual es el enfoque gráfico que se ilustra en seguida.

Problema del árbol de expansión mínima (II)

Este problema tiene muchas aplicaciones prácticas importantes. Por ejemplo, puede ser útil en la planeacion de redes de transporte que no se transmitirán mucho y en las que la inquietud principal es proporcionar algún tipo de conexión entre todos los pares de nodos de la manera más ecónomica. Los nodosserán las localidades que requieren acceso a otras localidades, las ligaduras serían las líneas de transporte (carreteras, vias de ferrocarril, vias aereas, etc.) y las "distancias" (valores de las ligaduras) serían los costos de proporcionar la comunicación. En este contexto, el problema del árbol de mínima expansión tiene como  objetivo determinar cuáles serián las líneas de comunicación que darían servicio a todas las localidades con un costo total mínimo. Otros ejemplos en los que surge una decisión parecida incluyen la pleanación de redes de comunicación y redes de distribución de gran escala. Ambos representa áreas de aplicación importantes.

El problema del árbol de mínima se puede resolver de una forma bastante directa, pues ocurre que se trata de uno de los pocos problemas de investigación de operaciones el que la codicia en cada etapa del procedimiento de solución iconduce al final a una solución óptima. Así, con el inicio en cualquier nodo, la primera etapa consiste en elegir la rama más corta posible a otro nodo, sin preocuparse del efecto que esta elección pueda tener en las decisiones posteriores. En la segunda etapa se trata de identificar el nodo no conectado que esté más cerca de cualquiera de los dos que se acaban de conectar y después agregar la ligadura correspondiente la red. Este proceso se repetirá, según el resumen que se da a continuación, hasta que se hayan conectado todos los nodos. Se garantiza que la red resultante es un árbol de mínima expansión.

Problema del árbol de expansión mínima (I)

El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta que se presentó en la sección anterior. En ambos casos se considera una red no dirigida, en la que la información dada incluye los nodos y las distancias entre pares de nodos. Sin embargo, la diferencia crucial para el problema del árbol de expansión mímina es que las ligaduras (arcos no dirigidos) ya no se especifican. Entonces, en lugar de encontrar la ruta más corta a través de una red completamente definida, el problema elige las lugaduras en la red que tenga la longitud total más corta al mismo tiempo que proporciona una trayectoria ente cada par de nodos. Es necesario que las ligaduras se elijan de tal manera que la red resultante forme un árbol (según la definición dada en la sección ) que se expande (conecta) todos los nodos dados. En resumen, el programa es encontrar el árbol de expansión con la longitud total mínima de sus ligaduras.

La figura ilustra el concepto de árbol de expansión para el problema de Seervada Park. La sección a no es un árbol de expansión, pues los nodos (O,A, B, C) no están conectados con los nodos (D,E,T). Se necesita una rama más para hacer esta conexión. En realidad esta red consiste en dos árboles, uno para cada conjunto de nodos. Las ligaduras de la figura 10.4b si  se expanden por toda la red (esto es,  es una gráfica conexa según la definición de la sección 10.2) pero no es un árbol porque tiene dos ciclos (0-A-B-C-O Y D-T-E-D). Tiene demasiadas ligaduras. El problema de Seervada Prak tiene n=7 nodos, y coo se indicó en la sección 10.2, una red debe tener justo (n-1)= 6 ligaduras y no tener ciclos para calificar como un árbol de expansión. Esta condición se logra en la figura 10.4c, por lo que esta red es una solución factible (con una longitud total de 24 millas en las ramas) para el problema del árbol de mínima expansión.

Otras aplicaciones (II)

Otra versión del problema de la ruta más corta es encontrar las rutas más cortas del origen a todos los demás nodos de la red. Nótese que el algoritmo obtiene las rutas más cortas a cada nodo que está más cerca del origen que el destino. Entonces, si todos los nodos son destinos potenciales, la única modificación que se necesita es que el algoritmo no se detenga, hasta que todos los nodos se hayan resuelto.

Otra versión aún más general del problema de la ruta más corta es encontrar la ruta más corta desde todos los nodos a todos los demás nodos. Otra opción es eliminar la restricción de que las "distancias" (valores de los arcos) sean no negativas. Se pueden poner también restricciones sobre las trayectorias que se pueden seguir. Todas estas variaciones surgen en ocasiones  en la práctica y por esto han sido estudiadas por los investigadores.

Los algoritmos para una gran variadad de problemas de optimizanción de análisis combinatorio - como los problemas de diseño de ruta de vehículos- con frecuencia utlizan como parte de sus subrutinas, la solución de un gran número de problemas de la ruta más corta. Aunque no se dispone de espacio suficiente para profundizar en este tema, tal vez esta aplicación sea una de las más importantes de este algoritmo.

Otras aplicaciones (I)

Antes de concluir con la presentación del problema de la ruta más corta, es necesario hacer hincapié en un punto. Hasta aquí, se ha descrito el problema en términos de minimizar la distancia de un origen a un destino. Sin embargo, en realidad el problema de redes que se estudia es el de encontrar cuál es la ruta que conecta a dos nodos específicos que minimiza la suma de los valores de las ligaduras sobre esa ruta. Por ejemplo, las ramas pueden corresponder a actividades de algún tipo y los valores asociados a cada una pueden representar el costo de esa actividad entonces, el problema sería encontrar qué secuencia de actividades logra el objetivo específico de minimizar el costo total relacionado. (Véase el problema 2.) Otra  posibilidad consiste en que el valor asociado a cada ligadura sea el tiempo requerido para realizar esa actividad. En este caso se desearía encontrar la secuencia de actividades que logra el objetivo específico de minimizar el tiempo total requerido. (véase el problema 6). Así, algunas de las aplicaciones más importantes del problema de la ruta más corta no tienen nada que ver con caminos en el sentido normal de la palabra.

Muchas aplicaciones requieren encontrar la trayectoria dirigida del origen al destino de una red dirigida. El algoritmo que acaba de presentarse se puede modificar con facilidad para que maneje trayectorias dirigidas en cada iteración. En particular, cuando se identifican candidatos para el n-ésimo nodo más cercano, sólo se considerarán los arcos dirigidos desde un nodo resuelto a un nodo no resuelto.

Problema Algoritmo de la ruta más corta

La administración de SEervada Park necesita encontrar la ruta más corta desde la entrada del parque (nodo O) al mirador (nodo T) a través del sistema de caminos que se muestra en la figura 10.1. En la tabla 10.2 se encuentran los resultados obtenidos al aplicar el algoritmo anterior a este problema (en donde el empate para el segundo nodo más cercano). La primera columna (n) indica el número de la iteración. La segunda columna da una lista de los nodos resueltos para comenzar la iteración actual, después de quitar los que no sirven (aquellos que no tienen conexión directa con nodo no resueltos). La tercera columna da los candidatos para el n-ésimo nodo más cercano (los nodos no resueltos con la ligadura más corta  al nodo resuelto). La cuarta columna calcula la distancia de la ruta más corta desde el origen a cada uno de los estos candidatos (esto es, la distancia al nodo resuelto más la distancia de la ligadura que va al candidato). El candidato con la suma de distancias más pequeñas es el n-ésimo nodo más cercano al origen, el cual se indica en la quinta columna. Las dos últimas columnas resumen la información de este último nodo resuelto necesaria para pasar las iteraciones siguientes (a saber, la distancia de la ruta más corta desde el origen a este nodo y la última rama en esta ruta más corta).

La ruta más corta desde es el nodo destino hasta el origen se puede rastrear hacia atrás en la última columna de la tabla 10., con lo que se obtiene T→D→E→B→A→O o bien T→D→B→A→O. Por tanto,, se identificaron las dos opciones para la ruta más corta desde el origen hasta el destino como las cadenas O→A→B→E→D→T y O→A→B→D→T, con una distancia total de 13 millas en cualquiera de las dos rutas.

Algoritmo de la ruta más corta (II)

Candidatos para el n-ésimo nodo más cercano: cada nodo resuelto que está conectado directamente por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta.

Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El  candidato con al distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.

Algoritmo de la ruta más corta (I)

Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetira para n = 1,2....., hasta que el n-ésimo nodo más cercano sea el nodo destino).

Datos para la n-ésima iteración: (n-1) nodos más cercanos al origen (encontrados en las iteraciones previas), y también su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llamarán nodos resueltos; el resto son nodos no resueltos)