Please use this identifier to cite or link to this item: http://bibdigital.epn.edu.ec/handle/15000/15369
Title: Partición de Grafos con Restricciones de Tamaño, Peso y Pertenencia
Authors: Gaibor Costta, Angel Gabriel
Keywords: Optimización matemática
Teoría de grafos
Programación lineal
Issue Date: 24-Apr-2016
Publisher: Quito, 2016.
Citation: Gaibor Costta, A. G. (2016). Partición de Grafos con Restricciones de Tamaño, Peso y Pertenencia. 69 hojas. Quito : EPN.
Abstract: 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.
Description: 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
Type: bachelorThesis
Appears in Collections:Tesis Matemáticas (MAT)

Files in This Item:
File Description SizeFormat 
CD-7060.pdf2,23 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.