OTIMIZAÇÃO DE SISTEMA DE TRANSPORTES. (1)

Prévia do material em texto

PROF.ROBERTO JANNUZZI
OTIMIZAÇÃO DE SISTEMA DE 
UNIVERSIDADE ESTÁCIO DE SÁ
PROF.ROBERTO JANNUZZI
OTIMIZAÇÃO DE SISTEMA DE TRANSPORTES
UNIVERSIDADE ESTÁCIO DE SÁ
2017
Layout do Título
Subtítulo
Layout do Título
Subtítulo
OTIMIZAÇÃO DE SISTEMA DE 
1
Conceitos Básicos para Otimização 
OTIMIZAÇÃO DE SISTEMA DE TRANSPORTES
1
Conceitos Básicos para Otimização 
3
Pesquisa Operacional
• Como o próprio nome indica,
envolve “pesquisa sobre operações”
operacional é aplicada a
conduzir e coordenar as atividades
sido largamente aplicadasido largamente aplicada
manufatura, transportes, construção,
planejamento financeiro, assistência
públicos, entre outros (Hillier
operacional teve impacto na melhoria
organizações pelo mundo. Conforme
Pesquisa Operacional
indica, a pesquisa operacional (PO)
operações”. Portanto, a pesquisa
problemas envolvendo como
atividades em uma organização e tem
em áreas tão distintas comoem áreas tão distintas como
construção, telecomunicações,
assistência mé- dica e serviços
e Lieberman, 2006). A pesquisa
melhoria da eficiência de diversas
Conforme Hillier e Lieberman (2006).
4
• Fazendo uso de modelos matemáticos,
facilita o processo de análise e decisão
que uma decisão pode ser mais bem
efetivamente implementada: os
uma solução de programação da
esta seja posta em prática.
• E desde quando a pesquisa de operações
O termo Pesquisa Operacional foiO termo Pesquisa Operacional foi
Bretanha em 1938 para designar
estratégicos e táticos decorrentes de
A Pesquisa Operacional surgiu durante
necessidade de lidar com problemas
estratégia militar de grande dimensão
•
matemáticos, a pesquisa operacional
decisão dos resultados. Isso significa
bem avaliada e testada antes de ser
os resultados permitem a análise de
da produção, por exemplo, antes que
operações é utilizada?
utilizado pela primeira vez na Grã-utilizado pela primeira vez na Grã-
o estudo sistemático de problemas
de operações militares.
durante a Segunda Guerra Mundial, da
problemas de natureza logística, tática e de
dimensão e complexidade.
5
• Após a Segunda Guerra Mundial,
estiveram envolvidos no planejamento
deram continuidade a suas pesquisas,
operações não militares.
• A utilização da pesquisa operacional• A utilização da pesquisa operacional
e usuá- rios de duas formas: o
solução ótima e o enfoque “atual”,
que é o uso do modelo para
clássico. Nesta disciplina, trataremos
processo de modelagem e
próxima seção.
Mundial, muitos dos especialistas que
planejamento de operações militares
pesquisas, agora visando também
operacional tem sido vista por gestoresoperacional tem sido vista por gestores
o enfoque clássico que busca a
“atual”, segundo Andrade (2004)
para identificação do problema
trataremos do enfoque clássico. O
otimização serão discutidos na
6
Fundamentos da pesquisa Operacional
• A pesquisa operacional é definida
de modelagem a problemas de
modelos identificados por meio
estatísticos visando à obtenção de
• Modelagem e programação • Modelagem e programação 
• Uma representação de uma situação
por uma pessoa ou um grupo de
auxiliar o tratamento daquela situação
Por um lado, um modelo deve
captar elementos essenciais e representar
lado, ele deve ser suficientemente
tratável por métodos de análise e
da pesquisa Operacional
definida como a arte de aplicar técnicas
de tomada de decisão e resolver os
meio de métodos matemáticos e
de uma solução ótima.
Modelagem e programação linearModelagem e programação linear
situação ou realidade, conforme vista
de pessoas, e construída de forma a
situação de uma maneira sistemática.
ser suficientemente detalhado para
representar o sistema real; por outro
suficientemente simplificado (abstraído) para ser
e resolução conhecidos.
7
• A pesquisa operacional e a programação
de problemas de decisão
problema real, ou seja, é necessária
modelo. Variáveis (incógnitas)
matemáticas entre essas variáveismatemáticas entre essas variáveis
que o comportamento do sistema
resolvido seja descrito (Arenales
• Veja o processo de modelagem,
al. 2011).
programação matemática tratam
que procuram representar o
necessária a elaboração de um
(incógnitas) são definidas e relações
variáveis são estabelecidas de formavariáveis são estabelecidas de forma
sistema ou do problema a ser
Arenales et al. 2011).
modelagem, de acordo com (Arenales et
8
9
• Otimização Pode-se definir a otimização
determinar as “melhores” soluções
matematicamente formulados. Esta
para muitas profissões. Por exemplo,
estão interessados em maximizar a
química, levando em consideração
exemplo custo e poluição. Os
operação por suas vezes, têm queoperação por suas vezes, têm que
recursos em colocações industriais
envolvem apenas modelos lineares,
e apresentam comportamento linear,
objetivo com às restrições.
otimização como sendo a tarefa de
soluções para certos problemas
Esta tarefa é de grande importância
exemplo, físicos, químicos e engenheiros
a produção ao projetar uma indústria
consideração certas restrições, como por
economistas e investigadores de
que considerar a ótima alocação deque considerar a ótima alocação de
industriais e sociais. Alguns destes problemas
lineares, em que as variáveis são contínuas
linear, tanto em relação à função
10
• segundo Morabito e Pureza
sugeridas para serem utilizadas
operacional para enfrentar problemas
• FaseFase II: Definição do problema
• FaseFase IIII: Construção de um
representar o problema.
• FaseFase IIIIII: Solução do Modelo.
• FaseFase IVIV: Validação do modelo
(2010) há quatro etapas usuais,
utilizadas por equipes de pesquisa
problemas reais:
de interesse e coleta dados.
um modelo matemático para
modelo.
11
•• FaseFase II - Dependerá então do
resolver: a equipe de pesquisa
corretamente o problema em estudo
a partir de um sistema integrado,
componentes, todas elas interdependentes,
•• JáJá asas fasesfases IIII ee IIIIII - Possuem bastante
• Vamos ver como proceder para modelar
• a) Formulação do problema nesta
os objetivos que se pretendem
problema;problema;
• As restrições (limitações) existentes
• As relações de interdependência
integrantes do sistema.
• Este passo deve ser executado com
será sempre reformulada até que
a situação real em estudo.
problema que identificaremos para
pesquisa operacional deve formular
estudo. O problema deve ser analisado
integrado, em que interagem várias
interdependentes, para o qual é p
bastante rigor matemático.
modelar uma situação, para a fase II:
nesta etapa devem ficar bem definidos,
pretendem alcançar com a resolução do
existentes no sistema em geral;
interdependência de todas as componentes
com muito rigor e a formulação inicial
que se alcance a que melhor represente
12
Logística
• De acordo com o Coun, cil of Logistics
planejamento, implementação
economicamente eficaz de
processo, produtos acabados
ponto de origem até o ponto
atender às exigências dos clientesatender às exigências dos clientes
• Um sistema logístico qualquer
dos fluxos físicos e de informações,
movimentação de materiais e
necessidades para suprimento
componentes, passando pelo
consequente programação de
distribuição para o mercado consumidor
Logística
Logistics, logística é o processo de
implementação e controle do fluxo eficiente e
matérias primas, estoque em
e informa- ções relativas desde o
de consumo, com o propósito de
clientes (CSCMP,2015).clientes (CSCMP,2015).
qualquer deve estabelecer a integração
informações, responsáveis pela
e produtos, desde a previsão das
suprimento de matérias-primas e
pelo planejamento da produção e
de fornecimento aos canais de
consumidor.
13
•A cada transformação que
temporal e/ou espacial, lhe é
ele condições de melhor atendimento
adicionado é adquirido a
propriedade entre agentes, os
relação de troca destes bens
logística cuida da movimentação
por três áreas principais:
• Suprimento, apoio à produção
• Para vencer a distância
fornecedores, a gestão logística
a tempo, espaço, custo, comunicação,
transporte de materiais e produtos
que o produto passa, seja física,
agregado valor e incorporado a
atendimento ao consumo. Este valor
a partir da transferência de
os quais estabelecem entre si uma
bens e serviços. Portanto, a gestão
movimentação geral dos produtos, que se dá
produção e distribuição física.
que separa os clientes dos
logística enfrenta problemas referentes
comunicação, movimentação e
produtos (roteirização) (Costa, 2002).
14
• O termo roteirização pode ser
sequências de paradas determinadas
percorrer, com o objetivo
geograficamente.
ser descrito como um processo de
determinadas que um veículo deva
de atender pontos dispersos
15
Introdução à teoria dos GrafosIntrodução à teoria dos Grafos
• A Teoria dos Grafos é um ramo
estudo de objetos combinatórios
são representados por pontos
denominados de nós, ou vértices,
chamadas de arestas.
• A Pesquisa Operacional utiliza
por exemplo em interligações
chamados vértices (ou nós) e as
entre os “locais”.
• Obs. Pesquise e apresente a Teoria
• Os modelos e desenhos;
Introdução à teoria dos GrafosIntrodução à teoria dos Grafos
ramo da matemática que remete ao
combinatórios denominados Grafos. Grafos
dispostos em posições arbitrárias
vértices, conectados por curvas
utiliza os grafos em diversas situações,
interligações entre “locais”. Os “locais” são
as ligações são chamadas arestas
Teoria de Grafos;
16
Árvores binárias
Árvores são estruturas de dados
aplicações. Uma árvore é formada
elementos denominados vértices ou
árvore é vazia, caso contrário temos
árvore (r), e cujos elementos restantesárvore (r), e cujos elementos restantes
conjuntos distintos não vazios, as
destes conjuntos por sua vez uma árvore
Obs. Pesquise e apresente a Representação
Os modelos e desenhos.
Árvores binárias
dados extremamente úteis em muitas
formada por um conjunto finito T de
ou nós de tal modo que se T = 0 a
temos um nó especial chamado raiz da
restantes são particionados em m >= 1restantes são particionados em m >= 1
sub árvores de r, sendo cada um
árvore.
Representação de àrvores.
17
• Formalmente uma árvore binária
conjunto finito de nós, que é vazio,
dois conjuntos disjuntos de nós,
árvore direita. É importante observar
não é um caso especial denão é um caso especial de
completamente diferente.
binária pode ser definida como um
vazio, ou consiste de um nó raiz e
nós, a sub árvore esquerda e a sub
observar que uma árvore binária
de árvore e sim um conceitode árvore e sim um conceito
18
EXERCÍCIOS:
• O que é Pesquisa Operacional? 
• Como se define “modelo” e quais as
modelo?
• Quais são as fases de construção do modelo
• O que é uma árvore binária? 
• Existe uma ordem natural para percorrer as árvores binárias? Quais são os três 
métodos propostos?
características necessárias para um bom
são as fases de construção do modelo?
uma ordem natural para percorrer as árvores binárias? Quais são os três 
19
22
Algoritmos Algoritmos e Problemas de e Problemas de 
Cobertura de Nós Cobertura de Nós Cobertura de Nós Cobertura de Nós 
22
e Problemas de e Problemas de 
Cobertura de Nós Cobertura de Nós Cobertura de Nós Cobertura de Nós 
20
Algoritmos
• Genericamente, pode-se ver um
de passos que orientam as
resultado; uma sequência finita
resolver um determinado
desenvolvemos um algoritmo
padrão de comportamento
norma de execução de ações)
um problema. Para o desenvolvimento
eficiente é necessário obedecermos
um problema. Para o desenvolvimento
eficiente é necessário obedecermos
no momento de sua construção
• Definir ações simples e sem ambiguidade
• Organizar as ações de forma ordenada
• Estabelecer as ações dentro de
Algoritmos
um algoritmo como uma coleção
ações para se chegar a um
finita de passos (instruções) para
determinado problema. Sempre que
algoritmo estamos estabelecendo um
que deverá ser seguido (uma
ações) para alcançar o resultado de
desenvolvimento de um algoritmo
obedecermos algumas premissas básicas
desenvolvimento de um algoritmo
obedecermos algumas premissas básicas
construção:
ambiguidade;
ordenada
de uma sequência finita de passos.
21
• Um algoritmo é capaz 
• Ler e escrever dados; 
• Avaliar expressões algébricas, relacionais e lógicas; 
• Tomar decisões com base nos resultados das expressões 
avaliadas; 
• Repetir um conjunto de ações de acordo com uma condição
• Um exemplo simples de algoritmo
repetições) para troca de um pneu
Um algoritmo é capaz :
expressões algébricas, relacionais e lógicas; 
decisões com base nos resultados das expressões 
um conjunto de ações de acordo com uma condição;
algoritmo (sem condições ou
pneu:
22
• 1: desligar o carro 
• 2: pegar as ferramentas (chave e macaco) 
• 3: pegar o estepe 
• 4: suspender o carro com o macaco 
• 5: desenroscar os 4 parafusos do pneu furado 
• 6: colocar o estepe 
• 7: enroscar os 4 parafusos • 7: enroscar os 4 parafusos 
• 8: baixar o carro com o macaco 
• 9: guardar as ferramentas
• Como é a expressão da cultura
através das gerações e em
raramente constitui um sistema
implementada numa máquina
logicamente.
: pegar as ferramentas (chave e macaco) 
: suspender o carro com o macaco 
: desenroscar os 4 parafusos do pneu furado 
cultura de uma sociedade, desenvolvida
diferentes situações, a linguagem
sistema de regras rígidas que possa ser
máquina ou que possa ser transcrita
23
• Além da linguagem falada,
comunicação gestos e posturas,
diretamente adaptados para
Por fim, toda a comunicação
conhecimento prévio comumconhecimento prévio comum
exemplo a mesma língua, a mesma
por diante.
• Obs.
• Ao contrário dos seres humanos,
computadores) são projetadas
determinadas a partir de determinadas
falada, fazem parte da nossa
posturas, que não podem ser
compreensão de uma máquina.
comunicação eficiente pressupõe um
comum entre os interlocutores, porcomum entre os interlocutores, por
mesma bagagem cultural e assim
humanos, as máquinas (dentre elas os
projetadas para executar tarefas bem
determinadas instruções.
24
• Um algoritmo quando programado
pelo menos de 3 partes:
DADOS 
DA PROCESSAMENTO 
• Na parte de entrada São fornecidas
que o algoritmo possa ser executado
fornecidas no momento em que
ou podem estar embutidas dentro
fornecidas são armazenadas como
maneira de organizar dados e operar
DA
ENTRADA
PROCESSAMENTO 
TRANSFORMAÇÃO
programado num computador é constituído
DADOS 
DA
fornecidas as informações necessárias para
executado. Estas informações podem ser
que o programa está sendo executado
dentro do mesmo. As informações
como estruturas de dados, que é uma
operar sobre eles.
DA
SAÍDA
25
•• NaNa parteparte dodo processamentoprocessamento são
algébricas, relacionais e lógicas,
de controle existentes no algoritmo
Assim, um programa é a junção
estruturas de dados.estruturas de dados.
• Na parte de saída, todos os resultados
parte deles) são enviados para
como: monitor, impressora, ou
computador.
são avaliadas todas as expressões
lógicas, assim como todas as estruturas
algoritmo (condição e/ou repetição).
junção do algoritmo e de uma ou mais
resultados do processamento (ou
para um ou mais dispositivos de saída,
até mesmo a própria memória do
26
• A linguagem natural é a maneira
e trocamos informação.
• Ex.a troca do pneu.
• Um computador é somente capaz
que lhe forem delegadas e que
ações que ele pode executar.
• Assim, é necessário compreender
executadas pelos computadoresexecutadas pelos computadores
ou seja, instruí-los com a sequência
resolver um determinado problema,
do modo desejado. Daí a necessidade
implementação de um programa
entrada, entender o que é esperado
método. Se o método for correto,
método; caso contrário retornamos
este é revisado.
maneira como expressamos nosso raciocínio
capaz de realizar estritamente as tarefas
façam parte do conjunto daquelas
compreender que tipo de instruções podem ser
computadores para que possamos programá-los,computadores para que possamos programá-los,
sequência de ações necessárias para
problema, de modo que realizem a tarefa
necessidade de se discutir a boa
programa. Primeiramente, deve-se entender a
esperado na saída e desenvolver um
correto, analisa-se a complexidade do
retornamos ao passo de bolar um método e
27
•• Algoritmo Algoritmo 
• Os Algoritmos Genéticos formam
inspirados na natureza; simulando
aplicando-os à solução de
generalizados de busca e otimização
naturais de evolução. Capazes
ambientais e convergir para soluções
Na natureza os indivíduos competem
comida e água.
• Adicionalmente, entre os animais
aqueles que não obtêm êxito
número reduzido de descendentes,
probabilidade de seus genes
sucessivas gerações. A combinação
indivíduos que perduram na
indivíduo muito melhor adaptado
ambiente.
Algoritmo Algoritmo genéticogenético
formam a parte da área dos sistemas
simulando os processos naturais e
problemas reais. São métodos
otimização que simulam os processos
Capazes de identificar e explorar fatores
soluções ótimas ou aproximadas.
competem entre si por recursos como
animais de uma mesma espécie,
tendem provavelmente a ter um
descendentes, tendo, portanto menor
serem propagados ao longo de
combinação entre os genes dos
espécie pode produzir um novo
adaptado às características de seu meio
28
Complexidade e implementação de algoritmosComplexidade e implementação de algoritmos
• A preocupação com a complexidade
fundamental para projetar
desenvolver um algoritmo e depois
para verificar a sua eficiência
preocupação de projetar algoritmos
concepção.concepção.
• Ex. Para um dado problema
resolvem.
• Como podemos comparar os
melhor?
• Precisamos definir alguma medida
Complexidade e implementação de algoritmosComplexidade e implementação de algoritmos
complexidade de algoritmos é
algoritmos eficientes. Podemos
depois analisar a sua complexidade
eficiência. Mas o melhor ainda é ter a
algoritmos eficientes desde a sua
considere dois algoritmos que o
os dois algoritmos para escolher o
medida que expresse a eficiência.
29
• No entanto, de nada vale um algoritmo
correto, queremos dizer que o algoritmo
correta para todo entrada.
• Devemos, assim, ser capazes de
eficientes e corretos.
• Para correção do algoritmo, seguimos• Para correção do algoritmo, seguimos
• Se o algoritmo não é óbvio, deve
correção. Em particular, faça a
entrada admitida pelo algoritmo,
computado satisfaz o que é pedido
resultado correto é omitido.
algoritmo eficiente mas incorreto. Por
algoritmo sempre pára com a resposta
de mostrar que nossos algoritmos são
seguimos os seguintes passos:seguimos os seguintes passos:
deve-se dar uma justificativa de sua
a numeração das restrições sobre a
algoritmo, explique porque cada resultado
pedido e explique porque nenhum
30
Estruturas de dados
• Em linguagens de programação
constante ou função define o conjunto
constante ou função podem assumir
•• VetoresVetores
• É uma variável composta por
individuais com as seguintes característicasindividuais com as seguintes características
• OrdenadoOrdenado:: os elementos de um
ordenada.
• HomogêneoHomogêneo:: Todo valor armazenado
ser do mesmo tipo (exemplo: valores
Estruturas de dados
o tipo de dado de uma variável,
conjunto de valores que a variável,
assumir.
VetoresVetores
por uma coleção de elementos
características:características:
um vetor são indexados de forma
armazenado em um mesmo vetor deve
valores inteiros, reais, etc).
31
MatrizesMatrizes
• Uma matriz é vetor de vetores
determinado elemento da matriz
índice representa a linha e
coluna.
•• Tipo de Dados Tipo de Dados •• Tipo de Dados Tipo de Dados 
• Os tipos e estruturas de dados
programa para acessar informações
meio de operações apropriadas
programador, muitas vezes é conveniente
de dados em termos das operações
da maneira como elas são implementadas
MatrizesMatrizes
vetores. Para fazer referência a um
matriz usa-se dois índices: o primeiro
o segundo índice representa a
Tipo de Dados Tipo de Dados AbstratoAbstratoTipo de Dados Tipo de Dados AbstratoAbstrato
dados existem para serem usados pelo
informações neles armazenadas, por
apropriadas. Do ponto de vista do
conveniente pensar nas estruturas
operações que elas suportam, e não
implementadas.
32
Problemas de TransporteProblemas de Transporte
• Um problema de transporte é definido
centros de origens a centros de
produto no local onde o mercado
mercado, é inútil que o fornecedormercado, é inútil que o fornecedor
produto que não é encontrado
que deseja (Andrade, 2004).
Problemas de TransporteProblemas de Transporte
definido como transportar itens de
de destinos, ou seja, disponibilizar o
mercado o exige. Do ponto de vista do
fornecedor disponha de um bomfornecedor disponha de um bom
encontrado pelo cliente no momento em
33
• Na figura acima modelada de
que o produto passa por outros
consumidor, chamada de transporte
variação do modelo de transporte
de tarefas: deve-se designar um
de máquinas ou pessoas, por exemplo,
máquina tem seu respectivo custo
maneira semelhante, é o caso em
outros destinos antes de chegar ao
transporte com transbordo. Ainda, há uma
transporte que é o modelo de designação
um conjunto de serviços a um conjunto
exemplo, sendo que cada par serviço-
custo.
34
• O problema de transporte pode surgir em diversas 
exemplo em transporte de alimentos de industrias aos mercados 
consumidores;
• Transporte de pedras de centros de 
ao longo de uma rodovia em construção; designação 
tarefas a maquinas; 
• Transporte de produção agrícola 
etc.etc.
São dados conhecidos do problema de transporte:
• O custo de transporte de cada item;
• As quantidades dos itens disponíveis 
• As demandas de cada consumidor.
O problema de transporte pode surgir em diversas situações, por 
transporte de alimentos de industrias aos mercados 
pedras de centros de mineração para depósitos 
rodovia em construção; designação de 
produção agrícola do campo ate armazéns e 
dados conhecidos do problema de transporte:
custo de transporte de cada item;
disponíveis em cada centro;
demandas de cada consumidor.
35
• O transporte deve ser efetuado
oferta em cada centro seja respeitadaoferta em cada centro seja respeitada
mercado atendida e o custo total
efetuado de modo que as limitações de
respeitada e a demanda de cadarespeitada e a demanda de cada
total de transporte seja mínimo.
36
Roteamento de Veículos: 
Problemas de cobertura de nós
• Um problema de roteamento
conjunto de elementos que
demandas localizadas nos
determinada rede de transporte
estabelecer quais veículos vão
forma a minimizar os custosforma a minimizar os custos
conjunto de cidades/consumidores,
demanda , um deposito, e
capacidade.
• A finalidade desse tipo de problema
de paradas de veículos, bem
sequencia com que esses pontos
estabelecendo assim, as rotas para
Roteamento de Veículos: 
de cobertura de nós
pode ser considerado como um
que tem como objetivo atenderarcos ou nos vértices de
transporte. Ou seja, consiste em
vão atender a quais clientes de
custos de transporte, analisando umcustos de transporte, analisando um
cidades/consumidores, cada qual com uma
e uma frota com veículos de
problema é a designação de pontos
bem como a determinação da
pontos de parada são visitados,
para os veículos.
37
Problema do Caixeiro Viajante
• O problema do caixeiro viajante
ciclo de Hamilton, em um grafo,
ciclo Hamiltoniano e caracterizado
existência de uma rota, que passasse
terminando no mesmo no, sem
Este ciclo e denominado de HamiltonEste ciclo e denominado de Hamilton
Rowan Hamilton, que em 1957
Around the World . O ciclo Hamiltoniano
representado em preto na figura
todos baseados em Campos, 1998
Problema do Caixeiro Viajante
viajante e baseado no calculo de um
grafo, de minimização de custo. O
caracterizado pela possibilidade da
passasse pelos nos, iniciando e
sem nunca repetir uma passagem.
Hamilton em homenagem WillianHamilton em homenagem Willian
1957 propôs um jogo denominado
Hamiltoniano em um grafo esta
figura 2.5. Os exemplos a seguir são
1998.
38
39
Trabalho:
• O que é o Problema do caixeiro Viajante?
• Suas característica;
• Seus objetivos;
• Possíveis recursos a serem aplicados;
• Figuras e explicações citando exemplos na prática.
• Quais os métodos de resolução aplicados?
Trabalho:
O que é o Problema do caixeiro Viajante?
Possíveis recursos a serem aplicados;
Figuras e explicações citando exemplos na prática.
Quais os métodos de resolução aplicados?
40
Exercícios:
• 01. O que é um algoritmo e quais os passos se deve seguir para 
que seja desenvolvido de maneira 
• 02. Escreva um algoritmo em linguagem natural que represente 
a troca de uma lâmpada.
• 03. Quais os passos para correção de um algoritmo?
04. O que é um vetor?• 04. O que é um vetor?
• 05. O que é uma matriz?
• 06. Para que um problema de transporte tenha solução, o que é 
necessário verificar?
• 07. Qual a finalidade de um problema de roteamento de 
veículos?
Exercícios:
01. O que é um algoritmo e quais os passos se deve seguir para 
de maneira eficiente?
02. Escreva um algoritmo em linguagem natural que represente 
03. Quais os passos para correção de um algoritmo?
06. Para que um problema de transporte tenha solução, o que é 
Qual a finalidade de um problema de roteamento de 
41
3333
Tomada Tomada de de Decisão e Decisão e Resolução Resolução 
3333
Resolução Resolução de Sistemas de Sistemas LinearesLineares
42
Tomada de decisão em 
• Supondo que estamos numa
um problema que foi resolvido
operacional.
• A solução esta pronta para ser
• E prática? E possível? Ela realmente
empresa?empresa?
• Inicialmente, e necessário entender
situação da empresa. Quando
de um dos métodos de pesquisa
alguém que entenda da situação
Dessa forma, devemos compreender
validação, análise da solução
Tomada de decisão em sistemas logísticos
empresa e nos deparamos com
resolvido utilizando a pesquisa
ser implementada?
realmente representa a realidade da
entender se o modelo representa a
Quando obtemos uma resposta através
pesquisa operacional, precisamos de
situação para que analise a solução.
compreender os processos de
e tomada de decisão.
43
Validação de modelos de Validação de modelos de 
• Processo de validação pode ser
mais apropriada de se testar a realidade
mundo real (Vasco,2012). Segundo
pesquisa operacional e melhor aplicada
modelos que expliquem ou capturemmodelos que expliquem ou capturem
comportamento dos problemas
operacionais reais, que possam
das analises sejam testados na pratica
Validação de modelos de Validação de modelos de pesquisa operacionalpesquisa operacional
expresso como sendo a maneira
realidade percebida do sistema do
Segundo Morabito e Pureza (2010), a
aplicada quando são estudados
capturem parte importante docapturem parte importante do
problemas encontrados em processos
ser validados e cujos resultados
pratica.
44
• Uma área importante da validação
processo de testar os programas
esperado.
• Nesse processo, a realização
para identificar possíveis errospara identificar possíveis erros
desempenho da implementação
e comum.
• A verificação pode ser considerada
de validação, uma vez que e
assegura a si próprio e a outros
realmente o se pretendia construir
validação e a da verificação, que e o
programas para verificar o desempenho
realização de diversos testes preliminares
erros e verificar a adequação e oerros e verificar a adequação e o
implementação computacional do algoritmo
considerada como parte do processo
e o processo pelo qual o cientista
outros que o modelo desenvolvido e
construir.
45
• E importante considerar que
parte de quem observa o sistema
• Modelo pode parecer plausível
produzidos, mas, sob um
interessadas, produz diferentesinteressadas, produz diferentes
• A utilidade, ou conveniência,
usuário e do contexto ao qual
• Ex. Qual o melhor modelo de Gestão?
ha diferentes entendimentos por
sistema.
plausível na estrutura e resultados
minucioso exame de partes
diferentes interpretações.diferentes interpretações.
conveniência, depende do ponto de vista do
ele esta inserido.
Gestão?
46
Tomada de decisãoTomada de decisão
O processo de tomada de decisão,
gerencial e processo de colher informações,
posteriormente buscar possíveis alternativas
escolha entre alternativas.
Dai a importância de escolha de parâmetros
para a tomada de decisão e sua mensuraçãopara a tomada de decisão e sua mensuração
A tomada de decisão deve ser feita
competência e consciência, para que
esperado, ou mais próximo dele.
problema, reunião de dados para analise
do problema, investigação de soluções
alternativas, seleção da solução mais
solução escolhida e avaliação dos resultados
Tomada de decisãoTomada de decisão
decisão, de acordo com o ponto de vista
informações, atribuir importância a elas,
alternativas de solução e, depois, fazer
parâmetros Quantitativos/qualitativos
mensuração.mensuração.
feita com conhecimento, racionalidade,
que resulte no alcance do objetivo
Suas etapas são: identificação do
analise das causas e das consequências
soluções alternativas, avaliação das
mais adequada, implementação da
resultados
47
tomada de decisão esta cada vez mais difícil
ritmo de mudanças aceleradíssimo, incerteza
departamentos, poucos registros de situações
tomada de decisões. Ou seja, Problemas de processos
processo decisório inicia a partir da percepção
esta acontecendo, mas nem sempre o problemaesta acontecendo, mas nem sempre o problema
analise do problema e constituída de uma
aprendidos e utilizados como instrumentos
ajudam a qualificar as decisões. O conhecimento
decisório permite a tomada de consciência das
inclusive das possíveis omissões no próprio
habilidades necessárias ao reforço dos pontos
difícil devido a sobrecarga de informações,
incerteza crescente e metas conflitantes entre
situações anteriores e necessidade frequente de
processos.
percepção de que algo fora da normalidade
problema esta bem delimitado.problema esta bem delimitado.
uma serie de processos que podem ser
instrumentos do processo de trabalho gerencial, e
conhecimento das etapas ou fases do processo
das suas certezas e debilidades,
próprio processo, incitando a aquisição de
pontos fracos e das correções necessárias
48
• No campo da estratégia logística,
arranjo entre os diferentes componentes
sistema. Essas decisões são baseadas
(trade-off) entre diferentes critérios,
total, nível de serviço.
•• Alguns direcionadores:Alguns direcionadores:
1. Definir o problema de maneira clara e precisa.
2. Listar alternativas potenciais.2. Listar alternativas potenciais.3. Listar vulnerabilidades potenciais.
4. Quantificar e ponderar as alternativas estudadas.
5. Identificar os custos e benefícios de cada alternativa.
6. Criar o modelo matemático para busca da 
7. Identificar e implantar a solução ótima.
decisões referem-se a definição do
componentes logísticos para a montagem do
baseadas em analise de balanceamento
critérios, como por .exemplo menor custo
Alguns direcionadores:Alguns direcionadores:
Definir o problema de maneira clara e precisa.
Quantificar e ponderar as alternativas estudadas.
de cada alternativa.
para busca da solução.
solução ótima.
49
DentroDentro dodo contextocontexto logístico,logístico, háhá variasvarias decisõesdecisões
Os componentes do sistema logístico como
necessidades de materiais, processamento
e manuseio de materiais, organização
custo do serviço, escolha dos modais de
Pode-se organizar o processo de tomada
inteligências, obtenção de conclusões e
Os quadros determinam o ponto de vistaOs quadros determinam o ponto de vista
observa a questão e define parâmetros
considera importante e também para o
de modo preliminar quais critérios fazem
A informação buscada deve ser adequada
oportuna, clara e de baixo custo.
decisõesdecisões aa seremserem tomadas,tomadas, porpor exemploexemplo
como estrutura de instalações, previsão
processamento de pedidos, estoque, armazenagem
do serviço de transporte, nível de serviço,
de transporte, rotas e etc.
tomada de decisão em quadros, reunião
e aprendizado com a experiência.
vista a partir do qual quem toma decisõesvista a partir do qual quem toma decisões
parâmetros para os aspectos da situação que
o que não considera importante. Definem
fazem preferir uma opção em lugar de outra
adequada a situação, ter qualidade,
50
Por sua vez, o pensamento para se tomar uma 
simples (mecanicista) ou sistêmico:
Por sua vez, o pensamento para se tomar uma decisão pode ser 
51
Informação e Sistemas de Apoio à decisãoInformação e Sistemas de Apoio à decisão
Vive-se o momento da informação cada
de distancias, dados os avanços tecnológicos
como fonte geradora de negócios.
ser considerada como diferencial de
alternativas de lucratividade e retorno
oportunidades de negócios ou contribuindo
empresa no mercado.empresa no mercado.
Diante disso e importante observar
Gestores, frente a importância da tecnologia
uma área estratégica e não simplesmente
sobretudo, os impactos da TI nas empresas
Informação e Sistemas de Apoio à decisãoInformação e Sistemas de Apoio à decisão
cada vez mais ágil e sem barreiras
tecnológicos contemporâneos, e
Dessa forma, a informação deve
de negócios quando proporciona
retorno para a empresa, seja criando
contribuindo para posicionamento da
o papel dos Administradores /
tecnologia da informação como
simplesmente tecnicista, observando,
empresas.
52
• O sistema de informações gerenciais
dos diversos níveis gerenciais
provendo relatórios gerenciais
imediato, ou seja, online, às ocorrências
dados internos. Os relatórios gerenciaisdados internos. Os relatórios gerenciais
tomar uma decisão mais precisa
gerenciais atende às necessidades
gerenciais da gestão nas organizações,
e, em alguns casos, com acesso
ocorrências de desempenho e a
gerenciais devem ajudar o gestor agerenciais devem ajudar o gestor a
precisa.
53
54
Aplicações de suporte às 
• Apesar de existirem decisões fáceis
padronizados, também há decisões
lento, complexo e confuso
problemas forem, mais instáveis
estratégia de decisão maisestratégia de decisão mais
simples e habituais permitem decisões
resultado de regras conhecidas
aceitas por eles. Os problemas
decisão complexa e não programada,
utilização de modelos analíticos
figura.
Aplicações de suporte às decisões
fáceis que seguem procedimentos
decisões em que o processo é mais
confuso. Quanto menos familiares os
instáveis e complexos, o que requer uma
analítica e lenta Os problemasanalítica e lenta Os problemas
decisões programadas. Estas são o
conhecidas dos atores organizacionais e
problemas menos familiares exigem uma
programada, que pode demandar a
analíticos como os representados na
55
56
Método simplexMétodo simplex
• Programação Linear A programação
utilizada para calcular a solução
requer uma decisão ou um conjunto
melhor uso de um conjunto limitado
atingir um ou mais objetivos. Para
é necessário converter o problema
matemático que incorporematemático que incorpore
problema; explorar as diferentes
calcular a solu- ção mais favorável
importante observar que A Programação
requer que, no modelo, todas as
Método simplexMétodo simplex
programação linear é uma técnica
solução ótima de um problema que
conjunto de decisões acerca do
limitado de recursos disponíveis para
Para utilizar a programação linear,
problema proposto num modelo
os elementos essenciais doos elementos essenciais do
diferentes soluções do problema e
favorável ou a solução ótima. É
Programação Matemática Linear
as funções sejam lineares.
57
Os conceitos e nomenclaturas utilizados por essa 
• Solução (decisão, ponto): conjunto de valores
e auxiliares) independentemente de serem desejáveis
• Solução admissível: uma solução que satisfaz
• Região admissível (espaço das soluções admissíveis,
coleção de todas as soluções admissíveis;
• Retas de nível da função objetivo (linhas de
a função tem o mesmo valor;
• Solução Ótima (ótimo): uma solução admissível
favorável (máximo ou mínimo);
• Valor Ótimo: valor da função objetivo associado
• Restrição ativa: diz-se de uma restrição saturada
• Restrição inativa ou não ativa: diz-se de uma
nula);
• Ponto extremo: é um ponto do conjunto
combinação linear convexa de pontos do conjunto
conceitos e nomenclaturas utilizados por essa técnica
valores para todas as variáveis do modelo (decisão
desejáveis ou mesmo admissíveis;
satisfaz todas as restrições (técnicas e lógicas);
admissíveis, convexo das soluções admissíveis):
isso-custo ou isso-lucro): retas em cujos pontos
admissível onde a função atinge o valor mais
associado a uma solução ótima;
saturada (a variável auxiliar é nula);
uma restrição não saturada (variável auxiliar não
de soluções que não pode ser obtido por
conjunto.
58
• Um problema de programação linear pode ter três tipos de 
solução: 
• Sem solução: a região admissível é vazia; 
• Solução ilimitada: a região admissível é ilimitada na direção 
ótima de otimização; 
Solução admissível e limitada: há região admissível e num ou • Solução admissível e limitada: há região admissível e num ou 
mais dos seus extremos a solução é ótima.
Um problema de programação linear pode ter três tipos de 
solução: a região admissível é vazia; 
ilimitada: a região admissível é ilimitada na direção 
admissível e limitada: há região admissível e num ou admissível e limitada: há região admissível e num ou 
mais dos seus extremos a solução é ótima.
59
ATIVIDADESATIVIDADES
01. Quando se considera um modelo de pesquisa operacional válido? 
02. Defina processo de tomada de decisão
03. Quais as principais dificuldades no processo de tomada de decisão 
contemporâneo? 
04. Quais direcionadores utilizamos para facilitar o processo decisório? 
05. Quais as principais decisões a serem tomadas dentro do campo logístico
06. Como se pode organizar o processo de tomada de decisão? Disserte sobre 06. Como se pode organizar o processo de tomada de decisão? Disserte sobre 
cada um dos passos. 
07. Qual a diferença entre o pensamento mecanicista e o pensamento tecnicista? 
08. O que um sistema de informação precisa para ser efetivo
09. Quais são os modelos analíticos utilizados em um sistema de tomada de 
decisão? 
10. Quais tipos de problema o método simplex pode resolver
11. O que éprogramação linear?
ATIVIDADESATIVIDADES
. Quando se considera um modelo de pesquisa operacional válido? 
. Defina processo de tomada de decisão.
. Quais as principais dificuldades no processo de tomada de decisão 
. Quais direcionadores utilizamos para facilitar o processo decisório? 
. Quais as principais decisões a serem tomadas dentro do campo logístico?
. Como se pode organizar o processo de tomada de decisão? Disserte sobre . Como se pode organizar o processo de tomada de decisão? Disserte sobre 
. Qual a diferença entre o pensamento mecanicista e o pensamento tecnicista? 
. O que um sistema de informação precisa para ser efetivo?
. Quais são os modelos analíticos utilizados em um sistema de tomada de 
. Quais tipos de problema o método simplex pode resolver?
60
• 12. Qual o primeiro passo na resolução de sistemas de 
equações lineares? 
• 13. O que se deve fazer quando, em um problema de 
transporte, a utilização de recurso é menor que a 
disponibilidade?
• 14. O que se deve fazer quando, em um problema de 
transporte, a disponibilidade é maior do que a demandatransporte, a disponibilidade é maior do que a demanda
• 15. Quais os passos para deixar um modelo de programação 
linear na forma padrão do método simplex?
o primeiro passo na resolução de sistemas de 
. O que se deve fazer quando, em um problema de 
transporte, a utilização de recurso é menor que a 
. O que se deve fazer quando, em um problema de 
transporte, a disponibilidade é maior do que a demanda?transporte, a disponibilidade é maior do que a demanda?
. Quais os passos para deixar um modelo de programação 
linear na forma padrão do método simplex?
61
44
Resolução de Problemas de TransporteResolução de Problemas de TransporteResolução de Problemas de TransporteResolução de Problemas de Transporte
44
Resolução de Problemas de TransporteResolução de Problemas de TransporteResolução de Problemas de TransporteResolução de Problemas de Transporte
62
Problema do fluxo máximoProblema do fluxo máximo
• O objetivo de um problema de fluxo máximo é desenvolver
quantidade de material enviada entre dois pontos de
• Um problema de fluxo máximo pode ser modelado por
materiais são transportados.
•• Aplicações de um problema de fluxo Aplicações de um problema de fluxo 
• O envio de produtos do produtor ao distribuidor;
• A desde a estação de correio até os seus destinatários
de trabalho;de trabalho;
• A expedição de cartas;
• Modelagem de líquidos fluindo por tubos;
• Peças por linha de montagem;
• Informações por redes de comunicações;
• Correntes por redes elétricas, entre outras;
Problema do fluxo máximoProblema do fluxo máximo
desenvolver um esquema de transporte que maximize a
de origem e destino.
por uma rede. A origem, o destino e por meio das quais os
Aplicações de um problema de fluxo Aplicações de um problema de fluxo máximomáximo
destinatários deslocação das pessoas das suas casas para os locais
63
Resolução utilizando algoritmos de transporteResolução utilizando algoritmos de transporte
• Um problema de transporte é considerado
supre toda a demanda. Num problema
igualdades.
• Como balancear um problema de
fornecimento excede a demanda: cria
• A demanda nesse ponto será igual
variável de folga).variável de folga).
• Como balancear o problema quando
capacidade de fornecimento?
• Neste caso, o problema não possui
pode-se adicionar um ponto fictício
atraso ou de estoque).
• O custo de fornecimento daquele ponto
pelo não fornecimento do insumo.
Resolução utilizando algoritmos de transporteResolução utilizando algoritmos de transporte
considerado balanceado se o fornecimento
problema balanceado, as restrições são todas
de transporte quando a capacidade de
cria-se um ponto fictício de demanda.
igual ao excedente da capacidade (uma
quando a demanda é maior que a
possui soluções viáveis. Como alternativa,
fictício de fornecimento (uma variável de
ponto será igual à penalização incorrida
64
ATIVIDADESATIVIDADES
• 01. Qual o objetivo de um problema de fluxo 
• 02. Como um problema de fluxo máximo pode ser modelado
• 03. Quais as três propriedades que um fluxo em redes deve 
respeitar?respeitar?
• O que é capacidade residual?
ATIVIDADESATIVIDADES
. Qual o objetivo de um problema de fluxo máximo
02. Como um problema de fluxo máximo pode ser modelado?
03. Quais as três propriedades que um fluxo em redes deve 
O que é capacidade residual?
65
Um problema de fluxo em redes:
• O Fluxo em redes deve respeitar as seguintes
• Restrição de capacidade: o fluxo que
ou menor que a capacidade máxima deste
• Anti-simetria obliqua: o fluxo em uma
direção oposta. Essa propriedade e valida
• Conservação de fluxo: O fluxo que entra
origem e no sorvedouro.origem e no sorvedouro.
• O papel do nó sorvedouro é o de fazer
em que ele faz parte com uma rede
ou por um link de internet, além de poder,
recebidos antes de efetuar a sua transmissão
• Obs. O sorvedouro é para onde
coletados. O sorvedouro pode ser o
ou apenas um gateway para uma rede
• Obs. Um Gateway, ou ponte de ligação,
destinada, geralmente, a interligar
mesmo traduzir protocolos.
problema de fluxo em redes:
seguintes propriedades:
que circulará em um grafo deve ser igual
deste fluxo.
uma direção deve ser igual ao seu fluxo na
valida para grafos não orientados.
entra deve ser igual ao que sai, exceto na
fazer a comunicação dos dados da rede
rede externa, seja por meio de um gateway
poder, também, fazer a fusão dos dados
transmissão.
os nós sensores transmitem os dados
o consumidor final dos dados coletados,
rede externa (Internet).
ligação, é uma máquina intermediária
redes, separar domínios de colisão, ou
66
A Capacidade Residual
• A Capacidade Residual e representada
capacidade restante em umacapacidade restante em uma
fluxo f na mesma.
A Capacidade Residual
representada por: (cf), onde e a
uma aresta ou arco apos passar umuma aresta ou arco apos passar um
67
Algoritmo de Fluxo Máximo
• De acordo com Cormen (2009), o
máximo através das seguintes interações
• 1. Injetar um fluxo nulo no nó de entrada
• 2. Capacidades iniciais dos ramos = capacidade
• 3. Determinar um caminho não saturado
entrada e o no de saída; se não existir,
• 4. Somar ao fluxo de entrada um
selecionado;
• 5. Alterar as capacidades dos ramos
lhes o fluxo injetado;
• 6. Voltar ao ponto 3.
Algoritmo de Fluxo Máximo
o pode-se resumir o algoritmo de fluxo
interações:
entrada;
capacidade total dos ramos;
saturado (capacidade= 0) entre o no de
existir, foi encontrada a Solução Ótima;
fluxo igual a capacidade do caminho
ramos do caminho selecionado, diminuindo-
68
Algoritmo de Ford 
• De acordo com Alves et al. 2011, o algoritmo de Ford 
constituído pelas seguintes iterações:
• 1. Escolhe-se um caminho qualquer desde a origem ate ao destino, 
mas em que os arcos orientados que os constituem tenham 
capacidade positiva (>0).
2. Procurar nesse caminho o arco orientado com menor capacidade, • 2. Procurar nesse caminho o arco orientado com menor capacidade, 
c.
• 3. Diminuir de c a capacidade de fluxo em cada arco do caminho no 
sentido considerado.
• 4. Regressar ao 1o passo. Se já não 
todos os arcos tenham capacidade positiva, tal significa que 
determinou o fluxo maximo.
Algoritmo de Ford – Fulkerson
acordo com Alves et al. 2011, o algoritmo de Ford – Fulkerson e 
iterações:
se um caminho qualquer desde a origem ate ao destino, 
que os arcos orientados que os constituem tenham 
Procurar nesse caminho o arco orientado com menor capacidade, Procurar nesse caminho o arco orientado com menor capacidade, 
Diminuir de c a capacidade de fluxo em cada arco do caminho no 
já não existir nenhum caminho em quearcos tenham capacidade positiva, tal significa que já se 
69
Problema do caminho mínimo
• De acordo com Campos (1998
dependendo das suas características,
caminhos entre um par de nos,
destino (t). Entre os vários caminhos
“peso” e chamado de caminho
• Este peso representa a soma
compõem o caminho e estes
anteriormente podem ser: o
percorrida ou um custo qualquer
• Assim, os algoritmos de Caminho
menor tempo, distancia ou custo
origem e destino.
Problema do caminho mínimo
1998), em uma rede qualquer,
características, podem existir vários
nos, definidos como origem (s) e
caminhos aquele que possui o menor
caminho mínimo.
total dos valores dos arcos que
estes valores conforme referenciados
tempo de viagem, a distancia
qualquer do arco.
Caminho Mínimo determinam a rota de
custo entre um par ou pares de
70
Resolução utilizando algoritmos de
transporte
• Para utilizar um algoritmo de transporte
• Um problema de transporte e considerado
supre toda a demanda.
• Num problema balanceado, as restrições
balancear um problema de transporte
fornecimento excede a demanda: criafornecimento excede a demanda: cria
demanda nesse ponto será igual
variável de folga). Como balancear
maior que a capacidade de fornecimento?
• Neste caso, o problema não possui soluções viáveis. 
se adicionar um ponto fictício de fornecimento (uma 
de estoque).
• O custo de fornecimento daquele ponto 
pelo não fornecimento do insumo.
Resolução utilizando algoritmos de
transporte
transporte o problema deve estar balanceado.
considerado balanceado se o fornecimento
restrições são todas igualdades. Como
transporte quando a capacidade de
cria-se um ponto fictício de demanda. Acria-se um ponto fictício de demanda. A
ao excedente da capacidade (uma
balancear o problema quando a demanda e
fornecimento?
soluções viáveis. Como alternativa, pode-
de fornecimento (uma variável de atraso ou 
O custo de fornecimento daquele ponto será igual a penalização incorrida 
71
Exercícios
• 01. Qual o objetivo de um problema de fluxo 
• 02. Como um problema de fluxo máximo pode ser modelado?
• 03. Quais as três propriedades que um fluxo em redes deve 
respeitar?respeitar?
• 04. O que é capacidade residual?
• 05. O que calcula o algoritmo de 
Exercícios
o objetivo de um problema de fluxo máximo?
02. Como um problema de fluxo máximo pode ser modelado?
03. Quais as três propriedades que um fluxo em redes deve 
O que é capacidade residual?
O que calcula o algoritmo de Dijkstra?
72
5
CongestionamentoCongestionamento
Teoria das Filas
5
Congestionamento:Congestionamento:
Teoria das Filas
73
• No caso logístico, tal teoria
ferroviário, rodoviário, marítimo
No transporte ferroviário o
apresenta problemas interessantes,
localização dos desvios e alocaçãolocalização dos desvios e alocação
(com base em uma tabela de
ou adicionados), além da tabela
que passam pelo local.
tem sido usada no transporte
marítimo e no transporte por elevadores.
pátio de consertos e serviços
interessantes, que incluem o numero e
alocação de maquinas de serviçoalocação de maquinas de serviço
de trens e carros a serem removidos
tabela de horários de trens diretos
74
• Por outro lado, o sistema ferroviário
um todo, com o objetivo de minimizar
vazios. No transporte marítimo
a confecção da tabela de
portos e aeroportos.portos e aeroportos.
• No modelo rodoviário e possível
estabelecer o melhor esquema
de uma cidade, com as durações
melhorar o serviço, agilizando
diminuindo os gastos com combustível
ferroviário pode ser analisado como
minimizar o movimento de carros
e aéreo as aplicações se referem
horários e dimensionamento de
possível dimensionar um pedágio ou
esquema do fluxo de veículos pelas ruas
durações dos semáforos, de modo a
o sistema e, consequentemente,
combustível.
75
Teoria das Filas
• A teoria das filas tem como objetivo
sistema de filas e seus parâmetros,
2004):
Tempo de espera médio
Probabilidade de formação de fila
Porcentagem de clientes rejeitados pelo sistema
Probabilidade de um cliente esperar mais do que um certo tempo
Numero médio de clientes na fila
Probabilidade de que todos os servidores estejam ociosos
Teoria das Filas
objetivo avaliar o comportamento de um
parâmetros, como por exemplo (Andrade,
Porcentagem de clientes rejeitados pelo sistema
Probabilidade de um cliente esperar mais do que um certo tempo
Probabilidade de que todos os servidores estejam ociosos
76
• Os sistemas de filas diferem entre si de
a respeito dos padrões de chegada
precisamos adotar hipóteses sobre
características de um sistema de
discutidas mais profundamente no decorrer
• a) Processo de Chegada• a) Processo de Chegada
• b) Distribuicao de Tempo de Servico
• c) Quantidade de Servidores
• d) Tamanho do Sistema de Fila
• e) Populacao de Clientes
• f) Disciplina de Atendimento
de acordo com as hipóteses que fazemos
chegada e das taxas de serviço. Na analise,
sobre o comportamento do sistema. As
filas estão listadas a seguir e serão
decorrer deste capitulo.
77
• Processo de chegada De acordo com
chegada de usuários no sistema e
chegadas sucessivas de usuários.
• Em geral, admite-se que não mais de
instante e que o processo de chegada
Também admitimos que ele não
presentes no sistema.presentes no sistema.
• Uma exceção e sistema com desistência
exemplo, um cliente desiste de entrar
longa.
• Em suma, podemos considerar que
mesma classe ou agrupados em múltiplas
supõe-se todos os usuários de uma
idênticos, com intervalos entre chegadas
probabilidade.
com Arenales et al., 2011, o processo de
descrito pelo intervalo de tempo entre
de um usuário pode chegar no mesmo
chegada não varia ao longo do tempo.
e afetado pelo numero de usuários
desistência na chegada, como quando, por
entrar em um cinema porque a fila esta muito
que todos os usuários pertencem a uma
múltiplas classes diferentes. Dessa forma,
uma mesma classe são estatisticamente
chegadas modelados por um distribuição de
78
• Se os clientes chegam em instantes
randômica τj = tj - tj-1 e chamada
Assume-se que os τ j formam
aleatórias independentes
processo de chegada mais comumprocesso de chegada mais comum
significa que os Tempos Inter chegadas
distribuídos.
instantes t1 , t2 , ..., tj a variável
chamada Tempo entre chegadas.
formam uma sequencia de variáveis
identicamente distribuídas. O
comum e o Processo de Poisson. Issocomum e o Processo de Poisson. Isso
chegadas são exponencialmente
79
Distribuição de Tempo
• O processo de atendimento e
de atendimento e taxa de
representam a velocidade com
realizando o atendimento. Seu
processo de chegadas.processo de chegadas.
Tempo de Serviço
e especificado pelo tempo médio
atendimento que na verdade
com que o servidor do sistema esta
Seu comportamento e análogo ao
80
Quantidade de servidores
• O mais simples sistema de filas
que pode atender um único
aumente o ritmo de chegada,
serviço aumentando convenientemente
servidores. Esta e, portanto, umaservidores. Esta e, portanto, uma
que pode-se utilizar para modelar
2004).
Quantidade de servidores
filas e aquele de um único servidor
cliente de cada vez. Conforme
chegada, pode-se manter a qualidade do
convenientemente o numero de
uma das características de uma filauma das características de uma fila
modelar um sistema de filas (Andrade,
81
Tamanho do Sistema de Fila 
ou 
Capacidade 
• Esta característica indica o numero
sistema comporta, tanto clientes
fila, também pode ser chamadofila, também pode ser chamado
capacidade pode ser finita
aguardando para serem torneadas
como também infinita no caso
para ingressarem no porto
capacidade finita, caso ela seja
rejeitadosem virtude da incapacidade
do Sistema de Fila 
ou 
Capacidade do Sistema
numero máximo de usuários que o
clientes em atendimento quanto em
chamado de buffer do sistema. Estachamado de buffer do sistema. Esta
finita como no caso de pecas
torneadas em uma linha de produção
caso de trens aguardando na ferrovia
porto. No caso de sistemas com
seja atingida, novos clientes serão
incapacidade de atendimento.
82
População de Clientes
• E a quantidade de usuários em
momento, usar o sistema ,
banco, assinante de linha telefônica
• Nos sistema reais a população
população e finita, a taxapopulação e finita, a taxa
população, ou seja a taxa de chegada
população e assumida como
chegada e considerada constante
População de Clientes
em potencial que pode, em algum
como por exemplo clientes de
telefônica.
população e limitada ou finita. Quando a
taxa de chegada dependera dataxa de chegada dependera da
chegada será variável. Quando a
como infinita temos que a taxa de
constante.
83
Disciplina das filasDisciplina das filas
• A disciplina das filas define a regra
sistema.
• Podem ser dos seguintes tipos:
“Primeiro a Entrar Primeiro a Sair”)
acordo com a ordem de chegada
com a ordem de chegada. LIFO
a Entrar Primeiro a Sair”): isto e, quem
com a ordem de chegada. LIFO
a Entrar Primeiro a Sair”): isto e, quem
ser atendido. E um tipo de disciplina
estoque. PRI (“priority service”):
acordo com uma prioridade pré-
se citar o ingresso de mulheres gravidas
cargas para navios com vencimento
(“service in random order”) serviço
atendimentos ocorrem de forma
de consórcios (Andrade, 2004).
Disciplina das filasDisciplina das filas
regra de atendimento dos usuários no
FIFO ou PEPS (“First in First Out” ou
Sair”): os usuários sao atendidos de
chegada isto e, atendimento de acordo
ou UEPS (“Last in Firs Out” ou “Ultimo
quem chega por ultimo e o primeiro a
ou UEPS (“Last in Firs Out” ou “Ultimo
quem chega por ultimo e o primeiro a
disciplina mais aplicado a modelos de
: os atendimentos acontecem de
-estabelecida. Como exemplo pode-
gravidas em um ônibus ou transito de
vencimento do dead line data limite. SIRO
em ordem aleatória o: e o caso em que os
forma aleatória. Exemplo: contemplação
84
Notação de Kendall 
• Para simplificar a analise dos sistemas
classificados conforme a notação
sistemas de fila única com um
paralelo (Arenales et al. 2011).
• A = Distribuição de tempo Inter chegada
• S = Distribuição de tempo de serviço
• m = Numero de canais de serviço
• B = Capacidade do sistema
• K = Tamanho da população
• DS = Disciplina de serviço
Notação de Kendall – Lee
sistemas de filas, os mais simples foram
notação de Kendall-Lee, que considera
um ou mais servidores idênticos em
chegada
serviço
serviço simultâneo (servidores)
85
Classificação de um sistema de filas
• De acordo com a notação de
combinações de elementos para
• Processo de nascimento e morte
• O processo de nascimento e
processos estocásticos (função ou
do tempo) em que são permitidas
vizinhos.
• As probabilidades de transição
estado atual e das medias das
chegada e de atendimento.
• Para cada novo elemento que
atendido, caso não seja possível,
acontece o nascimento de um estado
atendimento estiver sendo feito
finalizado o atendimento de um elemento
nesse momento acontece o que
Classificação de um sistema de filas
de Kendall-Lee, podemos ter varias
para caracterizar uma fila.
Processo de nascimento e morte
morte e uma classe especial de
ou sequencia aleatória dependente
permitidas somente transições aos estados
são determinadas em função do
das distribuições dos processos de
que chega, se for possível ele será
possível, entrara na fila (e armazenado),
estado. Isso acontecera enquanto o
feito a outro elemento, quando e
elemento (ele sai do sistema de filas)
se chama de “morte” de um estado.
86