PO - 30/10/2012

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

  Problema do transporte.

  É um caso particular do problema do transbordo onde
  todo vertice ou é demandante, ou é ofertante.
  Não há meio termo.

  Definição do problema:

  É um problema onde nenhum vertice é ofertante e demandante ao mesmo tempo.

  Então eu tenho um conjunto "of" de vertices que fornecem material para
  um conjunto "dm" de vertices demandantes.

  Cada vertice fornecedor é equilibrado e portanto ele oferece tudo o que ele tem mesmo que exceda a demanda.

  Nosso objetivo então é:

  //
  // Notação:
  // Oi = oferta de i
  // Dj = demanda de j
  // xij = fluxo pelo vertice ij
  //

    min sum (i€of, j€dm) cij xij

    sum(j=1,n) xij = Oi, para todo i€of
    sum(i=1,m) xij = Dj, para todo j€dm

    xij >= 0

  // Em outras palavras:
  // Minimizar o somatorio de "fluxo × custo" das arestas.
  // Garantindo que todo vertice ceda exatamente o tanto que oferta.
  // e que todo vertice receba exatamente o tanto que demanda.

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

  Vamos começar um exemplo:

  O grafo exemplo possuí 3 ofertantes e 4 demandantes.
  Existem arestas entre todos eles com os seguintes custos:

    of/dm  |   1   |   2   |   3   |   4   |
      1    |   2   |   3   |  11   |   7   |
      2    |   1   |   0   |   6   |   1   |
      3    |   5   |   8   |  15   |   9   |

  Ofertas:             Demandas:
   (of1) oferece 6      (dm1) demanda 7
   (of2) oferece 1      (dm2) demanda 5
   (of3) oferece 10     (dm3) demanda 3
                        (dm4) demanda 2

  Note que "sum ofertas = sum demandas"

  A sol. viável inicial proposta pelo professor foi:

  (of1)---6---->(dm1)

  (of2)---1---->(dm2)

  (of3)---1---->(dm1)
          4---->(dm2)
          3---->(dm3)
          2---->(dm4)

  Expressando isso em forma de tabela temos:

    of/dm  |   1   |   2   |   3   |   4   |
      1    |2) 6   |3)     |11)    |7)     |
      2    |1)     |0) 1   |6)     |1)     |
      3    |5) 1   |8) 4   |15) 3  |9) 2   |

  Onde o valor entre parentesis é o custo, e o outro valor é o fluxo.

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

  Vamos especializar o Simplex para o problema do transporte.

  Vamos assumir que Dispomos de uma sol. Viável Inicial para o problema.

  Passos básicos:

  1) Det. Custos Reduzidos das variáveis não básicas.
  2) Pivoteamento.

  Lembrando o prob. Original era:

    min sum (i€of, j€dm) cij xij

    sum(j=1,n) xij = Oi, para todo i€of
    sum(i=1,m) xij = Dj, para todo j€dm

  Vamos escrever o dual desse problema nas variáveis Vi e Wj (i€of, j€dm):

    max sum(i=1,m) Oi Vi  + sum(j=1,n) Dj Wj

    Vi + Wj <= cij, onde (i,j) € A ( ou seja (i,j) com "i € of" e "j € dm" )

    Vi e Wj são variáveis ilimitadas (negativas ou positivas tanto faiz)

  Seja B o conjunto de arcos que formam a solução básica atual.

     (1) cij - Vi - Wj = 0, (i,j) € B
  // A equação acima é uma versão justa das restrições do dual.
  // Ela vai ser verdadeira para toda variável básica.
  // (Ela vale para as variáveis básicas por causa do Teorema das Folgas Complementares)
  // (a restrição ser justa implica que Fij = 0 logo, a variável primal associada deve ser básica)
  // (Lembrando o Teorema das F. C. diz que: Fij * xij = 0, ou seja um deles deve ser 0 sempre)
         _
     (2) Cij = cij - Vi - Wj, (i,j) € N
  // Para as não básicas, ela não vai dar 0,    _
  // o resultado dela será nosso custo reduzido Cij.

  Note que a equação (1) nos dá m+n variáveis (Vi e Wj)
  porém apenas n+m-1 restrições, se zerarmos arbitrariamente uma variável (coloca-la como não-básica),
  teremos um sistema viável com uma única solução.
  Usaremos (1) para descobrir o valor de Vi e Wi, zerando um deles arbitrariamente.

  Note que a equação (2) dá != de 0 para todos os (i,j) não básicos.
  Esse é nosso custo reduzido.
  A restrição original era da forma:

    Vi + Wj <= cij     ou     cij - Vi - Wj >= 0
          _
  Logo se Cij for negativo, temos uma restrição infringida no dual.
  Isso como falamos na aula passada significa que a variável associada no primal
  deveria entrar na base para se aproximar da solução ótima.

  Portanto será dessa forma que iremos calcular o custo reduzido no exemplo abaixo,
  utilizando as variáveis duais.

  Com isso já sabemos obter os V`s e W`s que são variáveis duais.
  E com eles:

  2) Calculamos o custo reduzido e

  3) Escolhemos a variável que vai sair.

  Quando vamos escolher qual arco deverá ter seu fluxo acrescido (a partir de 0) temos que escolher um para sair.
  Ou seja essa é a troca de variáveis.

  O professor desenhou um quadro para expressar o problema:

  Matriz de custos abaixo:
     |       |       |       |       |  Oi  |  Vi  | of  |
     |2) 6   |3)     |11)    |7)     |  6   |      |  1  |
     |1)     |0) 1   |6)     |1)     |  1   |      |  2  |
     |5) 1   |8) 4   |15) 3  |9) 2   |  10  |      |  3  |

  Dj |   7   |   5   |   3   |   2   |      |      |     |
  Wj |       |       |       |       |      |      |     |
  dm |   1   |   2   |   3   |   4   |      |      |     |

  Notem que na tabela acima, eu coloquei valor de fluxo em 6 celulas da tabela de custos.
  Logo as demais celulas (arestas) tem fluxo zero.

  Isso significa que tenho 6 variáveis básicas.

  As variáveis duais indicam o fluxo nos arcos.

  Calculando a dual:

  B: {(1,1) (3,1), (2,2), (3,2), (3,3), (3,4)}
  _
  cij = cij - vi - wj = 0 para todo i,j € B

  (1,1):  2 - v1 - w1 = 0
  (2,2):  0 - v2 - w2 = 0
  (3,1):  5 - v3 - w1 = 0
  (3,2):  8 - v3 - w2 = 0
  (3,3): 15 - v3 - w3 = 0
  (3,4):  9 - v3 - w4 = 0

  O professor decidiu zerar v3.
  Assim v1 = -3
        v2 = -8
        v3 = 0 (arbitráriamente)
        w1 = 5
        w2 = 8
        w3 = 15
        w4 = 9

  Vamos escrever:

     |       |       |       |       |  Oi  |  Vi  | of  |
     |2) 6   |3)     |11)    |7)     |  6   |  -3  |  1  |
     |1)     |0) 1   |6)     |1)     |  1   |  -8  |  2  |
     |5) 1   |8) 4   |15) 3  |9) 2   |  10  |   0  |  3  |

  Dj |   7   |   5   |   3   |   2   |      |      |     |
  Wj |   5   |   8   |  15   |   9   |      |      |     |
  dm |   1   |   2   |   3   |   4   |      |      |     |

  Agora podemos calcular o custo reduzido das não-básicas com o método falado acima:

    ~c12 = c12 - v1 - w2 = -2
    ~c13 = c13 - v1 - w3 = -1
    ~c14 = c14 - v1 - w4 =  1
    ~c21 = c21 - v2 - w1 =  4
    ~c23 = c23 - v2 - w3 = -1
    ~c24 = c24 - v2 - w4 =  0
  // (Nota: eu testei o que aconteceria se zerassemos W2 ao invez de V3
  // os calculos acima teriam os mesmos resultados para todos os ~cij)
  // (isso prova que não faz diferença qual das variáveis duais nós escolhemos para zerar)

  Vamos então escreve-los em uma tabela
  (o professor escreveu na tabela original)
  (mas isso significa 3 numeros por quadrado da tabela O.O)
  (aqui no computador ia ficar um caos, vou fazer outra tabela)

  (CRed)
  of\dm |  1 |  2 |  3 |  4 |
    1   |  0 | -2 | -1 |  1 |
    2   |  4 |  0 | -1 |  0 |
    3   |  0 |  0 |  0 |  0 |

  Notem que os candidatos à entrar na base tem custo reduzido negativo.
  As variáveis de base tem custo = 0.
  E as demais tem custo não-negativo (aquelas que não iam contribuir em nada com o objetivo).

  Nossa escolha será sempre feita com base na variável não básica de menor indice (Critério de Blonde)
  no caso: (1,2)

  Com esse pivoteamento teremos algumas consequencias:
  Vamos ter que diminuir o fluxo em (1,1), aumentar em (3,1) e diminuir em (3,2)

  Esse pivoteamento está sujeito à algumas equações limitantes:

    Seja teta o tanto que (1,2) vai aumentar de fluxo.

    Aumentanto o teta em (1,2) implica em menos fluxo em (1,1)
    Como (1,1) não pode ter fluxo negativo:
      (1) 6-teta >= 0

    O mesmo se aplica ao (3,2) como ele não pode ter fluxo negativo:
      (2) 4-teta >= 0

  Obviamente o maior aumento que teta pode fazer é 4, pois
  a equação (2) é a que mais o limita.

  logo:

    teta* <= 4
  // O asterisco denota "solução"

  Então o valor máximo de fluxo que (1,2) pode assumir é 4 (antes ele era 0).

  Assim a posição (3,2) agora fica com fluxo 0, ou seja ele saiu da base! =].

  Vamos atualizar a tabela:

     |       |       |       |       |  Oi  |  Vi  | of  |
     |2) 2   |3) 4   |11)    |7)     |  6   |  -3  |  1  |
     |1)     |0) 1   |6)     |1)     |  1   |  -8  |  2  |
     |5) 5   |8)     |15) 3  |9) 2   |  10  |   0  |  3  |

  Dj |   7   |   5   |   3   |   2   |      |      |     |
  Wj |   5   |   8   |  15   |   9   |      |      |     |
  dm |   1   |   2   |   3   |   4   |      |      |     |

  Agora podemos apagar os calculos que fizemos na tabela (CRed)
  E os outros valores duais que calculamos:

     |       |       |       |       |  Oi  |  Vi  | of  |
     |2) 2   |3) 4   |11)    |7)     |  6   |      |  1  |
     |1)     |0) 1   |6)     |1)     |  1   |      |  2  |
     |5) 5   |8)     |15) 3  |9) 2   |  10  |      |  3  |

  Dj |   7   |   5   |   3   |   2   |      |      |     |
  Wj |       |       |       |       |      |      |     |
  dm |   1   |   2   |   3   |   4   |      |      |     |

  Zerando v3 e calculando os valores das demais variaveis duais temos:

    cij - vi - wj = 0 para todo i,j € B

    (1,1):  2 - v1 - w1 = 0
    (1,2):  3 - v1 - w2 = 0
    (2,2):  0 - v2 - w2 = 0
    (3,1):  5 - v3 - w1 = 0
    (3,3): 15 - v3 - w3 = 0
    (3,4):  9 - v3 - w4 = 0

    O professor decidiu zerar v3 de novo.
    Assim v1 = -3               w1 = 5
          v2 = -6               w2 = 6
          v3 =  0 (arbitrário)  w3 = 15
                                w4 = 9

     Tabela atualizada:
     |       |       |       |       |  Oi  |  Vi  | of  |
     |2) 2   |3) 4   |11)    |7)     |  6   |  -3  |  1  |
     |1)     |0) 1   |6)     |1)     |  1   |  -6  |  2  |
     |5) 5   |8)     |15) 3  |9) 2   |  10  |   0  |  3  |

  Dj |   7   |   5   |   3   |   2   |      |      |     |
  wj |   5   |   6   |  15   |   9   |      |      |     |
  dm |   1   |   2   |   3   |   4   |      |      |     |

  Calculando o custo reduzido:
   _
   cij = cij - vi - wj

  ~c13 = c13 - v1 - w3 = -1
  ~c14 = c14 - v1 - w4 =  1
  ~c21 = c21 - v2 - w1 =  2
  ~c23 = c23 - v2 - w3 = -3
  ~c24 = c24 - v2 - w4 = -2
  ~c32 = c32 - v3 - w2 =  2

    (CRed)
    of\dm |   1   |   2   |   3   |   4   |
      1   |   0   |   0   |  -1   |   1   |
      2   |   2   |   0   |  -3   |  -2   |
      3   |   0   |   2   |   0   |   0   |


  Vamos escolher alguém para sair da base e alguém para entrar.

  (1,3) vai entrar, pois é a variável com custo negativo de menor indice.

  Assim os candidatos a sair são: (1,1), (3,3)
  E os fluxos que irão ser afetados são: (1,1), (3,3) e (3,1)

  Mais especificamente o que menos permitir o crescimento de (1,3)

    fluxo de (1,1) >= 0
      2-teta       >= 0

    fluxo de (3,3) >= 0
      3-teta       >= 0

  Logo o valor máximo de crescimento de teta é:

    teta* = 2

  A próxima iteração ficou de para casa.
  Mas deu para pegar a idéia certo?

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

  Só uma última coisa antes da aula terminar:

  Qual a diferença do problema do Transbordo para o problema do Transporte?

  Transbordo tem vertices intermediarios (que recebem e ofertam 0)
  Transporte tem um método bonitinho de solução (a tabela)

  É possível resolver o problema do transbordo por meio de um algoritmo para o prob. do transporte?

  Sim, basta substituir os vertices intermediários por arestas ligando seus arcos incidentes nos arcos de saída.

  Assim teriamos os ofertantes, os demandantes e os intermediarios seriam convertidos em arcos.

  Assim voce pode resolver o problema do Transbordo através do problema do Transporte.

  Só resta uma dúvida, precisamos encontrar o caminho minímo entre um ofertante e um demandante para saber
  quais serão as arestas que substituirão os vertices intermediários.

  Afinal fazer arestas com custo maior do que o mínimo obviamente não é ótimo.

  E Pronto Dessa forma aprendemos a resolver dois problemas com um único algoritmo.
  (+ o algoritmo do caminho mínimo para transformar um no outro =P)

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

  // Fim da aula!