• Author / Uploaded
• Sr Holio

Citation preview

Actividad 1 Instrucciones: Encuentra la ruta mas corta para la siguiente red dada a

continuación. Nodo de origen 1, nodo destino 7. Al terminar envía tu trabajo al tutor.

Solución Para encontrar el camino mas corto dentro del grafo dirigido, a cuyos arcos se les determina valores y queremos hallar la ruta mas corta entre los vértices de origen

(1) y el final (7), de forma que la suma de los valores a los arcos que componen el camino sea mínima. Para la resolución de este problema se pueden aplicar distintos algoritmos tales como es el algoritmo de Dijkstra, sin embargo, para la solución de este problema se aplicó Excel. Para beneficio propio se modifico el problema para mayor facilidad al aplicarse en Excel, es decir, los nombres de los nodos que se identifican como números se cambiaron a letras. 1 2 3 4 5 6 7

A B C D E F G

Utilice el solucionador en Excel para encontrar la ruta más corta desde el nodo S al nodo T en una red no dirigida. Los puntos en una red se llaman nodos (A, B C, D, E, F, G). Las líneas en una red se llaman arcos. Para este problema, necesitamos Excel para saber si un arco está en la ruta más corta o no (Sí = 1, No = 0). Por ejemplo, si SB es parte de la ruta más corta, la celda F5 es igual a 1. De lo contrario, la celda F5 es igual a 0. El flujo neto (salida de flujo - entrada de flujo) de cada nodo debe ser igual a Suministro / Demanda. El nodo S solo debe tener un arco de salida (flujo neto = 1). El nodo T solo debería tener un arco entrante (flujo neto = -1). Todos los otros nodos deben tener un arco de salida y un arco de entrada si el nodo está en la ruta más corta (Flujo neto = 0) o no tiene flujo (Flujo neto = 0). La medida general de rendimiento es la distancia total de la ruta más corta, por lo que el objetivo es minimizar esta cantidad. DESDE A A B B C C

EN HACIA DISTANCIA RUTA B 0.2 1 C 0.9 0 D 0.8 0 C 0.6 1 D 0.1 0 E 0.3 1

D D E F NODO FLUO A 1 = B 0 = C 0 = D 0 = E 0 = F 0 = G -1 =

E F G G

0.4 0.35 0.25 0.5

0 0 1 0

1 0 0 0 0 0 -1 DISTANCIA MINIMA

1.35

CONDICION

Explicación: Las funciones SUMAR.SI calculan el flujo neto de cada nodo. Para el nodo A, la función SUMAR SUMA los valores en la columna HACIA con una "A" en la columna DESDE. Para el nodo G, la función SUMAR SUMA los valores en la columna HACIA con una "G" en la columna DESDE. La distancia total es igual al subproducto de RUTA Y DISTANCIA. Después se aplica SOLVER utilizando el método Simplex LP y como resultado de la condición binaria que agregamos para la columna RUTA dará como resultado 1 o 0, donde el numero 1 indica la arista que el nodo utilizara y el numero 0 para la arista que no se utilizara el grafo.