Problema de cobertura - Programação Linear Inteira (PLI)

Nessa classe de problemas, várias instalações oferecem serviços sobrepostos a várias localidades. O objetivo é determinar o número mínimo de instalações que cobrirão (isto é, satisfarão as necessidades) cada localidade. Por exemplo, estações de tratamento de água podem ser construídas em vários locais, sendo que cada uma atenderia a um conjunto diferente de cidades. A sobreposição surge quando uma dada cidade pode receber serviços de mais de uma estação.

Exemplo: Instalação de telefones de segurança

Para promover a segurança no campus, o Departamento de Segurança de uma universidade iniciou um processo de instalação de telefones de emergência em locais selecionados. O departamento quer instalar o número mínimo de telefones, contanto que cada uma das ruas principais do campus seja atendida por no mínimo um telefone. A Figura 1 mapeia as ruas principais (A a K) do campus.

É lógico colocar os telefones em cruzamentos de ruas, de modo que cada telefone atenda no mínimo duas ruas. A figura 1 mostra que o layout das ruas requer um máximo de oito localizações de telefones.

Figura 1

Resolução:

Defina-se

-Binário:

xj:  1, se um telefone for instalado no local j

      0, caso contrário

-Restrições

As restrições do problema requerem a instalação de no mínimo um telefone em cada uma das 11 ruas (A a K). Assim, o modelo se torna

Minimizar z= x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8

Sujeito a:

x1 + x2  >= 1 (Rua A)

x2 + x3 >= 1 (Rua B)

x4 + x5 >= 1 (Rua C)  

x7 + x8 >= 1 (Rua D)

x6 + x7 >= 1 (Rua E)

x2 + x6 >= 1 (Rua F)

x1 + x6 >= 1 (Rua G)

x4 + x7 >= 1 (Rua H)

x2 + x4 >= 1 (Rua I)

x5 + x8 >= 1 (Rua J)

x3 + x5 >= 1 (Rua k)

xj(0,1), j=1,2,3,4,5,6,7,8

A solução ótima do problema requer instalar quatro telefones nos cruzamento 1,2,5 e 7.

Comentários:Em sentido escrito, problemas de cobertura são caracterizados por:

1) as variáveis xj, j=1,2,...,n são binárias;

2) os coeficientes do lado esquerdo das restrições são 0 ou 1;

3) o lado direito de cada restrição é da forma (>=1);

4) a função objetivo minimiza c1x1 + c2x2 + ... + cnxn, em que cj>0 para todo j=1,2,...,n.

Neste exemplo, cj=1 para todo j. Se cj representar o custo de instalação no local j, então esses coeficientes podem assumir valores que não sejam 1.

Variações do problema de cobertura incluem condições adicionais de lado.