Problema de la ruta más Corta PDF

Preview

Summary

Modelos con ejemplos de Optimización y un Caso de Ejemplo...

Description

Problema de la ruta más corta Cristian David Sosa Aguirre Modelos Matemáticos de Ingeniería – Programa Maestría en Ingeniería Eléctrica, Universidad Tecnológica de Pereira [email protected]

Abstract- En el presente documento se encuentra información sobre la solución del problema de la ruta más corta, el cual es un problema de programación lineal, para ello se utilizan 3 herramientas, Matlab con la función linprog, AMPL y el algoritmo de Dijkstra donde se resuelve dos ejemplos del problema cada uno con los 3 métodos, se muestran los resultados, comparaciones y la manera en que se debe escribir el modelo para solucionarlo. I.

INTRODUCCIÓN

A. Programación Lineal. La programación lineal es un tipo de programación que tiene como fin resolver modelos matemáticos que son de carácter únicamente lineal, a su vez el objetivo es poder optimizar alguna problemática ya sea encontrando el valor mínimo o el máximo de la función objetivo que se analiza.

Fig 1. Representación de un flujo de red.

2. Modelo matemático del problema de planificación de la producción. El modelo matemático descrito de manera simbólica se presenta en la figura 2.

Un problema de programación matemática requiere de 4 componentes básicos:    

Conjunto de datos. Conjunto de variables involucradas y sus dominios. Conjunto de restricciones (región factible). Función objetivo.

B. El Problema de la Ruta Más Corta. El problema de la ruta más corta se puede representar como una derivación del problema del flujo de la red.

1. El problema de flujo en una red. Se considera una red homogénea, a través de la cual desea mandarse un producto desde ciertos puntos de la red que se denominan nodos fuente hacia otros nodos de destino denominados nodos sumideros. También la red posee nodos intermedios, donde no se genera ni se consume, son nodos de paso. Una convención es definir el flujo Xij como positivo desde la dirección i hasta la dirección j, y negativo en la dirección contraria. Las restricciones al problema es la capacidad de la red que existe para transportar entre el nodo i hacia el nodo j y la conservación del flujo. En la figura 1 se muestra una representación grafica de un problema de esta índole.

Fig 2. Modelo matemático de flujo de red.

Ahora conociendo el modelo de flujo de una red, se puede representar el modelo de la ruta más corta utilizando el mismo principio solo que con algunos cambios:



 

Solamente se tiene dos nodos, uno de origen y uno de destino, en el nodo de origen ingresa una unidad de flujo y en el de destino sale una unidad de flujo, el resto de los nodos se consideran de paso. Los arcos que se unen entre nodos se les asocia un costo, o una distancia no negativa. Se considera una red no dirigida.



Escribir el modelo de manera explicita y como lo solicita la función linprog.

En la siguiente figura se muestra como se debe aplicar la función linprog en Matlab.

Esta última condición a veces puede representar problemas en la función objetivo ya que al no darle una orientación definida al grafo, se podría encontrar flujos negativos que impacta a la función objetivo, mostrando un resultado erróneo no en la ruta pero si en la función objetivo para ello se plantea la siguiente solución. 



Se le da un sentido al grafo teniendo en cuenta los posibles sentidos más lógicos de ir desde el nodo de inicio i hasta el nodo final j, la propagación de la dirección es hacia adelante, buscando la ruta más corta. Para asegurarse de lo anterior la restricción de la capacidad de flujo que puede circular por cada tramo de red se define de acuerdo con la siguiente restricción. 0 ≤ X i− j ≤1 (1)

II.

EJERCICIO DE APLICACIÓN

Para entender el problema de la ruta más corta y comprobar la solución se muestran dos ejemplos uno con 8 nodos y otro con 20 nodos con su respectiva solución, cada uno se resuelve por los 3 métodos, con la herramienta linprog de Matlab , el algoritmo de Dijkstra programado en Matlab y programándolo en AMPL. A. Problema de la ruta más corta (8 nodos).

Fig 3. Ejercicio de aplicación de 8 nodos.

1. Resolviendo el modelo con la función linprog de Matlab. Para resolver el modelo utilizando esta función se debe tener en cuenta los siguientes aspectos: 

Conocer cómo aplicar la función linprog.

Fig 4. Función linprog.

A continuación se presenta el código escrito en Matlab para aplicar la función linprog al ejercicio de aplicación y sus resultados.

Fig 6. Solución al ejercicio de aplicación utilizando linprog.

De acuerdo con el orden de las variables, la solución de la ruta más corta a la figura 3 es:

Fig 5. Código en Matlab.

Los resultados se muestran a continuación.

  

Xoa—Xac—Xcf—Xft. El costo o la distancia total recorrida es de 10 unidades Tiempo de computo que le toma al algoritmo para encontrar el óptimo es de 0.1831s.

2. Resolviendo el modelo en AMPL. AMPL es un lenguaje de programación que su función es resolver problemas de optimización, la ventaja que ofrece este entorno es que el modelo se puede describir de manera simbólica, es decir como se muestra en la figura 2. Sin embargo se deben tener ciertos criterios:    

Conocer el entorno de programación. Para resolver cualquier problema se debe generar un archivo.mod, que es donde se describe el modelo de manera simbólica. Se debe generar un archivo.dat, es donde se especifican los parámetros del modelo. De manera opcional se puede elegir el solver para resolver el problema, sino el elige uno por defecto, esto se debe tener cuidado ya que algunos solver son exclusivos para un tipo de programación y no son tan eficientes resolviendo otro tipo de programación.

A continuación se presenta el código escrito en AMPL para resolver el ejercicio de aplicación y sus resultados.

Fig 9. Solución al ejercicio de aplicación utilizando AMPL.

De acuerdo con el orden de las variables, la solución de la ruta más corta a la figura 3 es:     Fig 7. Modelo escrito de manera simbólica (archivo.mod).

Xoa—Xac—Xcf—Xft. Las variables que tienen el orden por e-16 y e-17, se consideran cero. El costo o la distancia total recorrida es de 10 unidades Tiempo de computo que le toma al programa es de 0.109s.

3. Resolviendo el modelo con el algoritmo de Dijkstra.¨ El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista. Su nombre alude a Edsger Dijkstra, científico de la computación de los Países Bajos que lo describió por primera vez en 1959. La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen hasta el resto de los vértices que componen el grafo, el algoritmo se detiene.¨ [2]. A continuación se muestra el código escrito en Matlab utilizando el algoritmo de Dijkstra. Nota: Para esto se utilizó un algoritmo que ya lo habían creado en Matlab como función y estaba gratuito en la página oficial de Matlab. Solamente se tuvo que aprender cómo se debía escribir la función.

Fig 8. Parámetros del modelo (archivo.dat).

A. Problema de la ruta más corta (20 nodos). Para verificar la validez de los 3 métodos de solución, se implementa para un problema de la ruta más corta pero para un grafo de 20 nodos.

Fig 10. Código en Matlab algoritmo de Dijkstra.

Donde G: Es la matriz que indica los pesos entre los arcos, 1, corresponde al nodo de inicio y 8, corresponde al nodo final. Devuelve entonces, el costo de la ruta, y la ruta realiza pero desde el nodo final hasta el nodo inicial. Los resultados se muestran a continuación.

Fig 12. Ejercicio de aplicación de 20 nodos.

1. Resolviendo con la herramienta linprog de Matlab. Debido a que el ejercicio aumenta en cantidad de nodos, de la misma manera sucede con las restricciones y como para utilizar linprog se deben escribir las ecuaciones de manera explícita y luego, escribirlas de manera matricial, el código crece por ello, solo se mostraran los resultados. Adjunto a este documento se anexan los códigos realizados en Matlab.

Fig 11. Solución al ejemplo utilizando algoritmo de Dijkstra.

De acuerdo con el orden de las variables, la solución de la ruta más corta a la figura 3 es:   

Xoa—Xac—Xcf—Xft. El costo o la distancia total recorrida es de 10 unidades. Tiempo de computo que le toma al programa es de 0.105653s.

Fig 14. Solución al ejercicio de aplicación utilizando AMPL.

De acuerdo con el orden de las variables, la solución de la ruta más corta a la figura 12 es: Fig 13. Solución al ejercicio de aplicación utilizando linprog.

De acuerdo con el orden de las variables, la solución de la ruta más corta a la figura 12 es:   

X14—X47—X4_12—X12_20. El costo o la distancia total recorrida es de 163 unidades. Tiempo de computo que le toma al programa es de 0.242943s.

X14—X47—X4_12—X12_20. El costo o la distancia total recorrida es de 163 unidades.  Tiempo de computo que le toma al programa es de 0.078s. 3. Resolviendo el modelo con el algoritmo de Dijkstra. Por último se resuelve el ejercicio utilizando el algoritmo de Dijkstra, también no se muestra el código, debido al crecimiento del mismo para construir la matriz G. Por ello solo se muestran los resultados.  

2. Resolviendo el modelo en AMPL. En ampl sigue siendo el mismo modelo escrito en la figura 7, solamente se cambian los parámetros del archivo .data. Los resultados son los siguientes:

Fig 15. Solución al ejemplo utilizando algoritmo de Dijkstra.



X14—X47—X4_12—X12_20.

 

El costo o la distancia total recorrida es de 163 unidades. Tiempo de computo que le toma al programa es de 0.018343s.

Se concluye que por los 3 métodos para ambos casos de análisis se llegan a los mismos resultados, el tiempo de computo en general es del orden de centésimas de segundos por lo que no es un factor clave, la herramienta linprog es la que incluso en ese orden muestra más tiempo de computo. El verdadero factor clave está en la programación del código, a medida que el programa se vuelve más extenso, de la misma manera se torna complejo programar en linprog e incluso utilizando la función ya creada en Matlab del algoritmo de Dijkstra, sin embargo en ampl como ya se tenía el modelo escrito de manera simbólicas, solamente se tuvo que actualizar los parámetros y se hizo fácilmente. Los archivos de Matlab y AMPL se anexan junto este informe. III.

CONCLUSIONES

●

Poder modelar matemáticamente un problema permite poder implementar una optimización a través de algún software teniendo en cuenta el tipo de programación para asi poder tener la solución optima del mismo.

●

Como se concluyó en la sección anterior por las 3 metodologías se llegó al mismo resultado, sin embargo al programar en AMPL brinda la posibilidad de describir el modelo de manera simbólica sin importar si el numero de variables y/o restricciones que aumenten, solo se modifican son los parámetros, sin embargo en Matlab al tener que describir el modelo de manera exacta a medida que las variables y/o restricciones aumentan, también lo hace el código por lo que puede tornarse complejo de programar e inducir errores. Por ello AMPL se vuelve una herramienta de gran utilidad para problemas de optimización.

REFERENCIAS [ CITATION Mau19 \l 9226 ] M. Granada, Curso Modelos Matematicos de Ingenieria, Pereira, 2019. Universidad Tecnológica de Pereira. [ CITATION Wik19 \l 9226 ] Wikipedia, «Algoritmo de Dijkstra,» Wikipedia, 29 agosto 2019. [En línea]. Available: https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra. [Último acceso: 25 septiembre 2019]....