Detalhes bibliográficos
Ano de defesa: |
1989 |
Autor(a) principal: |
Hilcéa Ferreira Marengoni |
Orientador(a): |
Luiz Antonio Nogueira Lorena,
Edson Luiz França Senne |
Banca de defesa: |
Edgard Dias Batista Júnior |
Tipo de documento: |
Dissertação
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Instituto Nacional de Pesquisas Espaciais (INPE)
|
Programa de Pós-Graduação: |
Programa de Pós-Graduação do INPE em Análise de Sistemas e Aplicações
|
Departamento: |
Não Informado pela instituição
|
País: |
BR
|
Resumo em Inglês: |
This work reports a study of a few heuristic and exact methods for solving the p-median problem. It particularly covers an exact algorithm based on an integer programming formulation of the problem. A "branch and bound" algorithm is presented and the bounds are obtained by solving the lagrangean relaxation and using the subgradient optimization method. A data structure that takes into account the matricial character of the problem is developed and the algorithm is implemented to run on a IBM-PC micro-computer. |
Link de acesso: |
http://urlib.net/sid.inpe.br/iris@1905/2005/07.27.06.49
|
Resumo: |
Este trabalho descreve o estudo de alguns métodos exatos e heurísticos para resolver o problema da p-medianas. Em particular enfoca um algoritmo exato baseado em uma formulação de programação inteira do problema. Um algoritmo do tipo "branch and bound" é utilizado e os limitantes são obtidos através da relaxação lagrangeana do problema usando um método de otimização por subgradientes. Uma estrutura de dados explorando a estrutura matricial do problema é desenvolvida e a implementação é feita em microcomputadores IBM-PC. |