Modelos De Optimizacion De Redes

CAPÍTULO 9: Modelos de optimización de redes

Página 8 de 121

Introducción a la Investigacion de Operaciones, 8th Edition

sido conectado a otros nodos y a un nuevo nodo no conectado. Si se agregan arcos de esta manera, se evita que se forme un ciclo y además se asegura que el número de nodos conexos sea uno más que el número de arcos. Cada nuevo arco crea un árbol más grande, que es una red conexa —para algún subconjunto de n nodos— que no contiene ciclos no dirigidos. Una vez agregado el (n − l)-ésimo arco, el proceso se detiene porque el árbol resultante se expande (conecta) hacia todos los n nodos. Este árbol, que se llama árbol de expansión, es una red conexa para los n nodos que contienen ciclos no dirigidos. Todo árbol de expansión tiene exactamente n − 1 arcos, puesto que éste es el número mínimo de arcos necesario para tener una red conexa y el máximo número posible para que no haya ciclos no dirigidos. En la figura 9.3 se muestra los cinco nodos y algunos de los arcos de la figura 9.2 para ilustrar este proceso de hacer crecer un árbol mediante la colocación de un arco (rama) a la vez, hasta que se obtiene un árbol de expansión. En cada etapa del proceso existen varias alternativas para el nuevo arco, por lo que la figura 9.3 muestra sólo una de las muchas formas de construir un árbol de expansión en este caso. Sin embargo, observe cómo cada nuevo arco que se agrega satisface las condiciones especificadas en el párrafo anterior. Los árboles de expansión se estudiarán más a fondo en la sección 9.4. Los árboles de expansión tienen un papel clave en el análisis de muchas redes. Por ejemplo, forman la base del problema del árbol de mínima expansión que se presenta en la sección 9.4. Otro ejemplo es que los árboles de expansión (factibles) corresponden a las soluciones BF del método símplex de redes que se analizaen la sección 9.7.

Por último, será necesario introducir terminología adicional sobre los flujos en redes. La cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido se conoce como capacidad del arco. Entre los nodos se puede distinguir aquellos que son generadores de flujo, absorbedores netos o ninguno de los dos. Un nodo fuente — o nodo origen tiene la propiedad de que el flujo que sale del nodo supera al que entra a él. El caso inverso es un nodo demanda —o nodo destino—, donde el flujo que llega excede al que sale de él. Un nodo de trasbordo (o intermedio) satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale.

CAPÍTULO 9: Modelos de optimización de redes

Página 9 de 121

Introducción a la Investigacion de Operaciones, 8th Edition

FIGURA 9.3

Ejemplo de hacer crecer un árbol poniendo un arco a la vez en la red de la figura 9.2. a) Los nodos sin arcos; b) árbol con un arco; c) árbol con dos arcos; d) árbol con tres arcos; e) árbol de expansión. 379

CAPÍTULO 9: Modelos de optimización de redes

Página 10 de 121

Introducción a la Investigacion de Operaciones, 8th Edition

9.3 PROBLEMA DE LA RUTA MÁS CORTA

Aunque al final de la sección se mencionan otras versiones del problema de la ruta más corta —incluso algunas para redes dirigidas—, la atención se centrará en la siguiente versión sencilla. Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta —la trayectoria con la mínima distancia total— del origen al destino. Se dispone de un algoritmo relativamente sencillo para manejar este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino. Primero se describirá el método y después se ejemplificará con la solución del problema de la ruta más corta que enfrenta la administración de Seervada Park en la sección 9.1.

Algoritmo de la ruta más corta

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

Datos de la nésima iteración: n − 1 nodos más cercanos al origen —que se encontró en las iteraciones previas—, incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos; el resto son nodos no resueltos.)

Candidatos para nésimo nodo más cercano: cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato —esto es,

379

380

CAPÍTULO 9: Modelos de optimización de redes

Página 11 de 121

Introducción a la Investigacion de Operaciones, 8th Edition

el nodo no resuelto que tiene la ligadura más corta—. (Los empates

proporcionan candidatos

adicionales.)

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 la 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.

Aplicación de este algoritmo al problema de la ruta más corta de Seervada Park

La administración de Seervada Park necesita encontrar la ruta más corta desde la entrada del parque (nodo O) hasta el mirador (nodo T) a través del sistema decaminos que se presenta en la figura 9.1. En la tabla 9.2 se encuentran los resultados obtenidos al aplicar el algoritmo anterior —donde el empate del segundo nodo más cercano permite pasar directo a buscar el cuarto nodo más cercano—. La primera columna (n) indica el número de la iteración. La segunda proporciona una lista de los nodos resueltos para comenzar la iteración actual, después

...