Pesquisa operacional

Pesquisa Operacional

Paulo Roberto Maia

Conteúdo

1. Introdução

2. Problemas de PL

Problemas clássicos;

Mistura;

Investimentos;

Problema de corte;

Transporte;

Programação Multi-período,

Programação Inteira;

3. Solução de Problemas de PL

Método Gráfico;

Simplex;

Uso de Softwares.

4. Interpretação e Análise dos Resultados de Problemas de PL

Dualidade;

Análise Econômica;

Análise de Sensibilidade.

2

Introdução a Pesquisa

Operacional

3

Conceito

• Metodologia científica para o auxílio a tomada de decisão;

• Descreve um sistema organizado através de um modelo.

Etapas necessárias para estudar PO

• Formulação matemática do problema;

• Cálculo da solução;

• Análise dos resultados.

4

Exemplos de Problemas em PO

• Programação linear;

• Programação inteira;

• Programação não linear;

• Programação dinâmica;

• Simulação;

• Teoria das filas;

• Etc.

5

Termos utilizados em PO

• Métodos Determinísticos:

Trabalha com valores exatos.

• Métodos Estocásticos:

Os valores possuem uma distribuição de probabilidade.

• Solução Ótima:

O resultado obtido é a melhor solução.

• Solução Heurística:

O resultado obtido é um bom resultado, porém nem sempre é o

melhor.

6

Exemplo

Diferença entre solução ótima e heurística

O problema:

• Um vendedor precisa visitar 4 cidades distintas;

• Pretende viajar o menor número de quilômetros possível;

• É necessário percorrer todas as cidades e retornar a sua

origem.

E

60

Origem

80

90

40

70

A

D

40

70

50

B

20

30

C

7

Exemplo

Solução ótima

• Testa-se todas as possíveis rotas;

• Melhor rota: A – B – C – D – E – A;

• Total percorrido: 200 km;

• Para quatro cidades o número de combinações a serem

testados é 24;

• Se o número de cidades fosse 10, o número de combinações

seria 3.628.800;

• O número de combinações pode ser calculado por n!.

8

Exemplo

Solução heurística

• Regra: Viajar para a cidade mais próxima da que o viajante

se encontra no momento;

• Melhor rota: A – C – B – D – E – A;

• Total percorrido: 230 km;

• Nota-se que o esforço computacional seria bem menor

nesse caso.

9

Programação Linear

10

Programação Linear

• Uma das técnicas mais utilizadas na abordagem de

problemas em pesquisa operacional;

• Simplicidade do modelo envolvido;

• Disponibilidade de uma técnica de solução programável em

computador;

• É uma técnica de otimização;

• Ferramenta utilizada para encontrar o valor ótimo de uma

função nas quais tem-se diversas alternativas de escolha

sujeitas