[pt] O planejamento e a gestão de atividades esportivas é uma
área promissora e pouco explorada para aplicações de
Pesquisa Operacional. Os problemas nesta área são em geral
de formulação simples e alcançam grande difusão nos meios
de comunicação. Embora sua formulação seja simples, em
geral estes problemas são difíceis de serem resolvidos em
termos computacionais. Os resultados de muitos trabalhos
acadêmicos nesta área têm sido aceitos como soluções para
problemas reais e várias soluções vem sendo implementadas
na prática. Esta tese tem como objetivo principal estudar
dois tipos de problemas que surgem na área de esportes: a
programação de tabelas e os problemas da classificação. A
programação de tabelas para competições esportivas é uma
tarefa difícil, na qual diversas técnicas de otimização
combinatória têm sido aplicadas. Nesta tese, formula-se o
Problema do Torneio com Viagens Espelhado como um problema
de otimização em grafos. O problema é resolvido utilizando-
se algoritmos aproximados. Apresentam-se duas heurísticas
para este problema. A primeira é muito rápida e serve para
fornecer soluções iniciais para a segunda, que é capaz de
obter soluções de boa qualidade em tempos razoáveis. São
deduzidos limites duais para um tipo particular de
instâncias. Estes limites permitem provar a otimalidade
das soluções obtidas heuristicamente para instâncias muito
maiores do que as maiores instâncias resolvidas na
literatura. Por ultimo, é apresentado um modelo de
programação linear inteira para o problema, ao qual são
acrescentadas desigualdades válidas. Os problemas da
classificação visam obter condições, necessárias e
suficientes, para a classificação de uma determinada
equipe para as finais de um campeonato em relação ao
número de pontos a ser obtido. São apresentados modelos de
programação linear inteira que permitem resolver estes
problemas no contexto do Campeonato Brasileiro de Futebol. / [en] Sports management is a very attractive and not very
explored area for applications of Operations Research.
Problems in this area use to have simple formulations and
reach a big coveragge by the media. Although their
formulations are simple, in general these problems are
difficult to be solved in computational terms. The results
of many academic works in this area have been accepted as
solutions for real problems and some solutions are being
implemented.
This thesis has the main objective of studying two types
of problems that appear in the sports area: the fixture
creation and the qualification problems.
Fixture creation (also known as sport scheduling) for
sport competitions is a difficult task, in which several
combinatorial optimization techniques has been applied. In
this thesis, the Mirrored Traveling Tournament Problem is
formulated as a graph optmization problem. The problem is
solved using approximation algorithms. Two heuristics are
introduced for this problem. The first one is very fast
and is used to supply initial solutions for the second one
which is able to obtain high quality solutions in
reasonable computation times. Dual limits are deduced for
a particular type of instances. These limits allow to
prove the optimality of the heuristically abtained
solutions for instances that are much bigger than those
soved in the literature. Finally, an integer programming
model is introduced in wich valid inequalities are added.
The qualification problems aim to obtain necessary and
sufficient conditions for the playoffs qualification of a
given team in terms of the number of points to be
obtained. Integer programming models are introduced which
allow solving these problems in the context of the
Brazilian Football Championship.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:8203 |
| Date | 26 April 2006 |
| Creators | SEBASTIAN ALBERTO URRUTIA |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0022 seconds