Home   |   Structure   |   Research   |   Resources   |   Members   |   Training   |   Activities   |   Contact

EN | PT

BrBRCEEn0101-74382004000100009

BrBRCEEn0101-74382004000100009

National varietyBr
Country of publicationBR
SchoolEx-Tech-Multi Sciences
Great areaEngineering
ISSN0101-7438
Year2004
Issue0001
Article number00009

Javascript seems to be turned off, or there was a communication error. Turn on Javascript for more display options.

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 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 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 SK , <formula/> e o somatório é duplo: sobre todos os pares k Î K, L, para os quais 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 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 ´ 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 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 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 arco está na 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 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 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 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 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 passo do algoritmo.

Agora, c (AO) = 0,8 m1 = 16, c (OB) = 0,2.m1 = 4, etc, valores figurando na coluna da Tabela_2. Nesta nova extensão <formula/> resolvendo o problema do fluxo máximo, obtemos uma solução (indicada na coluna da Tabela_1) com valor 12 que serve agora como nova cota superior m2 , utilizada para iniciar a iteração, e assim por diante. O processo foi levado até a 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 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 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).

No nosso exemplo numérico, o algoritmo de Ford e Fulkerson aplicado à rede [/ img/revistas/pope/v24n1/20103s69.gif] fornece os seguintes fluxos elementares yl = 6 , 2 , 1,496 e 0,520 para as rotas l8 = AEFK, l10 = AEGIJL, l22 = BHIJL e l23 = BHL, respectivamente (yl = 0 para as outras rotas) com valor total v(y) = 10,016 , indicado na Tabela_1. A solução y do problema do evasor é obtida por "normalização" do vetor y: y = y/ (v(y)) isto é, sua estratégia ótima no confronto é utilizar (apenas) as rotas indicadas acima, com freqüências y8 = 6/ 10,016 = 0,5990, y10 = 0,1997, y22 = 0,1494 e y23 = 0,0519, respectivamente (60, 20, 15 e 5 pontos percentuais). O valor do jogo a probabilidade média de detecção (admitida a racionalidade dos jogadores) é 1/ v(y) = 0,0998 ou seja, 10%.

7. Testes Numéricos Descrevemos a seguir experimentos computacionais com o algoritmo proposto, na resolução de um problema de confronto com cotas, numa rede [/img/revistas/pope/ v24n1/20103s14.gif] de porte médio não trivial, mas estruturalmente simples, topológica e probabilisticamente, utilizada na literatura recente para testes em confrontos não-cotados (Sinotti, 2000 e, em dimensões inferiores, Cormican et al., 1988). Admitiremos sempre que os problemas tenham sido reformulados em termos de fluxos proporcionais máximos em essência, que geramos diretamente em cada simulação as capacidades [/img/revistas/pope/v24n1/ 20103x67.gif]nos diversos arcos (<formula/> sendo portanto as probabilidades de detecção [/img/revistas/pope/v24n1/ 20103x69.gif]nos problemas de confronto originais).

A estrutura básica utilizada foi de uma malha retangular plana [/img/revistas/ pope/v24n1/20103s14.gif] , 10 ´ 11 (linhas e colunas), com 3 origens (posições 1, 8 e 11 da coluna 1) e 4 destinos (coluna 11, posições 1, 4, 8 e 11), gerando um total de 112 nós (dois artificiais: O e D) e 206 arcos orientados verticalmente ao longo das colunas de modo aleatório, com p (-) = p (¯) = 0,50 (sentidos equiprováveis, exceto, é claro, no caso de arcos iniciais e terminais) e horizontalmente, no sentido do artificial terminal D.

Os parâmetros utilizados nas 16 simulações realizadas foram a = (0,50 , 0,35 , 0,15) para a distribuição de freqüências nas origens l, b = (0,40 , 0,30 , 0,20 , 0,10) nos destinos (as freqüências de uso dos extremos pelo evasor, no confronto original), e, essencialmente, os valores 8, 10, 15, e 50, para as capacidades dos arcos da rede, com exceção dos arcos iniciais (originando em I) e terminais (atingindo J), a maioria dos quais recebeu capacidades mais altas (24, 40 , 50 , 75 e 120). A tabela abaixo ilustra os resultados obtidos.

A atribuição de valores, k ® c k = 8, 10, 15 ou 50, isto é, a geração do vetor c foi feita aleatoriamente, arco a arco, simulação a simulação, segundo a distribuição (0,15 , 0,35 , 0,35 , 0,15). A escolha dos valores c k e das freqüências utilizadas em sua geração, ainda que arbitrárias, procurou sugerir situações plausíveis de chances mais altas, baixas ou médias de detecção ao longo da rede, neste caso, percentuais aproximados de 12,5, 10, 7 e 2, respectivamente (lembramos que <formula/>=[/img/ revistas/pope/v24n1/20103x68.gif]). Os valores mais altos atribuídos aos extremos visaram afastar casos computacionalmente simples (permitindo, em princípio, uma maior diversidade de fluxos através da rede).

O arco de retorno, de D para O, e os artificiais Oi e jD ( I, j Î D) são inicialmente capacitados com c = 9.999.999 (um número "suficientemente" alto).

Lembramos que o algoritmo modifica passo a passo as capacidades nos arcos artificiais, isto é, a extensão <formula/> da rede original <formula/>.

A resolução numérica do problema utilizou o módulo OR (Operations Research) do software SAS System, versão 8.00, através da procedure NETFLOW e foi implementada num PC Intel Pentium 4 (1.400 Mhz, 128.0 MB RAM). A geração pseudo-randômica das orientações verticais e das capacidades nos arcos interiores de <formula/> foi feita automaticamente pelo programa. Uma sub-rotina auxiliar foi implementada no próprio módulo OR do SAS, como macro destinada a atualizar iterativamente as capacidades nos arcos artificiais. Estabelecemos 19 com limite para o número de iterações em cada simulação para poder observar o comportamento das sucessivas soluções aproximadas: valor do fluxo máximo, correções de proporcionalidade, rotas, cortes, etc, passo a passo. Fixamos ainda o valor e = 0,00001 como nível da precisão desejada que, uma vez atingida (fluxos sucessivos com valores [/img/ revistas/pope/v24n1/20103x70.gif], interrompia a execução da simulação em curso.

Como ilustração, descreveremos a seguir o comportamento computacional e os resultados observados na 16ª simulação: (1) A rede resultante envolve cerca de 58.000 rotas entre O e M e, portanto, cerca de 12 milhões de combinações (l, k) possíveis, isto é, pares de estratégias puras do evasor (a escolha da rota de fuga l) e do detector (o local de patrulha). Quanto às mistas (x, y), é claro, apenas um subconjunto "reduzido", S K x [/img/revistas/pope/ v24n1/20103s28.gif] , do produto S K x[/img/revistas/pope/v24n1/ 20103s28.gif] , respeita as cotas estabelecidas a = (a ' , b ').

(2) Em linhas gerais, para um valor ótimo de [/img/revistas/pope/ v24n1/20103s41.gif]= 68 , os erros relativos observados, [/img/ revistas/pope/v24n1/20103x71.gif] foram inferiores a 1% na iteração e a 0,01% na 12ª iteração, atingido o nível de precisão estabelecido, e = 0,001%, apenas no 15º passo.

(3) Comportamento semelhante ocorreu com os fluxos individuais nos extremos, o principal indicador do grau de aproximação à proporcionalidade desejada.

(4) Do total de 206 arcos da rede, apenas 56% são ativados (têm fluxos não-nulos) na iteração, dos quais apenas 80% se mantêm ativos da iteração em diante, o mesmo se aplicando portanto às rotas associadas, para uso ótimo do evasor no jogo original. Os arcos mantidos após a iteração foram observados se agrupar em 12 classes distintas e os fluxos em cada uma delas são idênticos, arco a arco, indicando assim o total máximo de 12 trajetórias após a síntese [/ img/revistas/pope/v24n1/20103x72.gif](vide Seção 2). Lembramos aqui que a representação <formula/>é suficiente para descrever a estratégia ótima do evasor que (alternativamente à recuperação das rotas a partir dos fluxos nos arcos) pode ser explicitada em termos estocásticos, a , ao longo da rede (ver e.g., Sinotti, 2000).

(5) O tempo total de CPU gasto nesta simulação foi comparativamente alto, de 4,2 seg., devido à listagem, neste caso, de resultados intermediários, arco a arco, iteração por iteração, por parte do SAS.

8. Conclusões O algoritmo proposto, baseado na delimitação forçada, sucessiva, de fluxos máximos em extensões apropriadas da rede [/img/revistas/pope/v24n1/ 20103s14.gif], resolve o problema do evasor em redes com múltiplas origens e destinos cotados. O resultado teórico é exato no sentido de que (1) se o procedimento para, temos a solução ótima desejada, (2) caso contrário, prossegue monotonicamente, isto é, com melhoramentos sucessivos na direção do ótimo.

Conforme ressaltado, a técnica contorna o sério problema da determinação prévia do conjunto L de todas as rotas na rede e do cálculo dos pontos extremos do politopo <formula/>, ambas tarefas problemáticas do ponto de vista computacional, dadas as cardinalidades e dimensões envolvidas, mesmo em problemas de porte reduzido, no que se refere a nós e arcos veja e.g., a discussão (após a Figura_1) do exemplo numérico de baixa dimensão resolvido na Seção 6. Vale ressaltar que, embora os resultados da Seção 5 permitam reformular (6) em termos dos arcos da rede, isto é, a versão- arcos <formula/> do fluxo y (vide Seção 2), envolvendo a matriz de incidência ´ arco, e não a matriz arco ´ rota [/img/ revistas/pope/v24n1/20103s30.gif] (mais as condições lineares sobre os extremos da rede), possibilitando portanto a resolução direta, pelo Método Simplex digamos (ver e.g., Gass, 1996), restaria ainda o problema, computacionalmente árduo da síntese em termos de rotas: obter, a partir do solução ótima [/img/ revistas/pope/v24n1/20103s70.gif], o fluxo ótimo [/img/revistas/pope/v24n1/ 20103s37.gif], do qual se extrairia, por normalização, a estratégia ótima de evasão <formula/>.

Quanto ao desempenho numérico do esquema iterativo proposto na Seção 4, baseado no algoritmo de Ford e Fulkerson, acreditamos que os resultados observados nas simulações efetuadas com a rede de porte médio escolhida, apesar da limitação e do caráter preliminar do experimento, apontam na direção de comprovar a eficiência computacional esperada do algoritmo.

Linhas naturais para investigação no problema evasor ´ detector aqui relatado (algumas delas ativadas) incluem, entre outras: (1) Validação empírica, estatística, mediante simulações mais extensas e problemas de ainda maior porte, da qualidade do método.

(2) A implementação do algoritmo em estruturas topológicas distintas, como em Steinrauf (1991) (diagrama simplificado de bacia fluvial na fronteira Brasil-Bolívia, grande escoadouro de insumos, isto é, precursores químicos, e produtos da coca) e Lima & Muniz (2002) (uma estrutura radial, sugerindo níveis sucessivos de distribuição no tráfico urbano, com cinco níveis, 64 nós, mais de 150 arcos e 2.200 rotas).

(3) A busca de limites teóricos nas taxas de aproximação, visando formular regras de parada, avaliação de erros e questões de complexidade computacional.

(4) A possível recuperação da solução (ainda que aproximada) do problema primal, do detector, diretamente a partir da resolução do problema do fluxo proporcional máximo, associado ao evasor.

(5) A questão do uso de funções alternativas de avaliação (pay-off) no confronto, em particular a referente ao arrependimento máximo dos jogadores, ver Machado & Sinotti (2002) (no presente trabalho utilizamos a probabilidade média de detecção, g(x, y) como valor do jogo).

(6) Variantes do problema básico de confronto, como em Hohzaki & Iida (1996), que discutem estratégias de busca arco a arco, ao longo de uma rota de percurso pré-fixada pelo detector (uma rota de detecção), levando em consideração a troca custo ´ benefício (agregados) das eventuais inspeções locais, a possibilidade de utilizar recursos distintos na interceptação do evasor, digamos múltiplas unidades na inspeção simultânea em diferentes arcos da rede, como em Washburn & Wood (1995); mais geralmente, de recursos escassos diversos, a serem utilizados de modo independente, ao longo de <formula/>, como sugerido por Israeli (1999) (a probabilidade de detecção e.g., poderia depender da combinação local dos recursos); questões de vulnerabilidade em redes como em Mehdi (1994), Grötschel et al.

(1998) e Bell (2003); modelos envolvendo incerteza, informação parcial, dinâmica temporal, estocacidade, etc.


Download text