Por favor, use este identificador para citar o enlazar este ítem: http://bibdigital.epn.edu.ec/handle/15000/15369
Título : Partición de Grafos con Restricciones de Tamaño, Peso y Pertenencia
Autor : Gaibor Costta, Angel Gabriel
Palabras clave : Optimización matemática
Teoría de grafos
Programación lineal
Fecha de publicación : 24-abr-2016
Editorial : Quito, 2016.
Citación : Gaibor Costta, A. G. (2016). Partición de Grafos con Restricciones de Tamaño, Peso y Pertenencia. 69 hojas. Quito : EPN.
Resumen : The main objective of this work is to develop an efficient algorithm to find an acceptable solution to the graph partitioning problem with restrictions of size, weight and membership in a reasonable computation time. The problem addressed here is related to a team’s group construction problem in the second category of the ecuadorian football championship. First, the problem is formulated as an integer linear programming problem. Second, the provincial grouping of the teams playing in the second category of the ecuadorian football championship is explained. Third, a new grouping methodology of the teams is proposed, along with an alternative championship scheme to make it more competitive. Moreover, Kernighan-Lin based heuristics are addressed to find good solutions in a reasonable computation time. Finally, some numerical experiments, obtained from the real world application, are shown to evaluate the heuristic’s performace.
Descripción : El objetivo principal de este trabajo es desarrollar un algoritmo eficiente que permita hallar una buena solución del problema de partición de grafos con restricciones de tamaño, peso y pertenencia en un tiempo de computo razonable. El problema abordado está relacionado con un problema de construcción de grupos de equipos en el campeonato ecuatoriano de fútbol de segunda categoría. En primer lugar, se formulará el problema como un programa lineal entero. En segundo lugar, se particularizará y estudiará la zonificación provincial de los equipos del campeonato ecuatoriano de fútbol de segunda categoría. En tercer lugar, se propondrá un esquema alternativo que vuelva más competitivo el campeonato. Para esto se estudiará la heurística de Kernhigan-Lin y a partir de esta se generarán heurísticas alternativas que mejoren las soluciones actuales. Finalmente, se presentarán algunos experimentos numéricos obtenidos de la aplicación de los algoritmos desarrollados.
URI : http://bibdigital.epn.edu.ec/handle/15000/15369
Aparece en las colecciones: Tesis Matemáticas (MAT)

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
CD-7060.pdf2,23 MBAdobe PDFVisualizar/Abrir


Este ítem está protegido por copyright original



Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.