Programación Dinámica.docx

Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.

El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:     

Ruta 1-2-5-7-8: 4+8+17+9=38[km] Ruta 1-3-4-7-8: 3+12+20+9=44[km] Ruta 1-3-4-6-8: 3+12+2+22=39[km] Ruta 1-3-4-8: 3+12+15=30[km] Ruta 1-3-6-8: 3+4+22=29[km] La ruta o camino más corto esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km]. Variables de Decisión:

Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:

Restricciones:

1. La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1. 2. La restricción (2) determina que si se visito el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2. 3. La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos). 4. La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5. 5. La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6. 6. La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8. 7. La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8. 8. Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8. El problema del Camino más Corto o Ruta Mínimaanterior se alcanzan los siguientes resultados:

Donde se corrobora que la ruta más corta (solución óptima) corresponde al camino 1-3-6-8 con una distancia total de 29[km] (valor óptimo).