PO - 27/09/2012

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

  // PDF de referencia:
  // http://www.feg.unesp.br/~fmarins/po/slides/2o.s/Teoria%20da%20Dualidade.pdf

  Hoje vamos falar de Dualidade

  Dualidade significa duas formas de ver e solucionar um mesmo problema.
  Ou pensando de outra forma dois problemas fortemente associados.
  O primeiro chamado de Primal e o segundo chamaremos de Dual.

  Vamos começar com um exemplo, para então explicarmos as conexões:

             Primal             |            Dual
                                |
    min 1 y1 + 55 y2 + 3 y3     |  max 4 x1 + 1 x2 + 5 x3 + 3 x4
                                |
       y1 + 5 y2 -   y3 >= 4    |     x1 -   x2 -   x3 + 3 x4 <= 1
    -  y1 +   y2 + 2 y3 >= 1    |   5 x1 +   x2 + 3 x3 + 8 x4 <= 55
    -  y1 + 3 y2 + 3 y3 >= 5    |  -1 x1 + 2 x2 + 3 x3 - 5 x4 <= 3
     3 y1 + 8 y2 - 5 y3 >= 3    |                 x1,x2,x3,x4 >= 0
               y1,y2,y3 >= 0    |

  Notem as semelhanças entre os dois problemas:

  1° - Os coeficientes da matriz tecnologica do dual, são os mesmo da matriz Tecnologica do primal,
       porém Transpostos, ou seja, uma coluna dos coeficientes do primal, é uma linha de coeficientes no dual.
       logo o dual tem uma restrição associada a cada variável do primal, e vice versa.

  2° - As constantes (lado direito da eq.) das restrições do Dual são os coeficientes
       das variáveis y1, y2 e y3 do primal no objetivo e vice-versa.

  3° - Se o primal é "min" o dual é "max" e vice-versa.

  Agora vamos trabalhar sobre os sinais e desigualdades.
  Seja a forma normal de um dicionário a forma na qual todas as variáveis são >=0 e todas as desigualdades
  limitam o objetivo, ou seja:

    Em minimização todas as desigualdades são limites inferiores >=.
    Em maximização todas as desigualdades são limites superiores <=.

  Se o primal está na forma normal, voce tem uma garantia de que no dual as desigualdades estarão na forma normal
  e os sinais das variáveis serão >=0.

  Agora se uma variável do primal, é <=0, a restrição associada à ela terá a desigualdade oposta àquela
  da forma normal.

  Ou seja, se no exemplo acima y1 fosse <= 0. A restrição associada à ele, ou seja r1, teria uma desigualdade
  do tipo >=, que é o contrário da desigualdade da forma normal para uma maximização.

  Por fim se a variável não for, nem <=0 nem >=0 mas sim com um valor livre, a restrição associada
  será de igualdade. Nem de <= nem de >= mas somente de igualdade.

  Da mesma forma, se uma restrição do primal estiver fora da forma padrão a variável no dual também estará.
  E ela seguira as mesmas regras que acabei de falar acima.
  Se r1 do primal for de igualdade, a variável x1 do dual terá valor ilimitado em sinal.
  E assim por diante.

  Os critérios que citei acima são os mecanismos pelos quais é possível encontrar o dual
  de qualquer problema linear na forma de Dicionário.
  (com um objetivo, uma matriz tecnológica e restrições de sinal para as variáveis)

  Teorema Dual:

    Se existe um primal de minimização e um dual (de maximização) associado. E ambos com soluções viáveis.
    Necessáriamente a solução do primal é maior ou igual à solução do dual.
    E vice versa se o primal for de maximização.

    Para provar isso é fácil.
    Multiplique todas as restrições do primal por x1, x2 e x3 respectivamente.
    Some as 3 o que teremos?

    Do lado esquerdo (como é uma matriz) teremos todas as combinações de xiyj * coeficiente.

    Do lado direito teremos:

      4 x1 + 1 x2 + 5 x3 + 3 x4

    Note: Isso é o objetivo do dual.

    Façamos o mesmo com as restrições do dual:

    Multiplicando y1, y2 e y3 respectivamente pelas 3 restrições.

    Do lado esquerdo teremos xiyj * coeficiente.

    Do lado direito teremos o objetivo do primal ou seja:

      1 y1 + 55 y2 + 3 y3

    Agora notem, ambas as equações são na forma:

      xi yj coef >= objetivo dual
      xi yj coef <= objetivo primal

    Logo:

      objetivo primal >= objetivo dual

    Ficou muito informal dessa forma, porém se voces fizerem os calculos em um par primal-dual
    isso ficará claro.

    Com isso provamos que
    o objetivo do primal de minimização é sempre menor ou igual ao objetivo de seu dual associado.

    O mesmo vale para o inverso quando o problema primal é de maximização.

CONCEITO:
  Dualidade Fraca - Seja P uma solução para um primal de minimização.
  P é sempre maior do que qualquer solução de seu dual.
  E vice-versa para maximização.

    Resumo:

    Acabamos de falar da Dualidade Fraca.

    O teorema diz que uma solução válida do primal de minimização pode ser usado como limite inferior do dual de maximização.
    E vice-versa, uma solução qualquer de um primal de maximização é o limite superior do dual de minimização associado.
    E mais: A solução ótima do primal tem exatamente o mesmo valor da ótima do dual, mas não vou provar isso agora.

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

  Observação:

  Sobre o que eu acabei de dizer acima, sobre a solução ótima do primal ter exatamente o mesmo valor
  da solução ótima do dual. Isso se chama Dualidade Forte.

  Essa propriedade é muito útil e entre outras coisas permite uma avaliação interessante.

  Veja, o vetor objetivo dual:

    max 4 x1 + 1 x2 + 5 x3 + 3 x4

  é também o vetor de constantes do primal (que é um problema de minimização).

  Agora suponha que na solução ótima x1 = 10. (eu não calculei, estou apenas especulando)
  logo 4 x1 no objetivo resulta em 40 unidades.

  Se eu mudar um pouco o meu problema e aumentar o coeficiente para de x1 para 5, o valor irá subir para 50.

  Agora lembrando que estamos falando de uma constante do primal de minimização,
  ela pode ser por exemplo o custo de manutenção de determinado aparelho.

  Se eu aumento esse custo em uma unidade,
  o meu custo ótimo vai subir em 10 unidades se o valor de x1 no dual for 10.

  Em outras palavras, o valor de x1 no dual ótimo indica o quanto que uma unidade de um recurso do meu primal vale.

  Se o custo de manutenção x1 = 10 e eu reduzo em duas unidades esse custo,
  eu vou ter um resultado final 20 unidades melhor, ou mais barato.

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

  Últimas observações sobre dualidade fraca:
    - Se um deles for ilimitado o outro é inviável.
    - Se um deles for inviável o outro pode ser inviável ou ilimitado.

  // Fim da aula!