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.
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.
