PO - 11/10/2012

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

  // Nota importante:
  // Na aula de hoje vamos falar sobre o programa de geração de colunas.
  // Eu achei mais fácil de entender isso depois que eu estudei o Método Simplex Revisado.
  // Os slides que usei para estudar seguem abaixo:

  O professor Fernando Marins da UNESP disponibilizou alguns ótimos slides que vou colocar abaixo:

  Uma boa apresentação de slides para explicar o MSR segue abaixo, também do mesmo autor do pdf acima.
  http://www.feg.unesp.br/~fmarins/po/slides/2o.s/MSR.pdf
  (MSR = Método Simplex Revisado) (oficialmente não faz parte da materia)

  Vou disponibilizar os slides no meu site também (eu estudei por eles)

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

  Decomposição Dantzig Wolfe:
  (conhecido em computação também como programa de geração de colunas)

    min cTx
    Ex = e
    Ax = b
    x >= 0

  Na aula anterior falamos que qualquer ponto de um PPL
  pode ser escrito pela combinação do conjunto de xj`s (R) somado com uma combinação do conjunto dj`s (D),
  onde R contém os pontos extremos e D as direções extremas.

  Ou seja:

    x = sum (j€R) lambdaj x^j + sum(i€D) tetai d^i

    sum(j€R) lambdaj = 1

    lambdaj e tetai >= 0

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

  Problema mestre:

  Introdução:
    O problema mestre é escrito re-escrevendo cada restrição, e o vetor objetivo
    em termos de combinações dos conjuntos R e D do problema.

    Se voce pensar bem, fazer essa conversão pode ser chato, mas não é dificil de imaginar:

    Um objetivo é um vetor certo?
    Para criar um vetor basta ter dois pontos não sobrepostos.
    Mostramos na última aula que é possível escrever qualquer ponto do dominio em termos de xj e dj
    logo é possível re-escrever o vetor objetivo com base na mesma idéia.

    As restrições de desigualdade são como linhas de um gradiente.
    Se tem o gradiente tem o vetor gradiente, basta dizermos que o valor desse vetor,
    a partir do ponto p contido na linha tem de ser positivo, ou algo assim.
    Digo é chato de pensar como fazer a conversão, mas não é impossível.

  Formalização do Prob. Mestre:

    // Usarei l para denotar lambda e t para teta.
    // (Notem que xj e dj são constantes, e as variáveis são lj e tj)

    min sum(j€R) cT(lj xj) + sum(j€D) cT(tj dj)

    sum(j€R) E(l^j x^j) + sum(j€D) E(t^j d^j) = e

    sum(j€R) l^j = 1
    (combinação convexa)

  Podemos re-escrever:

    min sum(j€R) (cT x^j) l^j + sum(j€D) (cT d^i) t^i

    (ß) sum(j€R) (E x^j)l^j + sum(j€D) (E d^j)t^j = e

    (r) sum(j€R) l^j = 1
    (combinação convexa)

  O problema é que da forma que escrevemos agora temos um conjunto muito grande de variáveis.
  Se voce pensar bem, cada variável antiga agora pode ser descrita por |R| variáveis no mínimo.
  Aumentando nosso total de variável para numV*|R|

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

  Agora suponhamos que possamos encontrar um subconjunto de R e de D cuja solução relacionada seja solução também do problema envolvendo R e de D.

    RR contido em R
    DD contido em D

  Com as variáveis lj onde j € RR e tj onde j € DD

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

  Problema Mestre Restrito de PL (RPMPL (- tb não entendi essa sigla))

    min sum(j€RR) (cT x^j) l^j + sum(j€DD) (cT d^i) t^i

    sum(j€RR) (E x^j)l^j + sum(j€DD) (E d^j)t^j = e

    sum(j€RR) l^j = 1
    (combinação convexa)

  Ou seja a mesma coisa porém com um subconjunto de R e de D.

  Resolvendo o RPMPL obteremos uma solução na forma de valores fixados para as variáveis
  lambda e teta:

    lj*: j € RR, tj*: j € DD

  Precisamos agora verificar se essa solução além de resolver o RPMPL
  também resolve o PMPL (o prob original).

  Ou seja, existe algum ponto que do dominio de R e de D que faltou ser incluido em RR e DD?

  Podemos formular essa pergunta assim:
    Existe j cujo custo reduzido é menor que 0?

  Em outras palavras, o grande chan da decomposição é que
  para calcular o custo reduzido eu preciso de armazenar poucos dados
  das colunas que eu não estou usando atualmente.

  Assim temos dois tipos de iterações:
  Iterações do problema restrito usando o simplex.
  Iterações do problema Mestre onde se calcula os custos reduzidos,
  e adiciona a coluna de melhor custo à base.

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

  Vamos agora em pensar no calculo do custo reduzido com base
  na ideia do dual simplex falado na aula de 09/10/2012:

  Vamos escrever o dual desse problema:

    max ßT e + r

    ßT (E xj) + r <= cT xj, para todo j € R

    ßT (E dj)     <= cT dj, para todo j € D

  Com base no dual usando a idéia do dual simplex
  podemos descobrir uma coluna do primal com custo reduzido menor que 0
  verificando se há alguma restrição do dual violada.

  Se houver violação:
    Adicione essa variável no problema original.

  Se não houve:
    Precisamos de um atestado de otimalidade.

    cT xj - ßT ( E xj ) - x >= 0

    min cT xj - ßT ( E xj )

  A solução desse problema pelo simplex me da uma solução
  Vamos chama-la de x*.

  x* é um ponto extremo, ou direção extrema de P, logo temos alguém para adicionar no nosso problema RPMPL

  Repetimos esse processo até o problema atestar que não existe coluna com custo reduzido negativo.
  // Essa última parte eu re-li mas não entendi direito =P.
  // Durante essa aula eu tava cansado o que aumenta
  // a probabilidade de eu ter escrito bobeira nas linhas acima.

  // Ao menos a idéia geral ficou clara, armazene apenas o que precisa,
  // "passe o olho" (custo reduzido) pelo resto do problema
  // pra descobrir se precisa de algo mais
  // se precisar inclua essa coisa (coluna) no seu problema.

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

  Vamos fazer um exemplo:

  min -4x1 -  x2 - 6x3
  3x1 + 2x2 + 4x3 = 17

  1 <= xi <= 2 : i = 1,2,3

  P = { x € R³+ : 1 <= xi <= 2, i=1,2,3 } D = ø

  // note que o problema acima é uma minimização
  // em um plano (devido a restrição de igualdade)
  // descrito em um espaço de 3 dimensões.

  // Note que o plano é limitado (recortado) pelas restrições
  // de "1 <= xi <= 2" senão teriamos um plano infinito.

// Só passei a limpo até aqui, durante a aula disseram que esse exemplo é muito explicativo,
// mas estou estudando e não vou poder olhar agora.
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  Vértices serão utilizados para escrever o  RPMPL

  // Note que vou usar x¹ como o ponto extremo 1,
  // e x1 para a variável 1 do prob. original.

  l¹ x¹ = | 2 | c¹ = cTx¹ = ( - 4 - 1 - 6 ) (2 2 2)T = -22
          | 2 |
          | 2 | Ex¹ = [3 2 4] [2 2 2]T = 18

  l² x² = | 1 | c² = cTx² = ( - 4 - 1 - 6 ) (1 1 2)T = -17
          | 1 |
          | 2 | Ex² = [3 2 4] [1 1 2]T = 13

  1° RPMPL:

  min - 22 l¹ - 17 l²

  | 18 13 |⁻¹    |  0,2 -2,6 |
  |  1  1 |   =  | -0,2  3,6 |

  Resolvendo o sistema:

    18 l¹ + 13 l ² = 17
    l¹ + l² = 1

  l¹ = 0,8
  l² = 0,2

  (ß, r) = CB B⁻¹ = [-22 - 17] |  0,2 -2,6 | = [ -1 -4 ]
                               | -0,2  3,6 |

  Resolvendo o problema de precificação:

  min ( [-4 -1 -6] - (-1) [ 3 2 4 ] ) [x1 x2 x3]T

  min -1x1 + 1x2 - 2x3
  1<= x1 <= 2
  1<= x2 <= 2
  1<= x3 <= 2

  x1* = 2
  x2* = 1
  x3* = 2

  -5 = -1(2) + 1 -2(2)

  nova coluna l³, associada à x3 = [2 1 2]T

  c³ = cTx³ = (-4 -1 -6) (2 1 2)T = -21

  Ex³ = [3 2 4] [2 1 2]T = 16

  min -21 - l³

  l¹ = 0,8 - 0,6 l³
  l² = 0,2 - 0,4 l³

  l¹ = 1/2 + 1,5 l²
  l³ = 11/2 -2,5 l²

  min -21,5 + 2,5 l²

  2° prob. pricing:

  B = | 18 16 |  B⁻¹ |  1/2 -8 |
      |  1  1 |      | -1/2  9 |

  (ß,r) = [-22 -21] B⁻¹ = [ -0,5 -13 ]

  min ( [-4 -1 -6] + (1/2) [3 2 4] ) (x1 x2 x3)
  x € P
  min -5/2x1 + 0x2 - 4x3

  1<= x1 <=2
  1<= x2 <=2
  1<= x3 <=2

  (2 1 2)T ou (2 2 2)T

  -5/2(2) + 0(1) - 4(2) = -13 + 13 = 0

  Assim conseguimos nosso atestado de otimalidade e fim do problema.

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

  // Fim da aula!