Please use this identifier to cite or link to this item: http://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: http://hdl.handle.net/10316/1930
Rights: embargoedAccess
Appears in Collections:FCTUC Matemática - Teses de Doutoramento

Show full item record

Page view(s)

195
checked on Jul 9, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.