0a30c709d68c5f648cc2a44f1d104672Pesquisa_Operacional_Unidade_3

Prévia do material em texto

unidade 
3
Guilherme Corrêa Gonçalves
Ricardo Buneder
(Orgs.)
OPERACIONAL
Pesquisa
Teoria das Filas, Simulação e 
Programação Dinâmica (PD)
Prezado estudante,
Estamos começando uma unidade desta disciplina. Os textos que a compõem foram 
organizados com cuidado e atenção, para que você tenha contato com um conteúdo 
completo e atualizado tanto quanto possível. Leia com dedicação, realize as atividades e 
tire suas dúvidas com os tutores. Dessa forma, você, com certeza, alcançará os objetivos 
propostos para essa disciplina.
OBJETIVO GERAL 
Compreender os principais conceitos relacionados à Teoria das Filas, Simulação e 
Programação Dinâmica.
OBJETIVOS ESPECÍFICOS 
• Aplicar os conceitos de Teoria das Filas para a resolução de problemas; 
• Compreender a importância da simulação para a tomada de decisão;
• Entender o conceito de Programação Dinâmica.
QUESTÕES CONTEXTUAIS
1. Você já ficou “retido” em uma fila à espera de um serviço (banco ou caixa de um 
supermercado, por exemplo)?
2. Você sabia que entre os modelos estocásticos da pesquisa operacional existe um 
chamado Teoria das Filas que estuda o comportamento de um sistema no que diz 
respeito à formação de filas? 
3. Sabe o que é simulação e para que ela serve?
4. Já ouviu falar em programação dinâmica?
5. E recursividade, sabe o que é e para que serve? 
unidade 
3
PESQUISA OPERACIONAL | Ricardo Buneder88
3.1 Introdução
Olá, pessoal! Na terceira Unidade de nossa disciplina de Pesquisa Operacional 
estudaremos Teoria das Filas, Simulação e Programação Dinâmica (PD). A primeira 
delas, conforme mencionado por Belfiore e Fávero (2013, p. 11), “estuda o comportamento 
de um sistema especificamente no que diz respeito à formação de filas por meio de 
análises matemáticas, a partir de um ou mais servidores que fornecem determinado tipo 
de serviço a seus clientes”. 
Quanto à Simulação, esses mesmos autores afirmam que se trata de uma técnica 
numérica que estuda o comportamento de sistemas reais por meio de modelos, permitindo 
a comparação de diversos cenários, a fim de orientar o processo de tomada de decisão 
através da análise de como as variações nos parâmetros de entrada afetam as variáveis 
de saída.
Por fim, a Programação Dinâmica (PD), que pode ser determinística ou 
estocástica, é utilizada quando o problema principal puder ser decomposto em 
subproblemas. No caso da programação dinâmica determinística, todas as variáveis 
envolvidas no sistema são não aleatórias. Já a programação dinâmica estocástica é uma 
variação da determinística, em que, pelo menos uma das variáveis envolvidas no sistema 
é aleatória. 
A fim de permitir uma melhor visualização das ferramentas da pesquisa 
operacional, apresenta-se o esquema mostrado na figura a seguir.
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 89
Figura 3.1 – Ferramentas da Pesquisa Operacional.
Fonte: Adaptado de Belfiore e Fávero (2013, p. 65).
Programação Linear
Programação em Redes
Programação Binária e Inteira
Programação por Metas ou Multiobjeto
Programação Não Linear
Programação Dinâmica Determinística
Modelos Determinísticos
Teoria das Filas
Modelos de Simulação
Programação Dinâmica Estocástica (Cadeias de Markov)
Teoria dos Jogos
Modelos Estocásticos
Outras Técnicas
Metodologia Multicritério de Apoio e Decisão (AHP)
Análise Envoltória de Dados
Inteligência Artificial
Inteligência Computacional
Heurística e Meta-heuristicas
Outras
{
{
{
PESQUISA OPERACIONAL | Ricardo Buneder90
3.2 Teoria das Filas
O que que se entende por Teoria das Filas? Para Moreira (2013), trata-se de 
um corpo de conhecimentos matemáticos aplicado ao fenômeno das filas. Andrade 
(2014) menciona que representa um tópico da Pesquisa Operacional que exibe muitas 
aplicações relacionadas ao campo da Administração de Empresas. A Teoria das Filas, 
de acordo com esse mesmo autor, diz respeito a problemas de congestionamento de 
sistemas, tendo como principal característica a presença de clientes solicitando serviços.
Nesse sentido, o autor continua dizendo que “um sistema de filas é composto 
por elementos que querem ser atendidos em um posto de serviço e que, eventualmente, 
devem esperar até que o posto esteja disponível”. (ANDRADE, 2014, p. 104).
Existem várias aplicações para a Teoria das Filas em Administração, dentre 
as quais podemos mencionar: estabelecimento de políticas de atendimento ao público 
com a finalidade de determinar o número de atendentes, bem como sua especialização; 
determinação de equipes de manutenção em instalações onde os custos associados 
a equipamentos a espera de reparos for elevado; estudo de operação de caixas em 
estabelecimentos diversos, tais como bancos, supermercados, a fim de estabelecer uma 
política ótima de atendimento ao público e programação de tráfego aéreo em aeroportos.
É importante salientar que em todos os exemplos citados há clientes solicitando 
serviços que são limitados por restrições do sistema, o que gera a possibilidade de que 
tais clientes venham a formar filas até que o serviço solicitado possa ser prestado.
Outro aspecto que deve ser enfatizado é o sentido dado à palavra fila em pesquisa 
operacional. Para isso utilizaremos a definição proposta por Moreira (2013, p. 297), que 
diz que fila designa todas as situações “[...] em que pessoas aguardam atendimento 
ou objetos (ou outra coisa qualquer) aguardam sua vez de processamento, dando-se à 
palavra processamento um sentido bem amplo (aterrissar um avião, tornear uma peça, 
atracar um navio etc., tudo isso pode ser considerado “processamento)”. 
A figura a seguir mostra esquematicamente uma aplicação da Teoria das Filas 
aplicada a um sistema de trens urbanos. 
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 91
Figura 3.2 – Teoria das Filas.
Fonte: Instituto Paralelo (2013) adaptado por Universidade La Salle (2019.
Cabe aqui questionar como se forma uma fila? Moreira (2013) responde esse 
questionamento dizendo que nem sempre as filas se formam em função de uma capacidade 
de atendimento insuficiente. Ou seja, pelo fato de haver mais clientes para atender do que 
postos de atendimento. Para ele “[...] em teoria, a capacidade de atendimento é o bastante, 
mas a própria dinâmica das coisas leva à formação de filas”. (MOREIRA, 2013, p. 298).
Nesse sentido, esse autor apresenta o exemplo seguinte: 
1
2
n
{
{
Chegada de
Clientes Fila de Clientes
Saída
Canais de Serviço
Capacidade do Sistema
Frequencia
de chegada
(tempo entre
chegadas)
Tempo de
atendimento
Número
de canais
atuando
ESTRUTURA DO SISTEMA
PESQUISA OPERACIONAL | Ricardo Buneder92
Imagine que a secretaria de uma escola esteja atendendo alunos que fazem 
suas matrículas em certo curso. Vamos assumir que haja um só guichê de 
atendimento. Digamos que o tempo para atender um aluno seja de exatamente 
5 minutos, invariável de um aluno a outro. 
Vamos supor que, em média, chegue um aluno a cada 8 minutos para ser 
atendido. Percebe-se que o atendente do guichê estará ocupado na fração de 
5/8 do tempo e terá (8 – 5) = 3 minutos de ociosidade a cada 8 minutos. Em 
outras palavras, estará ocupado 62,5% (5/8) do tempo e ocioso nos 37,5% 
(3/8) restantes. Está claro que há capacidade de sobra para o atendimento. 
Pode-se então afirmar que não haverá formação de fila? Infelizmente não, 
pois é possível que uma fila se forme mesmo com a folga no atendimento. 
Para isso basta que, enquanto um aluno se encontre no guichê, sendo 
atendido, cheguem mais dois ou três. Isto é, basta que os tempos entre a 
chegada de um aluno e a de outro sejam de 1 minuto, 2 minutos, 3 minutos, 
etc, podendo ser de 6 minutos, 11 minutos. 
Foi feita a afirmação de que chegava um aluno a cada 8 minutos, em média. 
A variabilidade em torno dessa média de 8 minutos é que é responsável pela 
formação da fila. De forma similar, o próprio tempo de atendimento suposto 
como sendo de 5 minutos fixos pode ser variávelem torno de uma média, 
tendo-se aí uma outra fonte de formação de filas. 
O que se pode concluir a partir do exemplo apresentado? Conclui-se que, 
conforme Moreira (2013), as filas não se formam única e exclusivamente por 
um problema de falta de capacidade de atendimento, mas também devido à 
variabilidade, tanto no intervalo entre chegadas de clientes como no tempo 
de atendimento desses clientes. 
Em relação ao exemplo apresentado é possível questionarmos o que ocorre 
se os clientes chegarem em intervalos fixos de tempo e forem atendidos em 
um intervalo de tempo também fixo. Ou seja, o que está sendo perguntado 
é o que ocorre se não houver variabilidade no intervalo entre chegadas de 
clientes e no tempo de atendimento dos mesmos. 
Para responder a esse questionamento é necessário desmembrar o problema 
nos seguintes casos:
Caso 1: a taxa de chegada é maior que a taxa de atendimento. Se houver 
um único posto de atendimento a tendência é de que a fila se torne cada vez 
maior.
(Cont...)
DESTAQUE
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 93
(...)
Caso 2: a taxa de chegada é igual à taxa de atendimento. Nesse caso não 
haverá fila, exceto se a mesma já existisse no início do atendimento (para 
essa possibilidade essa fila inicial vai se manter com tamanho constante).
Caso 3: a taxa de chegada é menor que a taxa de atendimento. Para essa 
hipótese, não havendo fila inicial, ela nunca será formada. Se houver uma 
fila formada no início do atendimento, seu esgotamento irá demandar 
certo tempo. Após o esgotamento o posto estará sempre disponível para 
atendimento.
Vamos trabalhar sobre esse caso a partir do exemplo da secretaria da escola 
em que o atendimento de um aluno consome 5 minutos e em que a taxa de 
chegada de alunos é de 1 a cada 8 minutos.
Vamos supor que esses tempos de 5 e 8 minutos sejam fixos. Outra hipótese 
que vamos levantar é a de que quando da abertura do guichê já havia 5 
alunos na fila aguardando por atendimento.
Como estamos considerando uma taxa fixa de chegada e um atendimento 
mais rápido do que a chegada de alunos, haverá um momento em que a fila 
deixará de existir. 
Outro aspecto a ser ressaltado é o de que o atendimento aos alunos que 
estavam originalmente na fila coexiste com a chegada de novos alunos. 
Para um melhor entendimento do que está sendo exposto foi construída a 
tabela a seguir: 
Observe que as colunas dessa tabela mostram: 
a) Coluna 1 - tempo decorrido desde a abertura do guichê. Esses tempos são 
múltiplos de 5 e 8 minutos para mostrar tanto o atendimento de um aluno (= 
5 minutos) quanto a taxa de chegada de novos alunos (= 8 minutos);
b) Coluna 2 - número acumulado de alunos atendidos; 
c) Coluna 3 – número acumulado de alunos que chegam para atendimento; 
d) Coluna 4 – número de alunos remanescentes na fila.
(Cont...)
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder94
(...)
Tabela 3.1 – Variação do tamanho da fila (taxas de chegada e de atendimento 
constantes).
Tempo (em minutos) (a) alunos atendidos - acumulado
(b) alunos que 
chegam - acumulado
Alunos 
remanescentes na 
fila (5 + b - a)
0 0 0 5
5 1 0 4
8 1 1 5
10 2 1 4
15 3 1 3
16 3 2 4
20 4 2 3
24 4 3 4
25 5 3 3
30 6 3 2
32 6 4 3
35 7 4 2
40 8 5 2
45 9 5 1
48 9 6 2
50 10 6 1
55 11 6 0
Fonte: Adaptado de Moreira (2013, p.229).
Constata-se que, de acordo com as informações mostradas na tabela acima, 
o tempo de esgotamento da fila é de 55 minutos.
(Cont...)
DESTAQUE
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 95
3.2.1 Custos de Atender e de Não Atender: um Balanço
No que diz respeito ao gerenciamento de filas, existem perguntas para as quais os 
gestores querem obter respostas. Moreira (2013) menciona as seguintes:
a. As áreas destinadas às filas são adequadas?
b. É conveniente introduzir prioridades para alguns tipos de clientes (office-boys, 
clientes com até 10 unidades de compras etc), além daquelas obrigatórias por 
força de lei (idosos, gestantes, etc)?
c. Quantos postos de atendimento devem ser empregados?
d. Vale a pena despender esforços para reduzir o tempo de atendimento (por exemplo, 
através da intensificação do uso da tecnologia da informação)?
Um ponto importante a ser observado é o de que quanto mais rápido o atendimento, 
maiores os custos envolvidos em função de um melhor treinamento dos colaboradores, 
maior emprego da tecnologia da informação, maior disponibilização de postos de 
atendimento, compra de máquinas e equipamentos mais sofisticados. 
Nesse momento você pode estar se perguntando: vale a pena incorrer nesses 
custos? A resposta dada por Moreira (2013, p. 301) é de que “talvez sim, se estiver 
ocorrendo uma grande perda de clientes por causa do não atendimento e da presença de 
filas”.
Para uma maior compreensão desse aspecto, pede-se que seja analisada a figura a 
seguir, onde é mostrado nas abscissas (eixo dos x) a medida do nível de serviço (nível de 
atendimento), e nas ordenadas (eixo dos y), três medidas diferentes de custos. 
PESQUISA OPERACIONAL | Ricardo Buneder96
Figura 3.3 – Modelo de Custo.
Fonte: Adaptado por Lopes (2016).
Observe na figura anterior que a linha “custo operacional da instalação de 
serviço por unidade de tempo” é uma curva ascendente, indicando que, quanto melhor o 
atendimento, maior o custo. Já a curva “custo de clientes à espera por unidade de tempo” 
indica o custo associado à existência de filas. Esse custo, de acordo com Moreira (2013), 
diz respeito, principalmente, a dois aspectos: receita direta perdida devida a clientes que 
vão embora por causa das filas e receita indireta perdida por causa do desgaste da boa 
imagem da instituição ou sua associação com ineficiência ou mau atendimento. 
Em síntese: é de esperar que quanto melhor o nível de serviço, menor seja o 
custo da fila, já que as esperas e o tempo de atendimento tendem a diminuir.
Na sequência serão apresentados alguns elementos que servem de base para o 
estudo de alguns modelos matemáticos fornecidos pela teoria das filas.
Nível de serviço
Nível ótimo
de serviço
Custo Total
Cu
st
o
Custo de clientes
à espera por
unidade de tempo
Custo operacional
da instalação de 
serviço por
unidade de tempo
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 97
3.2.2 Fonte de Clientes
Trata-se do conjunto total de clientes potenciais que podem demandar certo tipo 
de serviço (atendimento). Essa fonte pode ser finita ou infinita. Moreira (2013) define 
fonte infinita como aquela em que a probabilidade de uma chegada não é afetada de 
maneira significativa pelo fato de que alguns clientes já estão aguardando na fila, ou seja, o 
tamanho da fila não interfere em uma nova chegada. Como exemplos de fontes infinitas 
podemos citar sistemas abertos ao público em geral, como cinemas, postos de gasolina, 
clientes em um supermercado, carros chegando em um semáforo etc. Deve-se destacar 
que, a rigor, nenhum dos exemplos citados é composto por infinitas pessoas, mas ao fato de 
que a existência de clientes na fila não interferir na chegada de outros clientes que queiram 
juntar-se a essa fila. A figura abaixo mostra um exemplo de fonte infinita.
Figura 3.4 – Exemplo de fonte infinita: fila para cinema.
Fonte: Adaptado por Universidade La Salle (2019).
Por fim, uma fonte de clientes é classificada como finita quando o sistema de 
atendimento limita a população a ser atendida. O autor anteriormente referenciado 
cita como exemplo de fonte finita o caso de um técnico eletricista que tenha sob sua 
responsabilidade a manutenção de 20 máquinas. O número de máquinas aguardando 
reparos pode influenciar a probabilidade de uma nova máquina exigir reparos pelo fato de 
GU
ER
RE
IR
O
DE
ST
EM
ID
O 2
PERSEGUIÇÃO
NOITE DA
COMÉDIA
INGRESSOS
PESQUISA OPERACIONAL | Ricardo Buneder98
que a população de máquinas pode diminuir consideravelmente. Quanto mais máquinas 
houver em fila aguardandoreparo, maior a probabilidade de uma nova máquina exigir 
reparos, pois a população de máquinas disponíveis diminui.
3.2.3 Comportamento de Chegada dos Clientes
Moreira (2013) afirma que o processo de chegadas dos clientes é especificado 
pelo comportamento do fluxo de chegadas dos mesmos ao sistema. Se forem conhecidos 
o número de chegadas e os instantes de tempo em que elas acontecem, esse processo 
é denominado determinístico. Caso contrário, tem-se um comportamento aleatório 
constituindo-se em um processo estocástico caracterizado por uma distribuição de 
probabilidade. Para essa distribuição, é necessária a especificação de um parâmetro 
denominado taxa de chegadas, que representa o número médio de usuários que chegam 
ao sistema por unidade de tempo. Usualmente as taxas de chegadas são representadas 
por λ e há duas formas tradicionais de se falar sobre a chegada de clientes para o 
atendimento: número de clientes que chegam em um dado intervalo de tempo e tempo 
decorrido entre duas chegadas consecutivas. 
É muito comum nos estudos de teoria das filas utilizar a Distribuição de Poisson 
para configurar a taxa de chegada à fila e atendimento. O quadro a seguir apresenta 
as distribuições de probabilidade utilizadas em cada uma das formas tradicionais de 
chegada de clientes.
Quadro 3.1 – Distribuições de probabilidades utilizadas nas taxas de chegadas de clientes.
Grandezas Distribuição de chegada Médias
Número de chegadas na unidade de 
tempo (taxa de chegada) Poisson λ
Tempo decorrido entre duas chegadas 
consecutivas Exponencial 1/ λ
Adaptado de Moreira (2013, p. 245).
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 99
Ainda sobre o comportamento de chegada dos clientes, vamos chamar de λ ao 
número médio de ocorrências, ou seja, em nosso caso, ao número de clientes que chegam 
ou, como é conhecido na Teoria das Filas, a taxa de chegada. A unidade de tempo 
assumida (que pode ser qualquer uma) e a taxa de chegada λ devem ser constantes.
Distribuição de Poisson é uma distribuição discreta que se aplica ao caso 
em que, em uma certa unidade de exposição, uma dada variável pode 
assumir valores inteiros. Em boa parte dos casos, a unidade de exposição 
é alguma medida de tempo, comprimento, superfície, enquanto a variável é 
uma medida de ocorrências de algum tipo. 
Exemplo: número de acidentes de trânsito a cada 100 km de uma rodovia no 
período de uma semana. Neste caso, a unidade de exposição são os 100 km 
de rodovia, enquanto a variável representa o número semanal de acidentes.
De forma análoga, podemos ter interesse em estimar o número de clientes 
que chegam ao caixa eletrônico de um banco a cada 10 minutos. Nesse caso, 
unidade de exposição é o intervalo de 10 minutos, enquanto a variável é 
dada pelo número de clientes.
GLOSSÁRIO
Para mais detalhes sobre a Distribuição de Poisson, sugere-se a leitura do 
artigo “Probabilidade: Distribuição de Poisson”, da USP. O link está aqui: 
http://gg.gg/ftkdr.
SAIBA MAIS
Para mais detalhes sobre 
Distribuição de Poisson acesse o 
vídeo cujo link se encontra a 
seguir. Distribuição Poisson de 
Probabilidades - Conceito, 
Definição e Fórmulas: 
http://gg.gg/ftkdv do canal 
Professor Guru.
VÍDEO
PESQUISA OPERACIONAL | Ricardo Buneder100
Moreira (2013) afirma que a probabilidade de que, na unidade de tempo assumida, 
cheguem x clientes é dada pela fórmula mostrada na figura a seguir.
Figura 3.5 – Probabilidade de chegarem x clientes na unidade assumida de tempo.
Fonte: Adaptado de Moreira (2013, p. 267).
Onde:
λ = taxa de chegada = número médio de chegadas na unidade de tempo assumida;
e = base dos logaritmos neperianos (ln) = 2,7183;
x = número de clientes que chegam;
x! = fatorial de x = x. (x – 1). (x – 2) ... (3). (2). (1)
P(x) = λx e-λ
x!
Exemplo
O caixa de um restaurante fast-food nos horários de pico, recebe, em média, 
dois clientes a cada minuto. A chegada dos clientes nesses horários obedece 
à Distribuição de Poisson. Qual a probabilidade de que, em um dado minuto, o 
caixa receba:
(a) nenhum cliente?
(b) dois clientes?
(c) três clientes ou menos?
Solução
(a) probabilidade de não receber nenhum cliente: 
λ = 2 clientes por minuto
x = 0 (nenhum cliente)
P (0) = [(2^0). e-²] / 0!
P (0) = 0,135
Obs.: lembra-se que 0! é sempre 1.
(Cont...)
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 101
3.2.4 Tempo Decorrido entre Duas Chegadas Consecutivas
Até este ponto de nosso estudo adotamos a hipótese de que a chegada de clientes 
para atendimento obedece à Distribuição de Poisson. Agora, vamos à segunda forma de 
estudar a chegada de clientes para atendimento: o tempo decorrido entre duas chegadas 
consecutivas.
Moreira (2013) afirma que se o número de chegadas segue a Distribuição de 
Poisson com média (taxa de chegada) λ, então o intervalo de tempo entre duas chegadas 
consecutivas obedece a uma distribuição exponencial com média 1 / λ. 
Nesse caso teremos a fórmula mostrada na figura abaixo.
Figura 3.6 – Probabilidade de que o intervalo entre chegadas t 
seja inferior ou igual a um intervalo especificado T.
Fonte: Adaptado de Moreira (2013, p. 269).
(...)
(b) probabilidade de receber dois clientes:
P (2) = [(2². e-²)] / 2! = 0,27
(c) probabilidade de receber 3 clientes ou menos:
P (receber 3 clientes ou menos) = P(0) + P(1) + P(2) + P(3)
P (0) e P (2) já estão calculados.
P (1) = [(2¹. e-²)] / 1! = 0,27
P (3) = [(2³. e-²)] / 3! = 0,18
P (receber 3 clientes ou menos) = 0,135 + 0,27 + 0,27 + 0,18 = 0,855, ou seja, 
85,5%.
P (t ≤ T) = 1 - e-λT
Sendo(T 0)≤ 
PESQUISA OPERACIONAL | Ricardo Buneder102
Onde:
P (t ≤ T) = probabilidade de que o intervalo entre chegadas t seja inferior ou igual 
a um intervalo específico T;
λ = taxa média de chegada de clientes (lembrando que 1 / λ é o tempo médio 
decorrido entre as chegadas consecutivas de dois clientes);
e = base dos logaritmos neperianos (ln) = 2,7183.
3.2.5 Disciplina da Fila
Trata-se do critério de escolha de qual será o próximo cliente a ser atendido. 
Normalmente, para atividades de serviços, a disciplina adotada é a PEPS (Primeiro 
a Entrar, Primeiro a Sair), ou seja, é seguida a ordem de chegada. Essa é a regra mais 
utilizada.
É importante salientar que há outras disciplinas de filas possíveis, já que, por força 
de lei, idosos, gestantes e pessoas portadoras de necessidades especiais têm prioridade no 
atendimento. Na indústria, normalmente, são adotadas outras regras para processamento 
como, por exemplo, a MTP (Menor Tempo de Processamento: o trabalho de menor 
tempo de processamento é executado primeiro) e a DD (Data Devida: o trabalho cuja 
data de entrega é a mais próxima deve ser processado primeiro). 
3.2.6 O Posto de Atendimento
Para Moreira (2013), Posto de atendimento é a instalação ou sistema de instalações 
que serve de suporte ao atendimento da fila. Fila de canal único é aquela em que existe 
uma única instalação de atendimento. A figura a seguir mostra esse tipo de fila.
Figura 3.7 – Fila de canal Único.
Fonte: Adaptado de Andrade (2014, p. 145).
{
Chegada de
Clientes
Fila de
Clientes
Saída. . .
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 103
Fila de canal múltiplo é a que ocorre quando há duas ou mais instalações de 
atendimento em paralelo, cada uma atendendo de forma independente das demais. A 
figura abaixo a seguir um esquema para esse tipo de fila.
Figura 3.8 – Fila de Canal Múltiplo.
Fonte: Adaptado de Andrade (2014, p. 151).
Atendimento único e atendimento múltiplo: um atendimento é de canal único 
se for realizado integralmente por um só posto de serviço. Já o atendimento múltiplo é 
aquele em que são necessários dois ou mais postos em sequência, cada um responsável 
por uma parte do atendimento. Para um exemplo de atendimento múltiplo examine a 
figura seguir.
Figura 3.9 – Atendimento Múltiplo.
Fonte: Adaptado de Andrade (2014, p. 152).
{
Chegadade
Clientes
Fila de
Clientes
. . .
. 
 . 
 .
Saída
{
Chegada de
Clientes
Fila de
Clientes
. . . {. .
Canais
de
Serviço
Fila de
Clientes
Saída
PESQUISA OPERACIONAL | Ricardo Buneder104
3.2.7 O Comportamento do Atendimento
Inicialmente é necessário compreendermos que, de acordo com Moreira (2013), 
taxa de atendimento é o tempo que um posto de serviço demora para atender um 
cliente. Essa taxa de atendimento pode apresentar comportamento determinístico ou 
probabilístico. Exemplo: quando um posto de serviço consegue atender o mesmo número 
de clientes por unidade de tempo especificada, a taxa de atendimento é constante e 
apresenta comportamento determinístico.
No entanto, existem situações em que o tempo de atendimento varia de um cliente 
para outro. Nesse caso, a taxa de atendimento apresenta comportamento probabilístico. 
Para continuarmos nosso estudo sobre Teoria das Filas, vamos definir taxa 
média de atendimento como o número médio de clientes atendidos em uma dada 
unidade de tempo. A essa taxa média de atendimento chamaremos de µ (apenas para 
distinguir da taxa de chegada λ).
Se a taxa média de atendimento é µ, então o tempo médio de atendimento será 
de 1 / µ. 
Moreira (2013) afirma que, para muitas aplicações, a taxa de atendimento varia 
segundo uma Distribuição de Poisson com média µ. A probabilidade de que, na unidade 
de tempo assumida sejam atendidos y clientes será dada pela equação mostrada na figura 
a seguir:
Figura 3.10 – Probabilidade de que em uma unidade de tempo sejam atendidos y clientes.
Fonte: Adaptado de Moreira (2013, p. 271).
Onde:
µ = taxa de atendimento = número médio de clientes atendidos na unidade de 
tempo determinada;
P(y) =µ 
y -µ e
y!
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 105
e = base dos logaritmos neperianos (ln) = 2,7183;
y! = fatorial de y = y (y- 1) (y – 2) ... (3) (2) (1).
Considerando que a taxa de atendimento siga uma Distribuição de Poisson, então 
o tempo de atendimento variará segundo uma distribuição exponencial com tempo 
médio de atendimento de 1 / µ.
A probabilidade de que o tempo de atendimento t não ultrapasse um dado valor 
T é dada pela equação mostrada na figura abaixo.
Figura 3.11 – Probabilidade de que o tempo de atendimento 
a um cliente seja inferior ou igual a um intervalo especificado T.
Fonte: Adaptado de Moreira (2013, p. 274).
Onde:
P (t ≤ T) = probabilidade de que o tempo de atendimento a um cliente seja inferior 
ou igual a um intervalo especificado T;
µ = taxa média de atendimento;
e = base dos logaritmos neperianos.
P(t ≤ T)= 1 - e
-µT
Sendo(T 0)≤ 
PESQUISA OPERACIONAL | Ricardo Buneder106
A fim de sintetizar o que foi estudado até aqui sobre chegada e atendimento 
de clientes vamos adotar o exposto no quadro a seguir, de acordo com proposta de 
Moreira (2013).
Exemplo
Retomando o caso do restaurante fast food visto anteriormente, vamos agora 
supor que o atendente do caixa consiga atender, em média, quatro clientes por 
minuto. Se considerarmos que a taxa de atendimento obedece à Distribuição de 
Poisson, pede-se a probabilidade de que o tempo de atendimento seja igual ou 
inferior a:
a) 20 segundos
b) 10 segundos
c) 5 segundos
Solução
a) µ = 4 clientes / minuto;
T = 20 segundos;
Transformando 20 segundos em minutos, tem-se: 20 / 60 = 1 / 3 minuto;
Probabilidade de que o tempo de atendimento seja igual ou inferior a 20 segundos 
é dada por:
P (t ≤ 20) = 1 – e^ [-4. (1/3)] = 0,736, ou seja, 73,6%;
b) T = 10 segundos = 10 / 60 = 1 / 6 minuto;
Probabilidade de que o tempo de atendimento seja igual ou inferior a 10 segundos 
é dada por:
P (t ≤ 10) = 1 – e^ [-4. (1/6)] = 0,487
c) T = 5 segundos = 5 / 60 = 1/12
Probabilidade de que o tempo de atendimento seja igual ou inferior a 5 segundos 
é dada por:
P (t ≤ 5) = 1 – e^ [-4. (1/12)] = 0,283.
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 107
Quadro 3.2 – Distribuições de probabilidades utilizadas nas taxas de chegadas de clientes.
Grandezas Chegada Atendimento Médias
Número de chegadas na unidade de 
tempo (taxa de chegada) Poisson λ
Tempo decorrido entre duas chegadas 
consecutivas Exponencial 1/ λ
Número de atendimentos na unidade 
de tempo (taxa de atendimento) Poisson µ
Tempo decorrido entre dois 
atendimentos consecutivos Exponencial 1/ µ
Fonte: Adaptado de Moreira (2013, p. 281).
3.2.8 Características Operacionais de uma Fila
Neste tópico de nosso estudo vamos abordar algumas considerações importantes 
para a compreensão da Teoria das Filas propostas por Moreira (2013). Esse autor salienta 
que uma fila não pode ser otimizada tal como fazíamos em situações da programação 
linear. Ou seja, não podemos procurar os melhores valores de certas variáveis. O que 
desejamos é equilibrar os custos envolvidos na busca de um atendimento cada vez melhor 
sem, no entanto, onerar demais tal sistema. 
Para isso é necessário examinar algumas características da fila, as quais dá-
se o nome de características operacionais. Tratam-se de números ou indicadores 
de desempenho calculados com o auxílio do modelo adotado. Uma vez calculadas as 
características operacionais, será possível modificar (melhorar) uma ou algumas delas.
Continuando nosso estudo com foco na situação de Canal Único, temos as 
seguintes características operacionais principais:
I. Utilização do sistema = þ = λ / µ
Onde:
λ = taxa de chegada de clientes;
µ = taxa de atendimento de clientes.
A utilização do sistema possui mais de um entendimento:
• porcentagem de tempo que o sistema está sendo utilizado;
• probabilidade de que o sistema esteja sendo utilizado;
• probabilidade de que um cliente que chega tenha de esperar para ser atendido.
PESQUISA OPERACIONAL | Ricardo Buneder108
II. Probabilidade de que o sistema esteja ocioso: é a probabilidade de não 
haver cliente esperando por atendimento ou sendo atendido. Essa probabilidade é 
representada por:
P (0) = 1 – þ = 1 - λ / µ
III. Probabilidade de que haja n clientes esperando ou sendo atendidos no 
sistema [P (n)]: o sistema compreende a própria fila mais os clientes que estão sendo 
atendidos no posto de atendimento.
IV. Probabilidade de que a fila não tenha mais que k clientes [P (n = k)].
V. Número médio de clientes na fila (Lf): corresponde ao tamanho médio da fila 
(sem contar os clientes que estejam sendo atendidos).
VI. Número médio de clientes no sistema (L): diz respeito aos clientes que 
estão na fila e aos que estão sendo atendidos.
VII. Tempo médio que o cliente espera na fila (sem contar o tempo de 
atendimento) (Wf).
VIII. Tempo médio que o cliente espera no sistema (contando o tempo de fila 
mais o tempo de atendimento) (W).
3.2.9 Estudo do Modelo de Canal Único
Moreira (2013) afirma que ainda que o modelo de canal único seja o mais simples 
para as filas de espera, ele é também um dos mais utilizados. Adota-se a hipótese de que 
tanto a taxa de chegada (λ) como a taxa de atendimento (µ) obedecem à Distribuição de 
Poisson, o que implica que o tempo decorrido entre duas chegadas consecutivas e entre 
dois atendimentos consecutivos se distribuem de acordo com a distribuição exponencial. 
Também se considera que a taxa média de chegada e a taxa média de atendimento 
são constantes. 
Além disso, continua Moreira (2013), existem outras hipóteses:
• os clientes chegam a partir de uma população infinita;
• a disciplina da fila é a PEPS (Primeiro a Entrar, Primeiro a Sair), ou seja, 
atendimento pela ordem de chegada;
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 109
• não há abandono de fila;
• a taxa média de atendimento (µ) é maior que a taxa média de chegada (λ).
As fórmulas utilizadas para o modelo de canal único são as seguintes:
I. Utilização do sistema = þ = λ / µ
II. Probabilidade de que o sistema esteja ocioso = P (0) = 1 - þ = 1 - λ / µ
III. Probabilidade de que haja n clientes esperando ousendo atendidos no 
sistema = P (n) = (λ / µ) ^n x P (0) = [(λ / µ) elevado a n e multiplicado por P (0)].
IV. Probabilidade de que a fila não tenha mais que k clientes = P (n = k) = 1 
– (λ / µ) ^ (k + 1)
V. Número médio de clientes na fila = Lf = (λ)² / [µ (µ - λ)]
VI. Número médio de clientes no sistema = L = Lf + (/ µ) = (λ)² / [µ (µ - λ)] + 
(λ / µ)
VII. Tempo médio que o cliente espera na fila = Wf = Lf / λ
VIII. Tempo médio que o cliente espera no sistema = W = L / λ
Para um melhor entendimento sobre esses tópicos vamos analisar um exemplo 
proposto por Moreira (2013).
Exemplo
A Trampolândia, a capital da Cochinchina, mantém um serviço de ponte aérea 
com algumas das maiores cidades do país. O principal aeroporto da cidade é o Pouso 
Seguro, que concentra todo serviço de ponte aérea. Isso faz com que o tráfego aéreo 
fique um pouco congestionado. 
A intensidade desse tráfego é função da hora do dia, mas o momento mais crítico 
está entre 17 e 18 horas nos dias úteis, exatamente durante o retorno das pessoas que 
deixaram a capital pela ponte aérea para trabalhar fora. Os aviões que chegam ficam 
em uma “fila”, aguardando sua vez de aterrissar. Eles ficam sobrevoando em grandes 
círculos nas proximidades do aeroporto até que a torre de controle libere alguma pista 
para pouso.
PESQUISA OPERACIONAL | Ricardo Buneder110
Para o horário considerado – entre 17 e 18 horas – a taxa média de chegada de 
aviões é de um a cada 3 minutos. A torre de controle, por sua vez, consegue pousar, em 
média, um avião por minuto. 
Supondo que tanto a taxa de chegada como a taxa de pouso dos aviões obedeçam 
à uma distribuição de Poisson, pede-se determinar:
a. a taxa média de utilização do sistema de aterrissagem do aeroporto;
b. a probabilidade de que nenhum avião esteja pousando ou aguardando liberação 
de pista;
c. a probabilidade de que haja apenas um avião aterrissando ou aguardando ordem 
para isso; 
d. a probabilidade de que não haja mais que três aviões sobrevoando as cercanias do 
aeroporto aguardando instruções de pouso;
e. o número médio de aviões aguardando ordem de pouso;
f. o número médio de aviões pousando ou aguardando ordem de pouso;
g. o tempo médio que um avião fica sobrevoando as cercanias do aeroporto 
aguardando ordem para pousar;
h. o tempo médio que um avião demora para aterrissar, incluindo o tempo de 
aterrissagem mais o tempo que fica sobrevoando as cercanias do aeroporto 
aguardando ordem para pousar.
Solução
a. taxa média de utilização do sistema de aterrissagem do aeroporto: é a relação 
entre as taxas de chegada e de pouso = þ = λ / µ
λ = taxa de chegada de aviões = 1 a cada 3 minutos
µ = taxa de pouso = 1 avião por minuto
É importante observar que para trabalhar com µ e com λ, ambas as taxas devem 
se referir à mesma unidade de tempo: ou 1 minuto ou 3 minutos. Adotando o intervalo 
de 3 minutos como unidade de tempo, λ não se altera, mas µ passa a ser 3 (3 pousos a 
cada 3 minutos). Assim, λ = 1 e µ = 3.
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 111
Dessa forma: 
þ = λ / µ = ⅓
b. probabilidade de que nenhum avião esteja pousando ou aguardando liberação de 
pista: trata-se da probabilidade de que não haja nenhum avião no sistema = P (0) 
= 1 – þ = 1 - λ / µ = 1 – 1/3 = ⅔
c. probabilidade de que haja apenas um avião aterrissando ou aguardando ordem 
para isso = P (1) 
P (n) = (λ / µ) ^n x P (0)
Substituindo n por 1 na equação anterior, tem-se:
P (1) = (1/3) ¹ x (2/3) = 2/9
d. probabilidade de que não haja mais que três aviões sobrevoando as cercanias do 
aeroporto, aguardando instruções para pouso = P (n = k) = 1 – (λ / µ) ^ (k + 1)
Como k = 3, tem-se:
P (n = 3) = 1 – (1/3) ^ (3 + 1) = 1 – (1/81) = 80/81
e. número médio de aviões aguardando ordem de pouso: trata-se do número médio 
de clientes aguardando na fila = Lf = (λ)² / [µ (µ - λ)] = 1² / [3 x (3 – 1)] = 1/6
f. número médio de aviões pousando ou aguardando ordem de pouso = L = 
Lf + (λ / µ)
L = 1/6 + 1/3 = 1/2 
g. tempo médio que um avião fica sobrevoando as cercanias do aeroporto aguardando 
ordem para pousar: trata-se do tempo médio de permanência do cliente na fila = 
Wf = Lf / λ
Wf = (1/6) / 1 = ⅙
h. tempo médio que um avião demora para aterrissar, incluindo o tempo de 
aterrissagem mais o tempo que fica sobrevoando as cercanias do aeroporto 
aguardando ordem para pousar = W = L / λ = (1/2) / 1 = ½
PESQUISA OPERACIONAL | Ricardo Buneder112
Para mais detalhes sobre Teoria 
das Filas sugere-se o vídeo cujo 
link se encontra a seguir: 
http://gg.gg/ftkkh.
VÍDEO
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 113
3.3 Simulação
A simulação é uma técnica muito utilizada em Pesquisa Operacional e diz 
respeito a reproduzir o funcionamento de um sistema com o auxílio de um modelo.
Silva et al. (2017) salientam que os modelos de simulação aparecem sob a forma 
de jogos de empresa, simuladores de voos, modelos físicos de aeronaves para testes em 
túnel de vento etc.
Figura 3.12 – Modelo de Simulação: jogos de empresas.
Fonte: Adaptado por Universidade La Salle (2019).
A simulação é muito indicada para modelos dinâmicos que envolvem múltiplos 
períodos de tempo. Os modelos dinâmicos de simulação, segundo Silva et al. (2017), 
são usados de um período de tempo ao período seguinte, o que permite capturar as 
mudanças ocorridas ao longo do tempo.
Os autores anteriormente referenciados mencionam que a simulação em 
sistemas que incorporam elementos aleatórios é denominada Simulação Estocástica 
ou de Monte Carlo.
PESQUISA OPERACIONAL | Ricardo Buneder114
3.3.1 Razões para o Uso da Simulação
Existem muitas razões para justificar a utilização da simulação em administração. 
Dentre as principais, Andrade (2014) menciona:
1. impossibilidade ou custo muito elevado de observar diretamente certos processos 
no mundo real. Por exemplo: sincronização de sinais de trânsito em uma via.
2. complexidade do sistema observado de tal sorte que se torne impossível descrevê-
lo em termos de um conjunto de equações matemáticas de solução analítica 
viável. A título de exemplo pode-se citar a representação global de uma grande 
empresa, envolvendo múltiplas atividades como produção, vendas, marketing, 
planejamento etc.
3.3.2 Vantagens do Uso da Simulação
As principais vantagens do uso da simulação são, segundo Andrade (2014):
• possibilitar o estudo e a experimentação de interações internas complexas de um 
dado sistema, seja uma empresa ou parte dela;
• permitir que algumas variáveis sejam estudadas no ambiente e seus efeitos 
verificados;
• adquirir experiência na construção de modelos e realizar simulações pode levar a 
uma melhor compreensão do sistema, o que possibilita melhorá-lo;
• permitir perceber quais as variáveis mais importantes do sistema e como elas 
interagem;
Simulação Estocástica ou de Monte Carlo consiste na geração artificial 
de valores das variáveis de interesse, com o auxílio de números ao acaso 
ou números aleatórios. A cada faixa de frequências, atribui-se uma faixa 
correspondente de números ao acaso.
Fonte: Moreira (2013).
GLOSSÁRIO
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 115
• permitir fazer experiências com novas situações sobre as quais se têm pouca ou 
nenhuma informação;
• poder servir como um primeiro teste para o delineamento de novas políticas e 
regras de decisão para a operação de um sistema.
PESQUISA OPERACIONAL | Ricardo Buneder116
3.4 Programação Dinâmica
O que vem a ser programação dinâmica? De acordo com Colin (2013), trata-se 
de uma técnica versátil, utilizada para resolver problemas com variáveis inteiras ou 
contínuas, problemas lineares ou não lineares, problemas com horizonte de tomada de 
decisão finito ou infinito, problemas determinísticos ou estocásticos, ou uma combinação 
desses problemas.
Figura 3.13 – Exemplo de Programação Dinâmica em uma Linha de Montagem.Fonte: Ferreira (2012, p. 4).
Colin (2013) prossegue dizendo que a programação dinâmica (PD) é uma técnica 
de decomposição.
Em qualquer área do conhecimento, em geral, problemas grandes 
são difíceis de se resolver, ao passo que problemas pequenos são 
mais fáceis. Levando isso em conta, seria muito interessante caso um 
problema grande pudesse ser decomposto (subdividido) em pequenos, 
os pequenos fossem resolvidos e houvesse uma recomposição, de modo 
que o problema grande também o fosse. Obviamente que isso é muito 
difícil, pois quem garante que as soluções das pequenas partes de um 
problema grande remontadas levam a solução do problema grande? 
A PD serve exatamente para se fazer isso: pegar problemas grandes, 
decompô-los, resolver os pequenos e remontá-los de modo que a 
solução do problema grande seja correta. (COLIN, 2013, p. 238).
S1,1 S1,2 S1,3 S1,4 S1,5
S2,1 S2,2 S2,3 S2,4 S2,5
a1,1 a1,2 a1,3 a1,4 a1,5
a2,1 a2,2 a2,3 a2,4 a2,5
2
2
2 2 2
4
4
4
3
3
3
3
8
8
1
1
5 56
6
7 9
enter exit
X1
X2
e1
e2
t1,1 t1,2 t1,3 t1,4
t2,1 t2,2 t2,3 t2,4
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 117
3.4.1 Conceitos e Características dos Problemas de PD
Conforme já mencionado por Colin (2013), a PD é uma técnica de decomposição 
de problemas de otimização em uma família de subproblemas que podem ser resolvidos 
um após o outro.
Esquematicamente consideremos o caso de um estágio t qualquer, considerando 
que exista:
• um estado de entrada s (t – 1);
• um estado de saída s (t);
• uma variável de decisão x (t) que influencia a saída e o custo (ou retorno do 
estágio);
• o retorno (ou custo) do estágio f(t) [s (t – 1), x (t)] que mede a eficiência com que 
as entradas [s (t – 1) e x (t)] são transformadas em saídas;
• a transformação do estágio t, denominada φ(t), que expressa as saídas como uma 
função das entradas, ou seja, s (t) = φ (t) [s (t – 1), x (t)].
A figura abaixo mostra as variáveis descritas anteriormente.
Figura 3.14 – Caso genérico de um estágio T.
Fonte: Adaptado de Colin (2013, p. 241).
Decisão
xt
StSt-1
SaídaEntrada
Custo ou
retorno
f(St-1,xt)
Estágio t
Øt (St-1,xt)
PESQUISA OPERACIONAL | Ricardo Buneder118
Já a figura a seguir mostra a generalização do conceito para o caso de haver T 
estágios de decisão discretos em série.
Figura 3.15 – Caso Genérico de T Estados Discretos em Série.
Fonte: Colin (2013, p. 242).
As variáveis s (0), s (t), ..., s (T) são denominadas estados. Um estado qualquer 
s (t), segundo Colin (2013), depende unicamente do estado inicial s (0) e das variáveis 
de decisão que precederam o estado atual, isto é, x1, x2, ..., x (t – 1). O interesse é 
maximizar o retorno total ou minimizar o custo total, em que retorno e custo total são 
definidos pelo somatório dos retornos ou custos de cada um dos estágios. 
A formulação genérica do problema de PD é mostrada na figura abaixo.
Figura 3.16 – Formulação Genérica do Problema de PD.
Fonte: Colin (2013, p. 243).
x₁
S₁S0
f(S₀,x₁)
Estágio 1
Øt (St-1,xt)
x₂
S₂
f(S₁,x₂)
Estágio 2
Øt (St-1,xt)
Xt
StSt-1. . .
f(St-1,xt)
Estágio T
Øt (St-1,xt)
Σ
Фt
z= max T
t =1X₁, X₂ ..., XT
ft(St-1,Xt)
St = (St-1,Xt) para t = 1,2 ..., T - 1
ft e Фt podem ter qualquer formato
S0 é um parâmetro conhecido
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 119
A formulação genérica mostrada na figura acima pode ser utilizada para 
problemas distintos. No entanto, cabe salientar que, conforme alerta Colin (2013), nem 
todos os problemas que são estruturados de acordo com a formulação genérica podem 
ser resolvidos através da utilização da PD. Cabe, então, perguntar o que faz com que um 
problema possa ser solucionado apropriadamente através da PD?
Para responder a esse questionamento o autor acima referenciado afirma que uma 
condição necessária é que o princípio da otimalidade de Bellman possa ser aplicado. 
Segundo Colin (2013), este conceito afirma que uma política (ou estratégia) ótima 
tem a propriedade de que, quaisquer que sejam os estados e as decisões iniciais, as 
decisões remanescentes devem constituir uma política ótima com relação ao estado 
resultante da primeira decisão. 
Como definição alternativa temos: para um dado estado, em um dado estágio t, 
a solução ótima do restante do problema nos estágios t, t + 1, ..., T é independente das 
decisões feitas nos estágios anteriores 1, 2, ..., t – 1.
A PD só poderá ser utilizada para solucionar determinado problema se o princípio 
da otimalidade se aplicar a ele.
3.4.2 Recursividade
Considere-se um problema original com T variáveis de decisão, T – 1 variáveis de 
estado e T – 1 restrições. Colin (2013) afirma que a aplicação do princípio da otimalidade 
permite que o problema original seja transformado numa sequência de T subproblemas, 
em que o t-ésimo subproblema é definido conforme mostrado esquematicamente na 
figura abaixo.
Figura 3.17 – Definição do t-ésimo subproblema.
Fonte: Colin (2013, p. 246).
Zt (St - 1) = max {ft (St- 1, Xt)+Zt +1 (St)}
St = Φt (St-1, Xt) e ZT+1 (ST) = 0.
Xt
PESQUISA OPERACIONAL | Ricardo Buneder120
É importante salientar que, de acordo com Colin (2013), a equação da função-
objetivo é chamada de recursiva porque depende dela mesma, ou seja, sua solução 
requer a análise de recorrências.
Deve-se observar também que cada subproblema tem somente uma variável de 
decisão e uma restrição de estado, mas deve ser solucionada para todos os valores de 
s (t – 1).
Ainda de acordo com o autor referenciado, para que a decomposição do problema 
seja feita e a PD utilizada, duas propriedades são necessárias: separabilidade e 
monotonicidade (condições de Mitten).
Na sequência é apresentado um algoritmo simplificado de PD para uma solução 
geral de problemas.
ATIVIDADE: Algoritmo de programação dinâmica
1. Defina os estágios, as variáveis de decisão e os estados do problema em 
consideração;
2. Determine as funções de recorrência para cada um dos estágios;
3. Ache z1 como uma função de x1 para o valor conhecido de entrada s(0);
4. Ache z2 = f2 + z1. Avalie o resultado para os diversos valores de s1 e selecione 
o maior de todos, de modo que z2 seja encontrado;
5. Repita o passo 4 para os outros estágios até que todos eles estejam resolvidos.
Teoria das Filas, Simulação e Programação Dinâmica (PD) | UNIDADE 3 121
SÍNTESE DA UNIDADE
Chegamos ao final de mais uma unidade de nossa disciplina de Pesquisa 
Operacional. Tivemos a oportunidade de ter contato com mais ferramentas utilizadas 
para a resolução de problemas: teoria das filas, simulação e programação dinâmica (PD). 
Não esqueça de assistir à videoaula dessa Unidade. Ela é fundamental para que você 
compreenda, ainda mais, todos os assuntos abordados.
PESQUISA OPERACIONAL | Ricardo Buneder122
REFERÊNCIAS
ANDRADE, E. L. Introdução à Pesquisa Operacional: métodos e modelos para análise de 
decisões. Rio de Janeiro: LTC, 2014.
BELFIORE, P; FÁVERO, L. P. Pesquisa operacional para cursos de engenharia. Rio de 
Janeiro: Elsevier, 2013.
COLIN, E. C. Pesquisa Operacional: 170 aplicações em estratégia, finanças, logística, produção, 
marketing e vendas. Rio de Janeiro: LTC, 2013.
FERREIRA, A. A. Programação Dinâmica. 2012. Disponível em: http://gg.gg/ftkm9. Acesso em: 
30 out 2019.
INSTITUTO PARALELO. Os trens urbanos e a teoria das filas. 2013. Disponível em: 
http://gg.gg/ftkmc. Acesso em: 26 out. 2019.
LOPES, R. B. Mapeamento dos Processos e Simulação de um Terminal Regulador de 
Contêiner. 2016. Disponível em: http://gg.gg/ftkmq. Acesso em: 30 out. 2019.
MOREIRA, D. A. Pesquisa Operacional: curso introdutório. São Paulo: Cengage 
Learning, 2013. 
SILVA, E. et al. Pesquisa operacional: programação linear: simulação. São Paulo: Atlas, 2017.
PESQUISA OPERACIONAL | Ricardo Buneder150
Se você encontrar algum problema nesse material, entre em 
contato pelo email eadproducao@unilasalle.edu.br. Descreva oque você encontrou e indique a página.
Lembre-se: a boa educação se faz com a contribuição de todos!
CONTRIBUA COM A QUALIDADE DO SEU CURSO
Av. Victor Barreto, 2288
Canoas - RS
CEP: 92010-000 | 0800 541 8500
ead@unilasalle.edu.br