Aula 5 - Pesquisa Operacional

Prévia do material em texto

Disciplina: Seminários Integrados em
Engenharia de Produção
Aula 5: Pesquisa Operacional
Apresentação
Hoje veremos um tema de grande relevância para o futuro engenheiro de produção: pesquisa operacional.
Dentre outros assuntos, você terá a oportunidade de estudar temas como:
Modelos matemáticos analíticos e numéricos;
Problema de programação linear (PPL);
Conceitos fundamentais de teoria das �las; e
Matriz de probabilidades de transição — as conhecidas cadeias de Markov.
Assim, nesta quinta aula, trataremos das principais técnicas de pesquisa operacional associadas à engenharia de produção.
Aqui serão estudados não só as de�nições dos principais modelos matemáticos, mas também alguns exemplos de cunho
prático.
Objetivos
Identi�car os principais modelos matemáticos empregados para resolução de problemas em engenharia de produção;
Compreender os principais conceitos e procedimentos para resolução de problemas de programação linear;
Aplicar os conceitos de teoria das �las e processos markovianos em situações-problema associadas à engenharia de
produção.
Modelos Matemáticos
A pesquisa operacional apresenta técnicas e ferramentas de resolução que se baseiam na observação e de�nição de um sistema
real, e a construção de um modelo cientí�co.
Um aspecto relevante que você deve compreender é que os modelos precisam ser, ao mesmo tempo:
Detalhados: para captar os elementos essenciais e representativos do sistema real.
Simples: para que possam ser analisados e tratados por métodos de análise e resolução conhecidos
Assim, com base nas características dos sistemas reais estudados em engenharia de produção, há um conjunto de modelos
matemáticos, os quais são classi�cados de acordo com a formulação matemática adotada.
Segundo Neummann (2013), de modo geral, os modelos matemáticos utilizados em engenharia de produção se dividem em duas
categorias principais, são eles:
Clique nos botões para ver as informações.
São baseados em um conjunto de fórmulas e/ou algoritmos computacionais utilizados para gerar métricas de desempenho
a partir de parâmetros do modelo.
Modelos analíticos 
São modelos ou aplicações para imitar o comportamento de um sistema real com o uso do computador por meio de
experimentos. Trata-se de modelos bastante poderosos, sendo normalmente empregados para a análise de sistemas
complexos.
Modelos numéricos ou de simulação 
Além da duas categorias principais, podemos ainda dividir os métodos matemáticos em outras duas categorias, veja quais são:
Baseiam seus resultados em probabilidades (que podem ser �xas ou variantes com o tempo). Tais métodos apresentam um
comportamento dinâmico. Dentre seus exemplos, destacam-se técnicas como a teoria dos jogos, previsão e séries
temporais, teoria das �las, simulação de eventos discretos e a teoria da decisão (com incerteza).
Métodos estocásticos 
Tem-se um conjunto de entradas conhecido, do qual se obtém um único conjunto de saída. Em geral, emprega modelos
analíticos envolvendo técnicas como programação linear, programação não linear, �uxos de redes e programação
multiobjetivo.
Métodos determinísticos 
Vamos aplicar esses conceitos em dois exemplos, um envolvendo modelagem matemática e o outro versando sobre simulação
de eventos discretos.
Exemplo 1 (ENADE / 2005)
Uma pequena empresa fabrica apenas os produtos X e Y, em uma única máquina, que funciona durante 40 horas por semana.
O gerente decidiu rever seu mix de produção (quantidade fabricada de cada produto) porque tinha a sensação de fazer algo errado
e achava que poderia, de alguma maneira, aumentar seu lucro.
Para isso, pediu ajuda a um engenheiro de produção, que fez diversas entrevistas e resumiu os dados adicionais, relevantes para o
problema, na Tabela 1 a seguir:
O gerente explicou ao engenheiro que havia adotado o mix de produção atual porque acreditava ser mais interessante fabricar e
vender o máximo possível do produto de maior margem de contribuição para o lucro e usar o resto da capacidade para produzir e
vender o máximo possível do outro produto de menor margem de contribuição.
O engenheiro explicou ao gerente que essa hipótese poderia levar a um mau resultado, e que seria necessário examinar melhor os
“gargalos de lucro”, ou seja, as restrições que poderiam efetivamente limitar o lucro.
Com base exclusivamente na situação descrita anteriormente, responda:
a) Quais são as restrições ou gargalos que limitam o lucro total semanal?
b) Formule o problema de otimização do lucro usando um modelo de programação linear.
Comentário
a) Com base no enunciado, você pode observar os seguintes aspectos:
O tempo de funcionamento da máquina (40h) limita sua capacidade produtiva e, consequentemente, o lucro total semanal.
Adicionalmente, as demandas semanais de X (50) e Y (100) também limitam o lucro total.
b) A formulação do problema de otimização do lucro usando um modelo de programação linear requer que sejam
especi�cadas as variáveis de decisão, a função objetivo e as restrições.
Sendo assim, você pode observer que temos:
Variáveis de decisão:
- X: quantidade semanal a ser fabricada do produto X;
- Y: quantidade semanal a ser fabricada do produto Y.
O objetivo do problema é maximizar o lucro total semanal (Z), então a função objetivo será dada por max Z = 80X + 40 Y, em
função das margens de contribuição de cada produto para o lucro total.
Por �m, as restrições apontadas em a) podem ser escritas, respectivamente, como sendo
- 1X + 0,2Y ≤ 40
- X ≤ 50
- Y ≤ 100.
Adicionalmente é preciso considerar as condições de não negatividade, isto é, X, Y ≥ 0.
Exemplo 2 (ENADE / 2011)
Um trecho de 45 km de uma rodovia apresenta alto índice de acidentes, com ocorrências de�nidas da seguinte forma:
50% dos acidentes ocorrem uniformemente entre o km 0 e o km 15;
20% dos acidentes ocorrem uniformemente entre o km 15 e o km 30;
30% dos acidentes ocorrem uniformemente entre o km 30 e o km 45.
A equipe de resgate conta com uma única viatura para atendimento de emergência e uma base sediada no meio do trecho.
O grupo busca de�nir a opção que atende melhor a maior parte das ocorrências em até cinco minutos — tempo considerado
decisivo entre a vida e a morte para vítimas graves —, e estabeleceu as seguintes opções:
Opção 1: viatura permanece na base aguardando chamados de ocorrências.
Opção 2: viatura transita por toda a extensão do trecho aguardando chamados de ocorrências.
Opção 3: viatura transita em um raio de 22,5 km da base, aguardando chamados de ocorrências.
Os custos operacionais das três opções não são considerados relevantes quando o assunto é salvar vidas. O grá�co a seguir
(Figura 1), resultado de simulações de Monte Carlo, apresenta as funções de probabilidade acumuladas do tempo de viagem até
as ocorrências para as três opções, considerando-se a velocidade média igual a 100 km/h.
A partir dessas informações, avalie as asserções a seguir e a relação proposta entre elas.
A opção 1 é a melhor para atender as vítimas de acidentes graves.
PORQUE
O tempo de viagem da viatura até o local do acidente é menor que 15 minutos na opção 1.
Assinale a opção correta:
a) As duas asserções são proposições verdadeiras e a segunda é uma justi�cativa correta da primeira.
b) As duas asserções são proposições verdadeiras, mas a segunda não é uma justi�cativa correta da primeira.
c) A primeira asserção é uma proposição verdadeira e a segunda, uma proposição falsa.
d) A primeira asserção é uma proposição falsa e a segunda, uma proposição verdadeira.
e) Tanto a primeira quanto a segunda asserções são proposições falsas.
 Figura 1 - Distribuição de probabilidade acumulada do tempo de viagem até a ocorrência.
Comentário
De acordo com o enunciado, você pode perceber que a melhor opção é aquela que “atende melhor a maior parte das ocorrências
em até cinco minutos”.
Assim, de acordo com o grá�co apresentado no enunciado da questão, as melhores opções são, nessa ordem, a segunda, a
terceira e a primeira, já que oferecem mais probabilidade de atender uma ocorrênciaem até cinco minutos.
Já em relação à segunda proposição, observando o grá�co, você pode veri�car que, diante da opção 1, o tempo máximo que a
viatura demorará a chegar até o local do acidente é algo entre 12,5 e 15 minutos — ou seja, com certeza, a viatura chegará antes
de 15 minutos ao local do acidente.
Logo, a alternativa D é a resposta da questão.
 Representação matemática | Fonte: (shutterstock)
Problema de programação linear

O problema de programação linear (PPL) é um método analítico empregado para
resolver problemas em que se procura alocar recursos limitados a atividades ou a
identificação da solução ótima para tomada de decisões diversas.”
Sucena, 2018
No PPL, todas as funções de�nidas no modelo matemático que descreve o problema (função objetivo e restrições do problema)
devem ser lineares. A forma comum de representação matemática do PPL é descrita a seguir:
Min ou Max 
Com sujeição às restrições:
...
Z  =     ⋅     +   ⋅     +   …   +     ⋅  c1 x1 c2  x2 cn xn
  
  
  ⋅     +     ⋅     +   …   +     ⋅   =  a11 x1 a12 x2 a1n xn  b1
    ⋅     +     ⋅     +   …   +     ⋅     =  a21 x1 a22 x2 a2n xn b2
  
  
  ⋅     +   ⋅   +   …   +     ∙     =  am1 x1 am2  x2  amn xn bm 
>=  0,  i  =  1,  2,   … ,  nxi 
  
  
Na representação anterior, considere que:
x : variáveis de decisão para j = 1,2,...n;
b : quantidade disponível de determinado recurso para j = 1,2,...m;
n: quantidade de variáveis de decisão do modelo de PPL;
m: quantidade de restrições do modelo de PL;
Z: função-objetivo do modelo de PL
a ∙ x + a ∙ x + … + a ∙ x = bj → j-ésima restrição (j = 1, …, m)
j
j
j1 1 j2 2 jn n
A forma mais comum de resolução do PPL é a solução grá�ca, empregada para casos
simples com duas variáveis de decisão.
Veja como empregar a solução grá�ca a partir da resolução do exemplo a seguir, extraído de Sucena (2018).
Exemplo 3
Determine a solução ótima do PPL:
Com sujeição a:
Max  Z  =  3   +  4X1 X2
  
  
2, 5X1  +  X2  ≤  20 
3X1  +  3X2  ≤  30 
X1  +  2X2  ≤  16 
X1  ≥  0,  X2  ≥  0
  
  
Comentário
1º passo) Represente as restrições no plano cartesiano x-y. Como as restrições desse problema de PL são dadas em forma de
desigualdades, então a solução grá�ca do conjunto de restrições será um polígono convexo (não necessariamente fechado) que
recebe o nome de região de soluções viáveis (R.S.V.).
A solução ótima do problema de programação linear será um dos vértices desse polígono.
2º passo) Encontre o ponto ótimo. Começa-se traçando a reta que anula a função-objetivo, ou seja, a reta que passa pela origem
(X1 = 0, X2 = 0 e Z = 0) e que corresponde a Z = 0, representando a situação mais desfavorável
Em seguida, procura-se o vértice do polígono pelo qual passa a reta paralela à reta traçada anteriormente, ponto esse que deve
ser o mais afastado possível (visto que o problema é de maximização).
As equações de reta que representam Z = 0 e as paralelas que se destinam ao vértice mais afastado do polígono convexo são
também conhecidas como equações equipotenciais.
3º passo) Aplicando os dois passos anteriores, veri�ca-se que o ponto B apresenta a solução ótima do PPL. As coordenadas
cartesianas do ponto B são x1 = 4 e x2 = 6. Assim, conforme ilustrado na Figura 2, você pode concluir que a solução ótima, dado
que x1 = 4 e x2 = 6, é Z = 3 ∙ 4 + 4 ∙ 6 = 36.
 Figura 2 – Solução do PPL com emprego do método gráfico [3].
Outro aspecto relevante do PPL é a possibilidade de construção do dito problema dual. Mais do que um mero exercício
matemático, o conceito de dualidade foi uma das mais importantes descobertas no início do desenvolvimento da programação
linear, pois permite a análise de sensibilidade do resultado do sistema a variações nos valores dos coe�cientes das restrições.
Assim, o modelo dual apresenta informações sobre questões econômicas relevantes em um PPL.
Neste momento, é importante que você saiba que há um conjunto de relações simples que permitem transformar um problema
original (dito primal) em dual. Veja só:
Teoria das �las e cadeias de Markov
Conforme descrito em Batalha (2008), modelos de �las têm sido aplicados com sucesso em diversos sistemas produtivos, seja
em serviços, seja na manufatura.
Você também pode identi�car seu emprego em sistemas de transporte e sistemas computacionais.
Conforme descrito em Sucena (2013.1), os principais componentes de sistemas de �las são:
Os sistemas de �las podem ser classi�cados como:
 Fila de drive-thru | Fonte:
Exemplo 5 (ENADE 2011)
Uma rede de fast-food 24h de�niu a seguinte estratégia de venda para seu serviço de drive-thru: “se você encontrar mais que três
clientes no sistema (�la + atendimento) receberá uma sobremesa como cortesia”.
O custo dessa política é de R$ 2,00 por cliente vitimado. Na condição atual, os clientes chegam aleatoriamente segundo um
processo de Poisson a uma taxa de 18 por hora. O atendimento é realizado por um único empregado e segue uma distribuição
exponencial com média de 2,5 minutos.
Contudo, o gerente estima que conseguirá, por meio de melhorias no processo de montagem dos pedidos, reduzir o tempo médio
de atendimento para 2,0 minutos.
A Figura 3 apresenta as funções das probabilidades acumuladas de haver n clientes no drive-thru (�la + atendimento) para dois
tempos médios de atendimento (TA), em minutos:
Assinale a única alternativa correta:
a) O custo médio da estratégia atual da empresa pode ser obtido por CME = 18 clientes/h ∙ 24h/dia ∙ 2 (R$ cliente vitimado) ∙ p,
para n ≥ 3.
b) É melhor para a empresa modi�car a estratégia, para que o cliente não encontre mais de quatro clientes no sistema, mantendo
seu tempo médio de atendimento em 2,5 min, do que apenas reduzir seu tempo médio de atendimento para 2 min, mantendo a
estratégia atual.
c) A estratégia “se você encontrar mais que três clientes no sistema (�la + atendimento) receberá uma sobremesa como cortesia”
equivale à estratégia “se você encontrar mais que dois clientes em �la, aguardando atendimento, receberá uma sobremesa como
cortesia”.
d) A probabilidade de haver mais de quatro clientes em �la, para um tempo médio de atendimento de 2 mim, é 7,78%.
e) O drive-thru não trabalha em condição de equilíbrio, o que inviabiliza a adoção de outra estratégia de atendimento dos clientes.
Comentário
A chave para resolução desta questão reside no número de clientes no sistema:
Como existe apenas um empregado (ou seja, apenas um servidor), se houver n clientes na �la, então haverá n + 1 clientes no
sistema, já que um deles estará em atendimento.
Logo, a estratégia “se você encontrar mais que três clientes no sistema (�la + atendimento) receberá uma sobremesa como
cortesia” equivale a indicar que o cliente receberá uma sobremesa como cortesia se encontrar mais que dois clientes em �la,
aguardando atendimento.
Deste modo, conclui-se que a alternativa correta é a letra C.
Por �m, vamos tratar brevemente das ditas cadeias ou processos de Markov (GONTIJO; AZEVEDO; RODRIGUES, 2016):
São dois os principais elementos de um processo de Markov:
Um processo de Markov é um processo estocástico em que a probabilidade de o sistema
estar no estado i no período (n + 1) depende somente do estado em que o sistema está no
período n. Ou seja, para os processos de Markov, só interessa o estado imediato.
Atividade
1. (Petrobras / 2011)
Uma vantagem da simulação, em contraposição a modelos analíticos, é que a simulação:
a) costuma exigir poucas rodadas para ter uma boa estimativa do valor objetivo para determinada decisão.
b) é uma técnica a partir da qual é possível a obtenção de alguma apreciação para a variabilidade de resultados de interesse.
c) produz, em cada rodada, apenas estimativas das verdadeiras características do sistema analisado, para um conjunto particular de
parâmetros de entrada, tal como o modelo analítico.
d) dispensa a necessidade de análise da validade do modelo.
e) pode exigir a avaliação de várias decisões possíveis, tal como o modelo analítico.
2. (Petrobras / 2010)
Considereo seguinte problema de programação linear:
Minimize: 
Sujeito a:
Para quais valores de α e β o problema apresenta soluções múltiplas?
Para quais valores de α e β o problema apresenta soluções múltiplas?
Z  =  α  ⋅     +  β  ⋅  X1 X2
  
  ≤  3 X1
  ≤  4 X2
  +  2   ≥  9 X1 X2
  ≥  0 X1
  ≥  0X2
  
  
a) α = 2 e β = 4
b) α = 2 e β = 1
c) α = 1 e β = 1
d) α = 2 e β = 3
e) α = 3 e β = 3
3. (Petrobras / 2012)
Considere o seguinte problema de programação linear:
Maximize: 
Sujeito a:
Veri�ca-se que o valor ótimo da função objetivo é:
Z  =     +  4x1 x2
  
  
2   +  4   ≤ 20  x1 x2
− +  2   ≤ 8  x1  x2
  +     ≤ 5  x1 x2
  ≥  0,     ≥  0 x1 x2
  
  
a) 0
b) 9
c) 17
d) 18
e) 20
4. (Petrobras / 2011)
Considere o seguinte problema de programação linear:
Min: 
Sujeito a:
Qual é a solução ótima?
Z  =  2x1 —  x2 
  
  
— x1  +  x2  ≤  3  
2x1 —  x2  ≤  6  
x1  ≥  0,  x2  ≥  0
  
  
a) x1 = 0 e x2 = 1
b) x1 = 0 e x2 = 3
c) x1 = 1 e x2 = 0
d) x1 = 1 e x2 = 4
e) x1 = 3 e x2 = 0
5. (Petrobras / 2010)
A avaliação de projetos de investimento em situação de futuro indeterminado é uma atividade rotineira da maioria dos dirigentes
de empresas. Diversos critérios podem ser adotados para a tomada de decisão.
Considere que um dirigente quer aumentar a participação de mercado de sua empresa seguindo uma das quatro estratégias
disponíveis (E1, E2, E3 ou E4), e que uma análise da concorrência indicou que a reação poderia ocorrer de três formas diferentes
(A1, A2 ou A3), mas, sem condições de determinar qualquer probabilidade de ocorrência de cada reação.
Analisando cada um dos possíveis estados da natureza, o dirigente elaborou a matriz de ganhos abaixo.
Orientado por um consultor, o dirigente deverá adotar o critério de Wald, também conhecido como Maximin. Nessa situação, conclui-
se que a estratégia adotada foi:
a) lançar um novo produto, pois apresenta o melhor resultado potencial.
b) lançar uma campanha publicitária, pois se identificou, para cada estratégia possível, o estado da natureza que conduzirá ao resultado
menos desfavorável.
c) lançar uma promoção de vendas, pois apresentou a maior média ponderada entre o pior e melhor resultado potencial.
d) praticar uma política de baixa de preços, pois se efetuou uma média aritmética simples dos resultados esperados.
e) praticar uma política de baixa de preços, pois se identificou, para cada um dos estados da natureza, a estratégia mais favorável para
que, então, se determinasse o quanto deixaria de ganhar.
Notas
Título modal 1
Lorem Ipsum é simplesmente uma simulação de texto da indústria tipográ�ca e de impressos. Lorem Ipsum é simplesmente uma
simulação de texto da indústria tipográ�ca e de impressos. Lorem Ipsum é simplesmente uma simulação de texto da indústria
tipográ�ca e de impressos.
Título modal 1
Lorem Ipsum é simplesmente uma simulação de texto da indústria tipográ�ca e de impressos. Lorem Ipsum é simplesmente uma
simulação de texto da indústria tipográ�ca e de impressos. Lorem Ipsum é simplesmente uma simulação de texto da indústria
tipográ�ca e de impressos.
Referências
BATALHA, M. O. (Org.). Introdução à engenharia de produção. 4. reimpr. Rio de Janeiro: Elsevier, 2008.
GONTIJO, T. S.; AZEVEDO, A. A.; RODRIGUES, A. C. ENADE comentado: engenharia de produção. Belo Horizonte: Cia. do Ebook.
2016. v. 1.
NEUMANN, C. Engenharia de produção: Questões – Cesgranrio. 2. ed. Rio de Janeiro: Elsevier, 2013.
SUCENA, M. P., Apostila de pesquisa operacional I: CCE 1012 – 2018/2. Disponível em: http://sucena.eng.br/ eng_producao/
2018/UNESA_PESQUISA_ OPERACIONAL_I_ 2018_2_parte1.pdf
<http://sucena.eng.br/eng_producao/2018/UNESA_PESQUISA_OPERACIONAL_I_2018_2_parte1.pdf> .
SUCENA, M. P. Apostila de teoria das filas: 2013.1. Disponível em:http://sucena.eng.br/ eng_producao/ UNESA_TEORIA _DAS_FILAS_
2013_1.pdf <http://sucena.eng.br/eng_producao/UNESA_TEORIA_DAS_FILAS_2013_1.pdf> .
Próxima aula
Revisão dos principais conceitos associados com estatística e engenharia da qualidade;
Aplicação dos conceitos estudados na resolução de questões de concurso envolvendo estatística e engenharia da qualidade.
Explore mais
Há materiais adicionais que podem complementar e ampliar seu conhecimento sobre pesquisa operacional, motivando-o ainda
mais para os novos desa�os que virão.
Assista ao vídeo:
O que é pesquisa operacional? <https://www.sobrapo.org.br/o-que-e-pesquisa-operacional>
http://sucena.eng.br/eng_producao/2018/UNESA_PESQUISA_OPERACIONAL_I_2018_2_parte1.pdf
http://sucena.eng.br/eng_producao/UNESA_TEORIA_DAS_FILAS_2013_1.pdf
https://www.sobrapo.org.br/o-que-e-pesquisa-operacional