Pesquisa Operacional - Unidades 01 a 09 - UNIDBSCO

Prévia do material em texto

Unidade 1 
 
 
CONCEITOS DE DECISÃO 
E O ENFOQUE GERENCIAL DA 
PESQUISA OPERACIONAL 
Profa. Marina Vargas 
 
• Conhecer as origens da pesquisa 
operacional; 
 
• Conhecer o processo de tomada de 
decisão; 
 
• Identificar o tipo de decisão; 
 
• Entender o que é pesquisa operacional. 
Objetivos: 
Origens: 
A expressão pesquisa operacional foi 
usada pela primeira vez em 1938 e se 
fortaleceu na 2.ª Guerra Mundial. 
 
- Natureza tática​ 
 
- Natureza logística​ 
 
- Táticas militares 
Fonte: <https://goo.gl/TUe2yD> 
 
Origens: 
das tropas, 
as táticas de 
defesa e 
ataques 
aéreos ou 
marítimos. 
Guerra: Cientistas britânicos tomavam 
decisões com bases científicas sobre a 
melhor utilização do material de guerra, o 
abastecimento 
Fonte: <https://aviacaocivilemilitar.wordpress.com/tag/alemanha-na-segunda-guerra-
mundial/> 
Origens: 
• Pós-Guerra: Após a guerra, as ideias 
propostas para as operações militares 
foram adaptadas para melhorar a 
eficiência e a produtividade no setor Civil. 
Método Simplex - 
George Dantzig (1947), 
para a resolução de 
problemas de programação 
linear 
 
Final dos anos 1950: 
programação linear, 
programação dinâmica, 
teoria 
das filas e teoria de 
estoques. 
Tomar decisões é uma tarefa 
básica da gestão 
Ciência da tomada de decisão. 
George B. Dantzig, em entrevista que foi republicada, in 
memoriam, na edição de junho de 2005 pela revista 
“OR/MS Today”. 
 Em 1957, a USP criou o primeiro curso de 
Engenharia de Produção do Brasil. Dois anos 
depois, o ITA também criou o curso, onde 
incluía disciplinas de PO, tais como teoria de 
jogos, simulação, filas e estatística, 
enquanto a USP já discutia aplicações de 
programação linear. 
PUC-RJ: primeiro computador 
IMPA e ENCE: programação linear 
No Brasil: 
• O primeiro Simpósio Brasileiro de Pesquisa 
Operacional (SBPO) foi realizado em 1968 
no ITA e incluía alguns pesquisadores do 
país. 
• Na sequencia foi criada a Sociedade 
Brasileira de Pesquisa Operacional 
(SOBRAPO). 
 
 
No Brasil: 
Cabe 
ao decisor:​ 
Identificar e 
definir o 
problema; 
Formular 
Objetivo(s); 
Analisar 
limitações. 
Avaliar 
alternativas e 
escolher a 
melhor; 
A solução de problemas através de pesquisa 
operacional pode ser implementada a partir de 
um procedimento de sete etapas 
Modelagem e tomada de 
decisão em sistemas reais, 
determinísticos ou 
probabilísticos, relativos à 
necessidade de alocação de 
recursos escassos (MARINS, 
2011). 
Ela pretende tornar científico, 
racional e lógico o processo 
decisório nas 
organizações (PANDOLFI, 
2011). 
Qualitativo: problemas simples, 
baseados na experiência do decisor. 
 
Quantitativo: problemas complexos; 
ótica científica. 
O processo de decisão pode ter duas 
abordagens:​ 
QUALITATIVO QUANTITATIVO 
APLICAÇÕES: Diversas áreas: 
 
Determinação de mix de produtos; 
Escalonamento de produção; 
Roteirização e logística; 
Planejamento financeiro; 
Análise de projetos; 
Alocação de recursos de mídia; 
Designação de equipe, etc. 
Exemplificação: 
 
 
 Qual a quantidade de cada tipo de casa 
que o condomínio deve ter? 
 
 2, 3 ou 4 quartos 
Custos e lucros diferentes 
para cada tamanho. 
Mínimo 20 casas de 2; 30 
de 3; 15 de 4. 
Valor máximo de dinheiro 
para investir. 
Projeto 
de 
Condo-
mínio 
REFERÊNCIAS 
 
MARINS, F. A. S. Introdução à pesquisa 
operacional. São Paulo: Cultura 
Acadêmica, 2011. 
PANDOLFI, C. Pesquisa operacional: 
notas de aula. Caxias do Sul: FSG, 2011. 
TAHA, H. A. Pesquisa operacional. 8. ed. 
São Paulo: Pearson, 2008. 
EHRLICH, P. J. Pesquisa operacional – 
curso introdutório. São Paulo: Atlas, 1988. 
Unidade 2 
 
 
 
 
 
FORMULAÇÃO DE 
PROBLEMAS 
Profa. Marina Vargas 
Objetivos: 
 
• Conhecer algumas técnicas qualitativas de 
auxílio à tomada de decisão; 
 
• Entender o processo de modelagem; 
 
• Formular problemas, identificando a função 
objetivo, as variáveis e as restrições. 
 
Algumas Técnicas Qualitativas: 
• Diagrama de Ishikawa ou dos 4M´s; 
• Brainstorming; 
• Brainwriting; 
• Método de Delineamento de Problemas 
Organizacionais (MDPO); 
• 5W2H; 
• Árvore de decisão qualitativa, etc. 
 
Diagrama de Ishikawa ou dos 
4M´s 
 
O diagrama de Ishikawa, também conhecido como dos 4M’s, 
ou de causa e efeito ou diagrama espinha de peixe, foi 
desenvolvido por Kaoru Ishikawa, da Universidade de 
Tóquio, em 1943. 
 
Os 4M’s iniciais foram: método, mão de 
obra, matéria-prima e máquinas. 
Brainstorming : 
“tempestade de ideias”. 
 
Dinâmica de grupo – "sem medo de críticas" 
 
Deve-se usar três etapas: 
 
- levantamento de dados gerais; 
- desenvolvimento de ideias como 
possíveis soluções; 
- escolha final da melhor solução. 
 
Brainwriting 
 
A técnica do brainwriting é iniciada por 
processo escrito e, no final, utiliza o 
brainstorming. 
 
A função é a mesma do brainstorming, mas 
garante um sigilo inicial da autoria das ideias, 
que pode aumentar as chances de 
aparecerem ideias muito criativas e 
desprovidas de preconceito. 
5W2H: 7 perguntas sobre o assunto em 
estudo, em três etapas distintas da solução 
de problemas: diagnóstico, plano de ação e 
de padronização. 
Inglês​ Português​ 
What?​ O quê?​ 
Who?​ Quem?​ 
When?​ Quando?​ 
Why?​ Por quê?​ 
Where?​ Onde?​ 
How?​ Como?​ 
Howmuch?​ Quanto custa?​ 
Processo de Modelagem 
As grandezas são 
representadas por 
variáveis de decisão e 
suas relações por 
expressões 
matemáticas.​ 
Problema 
descrito com 
palavras 
Problema de 
Programação 
Matemática 
Modelagem​ 
 
Etapas e modelagem​: 
a) entendimento do problema;​ 
b) coleta de dados relevantes​; 
c) modelagem​; 
d) validação​. 
​ 
Modelo de otimização​ 
​ 
​ 
​ 
• Modelo: representações de um 
sistema e de seu comportamento 
U = f ( X
i
 , Y
j
 ) 
 
 
• Onde 
–U = valor do desempenho do sistema 
–X
i
 = as variáveis que podem ser controladas 
–Y
j
 = as constantes que afetam U 
–f = o relacionamento entre U, X
j
 e Y
j
 
 
 
Um fazendeiro precisa decidir quantos hectares 
deve plantar de milho e arroz. Para cada hectare 
de milho plantado, recebe de lucro R$5, e para 
o arroz, R$2. Por razões técnicas, a área de milho 
não pode exceder 3 hectares e a de arroz não 
deve ser maior que 4 hectares. O milho necessita 
do cuidado de 1 pessoa por hectare, e o arroz, de 
2 pessoas. O número total de pessoas 
disponíveis é 9. Qual deve ser a decisão do 
fazendeiro para que tenha lucro máximo? 
Formulação de Problemas: 
Formulação de Problemas: 
• Variáveis de decisão: 
 
– x
1
 a área a ser plantada de milho 
– x
2
 a área a ser plantada de arroz 
 
• Variáveis incontroláveis: 
 
– lucro por ha de milho plantado: $ 5,00 
– lucro por ha de arroz plantado: $ 2,00 
Formulação de Problemas: 
Formulação de Problemas: 
REFERÊNCIAS 
 
MARINS, F. A. S. Introdução à pesquisa 
operacional. São Paulo: Cultura 
Acadêmica, 2011. 
PANDOLFI, C. Pesquisa operacional: notas 
de aula. Caxias do Sul: FSG, 2011. 
TAHA, H. A. Pesquisa operacional. 8. ed. 
São Paulo: Pearson, 2008. 
EHRLICH, P. J. Pesquisa operacional: curso 
introdutório. São Paulo: Atlas, 1988. 
Unidade 3 
 
 
SOLUÇÃO GRÁFICA DE 
PROBLEMAS LINEARES 
Profa. Marina Vargas 
Objetivos: 
 
• Identificar um problema de programação 
linear; 
 
• Formular o problema para a solução gráfica; 
 
• Inserir no gráfico todas as restrições; 
 
• Identificar no gráfico a solução ótima. 
 
Programação Linear: 
A programação linear foi um dos maiores 
avanços 
científicos dos meados do século XX e é 
considerado um dos mais importantes 
instrumentos da pesquisa 
Operacional. 
Tipos de Solução: 
1.Solução : Qualquer especificação de 
valores, dentro do domínio da função 
objetivo. 
 
1.Solução Viável : Todas as restrições 
são satisfeitas. 
 
1.SoluçãoÓtima : Restrições satisfeitas 
e valor mais favorável da função 
objetivo 
 
 
Solução Gráfica: 
1. Apenas duas variáveis de decisão; 
2. x
1
 e x
2
 representam as informações 
nos eixos X e Y. 
3. Equação linear com duas variáveis é 
uma reta. 
4. Inequação linear com duas variáveis 
é um dos semi-planos definidos pela 
reta da equação 
 
Exemplo: 
Problema Unidade 2: Um fazendeiro 
precisa decidir quantos hectares deve plantar 
de milho e arroz. Para cada hectare de milho 
plantado recebe de lucro R$ 5, e para o arroz 
R$ 2. Por razões técnicas a área de milho 
não pode exceder 3 hectares e a de arroz 
não deve ser maior que 4 hectares. O milho 
necessita do cuidado de 1 pessoa por 
hectare e o arroz de 2 pessoas. O número 
total de pessoas disponíveis é 9. Qual deve 
ser a decisão do fazendeiro para que tenha 
lucro máximo? 
Exemplo: 
Passo 1: Formulação do problema: 
• Variáveis de decisão (controláveis): 
– x
1
 a área a ser plantada de milho 
– x
2
 a área a ser plantada de arroz 
- Eixo X para a variável 
x
1
 (área a ser plantada 
de milho) 
 
- Eixo Y para a variável 
x
2
 (área a ser plantada 
de arroz). 
• Variáveis incontroláveis (constantes): 
 - lucro por há de milho plantado: R$ 5,00 
 - lucro por há de arroz plantado: R$ 2,00 
 
• Função objetivo: 
• Maximizar L=5x
1
+2x
2
 
• ou max L=f(x
i
,y
i
)=5x
1
+2x
2
 
 
• Restrições técnicas: 
 - Área máxima de milho = 3 ha = x
1
 ≤ 3 
 - Área máxima de arroz = 4 ha = x
2
 ≤ 4 
 
 
 
 
• Restrições técnicas: 
 
 
 
 
 
 
 
• Restrições de não negatividade (Condição 
de Existência): 
x
1
 ≥ 0 
x
2
 ≥ 0 
milho = 1 pessoa por ha 
arroz = 2 pessoas por ha 
Total de pessoas disponíveis = 9, ou seja, 
x
1
 + 2 x
2
 ≤ 9 
Passo 2: 
Pelos teoremas da 
programação linear, a 
solução ótima estará em 
pelo menos um dos 
pontos extremos do 
polígono que representa o 
conjunto de soluções 
viáveis. 
Passo 3: Inserir a função objetivo e identificar 
a solução ótima. 
A função objetivo é max L = 5 x
1
 + 2 x
2
 
Fonte: <https://www.geogebra.org/home> 
Portanto, pelos teoremas, a solução ótima está 
no ponto x
1
 = 3 e x
2
 =3, com um lucro máximo 
de R$ 21. Isso significa que o fazendeiro 
deverá plantar 3 ha de milho e 3 ha de arroz 
para ter o maior lucro! 
REFERÊNCIAS 
 
MARINS, F. A. S. Introdução à pesquisa 
operacional. São Paulo: Cultura 
Acadêmica, 2011. 
PANDOLFI, C. Pesquisa operacional: notas 
de aula. Caxias do Sul: FSG, 2011. 
TAHA, H. A. Pesquisa operacional. 8. ed. 
São Paulo: Pearson, 2008. 
EHRLICH, P. J. Pesquisa operacional: 
curso introdutório. São Paulo: Atlas, 1988. 
Unidade 4 
 
 
PROGRAMAÇÃO LINEAR: 
MÉTODO SIMPLEX 
Profa. Marina Vargas 
 
• Conhecer a solução analítica 
para problemas de programação linear; 
 
Aprender a usar a forma tabular Simplex; 
 
• Resolver problemas de programação linear. 
 
Objetivos: 
Método Simplex 
O método consiste em encontrar uma 
solução inicial viável e fazer iterações para 
melhorá-la. Para isso, as inequações das 
restrições deverão ser transformadas em 
equações. 
Fonte: adaptado de 
Lachtermacher (2009) 
Variáveis de Folga 
• Se a ≤ b, podemos dizer que a + c = 
b, onde c, um valor maior que zero, é 
chamado folga de a em relação a b. 
 
• Caso a ≥ b, podemos, da mesma 
forma, escrever que a – c =b, e neste 
caso c é chamado de excesso de a 
em relação a b. 
Problema da Unidade 2 
Resolvido graficamente na Unidade 3 
Função objetivo: 
Maximizar L = 5x
1
 + 2x
2
 
Sujeito a: 
-área máx. de milho = 3 ha : x
1
 ≤ 3 
-área máx. de arroz = 4 ha : x
2
 ≤ 4 
-total de pessoas disponíveis : x
1
 + 2 x
2
 ≤ 9 
Condição de Existência: 
x
1
 ≥ 0 
x
2
 ≥ 0 
Inserindo as variáveis de Folga 
temos: 
Variáveis de folga x
3
 , x
4
 e x
5
. Assim: 
 
x1 + x3 = 3 
x2 + x4 = 4 
x1 + 2x2 + x5 = 9 
Z – 5x1 – 2x2 = 0 
com 
x1 , x2 , x3 , x4 , x5 ≥ 0 
Calculadora Online: 
<http://www.phpsimplex.com/simplex/page1.php?l=pt&metodo=simplex&v=2&rt=3
&Submit=Continuar> 
x
1
 x
2
 x
3
 x
4
 x
5
 
-5 -2 0 0 0 Z 
x
3
 1 0 1 0 0 3 L1 
x
4
 0 1 0 1 0 4 L2 
x
5
 1 2 0 0 1 9 L3 
Tabela Simplex Original 
Procedimento Iterativo 
 
 
Solução inicial: 
(0, 0, 3, 4, 9) e Z = 0 
Note que as variáveis x
3
, x
4
 e x
5
 formam uma 
base em R3 , ou seja, essas três variáveis 
nos dão uma solução trivial do sistema linear: 
x
3
 = 2, x
4
 = 2 e x
5
 = 3. Nesse ponto, temos 
que x
1
 = 0 e x
2
 = 0, pois essas duas variáveis 
estão fora da base. 
Solução inicial 
(0, 0, 3, 4, 9) e Z = 0 
 
Análise gráfica dessa solução 
x
1
 x
2
 x
3
 x
4
 x
5
 
-5 -2 0 0 0 Z 
x
3
 1 0 1 0 0 3 L1 
x
4
 0 1 0 1 0 4 L2 
x
5
 1 2 0 0 1 9 L3 
Iteração 1: 
Coluna 1, pois tem maior valor absoluto entre 
x
1
 e x
2
; 
 
L1, pois 1/3> 0/4 e 1/3> 1/9. 
x
1
 x
2
 x
3
 x
4
 x
5
 
-5 -2 0 0 0 Z= 0 
x
3
 0 1 0 0 3 L1 
x
4
 0 1 0 1 0 4 L2 
x
5
 1 2 0 0 1 9 L3 
L3-L1 e LZ-5L1 
1 
Método da Redução de Gauss para 
escalonamento de matriz. 
x
1
 x
2
 x
3
 x
4
 x
5
 
0 -2 5 0 0 Z= 15 
x
3
 1 0 1 0 0 3 L1 
x
4
 0 1 0 1 0 4 L2 
x
5
 0 -1 0 1 6 L3 
Resultado da primeira iteração: 
Iteração 2: 
Coluna 2, transformar x
2
; 
 
L3, pois 2/6> 1/4 e 2/6> 0/3. 
2 
x
1
 x
2
 x
3
 x
4
 x
5
 
0 0 4 0 1 Z= 21 
x
3
 1 0 1 0 0 3 L1 
x
4
 0 0 1/2 1 -1/2 1 L2 
x
5
 0 1 -1/2 0 1/2 3 L3 
2L2-L3 e LZ+L3 
<http://www.phpsimplex.com/simplex/page4.php?f=1&l=pt> 
A solução ótima está no ponto x
1
 = 3 e x
2
 =3, 
com um lucro máximo de R$ 21 
 
Além de 
calcula-
doras 
online, 
também 
podemos 
usar o 
Solver 
do Excel 
ou Libre 
Office. 
 
Resolução Gráfica 
Fonte: <https://goo.gl/cMki9q> 
REFERÊNCIAS 
 
LACHTERMACHER, G. Pesquisa 
operacional na tomada de decisão. 4. ed. 
São Paulo: Pearson Prentice Hall, 2009. 
MOREIRA, Daniel A. Administração da 
produção e operações. São Paulo: Pioneira 
Thomson Learning, 2004. 619 p. 
MARINS, F. A. S. Introdução à pesquisa 
operacional. São Paulo: Cultura Acadêmica, 
2011. 
TAHA, H. A. Pesquisa operacional. 8. ed. 
São Paulo: Pearson, 2008. 
 
Unidade 5 
 
 
ÁRVORE DE DECISÃO 
Profa. Marina Vargas 
Objetivos: 
 
• Saber definir os elementos que constituem 
uma árvore de decisão; 
• Ter facilidade em estruturar uma árvore de 
decisão; 
• Saber resolver o problema por meio de 
uma árvore de decisão, encontrando a 
alternativa ótima; 
• Conhecer programas que utilizam a árvore 
de decisão. 
 
Sequência de Decisões 
Inter-Relacionadas e os 
Resultados Esperados. 
Conceitos gerais sobre árvores de 
decisão 
É um grafo composto por nós quadrados que 
representam as escolhas a serem feitas 
(alternativas possíveis), nós em forma de círculos 
que representam as chances de cada alternativa 
(estados da natureza) e nós triangulares com os 
resultados da decisão 
Árvore de Decisão 
Fonte: https://goo.gl/d9JrYn 
Deitada: Esquerda para a direita 
Em pé: Cima para baixo 
 
Exemplificação: 
Tabela de Pagamentos 
 
Caminho de um investidor. 
- debêntures, 
- ações 
- aplicação fixa. 
 
Probabilidades do mercado crescer, 
estagnar ou de haver inflação, eram de 50%, 
30% e 20%, respectivamente. 
 
Exemplificação: 
Tabela de Pagamentos 
 
Para cada situação haveria diferentes 
rentabilidades, para o caso de crescimento, 
estagnação ou inflação: 
 
• Debêntures: R$ 12, R$ 6 e R$ 3, 
respectivamente; 
• Ações: R$ 15, R$ 3 e –R$ 2, 
respectivamente; 
• Aplicação fixa: R$ 6,5 para as três 
condições. 
 
 
Exemplificação: 
Tabela de Pagamentos 
 
Passo 1 – Representar as alternativas de 
decisão: os arcos (ramos) que saem dos nós 
quadrados representam as diferentes 
alternativas de decisão 
Montagem da Árvore: 
 
Passo 2 – Representar os estados da 
natureza: Si representa o estado de natureza 
e pi a probabilidade de ocorrênciado estado 
de natureza. 
Passo 3 – Representar os pagamentos 
atingidos (pay-offs) 
Passo 4 – Cálculo das Probabilidades. 
Passo 5 – Verificar qual a alternativa que 
atende ao objetivo do problema. 
• Debêntures: 0,5(12) + 0,3(6) + 0,2(3) = R$ 8,40 
• Ações: 0,5(15) + 0,3(3) + 0,2(2) = R$ 8,00 
• Aplicação fixa: 0,5(6,5) + 0,3(6,5) + 0,2(6,5) = R$ 6,5 
Programas que utilizam a 
árvore de decisão 
Precision Tree®, da empresa Palisade, 
<http://www.palisade.com/precisiontree/>. 
 
Tree Plan®, desenvolvido pelo Prof. Michael R. 
Middleton, da School of Business and 
Management, da Universidade de São Francisco, 
Califórnia, <http:// www.treeplan.com/>. 
 
Planilha Excel: 
<http://ptcomputador.com/Software/microsoft-
access/139960.html>. 
http://http:
http://http:
http://http:
Bibliografia: 
-ACKOFF, R. L. & SASIENI, M. W. Pesquisa 
operacional. Livros Técnicos e Científicos e 
EDUSP. Rio de Janeiro, 1979. 
-EHRLICH, P. J. Pesquisa operacional – 
curso introdutório. Editora Atlas. São Paulo, 
1988. 
-LACHTERMACHER, G. Pesquisa 
operacional na tomada de decisão. 4. ed. 
São Paulo: Pearson Prentice Hall, 2009. 
-WAGNER, H. Pesquisa Operacional. 
Prentice Hall do Brasil, 1986. 
Unidade 6 
 
 
TEORIA DE FILAS 
Professora Marina Vargas 
Objetivos: 
• Conhecer os elementos que fazem parte das filas de 
espera; 
• Definir como são os componentes de um sistema de filas; 
• Saber quais são as características de operação das filas 
de espera; 
• Conhecer como funcionam os modelos de canal único e 
fase única; 
• Conhecer como funcionam os modelos de canais 
múltiplos e fase única. 
Elementos da análise de filas de espera 
Fila: uma simples fila de espera. 
Sistema de fila: engloba a distribuição 
de chegada dos clientes ao sistema; a 
distribuição do tempo que um cliente 
demora para ser atendido, dependendo 
do número de clientes que este encontra 
na fila de espera; a distribuição do 
serviço do cliente e o tempo que o 
cliente demora a ser servido e a sair 
do sistema. 
Fonte: <https://www.ime.unicamp.br/~hlachos/ME323-Teoria%20Filas.pdf> 
As filas são compostas pelos seguintes componentes: 
 
1. Fonte de usuários; 
2. Chegadas; 
3. Linhas de espera; 
4. Servidor(es); 
5. Usuários atendidos. 
Elementos da análise de filas de espera 
Elementos contribuintes de um sistema 
de filas de espera 
Dimensão da população: 
• Infinita: quando a probabilidade de ocorrer uma nova chegada não é influenciada 
pelo número de clientes que já se encontram no sistema. 
• Finita: enumerável e contável. 
Dimensão da chegada: 
• Clientes chegam um a um; 
• Clientes chegam em grupo. 
Controle das chegadas: 
• Chegadas controláveis (ex.: inscrições em dias fixos.) 
• Chegadas incontroláveis (ex.: urgência de um hospital.) 
• Distribuição das chegadas: o padrão das chegadas pode ser descrito pelo tempo 
entre duas chegadas consecutivas (tempo entre chegadas) ou pelo número de 
chegadas por unidade de tempo (distribuição das chegadas). 
 
• Atitude dos clientes: 
• Paciente, permanecem na fila até serem atendidos. 
• Impaciente, desistem de esperar ou simplesmente não se juntam à fila se ela for 
muito grande. 
 
• Taxas das chegadas (λ): número médio de clientes que procuram o serviço por 
unidade de tempo. 
 
Elementos contribuintes de um sistema 
de filas de espera 
 
 
Exemplo de uma distribuição de Poisson 
Grandezas Distribuição 
de chegada 
Médias 
Taxa de 
chegada 
Poisson 
Tempo 
decorrido 
entre duas 
chegadas 
consecutivas 
Exponencial 
Fonte: Moreira, 2007. 
Fila de espera 
Serviço 
• Configuração do serviço: corresponde ao número de postos de atendimento e 
fases de atendimento. 
 
• Dimensão do serviço: 
• Simples: um cliente por vez no servidor (ex.: banco). 
• Grupo: vários clientes por vez no servidor (ex.: elevador) 
 
• Taxas de serviço (μ): número médio de clientes que podem ser atendidos por cada 
servidor e por unidade de tempo. 
 
 
 
Distribuição do tempo de serviço. 
Fila de espera 
Capacidade do sistema 
A capacidade do sistema corresponde ao número máximo de clientes que o 
sistema suporta, incluindo os que estão em espera e os que estão sendo 
atendidos. 
 
• Infinita: não ocorrerá problemas de espera; 
 
• Finita: caso o sistema esteja cheio, não pode entrar nenhum cliente 
antes que outro saia. 
 
Importante! 
A taxa de chegada deve ser menor que a taxa de serviço; caso contrário, o 
sistema entrará em colapso! (λ < μ) . 
Disciplina de atendimento 
• FIFO (First In, First Out): o primeiro que entra é o primeiro a sair (ex.: filas 
em um banco). 
 
• LIFO (Last in, First Out): último cliente a chegar é o primeiro a ser 
atendido (ex.: Torre de Hanoi). 
 
• SIRO (Service In Random Order): atendimento aleatório. 
 
• PRI (Prioritárias): filas com prioridade, onde é atribuída uma prioridade a 
cada cliente. 
 
Estrutura de canais únicos 
Canal único; fase 
única. 
Canal único; fases 
múltiplas. 
Estrutura de canais múltiplos 
múltiplos canais; 
fase única. 
Modelos de canal único e fase única 
A seguir, temos os dados do problema: 
Taxa de chegada, λ = 24 por hora e taxa de serviço, μ= 30 usuários por hora. 
Taxa de utilização 
 
“DS for Windows”: < http://wps.prenhall.com/bp_weiss_software_1/1/358/91661.cw/index.html> 
REFERÊNCIAS 
 
LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. 
São Paulo: Pearson Prentice Hall, 2009. 
MOREIRA, Daniel A. Administração da produção e operações. São Paulo: 
Pioneira Thomson Learning, 2004. 619 p. 
MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo, 2007; 
MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura 
Acadêmica, 2011. 
TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. 
FOGLIATTI, M. C. e Mattos, N. M. C. Teoria de filas. Rio de Janeiro, 2007; 
COSTA, L. C. Teoria das filas. 2017. Disponível em: 
<http://www.deinf.ufma.br/~mario/grad/filas/TeoriaFilas_Cajado.pdf>. Acesso em: 07 
mar. 2018. 
Unidade 7 
 
PROBLEMAS DE ROTA 
MAIS CURTA 
Professora Marina Vargas 
Objetivos 
 
• Entender como representar e lidar com rotas; 
 
• Saber fazer o cálculo da rota mais curta; 
 
• Saber fazer o cálculo da entrega mais rápida. 
Redes 
Uma rede é um conjunto de pontos, chamados nós, e um conjunto de curvas, 
chamadas arcos (ou ramos, ou ligações), que conectam um certo número de 
pares de nós. 
 
Em geral, designam-se os nós por letras maiúsculas e os ramos pelos nós que 
eles conectam. 
Correntes, trilhas e circuitos 
• CORRENTE = sequência de arcos tal que cada arco apresenta 
exatamente um vértice em comum com o arco anterior; 
• TRILHA = sequência de arcos tal que o nó terminal de cada arco é 
idêntico ao nó inicial do arco seguinte. 
• CIRCUITO = trilha finita em que o nó terminal coincide com o nó inicial. 
 
Ex.: Correntes, trilhas e circuitos 
4 1 
2 3 
• Nós = { 1, 2, 3, 4}; 
 
• Arcos = {(1,2), (2,3), (3,4), (4,3), (4,1)}; 
 
• Ex. de corrente = (1,2) - (2,3) - (4,3); 
 
• Ex. de trilha = (1,2) – (2,3) – (3,4); 
 
• Ex. de circuito = (1,2) – (2,3) – (3,4) – (4,1). 
 
O problema de menor caminho representa um caso especial de problemas de 
rede, em que os arcos significam a distância entre dois pontos (nós). Quando 
desejamos achar a rota que une esses dois pontos com a menor distância, 
entre as possíveis, temos um problema do tipo menor caminho 
(LACHTERMACHER, 2009). 
Problema de rota mais curta 
Ex.: As letras envoltas em círculos representam os nós, e as linhas com 
números representam a distância entre esses nós. 
Exemplo de uma rede com nós, arcos e distâncias. 
Algoritmo de Dijkstra 
Passo 1: 
Faça uma marca negativa em todos os nós e coloque sua distância como 
infinito. 
Passo 2: 
Troque a marca da origem, ponto A, para a positiva e sua distância igual a 
zero. 
Algoritmo de DijkstraAlgoritmo de Dijkstra 
Passo 3: 
Atualize as distâncias entre o ponto A e todos os seus adjacentes 
(diretamente ligados ao ponto A). 
Passo 4: 
Escolha o nó com menor valor ainda com sinal de menos. Como C e I 
empatam, você pode escolher qualquer um deles. Escolheremos C. Faça o 
sinal de C ficar positivo, o que significa que a distância até ele já está definida. 
Assinale o caminho que foi usado para ter esse valor. 
Algoritmo de Dijkstra 
Algoritmo de Dijkstra 
Passo 5: 
Atualize as distâncias entre o nó com menor valor, no caso o ponto 3, e todos 
os seus adjacentes, se for para obter um valor menor; caso contrário, 
mantenha o valor anterior. D e F mudaram, B não, pois tinha valor 5 vindo 
direto de A. 
Algoritmo de Dijkstra 
Passo 6: 
Volte ao passo 4 até que todos os 
nós estejam com marca positiva. 
 
Atualize de I aos seus adjacentes e 
volte ao passo 4. 
Algoritmo de Dijkstra 
• Escolhemos B agora. • Escolhemos E. 
Algoritmo de Dijkstra 
• Continuamos o processo até que todos os nós estejam 
com marcas positivas. 
Caminho mais 
curto = A-C-F-H 
REFERÊNCIAS 
 
LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. 
São Paulo: Pearson Prentice Hall, 2009. 
MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo, 2007; 
HILLIER, F.S.; LIEBERMAN, G.G. Introdução à pesquisa operacional. 8. ed. 
Porto Alegre: AMGH, 2010. 
SILVA, E. M. da; SILVA, E. M. da; GONÇALVES, V.; MUROLO, A. C. Pesquisa 
operacional: programação linear e simulação. 3. ed. São Paulo: Atlas, 2009. 
FLEURY, P. F., ÁVILA, M. G., WANKE, P. Em busca da eficiência no 
transporte terceirizado: estrutura de custos, parcerias e eliminação de 
desperdícios, 1997. Disponível em: 
<http://www.scielo.br/pdf/gp/v4n2/a09v4n2.pdf>. Acesso em: 07 mar. 2018. 
 
 
Unidade 8 
 
 
PROBLEMAS DE LOCALIZAÇÃO 
Profa. Marina Vargas 
• Entender quais são os principais fatores que 
influenciam a localização de fábricas, depósitos e 
locais de vendas; 
 
• Verificar como encontrar uma região favorável; 
 
• Escolher, dentre vários pontos disponíveis, 
aquele que melhor se adéqua aos seus objetivos. 
Objetivos: 
Logística 
Serviço ao cliente 
Marketing = Combinação de quatro P’s (produto, preço, 
promoção e ponto de venda), em que o ponto de venda 
representa melhor a distribuição física. 
E é sobre a localização do ponto de venda, dos depósitos que o 
abastecem ou das fábricas que fornecem os produtos que 
iremos tratar. 
As instalações podem ser as seguintes: 
• Plantas (fábricas). 
• Armazéns. 
• Centros de distribuição. 
• Centros de serviço. 
• Operações de venda no varejo. 
Técnicas de análise de localização 
Três técnicas de localização: a classificação por fator de localização, o centro 
de gravidade e carga-distância. 
 
Classificação por fator de localização: 
 
• Passo 1: Identifique fatores importantes que influenciam a localização. 
 
• Passo 2: Atribua peso aos fatores (0.00 – 1.00) 
 
• Passo 3: Subjetivamente, pontue os fatores de cada site (0 – 100) 
 
• Passo 4: Ache a soma (pesos x pontuações) 
 
Fator de localização na prática: 
Fatores de localização e respectivos pesos e notas de cada fator. 
Técnicas de análise de localização 
Centro de gravidade: 
 
Como fazer: 
 
• Passo 1: Localizar a instalação no centro geográfico da área geográfica para 
minimizar os gastos com transportes. 
 
• Passo 2: Baseado em peso e distância do transporte. 
 
• Passo 3: Use um mapa com escalas da área. 
 
• Passo 4: Identifique coordenadas e pesos do transporte para cada 
localização. 
 
Centro de gravidade na prática (média 
ponderada): 
Centro de gravidade na prática (média 
ponderada): 
Achamos que o lugar ideal para se instalar a atividade é o ponto 
de coordenadas (238,444). Mas na maioria dos casos este local 
exato não está disponível, desta forma iremos tentar encontrar 
locais disponíveis próximos a este local ideal. 
Técnicas de análise de localização 
Carga-distância 
 
• Passo 1: Calcule Carga x Distância 
para cada local. 
 
• Passo 2: Escolha o local com mais 
baixa Carga x Distância. 
 
• Passo 3: Distância pode ser real ou 
linha reta. 
 
 
LD = valor de carga x distância. 
 
li = a carga, expressa como um peso, 
número de 
viagens ou unidades sendo 
transportadas do local proposto até a 
localização i. 
 
di= a distância entre o local proposto e 
a localização i. 
Carga-distância na prática: 
Carga-distância na prática: 
REFERÊNCIAS 
 
LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. 
São Paulo: Pearson Prentice Hall, 2009. 
MOREIRA, Daniel A. Administração da produção e operações. São Paulo: 
Pioneira Thomson Learning, 2004. 619 p. 
MOREIRA, D. A. Pesquisa operacional: curso introdutório. São Paulo, 2007; 
MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura 
Acadêmica, 2011. 
TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson, 2008. 
REID, R. Dan; SANDERS, Nada R. Gestão de operações. Tradução Dalton 
Conde de Alencar. Rio de Janeiro: LTC Editora, 2005 
 
Unidade 9 
 
 
SIMULAÇÃO MONTE CARLO 
Profa. Marina Vargas 
• Saber que a incerteza e a grande capacidade de 
dados exigem a adoção de simulações para 
conhecer as melhores alternativas; 
 
• Entender o método de simulação de Monte Carlo; 
 
• Saber como aplicar o método de simulação de 
Monte Carlo. 
Objetivos: 
O nome Monte Carlo (HAMMERSELEY,1964) surgiu durante 
o projeto Manhattan, na Segunda Guerra Mundial (década 
de 1940). No projeto de construção da bomba atômica, 
Stanisław Ulam, von Neumann e Fermi consideraram a 
possibilidade de utilizar o método, que envolvia a simulação 
direta de problemas de natureza probabilística relacionados 
com o coeficiente de difusão do nêutron em certos materiais. 
Origem 
Fonte: <http://mestra.me/E2hNI> 
https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial
https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial
https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial
https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial
https://pt.wikipedia.org/wiki/Segunda_Guerra_Mundial
https://pt.wikipedia.org/wiki/Stanis%C5%82aw_Ulam
https://pt.wikipedia.org/wiki/Stanis%C5%82aw_Ulam
https://pt.wikipedia.org/wiki/Stanis%C5%82aw_Ulam
https://pt.wikipedia.org/wiki/Von_Neumann
https://pt.wikipedia.org/wiki/Von_Neumann
https://pt.wikipedia.org/wiki/Von_Neumann
https://pt.wikipedia.org/wiki/Fermi
 
 
Origem 
Contudo, há registros de que um artigo escrito por Lord Kelvin, 
dezenas de anos antes, já utilizava técnicas de Monte Carlo em 
uma discussão das equações de Boltzmann. 
 
Hoje o método de simulação Monte Carlo é utilizado para 
desenvolver um panorama paramétrico confiável dos resultados 
de um processo e é vital em setores como finanças, fabricação, 
extração de gás e óleo, farmácia, dentre outros. 
Fonte: ROSAS, 2009. 
Exemplificação 
Considere as duas tabelas que representam distribuições de probabilidade. 
 
Frequência d um evento 
X P(X=x) 
1 0,33 
2 0,67 
Severidade do Evento 
Y P(Y=y) 
R$ 100 0,25 
R$ 200 0,50 
R$ 300 0,25 
O espaço amostral das despesas agregadas resultante da interação entre 
as duas distribuições acima é: Severidade do Evento 
S P(S=s) 
R$ 100 0,0833 
R$ 200 0,2083 
R$ 300 0,2500 
R$ 400 0,2500 
R$ 500 0,1667 
R$ 600 0,0417 
Fonte: <http://mestra.me/E2hNI> 
Exemplificação 
Gráfico de frequências: 
 
Distribuição da despesa agregada. Gerado no Microsoft® Excel . 
Severidade do Evento 
S P(S=s) 
R$ 100 0,0833 
R$ 200 0,2083 
R$ 300 0,2500 
R$ 400 0,2500 
R$ 500 0,1667 
R$ 600 0,0417 
Exemplificação 
Fonte: <http://mestra.me/E2hNI> 
 
Mas e se ao invés de ser 
dois registros de frequência 
fossem 10? 
 
A árvore de decisão 
aumentaria 
exponencialmente e só 
seria possível resolvê-la 
com rotinas computacionais 
e ajuda de softwares ou 
programação, para calcular 
seu espaço amostral final.Características Essenciais 
A exigência básica do método é que o sistema físico ou matemático seja 
modelado em termos de funções de distribuição de probabilidade 
(FDP), que podem ser discretas ou contínuas: Bernoulli, Binomial, Chi-
Quadrado, Gamma, Erlang, Normal, etc. 
 
 
Fonte: <http://mestra.me/OmWZh> 
Método Monte Carlo aplicado a aproximação do valor de π 
Uma vez conhecidas essas distribuições, a 
Simulação de Monte Carlo pode proceder fazendo 
as amostragens aleatórias a partir das mesmas. 
Este processo é repetido inúmeras vezes 
(milhares). 
 
Na prática, diante de um problema envolvendo incertezas, realizar uma 
Simulação com Monte Carlo para aproximar sua solução consiste em quatro 
passos padrões: 
A) Modelar o problema definindo uma FDP para representar o comportamento 
de cada uma das suas incertezas; 
B) Gerar valores pseudo-aleatórios aderentes à FDP de cada incerteza do 
problema; 
C) Substituir as incertezas por valores para calcular o resultado. 
Repetir os passos B e C até se obter uma amostra com o tamanho desejado de 
realizações; 
D) Obter uma estimativa para a solução do problema. 
Passo a Passo 
Um caixa eletrônico instalado em um shopping center atende clientes para as operações de 
saque, depósito e pagamentos de contas. Sempre que houver um cliente utilizando o caixa 
eletrônico, o próximo cliente fica na fila, aguardando a desocupação do terminal. Mas por 
outro lado, há o fator sorte, caso o cliente chegue ao terminal e este estiver desocupado. Para 
fins de análise do sistema de atendimento, foram coletados os tempos do intervalo de 
chegada de clientes ao terminal e os tempos de atendimento, que estão resumidos nos 
histogramas abaixo. (SHIBUYA, 2015) 
Simulação em Logística - exemplificação 
Simule o sistema de caixa eletrônico, prevendo o atendimento de 10 clientes e para isso, 
utilize os números aleatórios dados abaixo: 
Simulação em Logística - exemplificação 
Tabela: Tratamento de 
dados para intervalos de 
chegada. 
Simulação em Logística - exemplificação 
Tabela: Tratamento de dados para o tempo de atendimento. 
Simulação em Logística - exemplificação 
NF = 0,69 clientes, número médio de clientes em fila para a 
quantidade de atendimentos realizados (no caso, 10 
atendimentos). 
 
TF = 2,40 minutos, tempo médio que os clientes permanecem 
em fila aguardando atendimento, para a quantidade de 
atendimentos realizados (no caso, 10 atendimentos). 
 
NS= 1,54 clientes, número médio de clientes que permanecem 
no sistema ao longo do tempo de simulação (no caso, 10 
atendimentos). 
 
TS = 5,40 minutos, tempo médio que o cliente fica no sistema 
Simulação em Logística - exemplificação 
REFERÊNCIAS 
 
LACHTERMACHER, G. Pesquisa operacional na tomada de decisão. 4. ed. 
São Paulo: Pearson Prentice Hall, 2009. 
MARINS, F. A. S. Introdução à pesquisa operacional. São Paulo: Cultura 
Acadêmica, 2011. 
METROPOLIS, N., ULAM, S. The Monte Carlo Method. Journal of the 
American Statistical Association. 44 (247): 335–341. 1949. 
ROSAS, A. Método Monte-Carlo. Acessado em: 25 de fevereiro de 2018. 
Disponível em: 
<file:///C:/Users/varga/Downloads/Pesquisa%20Operacional/aulas%2008%20e
%2009/aula07-montecarlo.pdf> 
SHIBUYA, M. INTRODUÇÃO À SIMULAÇÃO DE SISTEMAS COM O 
SOFTWARE ARENA®. Acessado em: 25 de fevereiro de 2018. Disponível em: 
<http://mestra.me/7dDUh>