PO - 12/03/2013

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

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

  Aula 3: Introdução ao Método Simplex.

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

  Na aula de hoje vamos começar a explicar o Método Simplex =].
  // De simples ele não tem nada, mas ele é genérico.

  Para isso vamos partir do problema de maximização abaixo:

    max 3 x1 + 5 x2

    1 x1 + 0 x2 <= 4
    0 x1 + 2 x2 <= 12
    3 x1 + 2 x2 <= 18

    x1,x2 >= 0

  Temos 3 restrições e geramos portanto 3 retas no plano cartesiano:
  (além das de não negatividade de x1 e x2)

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

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

  Preparando para utilizar o Simplex:

  1° Forma Padrão:

    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

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

  2° Denotar uma solução inicial com uma escolha de V. Básicas:

  Seja F1, F2 e F3 nosso conjunto de Variáveis básicas:

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

  // B = variáveis básicas, N = Variáveis Não Básicas.

  Isso força x1 e x2 à serem 0, denotando o ponto Atual A=(0,0).

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

  Esse ponto está em nosso dominio de solução e é portanto válido.

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

  3° Preparando nossas equações:

    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

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

  Porque eu fiz essa mudança? Repare que tem as mesmas equações de antes.

  Desse jeito fica fácil ver que:

    F1 = 4  + 0 + 0
    F2 = 12 + 0 + 0
    F3 = 18 + 0 + 0

  Pois x1 e x2 atualmente tem o valor 0.

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

  Método Simplex Caminhando pelo Dominio:

  Partindo do ponto atual:

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

  Queremos seguir o vetor objetivo:

    max 3 x1 + 5 x2

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

  E encontrar um outro ponto, mais próximo do ótimo.

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

  1° Entendendo o Objetivo:

  x1 e x2 tem atualmente o valor 0 correto?

  Se eu aumentar seu valor, eu irei mudar o ponto A no plano cartesiano.

  Para saber qual direção o vetor aponta, basta eu ver quais variáveis
  que ao crescerem beneficiam o objetivo.

  No objetivo se eu aumentar em uma unidade x1, ganho 3 unidades de melhora.
              se eu aumentar em uma unidade x2, ganho 5 unidades de melhora.

  Escolherei assim x2 para aumentar, pois se aproxima mais do vetor objetivo.

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

  2° Implicações de aumentar a variável x2:

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

  a) Ao aumentar x2 o ponto A vai subir pelo eixo de x2.

  b) Ao aumentar x2 ele deixará de pertencer ao conjunto de Não-Básicas.

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

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

  c) Se ele crescer de mais, ele irá sair do dominio de solução.
     Se ele crescer de mais, ele irá infringir a restrição 2.

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

  3° Qual o melhor valor para x2?

  a) O aumento de x2 beneficia o objetivo.
  b) O aumento máximo de x2 é limitado pela restrição 2.

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

  Escolhamos portanto para o ponto A o ponto no justo sobre a restrição 2.

  Dessa forma obtivemos o aumento máximo desta variável fixando A = (6,0)

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

  Método Simplex - Implicações de se mudar valores.

    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

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

  a) x2 agora cresceu o máximo que podia, pois quase infringiu a restrição 2.

  b) Para a restrição não ser infringida F2 é obrigado a diminuir proporcionalmente.

  c) Como F2 representa a folga da restrição, o crescimento máximo de x2 força F2 à 0.

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

  Método Simplex - Escolhendo o novo Conjunto de Variáveis Básicas.

  F2 é agora uma variável no valor 0.

  x2 é agora uma variável com um valor tão grande quanto permitido.

  Façamos então o Pivoteamento:

CONCEITO:
  Pivoteamento é a troca de uma variável não-básica por uma básica,
  com o propósito de se apróximar do objetivo proposto.

  Antes tinhamos:
    B = {F1,F2,F3} N = {x1,x2} -> A = (0,0)

  Agora temos:
    B = {F1,x2,F3} N = {x1,F2} -> A = (0,6)

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

  Método Simplex - Atualizando Tabela de Valores:

    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

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

  a) Isolando x2 na restrição 2:

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

  b) Removendo x2 de todos os demais lugares:

    max 30 + 3 x1 - 5/2 F2

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

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

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

  // Exercicio - Confiram minhas contas =], foi só substituição de variáveis.

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

  Método Simplex - Avaliando Resultados da Iteração

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

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

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

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

  Pode-se observar que agora nosso objetivo tem o valor 30.

  Pode-se observar que F1 tem o valor 4.
                   que x2 tem o valor 6.
                   que F3 tem o valor 6.

                   que as demais variáveis tem o valor 0.

  Implicando que A = (0,6)

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


  Lembrando que nosso vetor objetivo aponta na diagonal: 3 x1 + 5 x2

  Fica claro que não estamos no ponto ótimo.

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

  Método Simplex - Fim da Introdução.

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

  // Antes de acabar a aula alguns nomes:

CONCEITO:
  Dicionário é o nome dado ao conjunto de informações que temos sobre o problema no caso acima:

    max 3 x1 + 5 x2

    1 x1 + 0 x2 + F1 = 4   linha vertical
    0 x1 + 2 x2 + F2 = 12  linha horizontal
    3 x1 + 2 x2 + F3 = 18  linha diagonal

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

CONCEITO:
  Matriz tecnológica é um outro nome dado ao conjunto de restrições justas do problema:

    1 x1 + 0 x2 + F1 = 4   linha vertical
    0 x1 + 2 x2 + F2 = 12  linha horizontal
    3 x1 + 2 x2 + F3 = 18  linha diagonal

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

  // Fim da aula!