Return to search

Métodos de subgradiente e de dilatação de espaços aplicados ao projeto de rede de telefonia móvel

Made available in DSpace on 2019-04-05T23:04:27Z (GMT). No. of bitstreams: 0
Previous issue date: 2005-12-28 / This work presents a comparative study of Lagrangean relaxation using Subgradient and Spaces Dilatation methods to solve the generalized assignment problem in diversity and capacity constraints (GAP-DC). This problem,appears during the planning of a mobile telephone network. It consists in assigning radio base stations to hubs at a minimal cost, so that the demands
on each station and on the capacity of each hub can be met. The GAP-DC is known to be NP-hard. Some computational tests was made with instances acquired from a instances generator and computational results indicatethat although Subgradient algorithms are capable of producing good lower bounds, but the tests based on Spaces Dilatation methods prove that this algorithm get better lower bounds, in a better computational time as well as in the first iteration. / Este trabalho apresenta um estudo comparativo entre a relaxacao Lagrangeana associada aos métodos de Subgradiente e de Dilatação de Espaços aplicada na resolução do Problema de Alocação Generalizada com Restrições de Diversidade e Capacidade (PAG-DC). Este problema surge durante o projeto de uma rede de telefonia celular e consiste na atribuição de estações rádio base a hubs, a um custo mínimo, tal que as demandas de cada estação e a capacidade de cada hub sejam atendidas. O PAG-DC é conhecido ser NP-difícil. Foram realizados alguns experimentos computacionais com instâncias geradas a partir de um gerador de instâncias e os resultados obtidos indicam
que os algoritmos baseados no método de Subgradiente são capazes de encontrar bons limitantes inferiores, porém os testes baseados no método de Dilatação de Espaços obtiveram melhores limitantes em um tempo computacional menor e em uma única iteração.

Identiferoai:union.ndltd.org:IBICT/oai:dspace.unifor.br:tede/70000
Date28 December 2005
CreatorsRigolon, Adriana Aparecida
ContributorsPinheiro, Plácido Rogério, Macambira, Elder Magalhaes, Pinheiro, Plácido Rogério, Macambira, Elder Magalhaes, Silva, Jose Lassance de Castro
PublisherUniversidade de Fortaleza, Mestrado Em Informática Aplicada, UNIFOR, Brasil, Centro de Ciências Tecnológicas
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UNIFOR, instname:Universidade de Fortaleza, instacron:UNIFOR
Rightsinfo:eu-repo/semantics/openAccess
Relation5443571202788449035, 500, 500, -7645770940771915222

Page generated in 0.0015 seconds