PO - 08/11/2012

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

  Na próxima aula estaremos falando da biblioteca que utilizaremos no tp.
  // A biblioteca se chama GLPK e é escrita na linguagem C.

  O tp terá como foco a materia de "decomposição de Dantzig Wolf".

  (nota Dantzig Wolf, cai na segunda prova)

  // Estude essa materia até a prox aula 13/11, pois ajudará a compreender o tp

  O TP é portanto resolver o problema de corte de chapas (otimização inteira)
  utilizando a biblioteca GLPK em C.

  (nota solta: o professor segue mais ou menos o livro do Dimitris Bertsimas)

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

  Problema do Fluxo Máximo. (maxFlow)

  A entrada é uma rede D formada com vertices V e arcos A

  Existem dois vertices especiais de V: s - flux Source(origem), e t - flux Target(destino).

  Os arcos são limitados pela capacidade cij que é o limite de fluxo que pode passar por eles.
  // Note que isso é a capacidade e não o custo.

  Objetivo:
  Encontrar o máximo fluxo que pode ser enviado da origem s à t respeitando as capacidades dos arcos.

  Variáveis de decisão:

    xij = quantidade de fluxo que efetivamente passa pelo arco (i,j).

  Restrições:

    (I) xij >= 0 e xij <= cij

  A última restrição é a de balanço de fluxo.

  Cada nó intermediario (todos exceto s e t) tem de dar saída a tudo que recebem de entrada:

  // Lembrando:
  // ð*(i) = conjunto de arcos que partem de i.
  // ð°(i) = conjunto de arcos que chegam em i.

  Então:

    (II) sum (j,i)€ð°(i) xji - sum (i,j)€ð*(i) = 0 para todo i
         // Somatório do que entra - o que saí = 0.

  Agora vamos supor um arco artificial (t,s) indo do destino para origem.

  Vamos portanto assumir que tudo que chega em t, volta para s por este arco.
  Logo o fluxo nesse arco é o fluxo em todo o sistema.

  A capacidade desse arco deve ser a maior possível.
  Consideremos a maior possível a soma de todas as capacidades dos demais arcos.

  Dessa forma fica fácil definir nosso objetivo.

    max xts  = min -xts

  // onde xts é o fluxo de t para s.

  Com isso nosso problema se torna um problema de fluxo de custo mínimo.

  Outra vantagem muito interessante desse arco é que a lei de balanço se aplica também para s e t.
  Já que eles também estão passando pra frente tudo que recebem.

CONCEITOS:
  Vetor de fluxo x:

  É uma solução viável que satisfaz as duas restrições (I) e (II)

CONCEITO:
  Capacidade residual é a capacidade que um arco tem de desfazer um fluxo.
  Representa-se isso com um arco artificial no sentido oposto, para indicar isso.

    Ex: há fluxo em (i,j) de 3 unidades.
        A capacidade residual de (i,j) diminui em 3 unidades.
        A capacidade residual de (j,i) aumenta em 3 unidades, se o arco j,i não existia antes, cria-se um.

CONCEITO:
  Um caminho residual é o caminho construído somente com os arcos cuja capacidade residual != 0.
  (ou seja arcos onde ainda pode-se passar fluxo, ou deixar de passar fluxo contrário)
  (inicialmente, o grafo de caminhos residuais é igual ao grafo original)

  Se existe um caminho residual entre s e t logo voce não está na solução ótima.

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

  Agora que já definimos o problema de fluxo máximo, vamos explicar um algoritmo para resolve-lo:

  Algoritmo de Ford Fuckerson - Algoritmo de Caminhos Aumentados:

  a) Dado um vetor de fluxo x, construa a rede residual associada a x.

  b) Encontre um caminho na rede residual que conecte origem s ao destino t.

    Caso 1:
    Existe um caminho.
    Então: Ð (delta maiusculo) = capacidade do arco de menor capacidade residual neste caminho.

    Aumente essa capacidade alongo de todos os arcos deste caminho. Obtendo um novo vetor de fluxo.

    Isso significa que o fluxo máximo agora cresceu em Ð unidades.

    Caso 2:
    Não existe um caminho.
    Então voce já está no fluxo máximo.

  Teorema: Se não há caminho de aumento para o vetor de fluxo x. Então o vetor atual é ótimo.

  O algoritmo é portanto simples (o dificil é entender a tal da rede residual =P).

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

  Exemplo:

  Grafo Original:
    Arestas:     (O,A), (O,B), (O,C), (A,B), (A,D), (B,C), (B,D), (B,E), (C,E), (D,T), (E,D), (E,T)
    Capacidades:   5      7      4      1      3      2      4      5      4      9      1      6

  Vamos partir do vetor de fluxo zerado, onde não há fluxo algum.

  O primeiro passo é encontrar um caminho entre O e T, e então aumentar o fluxo por ele tanto quando possível.

  Vamos achar esse caminho com Busca em largura:
  Lista L = {O}
  (O = origem, mudamos o nome de s para O =P)

  Vamos investigar recursivamente:

  O lado esquerdo contém os vertices sendo explorados,
  o direito contém os vertices inexplorados que já são alcançados pelos vertices explorados.

     |  {O}
  O  |  {A,B,C}
  A  |  {B,C,D}
  B  |  {C,D,E}
  C  |  {D,E}
  D  |  {E,T}
  T
// Note que o vertice E nem chegou a ser investigado.
// Pois já encontramos um caminho investigando D.

  Pronto encontramos o nosso primeiro caminho até T.
  O caminho passa por: {O,A,D,T}

  Observando nosso caminho o menor arco residual tem capacidade 3 (fica mais fácil entender desenhando).

  logo:

  Na primeira busca encontramos um Ð de 3.

  Vamos incrementar todos os elementos nesse caminho de 3 unidades.

  Note que agora a nossa rede residual, que mostra só as capacidades residuais, perdeu o arco (A,D)
  E ganhou 3 arcos no sentidos: (T,D), (D,A), (A,O).
  Todos os 3 tem capacidade 3.

  Grafo Residual:
    Arestas:     (O,A), (O,B), (O,C), (A,O), (A,B), (B,C), (B,D), (B,E), (C,E), (D,A), (D,T), (E,D), (E,T), (T,D)
    Capacidades:   5      7      4      3      1      2      4      5      4      3      9      1      6      3

  Note que é importante isso de que sempre existe um caminho residual contrário ao sentido de qualquer fluxo.

  Isso permite que sempre exista um caminho entre O e T mesmo depois de exaurirmos a maior parte dos arcos, pois podemos desfazer um arco.

  Segunda iteração: vamos investigar um novo caminho:

     |  {O}
  O  |  {A,B,C}
  A  |  {B,C}
  B  |  {C,D,E}
  C  |  {D,E}
  D  |  {E,T}
  T

  Segundo caminho encontrado: {O,B,D,T) onde a menor capacidade residual é Ð=4.

  Vamos atualizar nossa rede residual com um novo fluxo de 4 unidades no sentido desse caminho.
  Isso gera uma rede contrária

  // Note que o segundo caminho surgiu devido a inexitencia do arco residual (A,D)

     |  {O}
  O  |  {A,B,C}
  A  |  {B,C}
  B  |  {C,E}
  C  |  {E}
  E  |  {D,T}
  T

  Novo caminho: {O,B,E,T}
  A menor capacidade residual é do arco: (O,B) com Ð=3

  Incrementamos o fluxo em todo nosso caminho em 3 unidades.

  Nova iteração:

     |  {O}
  O  |  {A,C}
  A  |  {B,C}
  B  |  {C,E}
  C  |  {B,E}
  B  |  {E,C}
  E  |  {C,D,T}
  T

  Novo caminho: {O,C,E,T} com Ð = 3 em (E,T)

  Nova iteração:

     |  {O}
  O  |  {A,C}
  A  |  {B,C}
  C  |  {B,E}
  B  |  {E}
  E  |  {D}
  D  |  {T}
  T

  Novo caminho: {O,C,E,D,T}

  Ð = 1 em 3 arcos: (O,C), (C,E), (E,D)

  Aumentamos o fluxo nestes 3 arcos.

     |  {O}
  O  |  {A}
  A  |  {B}
  B  |  {C,E}
  C  |  {E}
  E  |

  Não encontramos mais um caminho pela rede residual.
  Logo estamos no ótimo e o nosso vetor de fluxo está no estado ótimo.

  O último caminho que encontramos foi o {O,A,B,C,E}
  Os que não encontramos foram: {D,T}

  Os arcos que estão no corte entre o primeiro grupo e o segundo somados dão 14.

  Esse é o valor do nosso corte mínimo (que é um outro problema).

  O problema do corte mínimo portanto pode ser obtido como solução extra do problema do fluxo máximo.
  Interessante não?
  Um é o dual do outro =].

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

  // E o dual desse problema é outro problema interessante:
  Problema do Corte Mínimo em Rede

  Mas vamos falar de tudo isso nas próximas aulas.

  // fim da aula!