PO - 25/09/2012

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

  // O professor começou a aula falando sobre a data do exame especial.

  Exame Especial: 27 dez

  Horário: 13hs - 14:40.

  Novo monitor: Rosklin

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

  Vamos discutir hoje sobre o que faltava para utilizarmos o método simplex.
  Já sabemos como caminhar pelo Dominio do problema até encontrar a solução ótima.
  Porém nos exemplos anteriores, nós chutamos o primeiro vertice cegamente.

  Na prática o algoritmo só funciona se nosso chute inicial estiver dentro do campo de soluções viáveis.

  Vamos então aprender um jeito de pegar um vertice qualquer, (mesmo um não viável) e caminhar
  com ele até chegarmos em um vertice viável. E só então usar o simplex para resolver o problema.

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

  Vamos começar com um exemplo de um problema que seja dificil chutar uma base inicial viável:

    min x1 - 2 x2
     x1 + x2 >= 2
    -x1 + x2 >= 1
          x2 <= 3
     x1,x2 >= 0

  Note que tem duas desigualdades >=.

  Para colocar no formato padrão temos de fazer assim:

    min x1 - 2x2
     x1 + x2 - x3 = 2
    -x1 + x2 - x4 = 1
     x2 + x5      = 3
     x1,x2 >= 0

  Note que na desigualdade >= eu subtraí x3 e x4 para representa-las.

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

  O chute mais simples que costumamos fazer é assumir que as variáveis de folga são base,
  e as variáveis originais do problema são iguais à 0.

  Ou seja:

    xb = {x3,x4,x5}
    xn = {x1,x2}

  Dessa forma estamos denotando o ponto: x1=0, x2=0 ou (0,0).

  Porém notem que no problema acima essa solução básica é inviável,
  pois a primeira e a segunda restrição são infringidas.
  Como discutido, uma solução inviável não serve para ser usada no método simplex.

  A seguir vamos mostrar como partir dessa solução e chegar em uma solução viável.

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

  O professor sugeriu trocar (temporariamente)
  a variável -x3 e -x4 por x'3 e x'4 sem restrições de sinal:

    min x1 - 2 x2
     x1 + x2 + x'3 = 2
    -x1 + x2 + x'4 = 1
     x2 + x5       = 3
     x1,x2 >= 0

  Qual a vantagem de enchergar o problema assim?

  Agora o ponto (0,0) tornou-se uma solução viável já que não existem mais desigualdades ">=".
  Ou seja basta pegarmos como sol. básica as variáveis de folga x'3 e x'4 e x5 zerando x1 e x2.

  Agora para re-escrever as variáveis x'3 e x'4 em termos de variáveis positivas façamos isso:

    x'3 = x6-x3
    x'4 = x7-x4

    min x1 - 2x2
     x1 + x2 + (x6-x3) = 2
    -x1 + x2 + (x7-x4) = 1
     x2 + x5           = 3
     x1,x2,x3,x4,x5 >= 0
     x6,x7 >= 0

  x6 e x7 são chamadas de variáveis Artificiais.

  Se utilizarmos uma base com elas:

    xb = {x5,x6,x7}
    xn = {x1,x2,x3,x4}

  Temos uma solução viável no ponto (0,0).

  Porém esse problema não é igual ao problema anterior, pois adicionamos duas variáveis a mais.

  Agora que já temos uma solução viável, queremos voltar para o problema inicial como fazer isso?
  Bem é só trocar nosso objetivo:

    min x6 + x7
     x1 + x2 + (x6-x3) = 2
    -x1 + x2 + (x7-x4) = 1
     x2 + x5           = 3
     x1,x2,x3,x4 >= 0
     x6,x7 >= 0

  Uma vez que x6 e x7 for igual à 0, nosso problema será identico ao nosso problema original,
  e poderemos retornar à ele removendo as duas variáveis e retomando o objetivo original.

  Se isso não for possível significa que o problema original não tem solução viável.

  E pronto =].
  // (é um macete legal né?)

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

  Vamos agora resolver esses dois problemas com o método simplex:

  Primeira interação do método:
  Vamos re-escrever tudo isolando as variáveis básicas:

  min 3 - 2x2 + x3 + x4
    x6 = 2 - x1 - x2 + x3
    x7 = 1 + x1 - x2 + x4
    x5 = 3 - x2

    xb = {x5,x6,x7}
    xn = {x1,x2,x3,x4}

  Como x2 tem coeficiente negativo no objetivo,
  aumenta-lo irá diminuir o objetivo, façamos então x2 se tornar uma variável básica.

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

  Pelo teste da razão, notamos que crescer x2 infringe primeiramente a regra do x7.

  Assim vamos trocar x7 com x2 nas variáveis básicas.

    min 1 - 2 x1 - x4 + 2x7 + x3
    x6 = 1 - 2x1 + x3 + x7 - x4
    x2 = 1 + x1 - x7 + x4
    x5 = 2 - x1 + x7 - x4

    xb = {x2,x5,x6}
    xn = {x1,x3,x4,x7}

// NOTA: Existem 3 tipos de nomeclaturas de variáveis:
//         Variáveis estruturais (as originais)
//         Variáveis de folga    (para denotar as desigualdades)
//         Variáveis artificais  (para encontrar a solução viável inicial)

  Agora x1 e x4 tem coeficientes negativos no objetivo.
  O professor disse que existem vários critérios de escolha nesses casos.

  Nas últimas aulas escolhemos sempre a variável cujo o coeficiente é mais benéfico ao nosso objetivo.
  No caso dessa mínimização seria x1 que tem -2 como coeficiente.

  Porém o professor disse que tem outro critério, disse que vai escolher o x1 por ela ser
  a variável de menor indice (ou seja a variável mais pra esquerda, é estranho esse critério).

  Isso não alterou nossa escolha então vamos continuar.

  Vamos fazer outra operação de pivoteamento.

  Nosso dicionário está assim:

    min 1 - 2 x1 - x4 + 2 x7 + x3
    x6 = 1 - 2x1 + x3 + x7 - x4
    x2 = 1 + x1 - x7 + x4
    x5 = 2 - x1 + x7 - x4

    xb = {x2,x5,x6}, xn = {x1,x3,x4,x7}

  O crescimento de x1 infringe primeiro a restrição de x6.
  Então trocaremos x1 com x6.

    min  0 - x6 + x3 - x4 + x7
    x1 = 1/2 - 1/2 x6 + 1/2 x3 - 1/2 x4 + 1/2 x7
    x2 = 3/2 + 1/2 x4 - 1/2 x7 - 1/2 x6 + 1/2 x3
    x5 = 3/2 + 1/2 x6 - 1/2 x3 - 1/2 x4 + 1/2 x7

    xb = {x1,x2,x5}, xn = {x3,x4,x6,x7}

  Agora note que o nosso objetivo não tem mais uma constante diferente de 0 e x6 e x7 tem o valor 0 (não-básicas)
  Com isso cumprimos nossa meta de zerar x6 e x7.

  Note também que por coincidencia x6 e x7 são não básicas, o que já facilita nossa vida.
  Se x6 e/ou x7 ainda fossem básicas no momento em que zeramos elas, agente teria de forçar a saida delas da base.
  Para isso bastaria fazer alguma troca que resolvesse o problema.

  Para voltar para o problema original, agora que x6 e x7 são não-básicas, é só remover elas da equação:

    min  0 + x3 - x4
    x1 = 1/2 + 1/2 x3 - 1/2 x4
    x2 = 3/2 + 1/2 x4 + 1/2 x3
    x5 = 3/2 - 1/2 x3 - 1/2 x4

    xb = {x1,x2,x5}, xn = {x3,x4}

  E agora falta só re-escrever o objetivo original:

    min x1 - 2 x2
    x1 = 1/2 + 1/2 x3 - 1/2 x4
    x2 = 3/2 + 1/2 x4 + 1/2 x3
    x5 = 3/2 - 1/2 x3 - 1/2 x4

    xb = {x1,x2,x5}, xn = {x3,x4}

  E voilá, problema original e solução viável!

  Super interessante não? Não vou terminar o cálculo já que é só aplicar o simplex normalmente.

  Mas agora já sabemos como fazer quando o ponto (0,0) não for uma solução viável,
  é só brincar um pouquinho de criar novas variáveis.

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

  Para encerrar a aula, e encerrar tudo o que temos de saber sobre o simplex puro
  vamos falar da Regra de Blond:

  Agente só aceita que o método simplex termina quando todas as variáveis do objetivo tem sinal positivo(min) ou negativo(max) certo?

  Porém é possível o método entrar em loop infinito. Chamamos esse processo de "Ciclagem"

  A Regra de Blond garante que não haverá ciclagem!

CONCEITO:
  Critério Regra de Blond delimita que sempre que formos escolher qual variável não básica sair
  (quando temos mais de uma opção)
  devemos escolher sempre a que tem o menor indice, tipo entre x2 e x7 escolho sempre o x2.

  Essa regra é contrária a idéia que tinhamos até agora de escolher a variável com maior coeficiente né?
  Escolher o maior coeficiente talvez seja um pouco mais eficiente, mas pode gerar ciclagem,
  então é melhor usar sempre a Regra de Blond.
  (principalmente por ela ser muito simples de entender né)

  // NOTA: Um PPL Degenerado é quando uma das variáveis básicas está presa no valor 0
  //       e ainda não temos o atestado de otimalidade.
  //       se o problema é degenerado pode ocorrer ciclagem.
  //       Graficamente isso ocorre quando mais de duas restrições se cruzam em um mesmo vertice.

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

  O professor está mostrando um slide que exemplifica a degeneração do método simplex.

  O site dos slides é:
  www.dcc.ufmg.br/~acunha/linear/simplex.pdf
  (ps: nao consegui acessar o endereço =P, fazer o que =P)

  Nesse slide haviam duas variáveis básicas com o valor 0 e sem certificado de otimalidade.
  Ou seja esse é um exemplo degenerado.

  porém ao fazer o pivoteamento obvio, ainda há variáveis positivas no objetivo, e pior agora temos duas variáveis positivas.

  E então fazemos mais pivoteamentos, e novamente temos variáveis positivas no pivoteamento.

  A partir daí utilizando o critério de maior coeficiente e chegamos em outro resultado com variáveis positivas no objetivo.

  Seguindo com esse critério continuamente, vamos após alguns loops voltar exatamente ao conjunto de variaveis básicas originais, ou seja loop infinito.

  Esse é o processo de ciclagem.

  Como evitar? Basta trocar o critério de escolher a variável com o maior coeficiente e escolher sempre a variável com menor indice (Regra de Blond).

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

  // Fim da aula!