BrBRCEEn0101-74382004000100009

Conflito em redes: origens e destinos cotados

1. Introdução A localização estratégica de recursos escassos ao longo de uma rede, visando detecção (interceptação, bloqueio ou apenas supervisão) de tráfego indesejável (inimigo, ilícito, clandestino) controlado por agentes racionais é por natureza, um problema de Jogos. Em sua forma mais simples, e por isso mesmo mais aplicada, trata-se do conflito de interesses no confronto entre dois jogadores: o evasor, que escolhe a rota a ser utilizada (para fuga, tráfico, transporte de suprimentos, evasão de capital) e o detector, que, independentemente, seleciona um arco da rede para se instalar (patrulhar, interceptar, inspecionar).

Os primeiros trabalhos sobre Interdição em Redes datam dos anos 50, resultado a posteriori do esforço de equipes multidisciplinares durante a 2ª Guerra Mundial, destacando-se nos Estados Unidos, o Grupo de Avaliação Operacional do Departamento Naval (sobre o assunto, ver Danskin, 1962). Nas décadas de 60 e 70, diversos modelos foram propostos e intensamente analisados, entre outras, pela necessidade de bloquear rotas de suprimento da guerrilha no Vietnã (Wolmer, 1964; Durbin, 1966; Wolmer, 1970a e 1970b; McMasters & Mustin, 1970), muitos deles utilizando como ferramenta teórica e computacional o algoritmo de Ford e Fulkerson, de 1954, sobre fluxo máximo e corte mínimo em redes capacitadas. Mais recentemente, Washburn (1980 e 1983), Steinrauf (1991), Wood (1993) e Caulkins et al. (1993) entre outros, abordaram modelos ainda determinísticos, de busca, obstrução simultânea de arcos e nós, etc., assim como, aplicações. O trabalho supracitado de Steinrauf, por exemplo, envolvia a apreensão de precursores químicos numa rede rodo-fluvial no Rio Mamoré na fronteira Brasil-Bolívia.

Em 1998, Cormican et al. analisaram uma versão estocástica, com solução à Stackelberg, isto é, em que obstrução destruição, parcial ou não, dos arcos da rede, é feita preliminarmente pelo interditor, o adversário procurando então otimizar seu uso fluxo máximo, custo mínimo, etc.

Em 1999 Israeli (a) reviu a literatura de Interdição, (b) estendeu os modelos a sistemas gerais, em princípio lineares, mas não necessariamente ligados a redes, designados Linear System-Interdiction Problems (LSIP) e Linear System- Defense Problems (LSDP) pelo autor (interdição e defesa), (c) propôs alguns algoritmos e heurísticas para a redução aproximada de problemas específicos em malhas e (d) relatou testes numéricos com malhas de porte médio, envolvendo fluxo máximo ou caminho mínimo como objetivo na otimização.

Trata-se de problemas estruturados, do tipo em que as variáveis de decisão [/img/revistas/pope/v24n1/ 20103s13.gif] (as duas primeiras binárias), representam respectivamente o reforço e o ataque seletivos ao conjunto K de arcos de [/img/revistas/pope/ v24n1/20103s14.gif] , e seu nível de utilização na rede remanescente (após sua destruição parcial). O modelo básico assume limitações lineares de recursos, [/ img/revistas/pope/v24n1/20103x8.gif], isto é, arcos reforçados não são atacados e <formula/> é a capacidade original do arco k.

Trata-se portanto de jogos à Stackelberg: no primeiro, o atacante considera a melhor utilização a posteriori da rede pelo usuário; no outro o usuário planeja reforçar <formula/> de modo a reduzir as conseqüências de um ataque bem executado, o pior possível, de seu ponto de vista.

Nos testes, Israeli gera randomicamente instâncias (10) de malhas (com cerca de 100 nós) e utiliza diversas técnicas (decomposição, cortes, propostas heurísticas e híbridas) para o cálculo aproximado dos ótimos. Apesar de tolerâncias da ordem de 3600 segundos de CPU, os resultados nem sempre se mostraram bem definidos (discriminação quanto à eficiência relativa) e, conforme se poderia esperar, exibiram grande sensibilidade à ordem de grandeza dos dados.

No trabalho, Israeli comenta que, além da possibilidade das aplicações mais óbvias, militares (detecção ou condução de ataques, defesa de rotas críticas, deslocamento de material e contingentes, questões de suprimento) e civis (tráfico em suas diversas formas, contrabando comercial, de capital, imigração) outras têm sido seriamente cogitadas, destacando-se a criação, em 1996, da comissão presidencial americana PCCIP (White House Executive Order 13010, 07/ 15) visando a proteção e sobrevivência de infraestruturas críticas, consideradas vitais, cuja incapacitação poderia vir a debilitar a segurança econômica e a defesa do país, incluindo telecomunicações, energia, redes financeiras, transportes, água, etc, a serem protegidos de possíveis ataques físicos ou eletrônicos.

A grande maioria dos modelos de interdição em redes era determinística até 1995, quando Washburn & Wood propuseram para o modelo estocástico básico, a redução do jogo a um par dual fluxo máximo-corte mínimo na rede, uma substancial vantagem computacional que evita a necessidade da enumeração a priori das rotas ao longo da rede (no jogo, as estratégias puras do evasor), utilizando o algoritmo de Ford & Fulkerson (1954).

Mais recentemente, algumas extensões do modelo Washburn-Wood, algoritmos e testes foram desenvolvidos em Machado & Sinotti (2002) (ver também Lima & Muniz, 2002). No presente trabalho buscamos resolver o caso em que são estipuladas, nos extremos da rede, cotas de utilização, mais precisamente, as freqüências de uso de cada uma das origens e de cada um dos destinos da rede [/ img/revistas/pope/v24n1/20103s14.gif] , no processo de evasão, uma extensão conceitualmente simples, mas que exige métodos indiretos para resolução via Ford e Fulkerson, e que é considerada relevante por suas possíveis aplicações e.g., em tráfico ilícito em que se tem estimativas das quantidades relativas de produção e consumo nos diversos centros envolvidos. A Seção 2 introduz conceitos básicos e formaliza o problema como um jogo matricial de soma zero. O dilema da redução do problema do evasor a um problema de fluxo máximo, segundo o esquema Washburn-Wood, é discutido na Seção 3, em que se ressalta a dificuldade introduzida pelas cotas nos extremos da rede. A Seção 4 propõe um algoritmo "de delimitação sucessiva de fluxos" cuja convergência é estabelecida na Seção 5. Sua implementação é ilustrada na Seção 6, em uma rede simples (17 arcos, 23 rotas). A Seção 7 relata resultados de testes numéricos preliminares, considerados satisfatórios, envolvendo uma malha de porte médio (cerca de 58.000 rotas). Finalmente, a Seção 8 delineia algumas conclusões e propostas naturais para futura investigação.

2. O Modelo Conceitos e Notação Básicos Trabalhamos com uma rede dimensionada <formula/>, com várias origens e destinos arcos k Î K, nós n Î N, origens iÎI, destinos j ÎJ (extremos e Î E = I È J ) e rotas l Î L, de I para J. O dimensionamento é descrito pelos vetores de cotas a = (a', b') ÎR½K½, onde a e b são distribuições de probabilidades sobre I e J respectivamente, e pÎ R½K½, de probabilidades de detecção pk, arco a arco.

As estratégias mistas dos jogadores são x e y, distribuições sobre os arcos k e as rotas l: freqüências de monitoramento de cada trecho (arco) k da rede pelo detector e de uso da particular rota l pelo evasor, isto é, das escolhas independentes, de k e de l, por ocasião do confronto dos jogadores que buscam por decisões ótimas, individuais. Trata-se de um jogo matricial de soma zero (ver e.g., Davis, 1973) com um condicionamento particular sobre as estratégias do evasor; mais especificadamente, sobre as freqüências com que as diversas origens e destinos serão utilizados.

Introduzimos aqui duas matrizes binárias de incidência (um termo usualmente reservado para a relação vértice ´ arco, ver Boaventura Netto (1996) e Szwarcfiter (1984)):

Temos ainda os seguintes elementos auxiliares: [/img/revistas/pope/v24n1/ 20103x11.gif] a matriz diagonal de detecção [/img/revistas/pope/v24n1/ 20103x12.gif] o vetor de capacidades nos arcos, [/img/revistas/pope/v24n1/ 20103x13.gif], (ck um número suficientemente grande, se pk = 0), a matriz [/ img/revistas/pope/v24n1/20103x14.gif] e o vetor e, que chamaremos de vetor unidade, de componentes iguais a 1 (e é a soma dos vetores unitários do espaço). A conveniência de introduzir o vetor c, isto é, de considerar a inversão ck = 1/pk , ficará evidente quando mais tarde convertermos o jogo num par dual fluxo máximo-corte mínimo: o "tráfego fica congestionado" em arcos de baixa capacidade, isto é, de alta probabilidade de detecção, direcionando assim, indiretamente, a busca pela estratégia ótima de evasão.

As estratégias dos jogadores são descritas geometricamente pelos seguintes símplices: <formula/>, o simplexo das estratégias, não cotadas (livres), do evasor.

<formula/>, o conjunto das estratégias proporcionais do evasor, isto é, que respeitam as cotas ai e bj nos extremos da rede. <formula/> é um politopo em SL, com, digamos, T pontos extremos n1, n2, ... , nT. Observe que se [/img/revistas/ pope/v24n1/20103s16.gif] é a matriz <formula/> com colunas nt , e ST é o simplexo <formula/>, ([/img/ revistas/pope/v24n1/20103s17.gif] é a envoltória convexa dos T vetores nt ).

<formula/>, o simplexo das estratégias do detector.

No confronto, descrito pelo par (x , y), utilizaremos como função de avaliação (ganho, pay-off) a probabilidade média de detecção:

onde xÎ SK , yÎ <formula/> e o somatório é duplo: sobre todos os pares k Î K, lÎ L, para os quais kÎ l uma notação sintética usada deste ponto em diante. Trata-se portanto de um jogo matricial de soma zero, com problemas simétricos:

Como y não varia livremente no simplexo S Le sim em S L, um subconjunto de S L, a transformação clássica do jogo num par dual em Programação Linear (ver e.g., Gass, 1969) não se aplica diretamente. Entretanto, como S L = V (ST), podemos reescrever g como

Temos agora um jogo matricial na forma clássica, com matriz [/img/revistas/ pope/v24n1/20103s18.gif] de ordem <formula/> e estratégias mistas x sobre os arcos k (cada arco é uma estratégia pura do detector) e estratégias z sobre as estratégias proporcionais básicas vt (as puras do evasor). É possível portanto (pelo menos em princípio) considerar a redução do problema, proposta por Washburn & Wood (1995), à um par dual fluxo máximo ´ corte mínimo (Ford & Fulkerson, 1954).

Denotaremos por <formula/> etc, o conjunto das rotas passando pelo arco k, iniciando na origem i, dos arcos ao longo da rota l, iniciando em i, etc, respectivamente. Assim, por exemplo, dizemos que, um subconjunto C de K é um corte em <formula/> quando L(C) = L, isto é, toda rota passa por algum dos arcos kÎ C (a remoção de C desconecta as origens dos destinos).

Aqui, um fluxo na rede é qualquer vetor não-negativo [/img/revistas/pope/v24n1/ 20103x21.gif] : as componentes yl ³ 0 são pensadas como fluxos elementares ao longo das diversas rotas l. Alternativamente, é claro, podemos trabalhar com o vetor <formula/> , cujas componentes são os fluxos agregados induzidos nos arcos da rede. Como trabalharemos com uma rede capacitada pelo vetor c, devemos limitar nossos fluxos: [/img/revistas/pope/ v24n1/20103x23.gif](desigualdade arco a arco: o fluxo fk no arco k não pode ultrapassar sua capacidade ck). O valor do fluxo [/img/revistas/pope/v24n1/ 20103x24.gif] onde <formula/> (o fluxo total entrando na rede através da particular origem i), etc. O valor de um corte [/ img/revistas/pope/v24n1/20103x26.gif]. Em geral temos v(y) £ v(C) para todo fluxo y e corte C na rede e, por dualidade, os valores extremos (máximo e mínimo, respectivamente) das funções v(y) e v(C) coincidem o clássico teorema de Ford e Fulkerson (ver e.g., Ahuja et al., 1993 e Shrijver, 2002).

Usaremos ainda a notação c(i), y(j), etc, para representar a capacidade total <formula/> de entrada na rede através da origem i, o fluxo total <formula/> de chegada ao destino j, etc. Note que <formula/> é uma restrição natural: o fluxo total de entrada em cada origem não pode ultrapassar a capacidade total de entrada neste ponto.

3. A Abordagem de Washburn e Wood Os problemas maxmin-minmax (1) podem ser formulados como um par dual em Programação Linear:

com soluções ótimas <formula/>, satisfazendo [/ img/revistas/pope/v24n1/20103s22.gif], relacionadas com as estratégias ótimas <formula/> dos jogadores e com o valor do jogo [/ img/revistas/pope/v24n1/20103s24.gif] <formula/> são as normalizações das soluções ótimas de (2)).

No problema livre, isto é, sem cotas (sem a restrição [/img/revistas/pope/ v24n1/20103s73.gif] = a) o par (2) tem a forma mais simples,

o que possibilitou Washburn & Wood (1995) reduzirem-no a um problema de fluxo max-corte min na rede <formula/> capacitada pelo vetor c, introduzido na Seção 2. Algebricamente (ver Machado & Sinotti, 2002), fazendo <formula/> x = X e observando que <formula/> é uma matriz não- negativa, que <formula/> e = c e e'x= c'X, obtemos o par dual:

Observe que (4b) é a versão-rotas do problema de fluxo máximo, usualmente formulado em termos dos fluxos nos arcos, mas aqui, dos fluxos ao longo das rotas. Por outro lado, dado um corte qualquer C na rede, tomando [/img/ revistas/pope/v24n1/20103s2.gif], caso contrário, obtemos uma solução viável X de (4a), (pois toda rota passa por algum arco do corte), cujo valor-objetivo é igual a V(C). A dualidade fluxo máximo-corte mínimo permite assim interpretar (4a) como o problema do corte mínimo na rede capacitada.

A superioridade da versão (4) do problema livre está no fato de dispormos de algoritmos combinatoriais eficientes (Ford e Fulkerson e variantes) para o problema do fluxo máximo, que utilizam a estrutura básica da rede diretamente, isto é, a matriz de incidência nó ´ arco (de ordem [/img/revistas/pope/v24n1/ 20103s3.gif]), dispensando assim a necessidade da especificação, a priori, de todas as possíveis rotas l da rede <formula/> uma tarefa onerosa, se não impraticável, mesmo em redes de dimensões modestas (ver e.g., Sinotti, 2000). Vale observar ainda que a ordem da matriz I, ([/img/ revistas/pope/v24n1/20103s4.gif], com L grande), essencial à versão original (3), dificulta computacionalmente também a aplicação direta do Método Simplexo.

Lastimavelmente, a vantagem computacional obtida no caso livre não se estende ao nosso problema, cotado nos extremos: as estratégias do evasor são proporcionais, isto é, devem respeitar as cotas definidas pelo vetor [/img/ revistas/pope/v24n1/20103s26.gif]. Agora o par dual (2) requer, além da especificação de todas as rotas em <formula/>, a determinação preliminar de todas as soluções básicas do sistema [/img/revistas/ pope/v24n1/20103s1.gif]= a (de ordem <formula/>), os pontos extremos vt do simplexo <formula/> um subconjunto de distribuições sobre as rotas l, capaz de gerar (mediante combinações convexas) todas as distribuições proporcionais, o objeto de nosso interesse.

Ainda que algébrica e conceitualmente simples, a restrição adicional, de proporcionalidade das estratégias y do evasor, não parece ser fácil e diretamente tratável por qualquer versão, apropriadamente adaptada, do algoritmo de Ford e Fulkerson, ou outro, do mesmo tipo, na literatura, prejudicando assim a base do sucesso computacional do esquema Washburn-Wood no caso livre. Na próxima seção mostramos como o problema do evasor ainda pode ser formulado, de modo natural, como um tipo particular de problema de fluxo máximo e propomos um esquema de resolução indireto, baseado em sucessivas delimitações do fluxo, utilizando o algoritmo de Ford e Fulkerson, passo a passo, no processo iterativo.

4. Um Esquema Iterativo Observe inicialmente que no problema do evasor (1b) temos, para y Î [/img/ revistas/pope/v24n1/20103s15.gif] fixado, que

De fato, o máximo é a maior das componentes do vetor [/img/revistas/pope/v24n1/ 20103s72.gif] y e, portanto, a menor das cotas superiores deste conjunto.

Podemos portanto reescrever (1b) na forma (5) abaixo

(a restrição e´y = 1 é redundante em (5), em presença da condição [/img/ revistas/pope/v24n1/20103s1.gif] = a). Fazendo y/l = y, multiplicando a desigualdade vetorial pela matriz não-negativa [/img/revistas/pope/v24n1/ 20103s29.gif] e observando que e´y = 1/l , obtemos a forma final (6).

Reduzimos assim o problema do evasor à determinação do fluxo proporcional máximo na rede capacitada, isto é, o fluxo [/img/revistas/pope/v24n1/ 20103s31.gif] y de maior valor possível (max e´y) que respeita arco a arco as diversas capacidades da rede (<formula/> y £ c) e os percentuais pré-estabelecidos do valor agregado [/img/revistas/pope/v24n1/ 20103s32.gif], nas diversas origens e nos diversos destinos (a restrição [/img/ revistas/pope/v24n1/20103s33.gif] Observe que ainda temos um problema de fluxo capacitado máximo; desta vez no entanto a maximização é restrita aos fluxos proporcionais: aqueles satisfazendo, para cada [/img/revistas/pope/v24n1/ 20103s34.gif].

Daqui em diante trabalharemos com a rede estendida [/img/revistas/pope/v24n1/ 20103s35.gif], obtida a partir da original pelo método tradicional: acrescentando dois extremos artificiais, uma origem O e um destino D (agora únicos) e um total de <formula/> arcos artificiais Oi e jD, ligando O a cada uma das origens i de [/img/revistas/pope/v24n1/ 20103s14.gif] e, cada destino j a D.

Se m é uma cota superior qualquer para o valor do fluxo proporcional máximo [/ img/revistas/pope/v24n1/20103s37.gif] em [/img/revistas/pope/v24n1/ 20103s14.gif], isto é, <formula/>, capacitaremos os novos arcos Oi e jD em <formula/> por [/img/ revistas/pope/v24n1/20103s39.gif] e <formula/> É fácil verificar que: (1) rotas em <formula/> (ligando i a j) se identificam com rotas em [/img/revistas/pope/v24n1/ 20103s35.gif] (ligando O a D e passando intermediariamente por i e j), (2) um vetor yÎ R êLê representa assim, tanto um fluxo em [/img/revistas/pope/v24n1/ 20103s14.gif], como em sua extensão <formula/> e (3) um fluxo que respeita as capacidades em [/img/revistas/pope/v24n1/ 20103s35.gif] é proporcional se e somente se respeita as capacidades nos arcos artificiais da extensão e é proporcional em [/img/revistas/pope/v24n1/ 20103s35.gif] , no sentido de que <formula/> nos arcos artificiais.

A busca da solução ótima <formula/> do problema (6) é portanto equivalente à do fluxo proporcional máximo na extensão [/img/ revistas/pope/v24n1/20103s35.gif] construída a partir de uma cota superior conhecida qualquer do valor <formula/> (em princípio, desconhecido) do fluxo proporcional máximo em [/img/revistas/pope/ v24n1/20103s14.gif].

Se y é um fluxo proporcional qualquer temos c (i) ³ y (i) = ai v(y) para cada origem i e algo análogo para os destinos j de [/img/revistas/pope/v24n1/ 20103s14.gif]. Assim, <formula/>, e temos em mãos uma majorante (a primeira delas) do valor ótimo [/img/revistas/pope/v24n1/ 20103s41.gif].

Considere inicialmente a extensão <formula/> da rede original <formula/>, associada à esta cota (isto é, construída como indicado anteriormente, a partir do valor m0) e y0 um fluxo máximo qualquer em <formula/>.

Necessariamente:

e o valor <formula/> é portanto uma nova majorante do valor ótimo <formula/>, tão boa quanto ou melhor do que a anterior: m1 £ m0. Caso se tenha m1 = m0, segue-se da desigualdade que <formula/> para toda origem i, o mesmo ocorrendo nos destinos j da rede <formula/>, e portanto y0 é um fluxo proporcional em [/img/revistas/pope/v24n1/ 20103s11.gif]. Por ser um fluxo máximo, y0 é necessariamente um máximo entre todos os fluxos proporcionais, isto é, y0 é um fluxo proporcional máximo e a busca de uma solução do problema (6) se encerra.

Se m1 < m0 então <formula/> não é um fluxo proporcional ótimo (pode ser proporcional mas, em princípio temos apenas que [/ img/revistas/pope/v24n1/20103s41.gif] £ m1 < m0 ) e a busca continua, construindo-se agora a extensão <formula/> da rede original <formula/> utilizando a nova cota m1 e assim por diante. O procedimento é interrompido se duas cotas sucessivas coincidem, mr+1 = mr, caso em que o fluxo máximo yr na rede estendida [/img/ revistas/pope/v24n1/20103s42.gif] é um fluxo proporcional máximo na rede [/img/ revistas/pope/v24n1/20103s14.gif]. Se a igualdade não ocorrer, temos uma seqüência decrescente de majorantes m 0 > m 1 > ... > [/img/revistas/pope/ v24n1/20103s41.gif] e de fluxos y0 , y1 , ... em [/img/revistas/pope/v24n1/ 20103s14.gif], com m r+1 = v(y r). Como veremos adiante, é possível mostrar que: (1) o valor limite <formula/> coincide com [/ img/revistas/pope/v24n1/20103s41.gif] e (2) todo ponto limite y* da seqüência <formula/> , isto é, limite de qualquer de suas subseqüências, é um fluxo proporcional máximo na rede [/img/revistas/pope/ v24n1/20103s14.gif] , isto é, uma solução do problema (6).

5. A Convergência do Algoritmo Na seção anterior introduzimos o esquema: majorante [/img/revistas/pope/v24n1/ 20103x36.gif] <formula/> nova majorante.

Admitiremos aqui que a seqüência mr é infinita (caso contrário, temos uma solução do problema original (6): a primeira possibilidade mencionada anteriormente), isto é, <formula/> decrescendo para um valor limite <formula/> é um fluxo proporcional máximo (a ser determinado). Mostraremos a seguir, de forma construtiva, que <formula/> = [/img/revistas/pope/ v24n1/20103s41.gif], isto é que <formula/>é o valor do fluxo proporcional ótimo.

Observe inicialmente que, nos arcos <formula/> e, nos arcos artificiais iniciais, <formula/> por construção, o mesmo ocorrendo com os terminais jD em [/img/revistas/pope/v24n1/ 20103s44.gif] (mesma observação, por default, daqui em diante).

A seqüência de extensões <formula/> associadas às majorantes <formula/>, converge para a extensão [/ img/revistas/pope/v24n1/20103s8.gif] associada à majorante [/img/revistas/pope/ v24n1/20103s10.gif]. De fato, nos arcos k, a capacidade ck é a mesma para todas as extensões, e nos arcos artificiais Oi, temos [/img/revistas/pope/v24n1/ 20103x43.gif] que converge (decrescentemente) para a i [/img/revistas/pope/ v24n1/20103s10.gif], que é a capacidade [/img/revistas/pope/v24n1/ 20103s74.gif]em <formula/>.

Note ainda que a seqüência dos fluxos <formula/> é limitada a um politopo P definido pelas desigualdades [/img/revistas/pope/ v24n1/20103x45.gif] e que, portanto, alguma subseqüência, que denotaremos por ys , da seqüência original yr converge (devido à compacidade de P). Seja [/img/ revistas/pope/v24n1/20103s9.gif] o limite de uma seqüência deste tipo, isto é, <formula/> Temos [/img/revistas/pope/v24n1/ 20103x47.gif] para os arcos k da rede original e [/img/revistas/pope/v24n1/ 20103x48.gif] para as origens i. De fato, como [/img/revistas/pope/v24n1/ 20103x49.gif](soma de componentes do vetor ys), basta passar a primeira expressão ao limite para obter a segunda. Por sua vez, das restrições de capacidade nos arcos <formula/> e nas origens [/ img/revistas/pope/v24n1/20103x51.gif]temos, no limite: [/img/revistas/pope/ v24n1/20103x52.gif] e <formula/>, isto é, [/img/ revistas/pope/v24n1/20103s9.gif] é um fluxo na rede capacitada[/img/revistas/ pope/v24n1/20103s8.gif].

Vale também a igualdade <formula/>, isto é, o valor do fluxo limite é o limite dos valores dos fluxos ys : basta observar que <formula/> (o mesmo valendo para [/img/revistas/ pope/v24n1/20103s9.gif]) e passar a expressão ao limite, como antes.

O vetor <formula/> é um fluxo proporcional em [/ img/revistas/pope/v24n1/20103x39.gif]: da desigualdade[/img/revistas/pope/ v24n1/20103x56.gif]<formula/> segue a igualdade das parcelas, <formula/>. Além disso, [/img/ revistas/pope/v24n1/20103s9.gif] é um fluxo máximo na rede[/img/revistas/pope/ v24n1/20103s8.gif]: os arcos artificiais Oi formam um corte C * com valor [/ img/revistas/pope/v24n1/20103x59.gif] = [/img/revistas/pope/v24n1/ 20103s50.gif], logo, pelo Teorema de Dualidade de Ford e Fulkerson, o fluxo [/ img/revistas/pope/v24n1/20103s9.gif] é máximo.

Finalmente, como <formula/> é proporcional e é também um fluxo máximo na rede estendida <formula/> associada à cota <formula/> = [/img/revistas/pope/ v24n1/20103s41.gif], <formula/> é um fluxo proporcional máximo na rede original <formula/>, com valor <formula/>.

Fica assim provado que, se o algoritmo descrito não fornecer uma solução ótima <formula/> em um número finito de passos, qualquer ponto limite da seqüência dos fluxos yr obtidos iterativamente no processo, é uma solução e que a seqüência decrescente de majorantes mr, gerada pelo algoritmo, converge para o valor ótimo, isto é, para o maior dos valores possíveis entre os fluxos proporcionais na rede [/img/revistas/pope/v24n1/ 20103s14.gif].

Lembramos aqui que as soluções y do problema de fluxo proporcional máximo e y do problema do evasor estão relacionadas por y = y/l onde e'y = 1/l (a mesma relação do esquema Washburn-Wood para a resolução do problema livre, isto é, sem cotas estabelecidas nas origens e destinos). Assim, se [/img/revistas/pope/ v24n1/20103s37.gif] é um fluxo proporcional máximo na rede [/img/revistas/pope/ v24n1/20103s14.gif] (capacitada por ck = 1/pk , arco a arco) com valor [/img/ revistas/pope/v24n1/20103s41.gif] e' <formula/> , então o valor do jogo de confronto (com probabilidades pk de detecção nos arcos) é <formula/> = [/img/revistas/pope/v24n1/ 20103x60.gif]e a estratégia ótima do evasor é [/img/revistas/pope/v24n1/ 20103x61.gif]

6. Um Exemplo de Implementação Ilustraremos agora a implementação do algoritmo da Seção 5 a uma rede simples <formula/>, representada abaixo, com 12 nós, mais origem e destino artificiais, aqui denotados por O e M, 17 arcos, mais 4 artificiais, e um total de 23 rotas ligando O e M.

Admitiremos aqui, que o problema de confronto evasor ´ detector já está na forma final (6), da Seção 4, isto é, de um problema de fluxo máximo proporcional. Assim, as capacidades arbitradas nos diversos arcos da Figura_1, e.g. c (AE) = 18 e c (FG) = 15, correspondem às probabilidades de detecção no problema original, p (AE) = 1/18 = 5,6% e p (FG) = 1/15 = 6,7%, percentuais aproximados, indicados entre parênteses. Arbitramos ainda as cotas a = (0,80 , 0,20) e b= (0,75 , 0,25) para as origens A e B e os destinos K e L, respectivamente.

Listados lexicograficamente, temos aqui os seguintes conjuntos (vide Seção 2): N = {A, B, ..., L} de 12 nós, K = {AC, AE, BC, ..., JL} de 17 arcos, E = {A, B, K, L} de 4 extremos e L, das 23 rotas, l1 = ACDEFGIJK, l2 = ACDEFGIJL, l3 = ACDEFK, ..., l23 = BHL. Correspondentemente, temos as matrizes [/img/revistas/ pope/v24n1/20103s29.gif] = diag (30, 18, 20, ..., 40) de capacidades e sua inversa <formula/> = diag (1/30, 1/18, 1/20, ..., 1/40) de probabilidades de detecção nos arcos (ordem 17), de incidência arco ´ rota <formula/>, com [/img/revistas/pope/v24n1/ 20103s30.gif]1,1 = 1 (o 1° arco está na 1ª rota),[/img/revistas/pope/v24n1/ 20103s30.gif] 17,23 = 0 (o arco JL não pertence à rota BLH), etc., e extremo ´ rota <formula/>, com [/img/revistas/pope/v24n1/ 20103s52.gif]1,1 = 1 (A Î l1), <formula/>3,23 = 0 (K Ï l23), etc. Temos ainda os símplices SL das estratégias (livres) do evasor, x = (x1, ..., x23) com xl ³ 0, <formula/> das estratégias do detector, y = (y1, ..., y17), onde [/img/revistas/pope/v24n1/ 20103x63.gif], das estratégias proporcionais do evasor, isto é, soluções do sistema <formula/>= a (sendo a = (0,80, 0,20, 0,75, 0,25)), que, pode-se mostrar, possui mais de 300 soluções básicas (isto é, T ³ 300), entre outras, <formula/> , onde [/ img/revistas/pope/v24n1/20103x66.gif], 0,05 ou 0,20 para as rotas l8 = AEFK, l10 = AEGIJL ou l23 = BHL, respectivamente, e [/img/revistas/pope/v24n1/ 20103x66.gif]= 0 , caso contrário, e <formula/>= 0,55 , 0,25 ou 0,20, para as rotas l1 = ACDEFGIJK, l10 = AEGIJL ou l21 = BHIJK, respectivamente e <formula/>= 0, caso contrário.

Os arcos artificiais, que receberiam normalmente as capacidades agregadas: c (OA) = 30 + 18 = 48, c(OB) = 20 + 6 + 34 = 60, c(KM) = 30 + 30 = 60 e c(LM) = 80 + 40 = 120, aqui receberam, no 1° passo do algoritmo, percentuais apropriados da cota superior inicial m0 = min {48/0,80 , 60/0,20 , 60/0,75 , 120/0,25} = min {60 , 300 , 80 , 480} = 60. Assim, c(OA) = 0,80 ´ m0 = 48, c (OB) = 0,20 ´ m0 = 12, c(KM) = 0,75 ´ m0 = 45 e c(LM) = 0,25 ´ m0 = 15, conforme indicado na Figura_1 e na 1ª coluna da Tabela_2, mais adiante. Esta é a nossa extensão inicial <formula/> da rede [/img/ revistas/pope/v24n1/20103s14.gif] original (sem origem e destino artificiais).

Na 1ª coluna da Tabela_1, a seguir, indicamos, arco a arco, o fluxo máximo [/ img/revistas/pope/v24n1/20103s54.gif] (ou melhor, sua versão-arcos) em [/img/ revistas/pope/v24n1/20103s55.gif], com valor [/img/revistas/pope/v24n1/ 20103s56.gif], o qual aparece na última linha. Isto encerra o 1° passo na implantação do algoritmo.

Observe que OB, EF e EG (com asteriscos na tabela) formam um corte de [/img/ revistas/pope/v24n1/20103s57.gif] com valor c(OB) + c(EF) + c(EG) = 12 + 6 + 2 = 20, coincidente com o valor do fluxo y0 , o que comprova a maximilidade em [/ img/revistas/pope/v24n1/20103s14.gif]0. Temos assim uma nova cota superior m1 = 20 da solução proporcional ótima, e com ela iniciamos o 2° passo do algoritmo.

Agora, c (AO) = 0,8 m1 = 16, c (OB) = 0,2.m1 = 4, etc, valores figurando na 2ª coluna da Tabela_2. Nesta nova extensão <formula/> resolvendo o problema do fluxo máximo, obtemos uma solução (indicada na 2ª coluna da Tabela_1) com valor 12 que serve agora como nova cota superior m2 , utilizada para iniciar a 3ª iteração, e assim por diante. O processo foi levado até a 5ª iteração e os resultados indicados nas Tabelas_1 (fluxos máximos) e 2 (cotas sucessivas m e as capacidades dos arcos artificiais nas diversas extensões <formula/>).

Na última coluna da Tabela_1, aparece uma solução ótima [/img/revistas/pope/ v24n1/20103s37.gif], isto é, um fluxo proporcional máximo em [/img/revistas/ pope/v24n1/20103s14.gif] (descrito em termos de arcos). De fato, como toda rota originando em A passa por um dos arcos EF e EG, com capacidade agregada 6 + 2 = 8, qualquer fluxo y na rede tem no máximo este valor associado ao nó A (y (A) £ 8, na notação da Seção 2). Se y for proporcional, seu valor v(y) é no máximo 8/ 0,80 = 10, o valor do fluxo (proporcional) em questão. No nosso exemplo, bastante simples, é possível mostrar a relação mr+1 = 8 + 0,2 mr , entre as cotas sucessivas mr e então, passando ao limite quando r ® ¥ , temos que m * = 8 + 0,2 m *, isto é, m* = 10, uma confirmação alternativa da otimalidade. Vale a pena observar que aqui não podemos usar a dualidade fluxo máximo-corte mínimo (o corte de menor valor na rede <formula/> tem valor 20, igual ao do fluxo máximo y0) pois a maximalidade aqui é restrita aos fluxos proporcionais e não livre.

Na última coluna da Tabela_2, indicamos os valores iniciais m5 e das capacidades nos arcos artificiais da rede [/img/revistas/pope/v24n1/ 20103s61.gif] que seriam utilizados na 6ª iteração. Sua proximidade, respectivamente, dos valores m*, 0,80m*, 0,20m*, 0,75m* e 0,25m* destacam quão próximos da proporcionalidade desejada estamos. Por sua vez, os fluxos sucessivos na Tabela_1 indicam o grau de aproximação da solução ótima, arco a arco.

Observe que a Tabela_1 especifica, na realidade, os sucessivos fluxos máximos em termos dos arcos da rede (e não das rotas, o que nos interessa na busca da estratégia ótima de evasão).

A relação <formula/>(Seção 2) tem inversa multívoca; é possível, ainda que em princípio computacionalmente oneroso, recuperar uma das inversas <formula/> (versão- rotas do fluxo) associadas a um dado <formula/> (versão-arcos). É importante notar no entanto, que o algoritmo de Ford e Fulkerson (e variantes), utilizado no cálculo de [/img/revistas/pope/v24n1/ 20103s65.gif], baseia-se na obtenção, passo a passo, dos chamados percursos de aumento (ver e.g. Boaventura Netto, 1996) e portanto fornece automaticamente um conjunto de fluxos elementares, isto é, de fluxos individuais yl ao longo de diferentes rotas l Î L um vetor <formula/>, com fluxos nos extremos satisfazendo as cotas estipuladas [/img/revistas/pope/ v24n1/20103s67.gif] o mesmo para os destinos j) isto é, proporcionais, de valor agregado <formula/> máximo, portanto, uma solução da versão (6) do problema do evasor, da qual se obtém diretamente a solução do problema original (vide Seção 2).