Análisis y casos
Tras la lectura del manual de usuario, a continuación puede conocer los diferentes tipos de análisis que se pueden realizar con el software Grafos.
¿cómo usar los algoritmos en Grafos?
En el modo de edición gráfico observará una barra de herramientas con los siguientes botones.
Desde esta barra podrá desplegar y utilizar todos los posibles algoritmos de Grafos que están organizados en las siguientes categorías:
- Caminos
- camino mínimo
- camino máximo
- Árboles
- árbol mínimo
- árbol máximo
- árbol de valor total mínimo
- árbol de valor total máximo
- Flujos
- flujo máximo
- problema de transbordo
- problema de asignación
- localización a coste mínimo
- Rutas
- circuito euleriano
- problema de viajante de comercio
- problema de m viajantes de comercio
- problema de rutas de vehículos (VRP)
- problema de rutas con vehículos capacitados (CVRP)
Al desplegar cualquiera de las categorías (con un grafo construido en pantalla) observará que que algunas opciones están habilitadas y otras no. Para la aplicación de algunos algoritmos, Grafos requiere de algún dato de entrada, como un nodo origen seleccionado (origen), un nodo destino seleccionado (destino), un conjunto de nodos seleccionados (selección), o meta-datos para los problemas CVRP (VRP-XML). Los algoritmos que no requieren datos de entrada estarán siempre habilitados y podrán ser utilizados directamente, en cambio, para habilitar el resto de algoritmos deberá seleccionar (origen, destino, otros) según se indica en la opción de menú elegida.
Recuerde que para activar un nodo origen (Nd1) debe hacer click sobre él con el botón izquierdo del ratón, el nodo destino (Nd2) se selecciona haciendo click el botón derecho del ratón. Conforme se encuentre el estado de la selección, observará que se activan o desactivan las opciones de menú.
En el caso de que Grafos requiera información adicional, se mostrará en pantalla una pequeña ventana con los datos de entrada. Grafos le da libertad para analizar un mismo grafo desde diferentes puntos de vista en cualquier momento, en caso de que la estructura del grafo no sea coherente con el algoritmo, de que falten datos asociados a los arcos, o de no factibilidad, etc. Grafos le avisará. De este modo, aprenderá sobre la utilidad de cada algoritmo y sobre los datos-estructura del grafo requerido. No se preocupe por probar y experimentar, Grafos es relativamente robusto.
Si todo es correcto, a continuación el algoritmo comenzará su proceso de cálculo. El tiempo requerido dependerá del tipo de heurística, de la complejidad del problema a resolver, y por supuesto de la capacidad de cómputo de su ordenador. En cualquier caso, los problemas de optimización tipo MILP (programación lineal entera mixta) son extremadamente complejos y requieren un tiempo de computación muy superior. Esto se tratará más adelante.
Al finalizar el algoritmo, ocurrirán varias cosas:
- Se muestra una ventana con los Resultados del Análisis. Donde se muestra la solución obtenida en modo texto, y el tiempo total de cómputo para el algoritmo seleccionado. En el caso de la optimización, además se podrá visualizar el modelo .lp o .mps del problema.
Utilizar esta ventana es algo bastante intuitivo. Fácilmente podrá guardar el texto de la solución, copiarlo al portapapeles, imprimirlo, cambiar el tamaño de letra (útil para monitores grandes), visualizar/ocultar la solución dibujada.
- Se dibujará la solución sobre el grafo, subrayando los arcos y nodos de la solución.
La solución se dibujará según los colores elegidos y trazos elegidos en Configuración de los Análisis. Es muy fácil, personalizar los colores y el trazado. Ocultando el dibujado de la solución (ventana de Resultados del Análisis), el grafo se dibujará como antes de la ejecución del algoritmo. En cualquier caso, es bueno guardar el estado del grafo antes y después de ejecutar el algoritmo.
Con todo esto, ya está preparado para aprender más sobre los diferentes algoritmos y su utilidad.
Algoritmos
Una posible definición de algoritmo es un conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas reglas definidas. Otra definición sería, algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Ha de tener las siguientes características: legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posible se ha de desarrollar en el menor tiempo posible. El término proviene del matemático árabe Al'Khwarizmi, que escribió un tratado sobre los números. Este texto se perdió, pero su versión latina, Algoritmi de Numero Indorum, sí se conoce.
Seguidamente se describirán los principales algoritmos incorporados en Grafos, prestando especial atención a su aplicación y utilidad.
- problema de localización (a coste mínimo)
- problema de rutas (paso por nodos seleccionados a coste mínimo)
Como puede observar Grafos incorpora un buen conjunto de algoritmos, pero el desarrollo sigue. En el futuro se incorporarán más algoritmos de análisis, nuevas funciones de dibujado y edición. Gracias por utilizar Grafos.
librería de Grafos
DISCULPA LAS MOLESTIAS, EL SERVICIO DE LIBRERÍA DE GRAFOS NO ESTÁ DISPONIBLE
Desde la librería de Grafos podrá descargarse grafos de ejemplo para aprender a usar el programa, utilizar en sus clases, etc. Con la última versión de Grafos podrá subir a la nube y compartir con el resto sus mejores grafos.