Ejercicio Flujo a costo minimo

[pic 1]

[pic 2]

[pic 3]

[pic 4]

[pic 5]

[pic 6]

[pic 7]

[pic 8]

[pic 9]

La solución en Solver puede observarse en el archivo de Excel anexo “Tarea 2 InvOp” en la pestaña FlujoMin.

a)

[pic 10]

[pic 11]

b)

[pic 12]

[pic 13]

Para obtener la solución de la pregunta en su literal b, se solicitó el análisis de sensibilidad del modelo, obteniendo el Rango de variación del arco 5-6 [3, 5].

[pic 14]

[pic 15]

[pic 16]

[pic 17]

[pic 18]

[pic 19]

[pic 20]

[pic 21]

[pic 22]

[pic 23]

[pic 24]

La solución inicial con el método de Vogel, da un valor en costos de 68 unidades, a partir de esta solución factible inicial a través del método de salto de piedra se determinará si esta solución es la optima o puede ser mejorada.

[pic 25]

[pic 26][pic 27]

La solución a este problema puede observarse en el archivo de Excel anexo “Tarea 2 InvOp”  en la pestaña Transporte.

Ruta más Corta – Algoritmo Dijkstra

Supongamos que existen 7 ciudades interconectadas, cada línea representa la trayectoria permitida de una ciudad a otra. Las distancias entre las ciudades están representadas por valor sobre la línea. Encuentre la secuencia de ciudades que dan la distancia mínima entre la ciudad A y la ciudad G e indique la distancia total utilizando el algoritmo de Dijkstra.[pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55][pic 56][pic 57][pic 58][pic 59][pic 60]

[pic 61] 

Para el algoritmo de Dijkstra en el etiquetado, la  etiqueta está dividida en 2 partes, la parte izquierda representa la distancia acumulada según la ruta hasta el nodo en estudio, la parte derecha de la etiqueta indica el nodo que antecede al nodo en estudio, la etiqueta viene entre corchetes, así por ejemplo la etiqueta del nodo C [5 , A] indica que la distancia del nodo A al C es de 5 Unidades.

[pic 62]

Mediante el etiquetado, se puede concluir que la ruta mas corta entre el nodo A y el nodo G es de 16 Unidades que se logran a través de la ruta A-D-C-E-G.

El algoritmo de Dijkstra También se puede ilustrar mediante la siguiente red, donde al igual que en el etiquetado Los cuadrados representan en su parte izquierda las distancias acumuladas hasta el nodo en estudio y la parte derecha el nodo que antecede al nodo en estudio.

En esta red pueden observarse las distancias acumuladas existentes entre los diferentes nodos.

En cada nodo, se colocarán tantos cuadrados como arcos lleguen al nodo, en el nodo en estudio se resaltará con un color la menor distancia existente, así por ejemplo el cuadrado etiquetado con [10 , B] en el nodo E significa que la distancia acumulada hasta el nodo E teniendo como nodo antecesor el nodo B es de 10 unidades Que no es nada mas que la suma de A hasta B 4 unidades más la distancia del nodo B al E 6 unidades para un total de 10 unidades. Por otra parte la otra etiqueta en el nodo E que esta resaltada en amarillo [9,C] indica que la menor distancia acumulada hasta este nodo es de 9 unidades lograda pasando por el nodo C.

...