Pesquisa Operacional

Universidade Federal de Viçosa Departamento de Informática
Prof. Mauro Nacif Rocha Prof. Luiz Aurélio Raggi Prof. Heleno do Nascimento Santos
Fevereiro de 2005
INF-280 Pesquisa Operacional I
Conteúdo:
Programação Linear Programação em Redes
ASPECTOS GERAIS DA PESQUISA OPERACIONAL
1
EXEMPLOS DE ALGUNS PROBLEMAS COMUNS DA P.O
5
PARTE I – PROGRAMAÇÃO LINEAR
8
EXEMPLOS DE MODELOS PARA ALGUNS PROBLEMAS CLÁSSICOS DE PROGRAMAÇÃO LINEAR
13
PROBLEMAS PARA MODELAGEM
17
SOLUÇÃO DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR – INTERPRETAÇÃO GEOMÉTRICA
19
CASOS ENCONTRADOS NA RESOLUÇÃO GRÁFICA
23
O MÉTODO SIMPLEX
27
MODELO MATEMÁTICO E FORMA PADRÃO DE UM PPL
27
DEFINIÇÕES BÁSICAS
30
TEOREMAS FUNDAMENTAIS
35
O ALGORITMO SIMPLEX
37
ALGORITMO SIMPLEX – MÉTODO DAS DUAS FASES
47
ELEMENTOS DE PÓS-OTIMIZAÇÃO
53
MUDANÇA NO VETOR C
5
MUDANÇA NO VETOR B
56
DUALIDADE
57
PARTE I – PROGRAMAÇÃO EM REDES
63
INTRODUÇÃO
63
INTRODUÇÃO À TEORIA DE GRAFOS
65
UMA BREVE HISTÓRIA DA TEORIA DOS GRAFOS
65
CONCEITOS BÁSICOS DA TEORIA DE GRAFOS
68
FLUXOS EM REDE
74
FORMULAÇÃO GERAL (CLÁSSICA) PARA PROBLEMAS DE FLUXOS EM REDE
75
O PROBLEMA DE FLUXO DE CUSTO MÍNIMO (PFCM)
79
O PROBLEMA DE TRANSPORTE (PT)
87
O PROBLEMA DE DESIGNAÇÃO (PD)
94
O PROBLEMA DO CAMINHO MAIS CURTO (PCMC)
100
O PROBLEMA DE FLUXO MÁXIMO (PFM)
104
O PROBLEMA DA ÁRVORE GERADORA MÍNIMA (AGM)
1
O PROBLEMA DE STEINER EM GRAFOS NÃO DIRECIONADOS
115
REDES PERT / CPM
117
REDES PERT
117
REDES PERT/CPM
121
Aspectos Gerais da Pesquisa Operacional
1. Introdução e Histórico
Durante a I Guerra Mundial, líderes militares da Inglaterra e dos Estados Unidos requisitaram um grupo de cientistas de diversas áreas de conhecimento para analisarem alguns problemas militares. Entre esses problemas citam-se: desenvolvimento, operação e localização de radares, gerenciamento e controle de navios de apoio, planejamento de ataques aéreos, lançamento de bombas contra submarinos, defesa das comunidades européias contra ataques aéreos inimigos, abastecimento de tropas com