O Problema Probabilístico de Localização-Alocação de Máxima Cobertura (PPLAMC) consiste em localizar facilidades, maximizando a população atendida e fornecendo um bom nível de serviço para toda a população, ou seja, deve-se garantir que um usuário, ao chegar a um centro, não espere mais que um tempo máximo permitido ou não encontre uma fila de atendimento com um número de usuário maior que um valor máximo. Estes dois parâmetros dependem da taxa de chegada dos usuários e do atendimento, ambos probabilísticos. Devido às dificuldades intrínsecas do problema, neste artigo são discutidos limitantes lagrangeanos para o PPLAMC obtidos com a relaxação lagrangeana com clusters (LagClus). Na sua proposição inicial, a LagClus utilizou um grafo de conflitos, porém neste artigo esta relaxação foi aplicada em um grafo especial denominado grafo de cobertura.

The Probabilistic Maximal Covering Location-Allocation Problem (PMCLAP) aims to locate facilities maximizing the number of people served and providing a good level of service. This means that customers would not have to wait longer than the wait time established or to wait in long lines. These parameters are influenced by the number of the requests for service and service time, both probabilistic. The PMCLAP is NP-Complete and in this paper we study bounds with a Lagrangean Relaxation with Clusters (LagClus). Instead of using a conflict graph to represent a problem, in this paper another strategy for the use of LagClus using a special graph called covering graph is proposed. This approach provides interesting bounds.