Final Degree Project
Análisis experimental de las estrategias antibluces de Miller-Tucker-Zemlin y Desrochers-Laporte para problemas de selección de árboles en grafos
Author/s | Delgado Gallo, Isabel |
Director | García Sánchez, Jose Manuel |
Department | Universidad de Sevilla. Departamento de Organización industrial y gestión de empresas I |
Publication Date | 2019 |
Deposit Date | 2020-07-20 |
Academic Title | Universidad de Sevilla. Grado en Ingeniería de Organización Industrial (UMA/USE) |
Abstract | Sabemos que, a la hora de modelar un problema para poder resolverlo, podemos modelarlo de
diferentes formas llegando con todas ellas a la solución óptima.
En este trabajo lo que se hará será analizar dos estrategias de ... Sabemos que, a la hora de modelar un problema para poder resolverlo, podemos modelarlo de diferentes formas llegando con todas ellas a la solución óptima. En este trabajo lo que se hará será analizar dos estrategias de formulación para dos tipos de problemas asociados a la selección de nodos en grafos. Concretamente, se trata del problema Minimum Spanning Tree y del problema de Steiner. En el primero se busca la selección del árbol de expansión a coste mínimo, donde deben seleccionarse todos los nodos del grafo, mientras que en el problema de Steiner solo es necesario seleccionar los nodos identificados como terminales. La resolución de estos dos problemas se realiza con dos estrategias de formulación matemática. Para el análisis de las dos estrategias se va a utilizar una batería de problemas existente en Internet. Se trata de la OR library, que se encuentra en la página web del departamento de investigación operativa del Imperial College de Londres. A partir de los datos proporcionados por dicha batería, y a través de la creación de un programa en C, obtenemos unos archivos legibles para el programa LINGO. De esta forma lo que se pretende es estudiar a través de los tiempos de resolución del programa que tipo de formulación sería más eficiente para cada tipo de problema según distintos niveles de dificultad. Esto será muy útil para cuando los problemas sean de gran tamaño ya que conseguiremos llegar a la solución óptima empleando menos tiempo. |
Citation | Delgado Gallo, I. (2019). Análisis experimental de las estrategias antibluces de Miller-Tucker-Zemlin y Desrochers-Laporte para problemas de selección de árboles en grafos. (Trabajo Fin de Grado Inédito). Universidad de Sevilla, Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
TFG 2274 Delgado Gallo.pdf | 3.968Mb | [PDF] | View/ | |