PO - 05/03/2013

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

  Estas aulas tomarão como base as aulas dos professores:

    Prof. Alexandre Salles da Cunha
      e-mail: [email protected]
      site: www.dcc.ufmg.br/~acunha/DCC035/2012_2

    Prof. Geraldo Robson Mateus
      e-mail:
      site: www.dcc.ufmg.br/~

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

  Livro Texto:
    Programação Linear e Otimização combinatória: Modelos e Algoritmos, Ed. Campus, Primeira Edição, 2000.

  Literatura complementar disponível no site do prof. Alexandre.

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

  Primeira aula Introdução:

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

  Otimização: Maximizar ou Minimizar um objetivo.

CONCEITO:
  Um Objetivo ou função Objetivo em PO é descrito como uma equação do tipo:

    z = f(x)

  onde x é um vetor de matriz composto pelas variáveis x1,x2,x3,...,xn
  Ou seja, uma equação qualquer.

  E z é o valor atual dessa equação.

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

  Problema Exemplo de Máximização:

  Queremos fabricar dois produtos, com dois recursos seguindo a tabela:

         r1     r2    lucro
    p1 - 3      5     280
    p2 - 5      2     220
    disp 10000  9000
  - (disp = disponibilidade dos recursos)

  Objetivo maximizar o lucro.

  função objetivo = 280 p1 + 220 p2

  Restrições:

    3 p1 + 5 p2 <= 10000
    5 p1 + 2 p2 <= 9000

  Ou seja, a produção de p1 e de p2 não pode gastar mais recursos do que os disponíveis.

  Geralmente adicionamos uma última restrição: p1, p2 >= 0 (apesar de ela ser meio obvia)

  Como o exemplo é simples podemos desenhar um plano cartesiano contendo as restrições, elas são retas nesse plano.

  (porém não vou conseguir desenhar isso bem em ASC ART)

  p1
  |     \ restrição 1
  |      \
  |       \
  |--------\-------- restrição 2
  |         \
  |          \
  |           \
  .____________\_____ p2

  Ou seja duas retas que se cruzam em algum ponto
  (obviamente o desenho ficou pessimo =P)

  A área que nos interessa é a área onde ambas as restrições são respeitadas.
  Ou seja como temos o problema de <= é a área a esquerda e abaixo das retas:

  p1
  |
  |--------- restrição 2
  |         \
  |          \ restrição 1
  |           \
  .____________\_____ p2

  E podemos expressar nosso objetivo como um vetor, que indica o seu sentido de crescimento:

  p1
  |
  |--------- restrição 2
  |         \
  |  ^       \ restrição 1
  | /         \
  ./___________\_____ p2

  O que iremos aprender, principalmente nas primeiras aulas é:

  1) Como denotar uma solução desse problema e entender o que esse ponto representa sem fazer o desenho.
  2) Como caminhar pelo problema, seguindo o vetor sem desenhar o vetor.
  3) O que acontece se as restrições permitirem uma otimização infinita, ou não permitirem nenhuma solução?

  4) Aprender a identificar soluções ótimas.

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

  Entendendo isso podemos aprender diferentes algoritmos para resolver esse e outros problemas.
  Muitos deles não podem ser desenhados como planos cartesianos, mas podem ser desenhados de outras formas,
  alguns exigem que as variáveis sejam inteiras, outros não.

  Ou seja, durante o decorrer do curso nos vamos estudar muitos algoritmos para muitos problemas.

  Etapas do curso:

    1) Entender o modelo + método simplex (método mais genérico, não exatamente o mais simples)
    2) Estudo de Algoritimos (estudar vários métodos usados para diferentes problemas)
    3) Estudo de Heurísticas e macetes para resolver problemas mais complicados.

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

  Otimização linear é um problema NP Polinomial.
  Otimização linear inteira é NP Difícil.
  Existem outros que são NP-Completo

  Vamos trabalhar no inicio só com a otimização linear,
  que é quando em nenhuma equação aparece uma variável elevado à 2 ou 3 etc,
  e nehuma variável se multiplica por outra.

  Na parte de Heurísticas e Macetes vamos falar um pouco dos problemas com variáveis lineares inteiras.
  (as inteiras são um pouco mais complicadas)

  Não iremos falar dos demais problemas.

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

  Para a próxima aula iremos começar a entender nosso modelo matemático
  que iremos usar para representar uma grande gama de problemas.

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

  // Fim da aula!