A carregar...
Publicação
Algoritmos para problemas de cobertura generalizados
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 127.33 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
A 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.
Descrição
Doutoramento em Estatística e Computação - Especialidade de Investigação Operacional
Palavras-chave
Resolução de problemas Heuristica Algoritmos
Contexto Educativo
Citação
Pato, Margarida Vaz. 1989. "Algoritmos para problemas de cobertura generalizados". Tese de Doutoramento. Universidade de Lisboa. Faculdade de Ciências
Editora
Faculdade de Ciências da Universidade de Lisboa