PROBLEMA DE LA RUTA MS CORTAEQUIPO 1

INTRODUCCINNodoArco

LA RUTA MS CORTA* El objetivo del problema de la ruta ms corta es

TCNICA DE LA RUTA MS CORTATodos los das, Ray Design debe transportar camassillas otros mueblesDe la fabrica al almacn; necesita pasar por varias ciudades y Ray desea encontrar la ruta con la distancia ms corta. La red de carreteras se muestra en la siguiente figura.

6Pasos de la tcnica de la ruta ms corta

Si observa la figura 11.10, ver que el nodo ms cercano a la planta es el nodo 2, con una distancia de 100 millas. Se conectan entonces los dos nodos. Esta primera iteracin se muestra en la figura 11.11.

FIGURA 11.10Carreteras de la planta de Ray al almacn

Verificamos los nodos 3, 4 y 5. El nodo 3 es el ms cercano, pero existen dos trayectorias posibles.La ruta 123 es la ms cercana al origen, con una distancia total de 150 millas (vase la figura 11.12).El siguiente nodo ms cercano es el nodo 4 o el 5. El nodo 4 est a 200millas del nodo 2, y el nodo 2 est a 100 millas del nodo 1.Entonces, el nodo 4 est a 300 millas del origen. Hay dos trayectorias para el nodo 5, 25 y 35, desde el origen. Advierta que no tenemos que regresar hasta el origen, porque ya conocemos la ruta ms corta de los nodos 2 y 3 al origen.Buscamos el nodo ms cercano alorigen.FIGURA 11.11Primera iteracin para Ray Design

FIGURA 11.12Segunda iteracin para Ray DesignLa ruta 25 tiene 100 millas y el nodo2 est a 100 millas del origen. Entonces, la distancia total es de 200 millas. De manera similar, determinamosque la trayectoria del nodo 5 al origen por el nodo 3 tiene 190 millas

El siguiente nodo ms cercano ser el nodo 4 o el 6, como los ltimos nodos que quedan. El nodo 4 est a 300 millas del origen (300 200 del 4 al 2 ms 100 del 2 al origen). El nodo 6 est a 290 millas del origen (290 100 190). El nodo 6 tiene la menor distancia y como es el nodo final.

Programacin lineal para el problema de la ruta ms cortaAl considerar esto como un problema de trasbordo, el nodo de origen (nodo 1) debe tener una unidad que se enva desde ah: X12+X13 = 1

El nodo destino final (nodo 6) debera tener una unidad enviada ah y esto se escribe como:

X46+X56=1

Cada nodo intermedio tendr una restriccin que requiere que la cantidad que llega al nodo sea igual a la cantidad que sale del nodo. Para el nodo 2 , esto seria

X12+X32=X23+X24+x25 o bien X12-X32-X23-X24-X25=0

GRACIAS POR SU ATENCINDudas & Sugerencias escrbalos en un papelito & trelo a la basura