PO - 02/10/2012

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

  Dualidade:
    - D. Fraca.                     ©
    - D. Forte.                     ×
    - T. das Folgas Complementares. ×
    - Pares P/D                     ×
    - Análise de Sensibilidade.     ×

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

  Este primeiro fala de "Dualidade Fraca" até "Pares P/D" e é muito bem explicado.
  http://www.feg.unesp.br/~fmarins/po/slides/2o.s/Teoria%20da%20Dualidade.pdf

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

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

REVISÃO:
  Dualidade Fraca:

  Sejam o seguinte par primal/dual:

    (P) max cTx  (D) min bTy
        Ax = b       yTA >= cT

  Seja ¯x uma solução viável do vetor x.
  Seja ¯y uma solução viável do vetor y.

  A Dualidade Fraca diz que:

    Se ¯x é viável para (P) e ȳ é viável para (D)

  Garantidamente: cT ¯x <= bT ¯y
  Ou seja, o valor do objetivo do primal será sempre menor ou igual ao do dual.

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

  Em dualidade fraca existem os casos:

  Suponha um primal de maximização e um dual de max.

  Se o primal for:      | O dual será:
  Ótima finito             Ótima finito.
  Inviável                 Inviável.
  Inviável                 Ilimitado.
  Ilimitado                Inviável.

  A inversa também é verdadeira.
  Isso é útil para voce descobrir por exemplo se seu problema não tem solução.
  Basta provar que o dual é ilimitado ou inviável.

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

  Exemplo de problema onde o primal e o dual são: "inviável/inviável":

  min  x1 + 2x2 (primal)
  x1 + x2 = 1
  2x1 + 2x2 = 3

  max p1 + 3p2 (dual)
  p1 + 2p2 = 1
  p1 + 2p2 = 2

  É visível que ambos não tem solução.
  // (Note que as variáveis do primal são irrestritas em sinal, e as do dual também)

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

CONCEITO:
  Dualidade Forte

  Seja o par primal dual:
  (P) max cTx  (D) min bTy
      Ax = b       yTA >= cT

  Seja ¯x os valores ótimos do vetor x.
  Seja ¯y os valores ótimos do vetor y.
  (considerando que ambos tem solução ótima viável)

    cT ¯x = bT ¯y

  Em outras palavras, esse teorema diz que os valores ótimos do problema primal e dual,
  se existirem serão exatamente de igual valor.

  Essa é talvez a propriedade mais surpreendente, e é a ligação mais forte entre o primal e o dual.

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

  Observações minhas:

  Voce pode pensar que existe uma linha entre o problema primal e o dual.

  Abaixo dessa linha há um problema de maximização tentando andar para cima,
  Acima  dessa linha há um problema de minimização tentando andar para baixo,

  As duas sempre se encontram no centro.

  Se um dos problemas é ilimitado, ou seja sua solução é infinitamente óima,
  significa que ele empurrou a linha até o infinito.
  Por causa disso o seu par não tem nenhum espaço de solução, e é portanto inviável.

  Se voce faz uma alteração em um dos problemas,
  (alterando por exemplo o custo de manutenção de determinado recurso)
  De forma a melhorar ou piorar o ótimo, voce estára também afetando o ótimo do outro problema em igual valor.

  É um jeito interessante de pensar na relação primal dual.

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

  Teorema das Folgas Complementares

  O teorema das folgas complementares diz respeito à uma relação entre as variáveis de folga
  do primal, e às variáveis estruturais do dual.

  Chamemos de F1 a variável de folga da      restrição 1 do primal.
  Chamemos de y1 a variável dual associada a restrição 1 do primal.

  Básicamente a única coisa que esse teorema diz é que:

    F1 * y1 = 0

  Para qualquer variável de folga, associada à sua respectiva variavel dual.
  Isso também vale para as folgas do dual em relação as variáveis do primal.

  Em outras palavras, se voce já fez uma escolha de variáveis primais e duais.
  E se o valor de F1 é diferente de 0, isso implica que y1 é necessáriamente não-básica.

  Note que é possível que Ambos sejam iguais à 0.

  Com esse teorema voce pode reconstruir uma solução dual associada à uma solução primal.

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

  Provando o Teorema da Dualidade Forte:
  // Eu não gosto de provas de teoremas, então eu não passei a limpo esse último trecho da aula.

  Base ótima associada à ¯x é B.
  Simplex terminou com a seguinte condição sendo satisfeita:

    (cnT - cbT B⁻¹N) <= 0

  Definir uma variável dual: yT = cb T B⁻¹
  Se yT = cb T B⁻¹  for viável o objetivo dual : cbT B⁻¹ b

  Sobre a viabilidade deste escolha:

    y T A     >= cT
    y T [B N] >= [cbT cnT]

  i) yTB >= cbT ?    cbT B⁻¹B= cbT (ok)
  ii) yTN >= cnT ?   cbTB⁻¹N >= cnT

  // Condição de otimalidade primal é condição de viabilidade dual.

  Em resumo a solução yT = cbT B⁻¹ é viável para o dual e cT¯x é igual à cb T B⁻¹b = ȳTb
  Logo ¯x e ȳ são ótimos respectivamente para P e D.

  Se ¯x e ȳ formam um par primal dual ótimo, então valem as condições de complementaridade e folga.

    (A¯x - b)T  ȳ = 0 (n restrições, uma para cada variável do dual)

    (ȳTA - cT) ¯x = 0 (m restrições, uma para cada variável do primal)

  Seja ai = linha i da matriz A

    (ai T ¯x = bi) yi = 0 i = 1, ..., n.

  Primal na forma padrão => a condição I é satisfeita dada a viabilidade de ~x em P

  Assim:

    (~yT Aj - cj) ~xj = 0, j = 1, ..., n

  Aj = j-ésimo coluna da matriz A.

  Dois casos à considerar:

  a) j é indice de variável básica ~xj >= 0 (~y T Aj - Ci)
     (assumir ~xj > 0)

  b) j é não básica: xj é não básica.
     ~xj = 0

  Se as condições de complementaridade de folga valem (C.C.F.) então ~x e ~y formam par primal dual ótimo.

  (A~x - b)T ~y = 0        (~y T A - cT) ~x = 0

  (A~x)T ~y = bT~y         ~y T A ~x = cT~x

  cT~x = y T A ~x <= bT~y = A~xT y
  yTA~x = A ~x T y


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

  Hoje nós varremos todos os significados teoricos importantes de programação linear.

    Dualidade:
    - D. Fraca.                     ©
    - D. Forte.                     ©
    - T. das Folgas Complementares. ©
    - Pares P/D                     ? (não sei se falamos disso =P)
    - Análise de Sensibilidade.     ×

  Na aula que vem vamos falar de Análise de Sensibilidade.

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

  // Fim da aula!