Optimization In Sports Sport Scheduling And Qualification Problems

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.