Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/3066
Título: Algoritmos para problemas de cobertura generalizados
Autor: Pato, Margarida Vaz
Orientador: Paixão, José
Data de Defesa: 1989
Editora: Faculdade de Ciências da Universidade de Lisboa
Citação: Pato, Margarida Vaz. 1989. "Algoritmos para problemas de cobertura generalizados". Tese de Doutoramento. Universidade de Lisboa. Faculdade de Ciências
Resumo: 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
URI: http://hdl.handle.net/10400.5/3066
Aparece nas colecções:BISEG - Teses de Doutoramento / Ph.D. Thesis
DM - Teses de Doutoramento / Ph.D. Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
TD-MVP-1989.pdf130,39 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.