PO - 04/10/2012

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

  Análise de Sensibilidade

  Análise de sensibilidade é um estudo feito sobre um problema já resolvido.
  Esse estudo tem o intuito de entender as propriedades da solução e prever por exemplo,
  qual a melhor forma de aumentar os lucros:
  Seria reduzindo o custo de manutenção? Aumentando o numero de horas de serviço?

  Pode-se detectar onde estão os garga-los do problema.

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

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

  Um bom slide para explicar Análise de Sensibilidade segue abaixo, também do mesmo autor do pdf acima.
  http://www.feg.unesp.br/~fmarins/po/slides/2o.s/analise%20de%20sensibilidade1.pdf

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

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

  Vamos então avaliar várias situações a partir do problema P abaixo:

    max cTx
    Ax = b
    x >= 0

  Questão 1) O que ocorreria se uma variável fosse adicionada no problema P?

  // Um exemplo mais realista para o problema P:

    max 5x1 + 4x2 + 3x3
    2x1 + 3x2 +  x3 + x4 = 5
    4x1 +  x2 + 2x3 + x5 = 11
    3x1 + 4x2 + 2x3 + x6 = 8
    x1,x2,x3,x4,x5,x6 >= 0

  Suponha que iremos adicionar x7, na primeira restrição com coeficiente 1 e no objetivo com coeficiente C7.

  Obviamente, considerando-a não básica ela certamente não irá afetar o problema.
  O valor da variável será 0, e portanto não afetará nem o valor ótimo do problema, nem as restrições do mesmo.

  Porém pode acontecer de que a variável x7 melhore o objetivo caso entre na base.
  Ou seja, a inserção de uma nova variável abre a possibilidade da solução atual não ser mais ótima.
  Mas também pode ser que ela não faça diferença nenhuma, e que não afete a sol. ótima.

  // Nota 1: Seja D o dual de P.
  //       Ao inserir x7, D irá ganhar uma nova restrição. Percebem a relação?

  // Nota 2: Lembrem que o único caso em que uma solução de D tem o mesmo valor que a solução de P é no ótimo.
  //         Portanto o que acontece se P não for mais ótimo?
  //         D deixará de ser viável.

  // Nota 3: Uma analogia para isso é que a restrição adicionada ao dual inviabilizou-o.

  A nova coluna altera a viabilidade do dual, se somente se ela for uma candidata desejável à entrar na base.
  Caso contrário nada muda.

  Note então que se o crescimento dessa nova variável diminuir o objetivo,
  e for um problema de maximização ela será não básica e terá o valor 0 não alterando nada no problema.

  Porém no caso contrário onde o aumento dela é desejável para melhorar o objetivo,
  teremos de buscar uma nova solução ótima.

  Questão 2) O que acontece se alterarmos o custo ou vetor tecnológico de uma variável existente?

  a) Alterando o custo (considerando maximização)
    Caso a variável considerada seja básica: xj(básica)
      - se cj crescer:  não altera nada.
      - se cj diminuir: recalcular os custos reduzidos (outra variável pode ser melhor como variável básica)

    Caso a varável considerada não seja básica: xj(não-básica)
      - se cj crescer:  recalcular os custos reduzidos (outra variável pode ser melhor como variável básica)
      - se cj diminuir: não altera nada.

  b) Modificando a constante aij na matriz tecnológica A

  Essa alteração seria como mudar a inclinação de uma das linhas/restrições do gráfico.

  Se xj for básica, essa mudança de inclinação pode tornar a solução atual não-ótima.
  E pode até tornar a solução básica atual inviável.

  Se xj for não-básica, essa mudança não deverá afetar a solução ótima, mas poderá
  tornar a solução atual inviável.

  Em ambos os casos há até a possibilidade de não haverem mais soluções viáveis,
  nesse caso todo o problema torna-se inviável.

  3) Modificação no vetor b.

  Uma modificação no vetor b seria como mover uma linha sem alterar seu angulo pelo plano cartesiano.

  Essa modificação pode tornar a base atual inviável.

  Para saber se a solução ótima antiga, tornou-se inviável, basta saber se alguma das constantes bj,
  tornou-se negativa.

  Assim, caso uma mudança ocorra no problema inicial, é preciso re-calcular o valor final dos bj's.

  Agora segue um exemplo de como recalcular esses valores.

  Problema inicial (ignorando as variáveis estruturais):
    1 F1 + 0 F2 + 0 F3 = 1
    0 F1 + 1 F2 + 0 F3 = 2
    0 F1 + 0 F2 + 1 F3 = 3

  No problema final a linha 2 ficou assim:

    2 F1 + 1/2 F2 + F3 = 6

  Suponha que vou aumentar b3 em uma unidade ou seja:

    1 F1 + 0 F2 + 0 F3 = 1
    0 F1 + 1 F2 + 0 F3 = 2
    0 F1 + 0 F2 + 1 F3 = 4

  Qual o novo valor de b2 no problema final?

    2 F1 + 1/2 F2 + F3 = ?

  O macete é lembrar que se a linha 3 foi somada com a linha 2, a variável de folga denuncia essa soma.
  Dessa forma eu posso dizer que:

    b2 final = 2 * 1 + 1/2 * 2 + 1 * 4 = 7

  É um macete útil para fazer esses cálculos.
  A regra também se aplica para qualquer variação em qualquer outro bj.

  Durante esse estudo do vetor B geralmente se realiza esse calculo em função de uma variável.
  Dessa forma fica fácil de ver qual o intervalo mínimo e máximo que seu bj pode variar sem inviabilizar nada.

  4) Suponha que eu tenho uma desigualdade adicional entre as restrições.
     E que essa nova restrição não viabilize a solução do problema original.

     Esse problema semelhante ao de adicionar uma nova variável, só que a nova variável seria dual.

     Uma vez que essa solução inviabiliza a solução primal o dual perdeu sua otimalidade,
     e é preciso econtrar o ótimo do dual novamente (podendo ser ilimitado) ou encontrar
     uma nova solução viável para o primal.

     Da mesma forma que uma nova variável no primal gera uma nova restrição no dual.
     Uma nova restrição no primal gera uma nova variável no dual.

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

  // Fim da aula!