Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/2902
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Agra, Agostinho | por |
dc.contributor.author | Silva, Sílvia Lima da | por |
dc.coverage.spatial | Aveiro | por |
dc.date.accessioned | 2011-04-19T14:29:51Z | - |
dc.date.available | 2011-04-19T14:29:51Z | - |
dc.date.issued | 2008 | por |
dc.identifier.uri | http://hdl.handle.net/10773/2902 | - |
dc.description | Mestrado em Matemática | por |
dc.description.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). | por |
dc.language.iso | por | por |
dc.publisher | Universidade de Aveiro | por |
dc.relation.uri | http://opac.ua.pt/F?func=find-b&find_code=SYS&request=000222184 | por |
dc.rights | openAccess | por |
dc.subject | Matemática | por |
dc.subject | Programação matemática | por |
dc.subject | Algoritmos | por |
dc.subject | Árvores (Teoria de grafos) | por |
dc.title | Problema do saco-mochila com estrutura em árvore | por |
dc.type | masterThesis | por |
thesis.degree.level | Mestrado | por |
thesis.degree.grantor | Universidade de Aveiro | por |
Appears in Collections: | UA - Dissertações de mestrado DMat - Dissertações de mestrado |
Files in This Item:
File | Size | Format | |
---|---|---|---|
2008001528.pdf | 1.17 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.