DSpace
 
  Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Dissertações de mestrado >
 Problema do saco-mochila com estrutura em árvore
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/2902

title: Problema do saco-mochila com estrutura em árvore
authors: Silva, Sílvia Lima da
advisors: Agra, Agostinho
keywords: Matemática
Programação matemática
Algoritmos
Árvores (Teoria de grafos)
issue date: 2008
publisher: Universidade de Aveiro
abstract: Nesta dissertação, são apresentados alguns dos algoritmos exactos existentes que permitem resolver o Problema do Saco-mochila com Estrutura em Árvore (TKP) e, em particular, são apresentadas de forma uniforme e completa as técnicas de resolução do TKP recorrendo a algoritmos de programação dinâmica. Posteriormente, o TKP é reformulado e são desenvolvidas duas formulações (SP1 e SP2) deste problema como um Problema de Caminho Mais Curto com Restrições de Capacidade. Em seguida, são desenvolvidas duas formulações estendidas (SP3 e SP4) do TKP como um Problema de Caminho Mais Curto. Para comparar a eficiência destas duas últimas formulações, foi feita uma análise da sua implementação computacional considerando diferentes instâncias do problema. Os resultados mostram que a sua eficiência depende da topologia da árvore. Finalmente, é apresentada uma aplicação do TKP ao Desenho de Redes de Acesso Local de Telecomunicações (LANTD). ABSTRACT: In this dissertation, we survey exact algorithms to solve the Tree Knapsack Problem (TKP) and, in particular, we provide a complete and unified presentation of dynamic programs. Then we present two distinct reformulations of the TKP (SP1 and SP2) as a Capacitated Shortest Path Problem. After that, we extend these formulations and develop another two models (SP3 and SP4) of TKP, as a Shortest Path Problem. In order to show the efficiency of the last two models we conduct a computational analysis that concern different problem instances. Our results show that the efficiency of these formulations depends from the tree topology. Finally, we present an application of the TKP to Local Access Network Telecommunications Design (LANTD).
description: Mestrado em Matemática
URI: http://hdl.handle.net/10773/2902
appears in collectionsMAT - Dissertações de mestrado
UA - Dissertações de mestrado

files in this item

file sizeformat
2008001528.pdf1.17 MBAdobe PDFview/open
statistics

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

 

Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2