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: | DM - Teses de Doutoramento / Ph.D. Thesis BISEG - Teses de Doutoramento / Ph.D. Thesis |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
TD-MVP-1989.pdf | 130,39 MB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.