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