Cap 08 - Pesquisa Operacional

Prévia do material em texto

Pontifícia Universidade Católica de Goiás
Departamento de Engenharia
Curso de Graduação em Engenharia de Produção
ENG 1090 – Introdução à Engenharia de Produção
Prof. Gustavo Suriani de Campos Meireles, M.Sc.
 Pesquisa Operacional (PO) é a aplicação de métodos 
científicos a problemas complexos para auxiliar no 
processo de tomada de decisões, tais como projetar, 
planejar e operar sistemas em situações que requerem 
alocações eficientes de recursos escassos
 Mais recentemente, tem sido chamada de ciência e 
tecnologia de decisão
 Apresenta os seguintes componentes:
 Científico – os problemas de decisão são tratados em 
objetivos e condições (restrições) para atingi-los
 Matemático – utilizado para a resolução dos problemas
 Tecnológico – são as ferramentas de software e hardware
2
 O termo no Brasil é uma tradução direta do inglês 
operational research; em Portugal é investigação 
operacional; nos países de língua hispânica é 
investigación operativa
 Na 2ª Guerra Mundial as organizações enfrentaram 
decisões administrativas de complexidade inédita, 
com enormes quantidades de força de trabalho, 
suprimentos, aviões, navios, materiais e outros
 Então os comandos militares britânico e norte-
americano convocaram cientistas para lidar com estes 
e outros problemas táticos e estratégicos com o 
objetivo de realizarem pesquisas sobre operações
(militares)
3
 A guerra acabou e a PO voltou-se, no início dos anos 
1950, para as universidades, indústrias, agências 
governamentais e firmas de consultoria
 Associações e sociedades científicas de PO foram 
fundadas no mundo todo, podendo-se destacar o 
Informs (instituto; http://www.informs.org) e a IFORS 
(federação internacional; http://www.ifors.org)
 No Brasil as atividade tiveram início na década de 
1960; o 1º simpósio brasileiro foi realizado em 1968 no 
ITA, em São José dos Campos, SP; logo depois foi 
fundada a Sociedade Brasileira de Pesquisa 
Operacional (SOBRAPO; http://www.sobrapo.org.br)
4
 Devido ao seu caráter multidisciplinar, a PO tem 
contribuições em praticamente todos os domínios da 
atividade humana, da Engenharia à Medicina, 
passando pela Economia e Gestão Empresarial
 Tem sido aplicada nas mais diversas áreas de 
indústrias e organizações de serviço (públicas e 
privadas), como:
 Agricultura, alimentação, atacadistas, automóveis, 
aeronáutica, coleta de lixo, computadores, bancos, 
biblioteca, defesa, educação, eletrônica, energia, 
esportes, finanças, farmacêutica, hospitais, metal-
mecânica, metalurgia, mineração, mísseis, móveis ...
5
 No âmbito da Engª de Produção, as principais 
aplicações referem-se às atividades de produção e 
logística
 Em função da complexidade e incertezas que 
envolvem planejamento, programação e controle da 
produção bem como planejamento e operações 
logísticas, a PO tem tratado esses problemas com certa 
reserva
 Entretanto, inúmeras aplicações de sucesso podem ser 
encontradas em livros e periódicos científicos; para tal, 
serão ilustrados a seguir alguns desses exemplos em 
grandes empresas e organizações de diversos setores 
6
1. Kellog – foco: tomada de decisão envolvendo 
produção e distribuição de cereais. Problema: onde 
produzir e como transportar das fábricas para os 
centros de distribuição. Resultado: redução nos 
custos de produção, estocagem e distribuição em 
US$ 4,5 milhões por ano
2. Ford – foco: dimensionamento e gerenciamento de 
testes de veículos protótipos. Problema: minimizar 
nº de veículos construídos para os testes dentro dos 
prazos estabelecidos. Resultado: redução em cerca 
de 25% do tamanho da frota necessária de 
protótipos, com economia de US$ 250 milhões/ano
7
 Aplicando método científico, a PO envolve a 
observação e definição de um sistema real e a 
construção de um modelo
 Um modelo é um veículo para se chegar a uma visão 
bem estruturada da realidade, ou seja, ele é uma 
representação simplificada de um sistema ou objeto 
real; pode ser concreto (protótipo de avião) ou 
abstrato (matemático ou de simulação)
 Vantagens:
 Melhoria da compreensão do sistema ou objeto foco
 Análise de alternativas de configurações (cenários)
 Possibilidade de experimentação
9
 Um processo simplificado da abordagem de solução 
de um problema usando a modelagem matemática 
pode ser observado abaixo
10
Fig. 8.1
 Os modelos de programação matemática 
(otimização) têm um papel destacado na PO
 Podem representar alternativas ou escolhas, por 
exemplo, como variáveis de decisão (quanto produzir 
de cada produto por período de tempo), e procura 
por valores dessas variáveis de decisão que 
minimizam ou maximizam funções dessas variáveis, 
chamadas funções objetivos, sujeitas a restrições 
sobre os possíveis valores dessas variáveis de decisão
 Então, as funções objetivos podem ser minimizadas 
ou maximizadas, sujeitas a restrições 
12
 Existem diversas técnicas e métodos de resolução 
disponíveis na literatura de PO
 No caso de modelos de otimização, um método 
ótimo é aquele que gera a melhor solução possível
 Para modelos de programação linear, métodos 
baseados no algoritmo simplex são mais adequados; 
para programação discreta o algoritmo branch-and-
bound
 Alguns softwares também são usados: CPLEX, Gino, 
Lindo, GAMS – para otimização, Arena, AutoMod, 
ProModel, Simul8 – para simulação
14
 Têm sido amplamente utilizados em grande 
diversidade de problemas de Engª de Produção:
 Planejamento da capacidade e força de trabalho
 Produção de grãos
 Produção de rações animais
 Corte de bobinas de papel
 Produção, armazenagem e distribuição de produtos 
agroindustriais
 Programação de projetos
 Gestão financeira (planejamento de fluxo de caixa)
 Meio ambiente (tratamento de águas residuárias)
 Composição granulométrica de materiais, ...
15
 Uma fábrica produz dois produtos (1 e 2), e possui 2 
linhas de produção, sendo uma para cada produto.
A linha 1 tem capacidade para produzir 60 produtos 
do tipo 1 por semana, enquanto a linha 2 pode 
produzir 50 produtos do tipo 2 por semana
Cada unidade do produto 1 requer 1 hora de trabalho 
para ser produzida, e cada unidade do produto 2 
requer 2 horas; estão disponíveis 120 horas/semana
Se os lucros unitários dos produtos 1 e 2 são R$ 20,00 
e R$ 30,00, respectivamente, quanto produzir de 
cada produto por semana para maximizar o lucro
16
Formulação do modelo:
Variáveis:
X1 = produção do prod 1/ semana
X2 = produção do prod 2/ semana
Função objetivo:
Maximizar lucro = 20X1 + 30x2
Restrições:
Capacidade da linha 1) X1  60
Capacidade da linha 2) X2  50
Horas disponíveis) 1X1 + 2X2  120
Não-negatividade) X1  0 e X2  0 17
Resolvendo pelo gráfico:
Resposta:
X1 = 60, X2 = 30
Lucro máximo = R$ 2.100
 Também têm sido utilizados com sucesso em uma 
grande diversidade de problemas, incluindo:
 Produção de lotes de bebida
 Balanceamento de linha de montagem
 Localização de centros de distribuição de produtos
 Distribuição de combustíveis em postos
 Corte de chapas em fábrica de móveis
 Arranjo de caixas em páletes e contêineres
 Atribuição de professores, cursos e salas de aula
 Programação de calendários em torneios esportivos
 Roteiro de clientes a serem visitados por um vendedor
 Coleta de lixo nas ruas de uma cidade, ...
18
 Uma montadora de veículos está iniciando as suas 
operações no país, construindo duas fábricas: uma na 
Bahia e outra em São Paulo
 A empresa está estudando a forma de distribuição de 
seus carros para as diversas revendas, localizadas nos 
estados de GO, RJ, MG, PR, SC e RS, que minimize o 
custo total de distribuição
 As capacidadesinstaladas de cada uma das fábricas, as 
demandas das revendas, bem como os custos unitários 
de transporte entre fábricas e revendas estão na Figura 
seguinte 
19
20
Variáveis de decisão:
X13 – carros da BA para MG
X14 – carros da BA para o RJ
X15 – carros da BA para GO
X23 – carros de SP para MG
X24 – carros de SP para o RJ
X26 – carros de SP para o PR
X27 – carros de SP para SC
X28 – carros de SP para o RS
X34 – carros de MG para o RJ
X35 – carros de MG para GO
X78 – carros de SC para o RS 
 Função objetivo:
MIN 25X13 + 30X14 + 40X15 + 20X23 + 15X24 + 20X26 + 
35X27 + 50X28 + 20X34 + 20X35 + 20X78
 Restrições de fluxo: 
no_1) – X13 – X14 – X15 ≤ – 500
no_2) – X23 – X24 – X26 – X27 – X28 ≤ – 600
no_3) X13 + X23 – X34 – X35 ≤ 200
no_4) X14 + X24 + X34 ≤ 350
no_5) X15 + X35 ≤ 150
no_6) X26 ≤ 300
no_7) X27 – X78 ≤ 150
no_8) X28 + X78 ≤ 250 21
 Resolvendo este 
problema pelo 
software LINDO:
22
 Programação não-linear:
As funções objetivo e restrições são não lineares, a 
exemplo do planejamento da produção de gasolina e 
fluídos de freios; de uso menos frequente
 Programação dinâmica: 
Normalmente decompõe o problema em problemas 
menores e mais simples de serem resolvidos; caso 
típico de situações que apresentam sequencia de 
decisões em estágios sucessivos: programação de 
tarefas em máquinas, problema de caminho mínimo
23
 Teoria das filas (relação entre demanda e atrasos):
De aplicação particular em sistemas de serviços: 
bancos, supermercados, correios, postos de gasolina; 
em geral, os usuários desses sistemas se deslocam até 
os servidores para obter algum tipo de serviço
 Controle de estoques (política de reposição): 
Um estoque é um bem usado para satisfazer uma 
demanda futura; o objetivo é definir quanto e quando 
pedir para repor o estoque, da forma mais econômica 
possível: lote econômico de compra ou de fabricação
24