PO - 14/03/2013

   # # # # # # # # # # # # #
  # Pesquisa Operacional    #
  # notasdogarcia.blog.com  #
   # # # # # # # # # # # # #

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

  Aula 4: Entendendo o Simplex

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

  Na aula passada aprendemos a caminhar pelo espaço utilizando o simplex.

  O nosso problema exemplo era:

    max 3 x1 + 5 x2

    1 x1 + 0 x2 + F1 = 4
    0 x1 + 2 x2 + F2 = 12
    3 x1 + 2 x2 + F3 = 18

    x1,x2,F1,F2,F3 >= 0

  Inicialmente escolhemos a base: B = {F1,F2,F3}

    max 3 x1 + 5 x2

    F1 = 4  - 1 x1 - 0 x2
    F2 = 12 - 0 x1 - 2 x2
    F3 = 18 - 3 x1 - 2 x2

    x1,x2,F1,F2,F3 >= 0

  E o problema ficou assim:

    ^ x2
    |
    |------\
    |       \
    |        \
    |        |
    |        |
    |        |
    |        |
    |        |
    A--------------------> x1

  E caminhamos através de uma operação de Pivoteamento até o ponto: (0,6) com B = {F1,x2,F3}

  Com o dicionario escrito assim:

    max z = 30 + 3 x1 - 5/2 F2

    F1 = 4 - 1 x1
    x2 = 6        - 1/2 F2
    F3 = 6 - 3 x1 -  1  F2

    x1,x2,F1,F2,F3 >= 0

    ^ x2
    |
    |
    |  restrição 2
    A------\
    |       \ restrição 3
    |        \
    |        |
    |        |
    |  ^     | restrição 1
    | /      |
    |/       |
    .--------------------> x1

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

  Na aula de hoje vamos ver mais afundo 3 detalhes do Dicionário do Simplex dos quais ainda não haviamos falado:

    1° Teste da Razão (fizemos ele na última aula, mas irei formaliza-lo nesta)
    2° Como confirmar a otimálidade de uma solução?
    3° Problema ilimitada
    4° Problema inviável

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

  Vamos continuar o exercicio da última aula falando de um ponto de vista agora mais técnico:

    max z = 30 + 3 x1 - 5/2 F2

    F1 = 4 - 1 x1
    x2 = 6        - 1/2 F2
    F3 = 6 - 3 x1 -  1  F2

    x1,x2,F1,F2,F3 >= 0

    B = {F1,x2,F3} N = {x1,F2}

  Então vamos fazer mais um pivoteamento.
  O pivoteamento é composto de duas etapas:

    1° Escolhe-se uma variável de N para entrar B.
    2° Através do Teste da razão descobre-se quem de B vai entrar N.

  Vamos então iniciar o processo de pivoteamento:

  A variável que vai sair de N precisa ser aquela cujo crescimento beneficia o objetivo:

    max z = 30 + 3 x1 - 5/2 F2

  Somente o crescimento de x1 beneficia o objetivo, logo queremos x1.

  Agora precisamos de aprender o que é o teste da razão:

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

CONCEITO:
  Teste da Razão é o teste pelo qual comparamos dentre um conjunto de restrições
  que restrigem o crescimento de uma variável,
  qual delas restringe mais, ou seja, permite que essa variável cresça menos.

  Uma vez detectada essa restrição, podemos fazer uma variável crescer
  até o ponto máximo permitido por ela.
  Sabendo que essa restrição é a mais restringente temos certeza que não estaremos
  infringindo outras restrições ou saindo do nosso dominio de soluções.

  Quando a variável cresce até o ponto máximo que essa restrição permite,
  naturalmente uma outra variável que estava associada a essa restrição diminuí.

  No momento em que ela chega no crescimento máximo essa outra variável atingirá o valor 0.

  É neste ponto que geramos uma variável Não-Básica, quando ela assume o valor 0.

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

  Fazendo o teste da razão temos de encontrar
  as restrições afetadas pelo crescimento de x1:

  Se olharmos as 3 restrições:

    (1) F1 = 4 - 1 x1
    (2) x2 = 6        - 1/2 F2
    (3) F3 = 6 - 3 x1 -  1  F2

  Notamos que somente as restrições (1) e (3) são afetadas.
  (vale notar que se x1 tivesse o coeficiente positivo nelas ela não seria afetada,
  pois o crescimento dele não infringiria as restrições)
  (se não houvesse nenhuma restrição restringindo o crescimento de x1 teriamos um problema ilimitado!)

  Assim podemos calcular o teste da razão:

  Qual o crescimento máximo de x1 em (1)?

    4/1 = 4

  Qual o crescimento máximo de x1 em (2)?

    infinito, x1 não aparece nessa restrição.

  Qual o crescimento máximo de x1 em (3)?

    6/3 = 2

  Logo a restrição que será infringida mais rapidamente é a (3).

  Concluímos duas coisas:

    1° x1 ira crescer para o valor 2.
    2° A varíavel básica F3 associada a restrição 3
       deverá ser zerada e se tornara uma Não-Básica.

  E esse foi o fim do teste da razão.

  Com isso temos uma nova base:

    B = {x1,F1,x2} N = {F2,F3}

  E um novo ponto A, Note que mesmo sem saber o valor de x1 e x2 podemos saber
  desenhar o plano cartesiano:

    ^ x2
    |
    |
    |  restrição 2
    |------A
    |       \ restrição 3
    |        \
    |        |
    |        |
    |  ^     | restrição 1
    | /      |
    |/       |
    .--------------------> x1

  Como as folgas F2 e F3 são não básicas (ou seja zero) significa que o Ponto A
  se localiza encima de ambas as retas da restrição 2 e da restrição 3,
  ou seja na intercessão das duas como mostrado acima =].

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

  Algumas notas:
    1° A variável x1 não aparece na restrição 2 certo?
       Graficamente isso significa que x1 é paralelo à restrição 2.

    2° E se eu ignorasse r3 durante o pivoteamento, onde ficaria o ponto A?

    ^ x2
    |
    |
    |  restrição 2
    |------\-A
    |       \|restrição 3
    |        \
    |        |
    |        |
    |  ^     | restrição 1
    | /      |
    |/       |
    .--------------------> x1

  Ficaria sobre a intercessão da próxima restrição no caminho, no caso r1.

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

  Vamos atualiar nosso Dicionário para enchergar exatamente qual é o ponto A:

    max z = 30 + 3 x1 - 5/2 F2

    F1 = 4 - 1 x1
    x2 = 6          - 1/2 F2
    x1 = 2 - 1/3 F3 - 1/3 F2

    x1,x2,F1,F2,F3 >= 0

    B = {x1,F1,x2} N = {F2,F3}

  Atualizando Fica:

    max z = 36 - 7/2 F2 - 1 F3

    F1 = 2 + 1/3 F3 + 1/3 F2
    x2 = 6          - 1/2 F2
    x1 = 2 - 1/3 F3 - 1/3 F2

    x1,x2,F1,F2,F3 >= 0

    B = {x1,F1,x2} N = {F2,F3}

  Agora fica claro:

    x1 = 2
    x2 = 6

  Ponto (2,6)

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

  Agora vamos observar nossa Dicionário

  O objetivo está na forma padrão, e não possuí variáveis positivas certo?
  Logo crescer qualquer uma delas não irá beneficiar o objetivo.

  O que isso quer dizer?

  Quer dizer Atestado de Solução Ótima.

  Se todos as variáveis do objetivo não podem crescer, temos um atestado de otimalidade.

  Uma vez que voce tenha o atestado voce tem certeza de estar no ótimo.

  Com isso terminamos nosso exercicio.
  E já sabemos como operar o Simplex do inicio ao fim =].

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

  Para completar o entendimento da materia vamos tornar o simplex mais genérico.

  1° O que fazer quando uma de nossas variáveis for negativa?

  Basta substituíla por uma positiva com um sinal de menos na frente (essa é fácil né)

  2° O que fazer se o sinal da nossa variável não for limitado, pode ser positivo ou negativo?

  Essa é mais difícil. O macete é criar duas variáveis positivas, e substituir a variável original pela diferença das duas novas.

  3° O que fazer se o ponto (0,0) não for uma solução viável?
  Até agora só encontramos problemas onde (0,0) é viável,
  porém o simplex só funciona se voce partir de uma solução viável.

  O que fazer?
  Um macete é criar uma variável chamada de "Artificial" A1 na restrição impeditiva.
  De forma que ela torne o ponto (0,0) viável.

  Para eliminar essa variável A1 basta resolver o seguinte problema de mínimização:

    min A1

  De forma que quando A1 for igual à 0 voce poderá corta-lo da solução e resolver sua vida.
  Pois quando ele for 0 haverá um conjunto de variáveis básicas que satisfaz o problema original.

  Com base nele voce pode recomeçar o problema agora com o obejtivo original.

  É um macete inteligente, mas não acho que precisaremos usa-lo nos exercicios da materia, apenas na vida real.

  Com isso eu encerro a segunda aula sobre o Simplex.

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

  // Fim da aula!