PO - 20/11/2012

   # # # # # # # # # # # # #
  # Pesquisa Operacional    #
  # Prof. Alexandre Cunha   #
  # notasdogarcia.blog.com  #
   # # # # # # # # # # # # #

  Sobre a documentação do tp:

  O que salvar de cada instancia do TP:

    Instancias | Solução ótima | NCols | tempo(s) | tempo de precificação em percentual do total.

  Rode várias instancias e gere uma tabela.

  Isso basta como documentação.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Vamos voltar a falar do

  Fluxo Máximo de Ford e Fulkerson

  a) Dado um vetor de fluxo X, determine a rede residual associada à X
     e procure um caminho (direcionado) entre a origem s e o destino de fluxo t.

  Possibilidades:

  1 ) Não existe caminho na rede residual que resolve o problema do fluxo máximo.
      Pare, o problema está resolvido.

  2 ) Existe um caminho então:
      Determine a capacidade máxima do caminho (o MIN das capacidades residuais deste caminho),
      chamemos ela de Ð

      Agora aumente o fluxo ao longo do caminho em Ð unidades de fluxo.
      Obtendo um novo X que é o vetor de fluxo.
      Atualize a Rede Residual.

      Repita tudo.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  Vamos focar nossa aula especificamente na etapa A.
  Na parte onde procuramos um caminho entre s e t.

  Existem diversas formas de pesquisar por estes caminhos e cada forma acaba implicando em um algortimo com características diferentes.

  Vamos estudar o algoritmo de Dinic que é um dos mais eficientes.

REVISÃO:
  O professor desenhou no quadro o que significa as capacidades residuais com base em um vetor de fluxo.

  Dado o grafo:

  Arestas: (s,1), (c,2), (2,1), (1,t), (2,t)
  Capacid:   C      C      1      C      C

  O professor mostrou um caso em que nós acabamos explorando um número de caminhos muito maior do que o necessário.

  O Algoritmo de Dinic evetaria esse excesso de exploração de caminhos.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Algoritmo de Fluxo Máximo de Dinic (cuja única diferença é a etapa de busca de caminhos):

  - É um algoritmo de caminhos de aumento.
  - Opera também sobre um vetor de fluxo, construindo a rede residual.
  - Difere de FF (Ford Fuckerson) pelo modo como os caminhos de aumento são encontrados.
    Gera caminhos de aumento de fluxo que empreguem número mínimo de arcos na rede residual.

  Em outras palavras esse algoritmo faz uma busca em largura.
  E detecta vários caminhos com o número de arcos igual à iteração por vez.

  Assim teremos vários caminhos de aumento.

  Usaremos "labels" associados aos vertices:
    - k(t) = 0
    - k(i): Representa o número mínimo de arcos em algum caminho de i a t.
  // Repare que vamos caminhar de t para s, ou seja do destino para a origem.

  Assim a cada iteração o que acontece é o seguinte:
    Voce faz uma busca em profundidade (num era em largura?) até encontrar os menores caminhos possíveis.
    (menores em número de arcos)

  Usa eles para atualizar seu vetor X e sua rede residual.

  Repita o algoritimo agora a distancia mínima em número de arcos deverá ser maior que a anterior.

  Repetindo esse processo chegara um ponto onde a distancia é infinita indicando o critério de parada do algoritmo.

  - - - - -

  Determinar os labels K(i) : i € V
  determinamos os arcos que podem participar de caminhos de aumento:

  | K(i) | K(j) |        |  K=0  |
  |      |      |        |       |
  |      |      |        |       |
  |      |      |        |       |

  Consideramos dois tipos de arco:

  // Os fluxos "reais" por assim dizer
  (i,j): k(i) = k(j) + 1    xij < cij

  // Os fluxos mais "residuais" por assim dizer, gerados ao reduzir o fluxo por um caminho.
  (i,j): k(i) + 1 = k(j)  xij > 0

  // Nota FF não funciona com valores não-reais. (pode não convergir, mas até que funciona)
  // Esse funciona.
  // Esse também é mais eficiente.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  Exemplo:

  Seja o grafo:

  // Notação para os Arcos:
  // AB#: A - vertice de origem do arco
  //      B - Vertice de destino do arco
  //      # - Capacidade do arco)

  oa5, ob7, oc4,
  ab1, ad3,
  bd4, be5,
  cb2, ce4,
  dt9,
  ed1, et6

  Inicialmente temos o vetor de fluxo 0.

  Rede residual inicial:

  ... é identico ao grafo original:

  oa5  , ob7  , oc4 ,
  ab1  , ad3  ,
  bd4  , be5  ,
  cb2  , ce4  ,
  dt9  ,
  ed1  , et6  ,

  (para indicar caminhos de volta vou usar uma barra ex: oa4/1)

  // Lembrando estamos caminhando de t para o
  |  k=3   |  k=2  |  k=1   |  k=0  |
  |   o    | a b c |  d e   |   t   |

  Pronto, encontramos os caminhos mínimos (em numero de arcos) até O.

  Vamos desenhar os arcos minimais:

  |        |       |        |       |
  |  oa5   |  ad3  |  dt9   |       |
  |  ob7   |  bd4  |  et6   |       |
  |  oc4   |  be5  |        |       |
  |        |  ce4  |        |       |
  |        |       |        |       |

  Então notem que chegamos em O por vários caminhos:

    oa5 - ad3 - dt9 -> oadt
    ob7 - bd4 - dt9 -> obdt
    ob7 - be5 - et6 -> obet
    oc4 - ce4 - et6 -> ocet

  Ou seja encontramos todos os caminhos que chegam de t à o em 3 arcos.
  Por isso chamamos de "arcos minimais" os arcos que fazem parte de um caminho mínimo em numero de arcos.

  Vamos pegar um caminho destes:

  oadt Ð=3 (Lembrando que Ð é o fluxo máximo que se pode passar por esse caminho)

    Aumento o fluxo pelo caminho.

  obdt Ð=4

    Aumento o fluxo pelo caminho (lembre de considerar os fluxos anteriores)

  ocet Ð=4

    Aumento o fluxo pelo caminho (senão voce pode ultrapassar a capacidade de algum arco)

  obet Ð=2

    Aumento o fluxo pelo caminho

  Fim de uma iteração do método.

  Agora atualizo meu vetor de fluxo.
  E atualizo minha rede residual:

  oa2/3 ob1/6 oc0/4
  ab1   ad0/3
  bd0/4 be3/2
  cb2   ce0/4
  dt2/7
  ed1   et0/6

  // Note que as capacidades diminuiram, algumas chegaram à 0.
  // E ao mesmo tempo surgiram numeros após a barra que indicam a capacidade de desfazer o fluxo naquela direção.
  // E que podem ser pensados como arestas no sentido oposto, ou esja et0/6 é igual à: et0 e te6

  Nova busca em largura:

  | k=4  |  k=3   |  k=2  |  k=1   |  k=0  |
  |  o   |   b    |   e   |   d    |   t   |

  Agora os arcos mínimos:

  |  ob  |   be   |   ed  |   dt   |       |

  Achamos só um camiho com k=4:

    ob - be - ed - dt -> obedt

  Caminho:

  obedt Ð=1

    Atualiza rede mínima.

  Fim da segunda iteração.
  Atualiza vetor de fluxo e rede residual:

  oa2/3 ob0/7 oc0/4
  ab1   ad0/3
  bd0/4 be2/3
  cb2   ce0/4
  dt1/8
  ed0/1 et0/6

  Vamos buscar os arcos mínimos:

  |  k=1  |  k=0  |
  |   d   |   t   |

  E só.
  Logo não é mais possível alcançar a origem a partir do destino.
  E assim nosso algoritmo alcançou o estado ótimo.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  Agora vamos fazer uma brincadeira.
  Vamos pegar todos os arcos do nosso vetor de fluxo que chegam em d ou t.

  et0/6
  ed0/1
  ad0/3
  bd0/4

  Vamos somar seus fluxos: 6+1+3+4 = 14

  Esse é o fluxo máximo.

  E o conjunto d t é o nosso conjunto de corte mínimo.

  Esse é um resultado muito importante.
  Pois conhecendo o corte mínimo fica fácil calcular um limite máximo de fluxo aceitável para a rede.

  E outra coisa interessante é que esta conclusão é gerada pelo problema dual.
  Ou seja: o dual do fluxo máximo = corte mínimo.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  // Fim da aula!