PO - 07/03/2013

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

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

  Aula 2 - Modelagem de Problemas de Prog. Linear

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

  Na aula de hoje vamos aprender a montar um modelo de Prog. Linear.

  Nosso modelo simples será semelhante ao criado na aula passada:

  "  Objetivo maximizar o lucro.
  "
  "  função objetivo = 280 p1 + 220 p2
  "
  "  Restrições:
  "    3 p1 + 5 p2 <= 10000
  "    5 p1 + 2 p2 <= 9000

  Vamos começar conceituando os jargões que usaremos na materia:

CONCEITO:
  PPL é sigla para Problema de Programação Linear.

CONCEITO:
  Função objetivo é uma função à ser maximizada ou minimizada.

    z = f(x) = cTx

  cTx significa vetor c transposto multiplicado pelo vetor x.

  Resultando em algo como:

    z = c1 x1 + c2 x2 + c3 x3 + c4 x4

  Por fim z é só o valor final da soma da equação
  que deverá ser maximizado ou mínimizado.

CONCEITO:
  Restrições são o conjunto de regras que limitam a flexibilidade das variáveis.

  No caso do plano cartesiano seriam as retas.

CONCEITO:
  O Dominio do problema é o espaço no plano cartesiano, que não infringe
  nenhuma das restrições, incluindo as de não negatividade das variáveis.

  O Dominio do Problema também pode ser chamado de Poliedro.

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

CONCEITO:
  Formato Padrão do modelo, é o formato que contém apenas restrições de igualdade.
  E onde todas as variáveis são maiores ou iguais a 0.

  Como transformar o exemplo da aula anterior para o formato padrão?

  "  max 280 p1 + 220 p2
  "
  "  Restrições:
  "    3 p1 + 5 p2 <= 10000
  "    5 p1 + 2 p2 <= 9000

  Basta adicionar as variáveis de Folga:

    max 280 p1 + 220 p2

    3 p1 + 5 p2 + F1 = 10000
    5 p1 + 2 p2 + F2 =  9000

    p1,p2,F1,F2 >= 0

  E voilá =].

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

  Abaixo vamos falar de um conceito importante.

  Usaremos ele para descrever soluções em nosso Poliedro.

  E com ele aprenderemos a caminhar pelo Poliedro em busca da sol. ótima.

CONCEITO:
  Variáveis Básicas ou Variáveis de Decisão são as variáveis
  com valor atualmente diferente de 0 no nosso PPL.

  No exemplo acima podemos dizer que F1 = 10000 e F2 = 9000.
  Logo todas as demais são 0.

  Assim F1 e F2 são Variáveis Básicas, e elas forçam p1 e p2 à serem = 0.

  Notas importantes:
    nota1 - Uma V. Básica por Restrição do problema.

    nota2 - A escolha atual de variáveis básicas faz p1 e p2 serem 0.
            Logo essa escolha denota o ponto (0,0) no plano cartesiano.

            Todo conjunto de variáveis básicas denota um ponto do problema.

    nota3 - Mudando a escolha das variáveis básicas, podemos obter outros pontos.

            Exemplo: seja F1 = 10000 e p2 = 4500 e as demais = 0.
            Agora o ponto é (0,4500) no plano cartesiano.

    nota4 - Todo ponto, obtido pela escolha
            de variáveis básicas são na verdade vertices.

  Ou seja se lembrarmos do plano cartesiano da aula passada:

    p1
    |
    |--------- restrição 2
    |         \
    |          \ restrição 1
    |           \
    .____________\_____ p2
  (0,0)        (0,4500)

  Ambos os pontos que encontramos são de fato vertices do desenho.

  Exercicio: Encontrem o vertice denotado pelo conjunto Básico: p1, p2
  (ou seja com p1 e p2 diferentes de 0 e todo o resto igual à 0)

  Acho que vai ser uma ótima idéia pra melhorar o entendimento.


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

  // Agora vamos dar um exemplo de um PPL típico:

  Seja o problema das ligas metálicas:

  Veja a tabela de ligas:

                Liga de alta resistência | liga de baixa resistencia | Disponibilidade de Insumos
    Cobre     |           0,2                        0,5                        16 ton
    Zinco     |           0,3                        0,25                       11 ton
    Chumbo    |           0,5                        0,25                       15 ton

    Lucro/ton |           5000                       3000


  Agora vamos modelar o problema seguindo 3 passos de modelagem:

  Passo 1: Quais são as nossas variaveis?

    Vamos escolher duas variáveis, B e A,
    que representam a quantidade em toneladas da liga de baixa e alta resistencia respectivamente.

  Passo 2: Qual é o nosso objetivo?

    A função objetivo é o lucro, ou seja:

      max 5000 A + 3000 B

  Passo 3: Precisamos agora então modelar as restrições.

    - A produção não pode ser menor que 0 logo:

        A,B >= 0

    - Não pode-se exceder a capacidade em estoque dos insumos logo:

        0,2 A + 0,5  B <= 16 (cobre)
        0,3 A + 0,25 B <= 11 (zinco)
        0,5 A + 0,25 B <= 15 (chumbo)

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

  Agora podemos escrever de forma completa nosso problema:

    max 5000 A + 3000 B

    0,2 A + 0,5  B <= 16
    0,3 A + 0,25 B <= 11
    0,5 A + 0,25 B <= 15

    A, B >= 0

  E já aprendemos colocar na forma padrão certo?

  // E para já irem acostumando, vou trocar A e B por x1 e x2, porque são os nomes mais usados.

  Então:

    max 5000 x1 + 3000 x2

    0,2 x1 + 0,5  x2 + F1 = 16
    0,3 x1 + 0,25 x2 + F2 = 11
    0,5 x1 + 0,25 x2 + F3 = 15

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

  Fim da modelagem do problema.

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

  Pontos a ter em mente quando for modelar:

    As vezes a tabela do problema não evidencia quais variáveis usar.

    Pode acontecer de voce escolher um conjunto de variáveis que geram restrições não lineares.
    Nesse caso o jeito é escolher outras variáveis.

    Pode acontecer de uma coluna na tabela gerar multiplas variáveis.
    Por exemplo suponha voce tem a variável de produção de um produto 1: p1
    Porém na seu problema envolve a produção do produto durante 3 meses.

      Ou seja: p11, p12 e p13

    Porque poderão ser produções diferentes durantes estes meses.

    Observem os exercicios em sala, ou pratiquem voces mesmos para pegar os macetes nisso.

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

  // Fim da aula!

  // Nessa aula o professor nos aconselhou a fazer esses exercicios em casa.