Pesquisa Operacional - Fabiano Fortunato Teixeira dos Santos

PESQUISA OPERACIONAL
Fabiano F. T. dos Santos
Instituto de Matemática e Estatística
Origens da Pesquisa Operacional
O termo
pesquisa operacional é atribuído a A. P.
Rowe, que, em 1938 na Grã-Bretanha, coordenava
equipes para examinar a eciência de técnicas de
operações advindas de experimentos com
interceptação de radar.
Seção de Pesquisa
Operacional do Comando da Força Aérea de
Combate, com equipes envolvidas em problemas de
Em 1941, foi inaugurada a
operações de guerra (alocação eciente dos escassos
recursos).
Após o nal da guerra a PO evoluiu rapidamente na
Inglaterra e nos EUA.
Em 1947, foi implantado o projeto SCOOP (Scientic
Computation of Optimal Programs) no Pentágono, com o
objetivo de apoiar decisões de operações na força aérea
americana.
Nesse período, o matemático George Danting criou o método
simplex e implementou o nome programação linear.
Em 1952 foi fundada a sociedade americana de PO: ORSA;
em 1953 foram fundadas a sociedade inglesa de PO: ORS e a
sociedade americana de ciências e administração: TIMS.
Em 1957 foi realizada a primeira conferência internacional de
PO, na Inglaterra.
Em 1968 foi fundada a sociedade brasileira de PO: SOBRAPO.
Os trabalhos apresentados focavam diversas
situações.
Teoria de estoques
Substituição de equipamentos
Teoria de las
Teoria de jogos
Programação de tarefas em máquinas
Fluxo em redes etc
Desde 1960 a PO vem sendo aplicada em diversas
áreas.
Mineração, metalurgia exploração de petróleo e construção
civil.
Setores têxtil, famacêutico, bancário, de telecomunicações e de
transportes.
Denição de Pesquisa Operacional
A PO consiste na abordagem cientíca para tomada de
decisões.
A PO consiste na abordagem cientíca para solução de
problemas no gerenciamento de sistemas complexos.
Modelagem Matemática
A matemática tem uma importância fundamental na descrição
de fenômenos naturais, sociais, econômicos etc. O objetivo é
encontrar leis que regem estes fenômenos.
Essas leis dão origem aos modelos matemáticos. Um modelo é
um objeto abstrato que procura imitar as principais
características de um objeto real.
Em geral, um modelo matemático é uma representação
simplicada do problema real que está sendo estudado.
Um modelo deve ser sucientemente detalhado para captar os
elementos essenciais do problema, mas sucientemente
tratável por métodos de resolução.
Processo de modelagem
O que estudaremos em Pesquisa Operacional?
Ementa
♠ Problemas Clássicos de Programação Linear
♣ Solução Gráca de Problemas de Programação Linear
♥ Método Simplex
♦ Dualidade
X Problema do transporte
z Análise de sensibilidade
Referências Bibliográcas
X DE ANDRADE, E. L. Introdução à pesquisa operacional:
métodos e modelos para análise de decisão
FREITAS, G. L. A. Pesquisa operacional na tomada de
decisão: modelagem em Excel
X YANASSE, H. H. Pesquisa operacional-Modelagem e
algoritmos
PRADO, D. Programação linear
MOREIRA, D. A. Pesquisa operacional-Curso introdutório
X LIEBERMAN, G. J., HILLIER, F. S. Introdução à pesquisa
operacional
Atendimento
Quartas e sextas - 17:00 às 18:40
Avaliações
P1 em 16/04/2014
P2 em 28/05/2014
P3 em 11/07/2014
E (no decorrer do curso)
MF = 0, 3 · P1 + 0, 3 · P2 + 0, 3 · P3 + 0, 1 · E
Problemas de Mistura
Problemas de mistura consistem em combinar materiais obtidos na
natureza (ou restos de outros já combinados anteriormente) para
gerar novos materiais ou produtos com características convenientes.
Exemplo 1
Uma empresa deve produzir um tipo de ração para determinado
animal. Essa ração é produzida pela mistura de farinhas de três
ingredientes básicos: osso, soja e resto de peixe. Cada um desse
três ingredientes contém diferentes quantidades de dois nutrientes
necessários a uma dieta nutricional balanceada: proteína e cálcio.
O nutricionista especica as necessidades mínimas desses nutrientes
em 1 kg de ração: a ração deve ser composta de pelo menos 30%
de proteína e 50% de cálcio. Cada ingrediente é adquirido no
mercado com um certo custo unitário ($/kg). Na tabela a seguir,
os dados do problema são apresentados.
Dados do problema
Nutrientes
Proteína
Cálcio
Custos ($/kg)
Osso
0,2
0,6
0,56
Ingredientes
Soja
0,5
0,4
0,81
Peixe
0,4
0,4
0,46
Ração
0,3
0,5
O objetivo é: determinar em que quantidades os ingredientes
devem ser misturados de modo a produzir uma ração que satisfaça
às restrições nutricionais com o mínimo custo.
X Sejam x1 , x2 e x3 as quantidades, em kg, de osso, soja e peixe,
respectivamente.
X O custo da mistura é dado por
Z = 0, 56x1 + 0, 81x2 + 0, 46x3 .
X As restrições da composição são dadas por
0, 2x1 + 0, 5x2 + 0, 4x3 ≥ 0, 3 e 0, 6x1 + 0, 4x2 + 0, 4x3 ≥ 0, 5.
X Sabemos também, que
x1 + x2 + x3 = 1, x1 ≥ 0, x2 ≥ 0 e x3 ≥ 0.
O modelo matemático completo ca assim
Minimizar:
Z = 0, 56x1 + 0, 81x2 + 0, 46x3 .
O modelo matemático completo ca assim
Minimizar:
Sujeito a:
Z = 0, 56x1 + 0, 81x2 + 0, 46x3 .
0, 2x1 + 0, 5x2 + 0, 4x3 ≥ 0, 3
0, 6x1 + 0, 4x2 + 0, 4x3 ≥ 0, 5
x1 + x2 + x3 = 1
x1 ≥ 0, x2 ≥ 0 x3 ≥ 0.
Neste modelo, os objetos envolvidos têm nome:
X x1 , x2 e x3 são as variáveis de decisão.
X Z é a função objetivo.
X As três inequações e a equação após a função objetivo são as
restrições de especicação e disponibilidade.
Problemas de Transporte
Esses problemas referem-se, por exemplo, ao transporte ou
distribuição de produtos dos centros de produção aos mercados
consumidores de modo que o custo total de transporte seja o menor
possível. Os produtos podem ser: petróleo, máquinas, produção
agrícola, energia elétrica etc.
Exemplo 2
Um companhia distribuidora de bebidas tem dois centros de
produção (Araraquara e São José dos Campos) e três mercados
consumidores principais (São Paulo, Belo Horizonte e Rio de
Janeiro). O custo unitário (em R$) de se transportar uma unidade
de um dado produto de cada centro de produção a cada mercado
consumidor é dado na tabela a seguir. Nessa tabela também são
apresentadas as demandas de cada mercado e quantidade máxima
disponível do produto em cada centro de produção.
Dados do problema
Centro de produção SP (1)
Araraquara (1)
S. J. Campos (2)
Demanda dos mercados
4
11
500
Mercado
BH (2)
2
7
400
RJ (3)
5
4
900
Suprimento disponível
800
1000
O objetivo é: determinar em que quantidades o produto deve ser
enviado para cada destino com o mínimo custo.
X Seja xij a quantidade do produto a ser enviada do centro de
X
X
X
X
produção i (i=1,2) ao mercado j (j=1,2,3).
O custo em transportar o produto dos centros de produção aos
mercados é dado por
Z = 4x11 + 2x12 + 5x13 + 11x21 + 7x22 + 4x23 .
A quantidade que pode ser transportada não pode ultrapassar
a disponibilidade do produto no centro de produção:
x11 + x12 + x13 ≤ 800 e x21 + x22 + x23 ≤ 1000.
As demandas dos mercados devem ser atendidas:
x11 + x21 = 500, x12 + x22 = 400 e x13 + x23 = 900.
Além disso,
x11 ≥ 0, x12 ≥ 0 x13 ≥ 0, x21 ≥ 0, x22 ≥ 0 e x23 ≥ 0.
O modelo matemático completo ca assim
Minimizar:
Z = 4x11 + 2x12 + 5x13 + 11x21 + 7x22 + 4x23 .
O modelo matemático completo ca assim
Minimizar:
Sujeito a:
Z = 4x11 + 2x12 + 5x13 + 11x21 + 7x22 + 4x23 .
x11 + x12 + x13 ≤ 800
x21 + x22 + x23 ≤ 1000
x11 + x21 = 500
x12 + x22 = 400
x13 + x23 = 900
x11 ≥ 0, x12 ≥ 0, x13 ≥ 0, x21 ≥ 0, x22 ≥ 0, x23 ≥ 0,
onde
X xij , i = 1, 2; j = 1, 2, 3 são as variáveis de decisão.
X Z é a função objetivo.
X As oito inequações e as três equações após a função objetivo
são as restrições de especicação e disponibilidade.
Nós somos aquilo que fazemos repetidamente.
Excelência, então, não é um modo de agir, mas um
hábito.
Aristóteles