Grafos Arboles

PREGUNTAS

1. ¿Problema del camino más corto?

2. ¿Problema de Flujo Máximo?

3. ¿Planeación de Proyectos (PERT/CPM)?

4. ¿Problema de Flujo Costo Mínimo?

Adicional

 ¿Problema del Agente Viajero?

1. PROBLEMA DEL CAMINO MAS CORTO

El problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínimo. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.

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.

Ejemplo:

Se dispone de un algoritmo bastante sencillo para 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.

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 para la n-ésima iteración: n-1 nodos más cercanos al origen (encontrados 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 el 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, y éste es 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.

Aplicaciones

Los algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre localizaciones físicas, tales como direcciones en mapas callejeros.

Si un algoritmo representa una máquina abstracta no determinista como un grafo, donde los vértices describen estados, y las aristas posibles transiciones, el algoritmo de los caminos más cortos se usa para encontrar una secuencia óptima de opciones para llegar a un cierto estado final o para establecer límites más bajos en el tiempo, necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un puzzle como el Cubo de Rubik, cada arista dirigida corresponde a un simple movimiento o giro. El algoritmo de los caminos más cortos se usa para encontrar la solución que utiliza el mínimo número posible de movimientos.

Generalización:

 El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.

 El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.

 El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo.

Ejemplo

Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Está estudiando cual es el trayecto más corto usando un mapa de carreteras. Las carreteras y sus distancias están representadas en la figura siguiente:

Se determinan las variables de decisión, en este caso:

• Xij: acción de desplazarse del pueblo i al j (0 indica que no hay desplazamiento y 1 que sí hay desplazamiento)

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen del balance entre los posibles caminos que parten desde cada pueblo y los que llegan hasta él (obviando los caminos que nos devuelvan al punto de partida y los que provengan del punto de destino):

 Balance de caminos del pueblo 1: X12 + X13 = 1

 Balance de caminos del pueblo 2: X24 + X25 – X12 – X42 – X52 = 0

 Balance de caminos del pueblo 3: X34 + X36 – X13 – X43 – X63 = 0

 Balance de caminos del pueblo 4: X42 + X43 + X45 – X24 – X34 – X54 = 0

 Balance de caminos del pueblo 5: X52 + X54 + X57 – X25 – X45 =

 Balance de caminos del pueblo 6: X63 + X67 – X36 = 0

 Balance de caminos del pueblo 7: – X57 – X67 = -1

 Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores,

En este caso las restricciones son que las variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto no pueden ser negativas:

 Xij ≥ 0

 Xij es booleano

Se determina la función objetivo:

Minimizar Z = 12•X12 + 4•X13 + 5•X24 + 3•X25 + 2•X34 + 10•X36 + 5•X42 + 2•X43 + 10•X45 + 3•X52 + 10•X54 + 2•X57 + 10•X63 + 4•X67

2. PROBLEMA DE FLUJO MAXIMO

Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.

Nos permite conocer (calcular) la máxima cantidad de cualquier artículo o información que podemos transportar desde un origen hasta un destino.

El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método simplex y usar cualquier software. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficientes. El algoritmo se basa en dos conceptos intuitivos, el de red residual y el de trayectoria aumentada.

Algoritmo de la trayectoria de aumento para el problema de flujo máximo:

 Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del origen al destino en la red residual, tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los flujos netos asignados constituyen un patrón del flujo óptimo).

 Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.

 Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa la paso 1.

En una red con flujo de capacidades en los arcos, el problema es determinar el flujo máximo posible proveniente de los orígenes de forma tal de ahogar las capacidades de flujos de los arcos. Considere una red con m nodos y n arcos con un flujo simple de bienes. Denote el arco de flujo (i a j) como Xij. Asociamos cada arco a una capacidad de flujo, kij. En esta red, deseamos encontrar el flujo total máximo en la red, F, del nodo 1 al nodo m.

En la formulación de la programación lineal, el objetivo es maximizar F. El monto que parte del origen por varias rutas. Para cada nodo intermedio, lo que entra debe ser igual a lo sale. En algunas rutas los flujos pueden tomar ambas direcciones. La capacidad que puede ser enviada a una dirección en particular también es mostrada en cada ruta.

CARACTERISTICAS

 Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.

 Los nodos restantes son nodos de trasbordo.

 Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dad por la capacidad del arco. En la fuente, todos los arcos señalan hacia fuera. En el destino, todos señalan hacia el nodo.

 El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.

 El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método símplex y usar cualquier software. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficientes. El algoritmo se basa en dos conceptos intuitivos, el de red residual y el de

...