Paixão, JoséPato, Margarida Vaz2011-04-192011-04-191989Pato, Margarida Vaz. 1989. "Algoritmos para problemas de cobertura generalizados". Tese de Doutoramento. Universidade de Lisboa. Faculdade de Ciênciashttp://hdl.handle.net/10400.5/3066Doutoramento em Estatística e Computação - Especialidade de Investigação OperacionalA presente tese refere-se ao estudo de técnicas de resolução para o problema de cobertura generalizado (PCG). Conhecida que é a complexidade computacional deste problema combinatório, começam por ser estudados métodos de tipo heurístico, envolvendo heurísticas greedy primais com pesquisa local e heurísticas duais. Na avaliação das heurísticas fazem-se análises da situação mais desfavorável e também análises estatísticas elementares dos resultados computacionais. Com vista ao melhoramento dos limites para o óptimo são exploradas três relaxações lagrangeanas para o problema em causa. Uma relaxa todas as restrições de cobertura e outras duas, a estrutural e a de decomposição sugeridas por casos particulares do PCG, exigem reformulações no problema para forçar o aparecimento de subestruturas de fluxo de custo mínimo. Escreve-se sobre a possibilidade de aplicação ao PCG de técnicas de corte, mais precisamente dos cortes condicionais e dos cortes-penalidades. É apresentado um algoritmo de pesquisa em árvore para o PCG que combina algumas técnicas estudadas com a programação linear. Nos testes computacionais para análise empírica dos procedimentos utilizaram-se quase exclusivamente instâncias relativas ao escalonamento dos condutores de transportes urbanos. No final, para além dos resultados obtidos com o mencionado conjunto de instâncias, é sintetizada a experiência efectuada num vasto conjunto de instâncias do problema de cobertura provenientes de aplicações reais e da literatura. Dá-se especial relevo aos casos de PCG relacionados com escalonamento de pessoal, contudo os mesmos métodos podem ser aplicados a qualquer tipo de problema de cobertura generalizado. Das conclusões deste trabalho, poder-se-á destacar a importância de que se revestiu o desenvolvimento da relaxação lagrangeana estrutural. Também os cortes-penalidades se mostraram de grande interesse.porResolução de problemasHeuristicaAlgoritmosdoctoral thesis101048823