Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/1930
Title: | Enumeração de soluções em problemas de optimização em redes | Other Titles: | Ranking solutions of network optimisation problems | Authors: | Pascoal, Marta Margarida Braz | Orientador: | Clímaco, João Carlos Namorado Captivo, Maria Eugénia Vasconcelos |
Keywords: | Matemática Aplicada; Optimização | Issue Date: | 1-Apr-2005 | Abstract: | A enumeração de K soluções de um dado problema combinatório é uma generalização, natural, desse problema combinatório, em que, em vez de se procurar uma única solução óptima, se pretende listar, por ordem não decrescente de um determinado custo, as K melhores soluções do problema. Este trabalho debruça-se sobre alguns problemas de determinação ordenada de soluções em Optimização em Redes, começando por analisar dois dos problemas clássicos, a enumeração de trajectos e a enumeração de caminhos, do ponto de vista mais habitual em que a função objectivo é aditiva, e para uma função objectivo genérica. Desenvolvem-se vários algoritmos para enumeração de trajectos e de caminhos que melhoram outros já conhecidos, incluindo processos para listar trajectos e caminhos relativamente a problemas que não verificam o Princípio de Optimalidade. Na sequência do estudo daqueles problemas analisa-se a enumeração de trajectos e caminhos óptimos segundo uma função objectivo concreta, conhecida como tempo total de transmissão e com aplicação nas áreas de redes de transportes e redes de telecomunicações. Introduzem-se dois algoritmos para enumerar caminhos segundo essa função objectivo e adaptam-se algoritmos de enumeração de caminhos e trajectos óptimos a esta função objectivo concreta. Aborda-se a determinação ordenada de soluções de problemas combinatórios na generalidade, com especial ênfase para a enumeração de afectações. Propõe-se um algoritmo para este último problema, donde resulta também uma rotina para determinar a segunda melhor afectação. Por fim, apresentam-se duas aplicações de algoritmos de enumeração a problemas de telecomunicações, nomeadamente um problema de encaminhamento de video-tráfego e um problema de encaminhamento de informação na internet. | Description: | Tese de doutoramento em Matemática (Matemática Aplicada) apresentada à Fac. de Ciências e Tecnologia de Coimbra | URI: | https://hdl.handle.net/10316/1930 | Rights: | embargoedAccess |
Appears in Collections: | FCTUC Matemática - Teses de Doutoramento |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.