1.
2.
3.
4.
5.
6.
problemas são representados de forma algébrica. Uma forma de fazê-lo é construir uma tabela
(o termo chique é “matriz”) cujas linhas correspondam às peças e cujas colunas correspondam
às regiões. Assim, a matriz tem quatro linhas e oito colunas. Como cada peça está ou não em
alguma região, podemos usar um 0 para mostrar que certa peça não está numa certa região e
um 1 para mostrar que está. A Figura 18.3 mostra a matriz correspondente à escolha de
Constantino. Podemos transformar seus preceitos em regras para a modificação das entradas
da matriz; dessa forma, o problema pode ser reformulado algebricamente. Por motivos óbvios,
chamamos tais questões de problemas de programação inteira zero-um.
Figura 18.3
A matriz escolhida por Constantino.Não vou entrar nos detalhes técnicos, mas vale a pena observar que o método de ReVelle e
Rosing parte o problema em dois. O primeiro é chamado de problema da dominação. Este
problema ignora a restrição de que há quatro peças, perguntando simplesmente qual é o menor
número de peças que podemos alocar de modo que todas as regiões possam ser protegidas em
no máximo uma jogada (se a resposta for “mais de quatro”, então é evidente que o problema
original não tem solução). O segundo problema é complementar ao primeiro, sendo chamado
de problema da cobertura máxima. Este problema respeita a restrição das quatro peças, mas
ignora a necessidade de protegermos todas as regiões. Em vez disso, ele pergunta qual é o
maior número de regiões que podemos proteger (em uma jogada ou nenhuma) com quatro
peças. (Também podemos considerar outras quantidades de peças, se necessário.)
Existem métodos gerais (incorporados em programas de computador) para resolver cada
um desses problemas; tais métodos “cercam” o problema original, dizendo-nos se existe uma
solução com quatro peças (sim) e se poderíamos resolvê-lo com menos peças (não). Além
disso, os dois métodos, combinados, permitem que encontremos todas as soluções possíveis.
Você já as encontrou? Esta é a sua última chance, pois vou dizer as respostas agora.
Em conjunto, temos agora seis soluções diferentes. Os números entre parênteses mostram
quantas peças devemos colocar nas regiões citadas (já conhecemos a solução 4).
Ibéria (2), Egito (2).
Ibéria (2), Constantinopla (2).
Ibéria (2), Ásia Menor (2).
Bretanha (1), Roma (2), Ásia Menor (1).
Bretanha (2), Egito (2).
Gália (2), Egito (2).