DSpace
 
  Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Dissertações de mestrado >
 Obtenção de limites inferiores para problemas de desenho de redes
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/2908

title: Obtenção de limites inferiores para problemas de desenho de redes
authors: Jesus, Mónica Ferreira de
advisors: Agra, Maria Cristina Saraiva Requejo
keywords: Matemática
Redes de telecomunicações
Optimização combinatória
issue date: 2008
publisher: Universidade de Aveiro
abstract: Nesta tese descrevemos a técnica da relaxação lagrangeana e métodos para optimizar o problema dual lagrangeano. Descrevemos o método do subgradiente, o método do subgradiente radar e o método do feixe de subgradientes. Em particular apresentamos uma relaxação lagrangeana para o problema da Árvore de Suporte de Custo Mínimo com Restrições de Salto (HMST) e aplicamos alguns destes métodos à sua resolução. O problema HMST surge, por exemplo, em situações de desenho de redes de telecomunicações centralizadas com restrições de qualidade de serviço e consiste em determinar uma árvore de suporte de custo mínimo com a restrição adicional de o número de arestas no único caminho de um nodo central a qualquer outro nodo da árvore não ser superior a um determinado valor. Apresentamos, ainda alguns resultados computacionais obtidos com a aplicação de alguns dos métodos descritos para a obtenção de uma aproximação do valor da relaxação lagrangeana apresentada para o problema HMST. ABSTRACT: In this thesis we describe the lagrangean relaxation technique and methods to optimize the lagrangean dual problem. We describe the subgradient method, the radar subgradient method and the bundle method. We present a lagrangean relaxation for the Hop-constrained minimum spanning tree problem (HMST) and use some of the described methods to solve this relaxation. The HMST appears in centralized network design problems where quality of service constraints are required and the problem is to determine a minimum spanning tree such that the length of the only path between the central node and any node in the tree is at most a certain value. We also present some computational results obtained when solving the lagrangean relaxation presented for the HMST using some the methods described.
description: Mestrado em Matemática
URI: http://hdl.handle.net/10773/2908
appears in collectionsMAT - Dissertações de mestrado
UA - Dissertações de mestrado

files in this item

file sizeformat
2008001809.pdf745.42 kBAdobe 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