Distribuicao Fisica

Prévia do material em texto

distribuição física
ENG 1545
G
,
- distribuição física
problema de localização
↳ decisão de onde localizar uma ou maisinstalações( infraestrutura , veículos estacionários , etc,
num determinado espaço com resta a atingir
um ou vários objetivos e máis vazando um
conjunto de restrições .
→ vocalização ótima depende do aiipo de infra
-
estrutura em análise .Ls
varia também com o setor do projeto. ( nívb /Miv )
a localização ótima depende da medida deeficiência
do sistema , isto
é
,
da função obreiro .
problemas do localização podem ser dassesucoodos :
o estáticos - não se considera a existência de um
horizonte Imemorial , nem possíveis alterações dos
dados do problema em punção do a-mpo .
o dinâmicos - permitem a consideração explícita de
mais do que um período Imporal .
possibilitam alterações nas configurações dasinstalações
ao longo do a-mpo
. as decisões a tomar
implicam também drpinir quando abriu ou
fechar instalações .
o determinísticas - considera - se que Todos os dados do
problema são conhecidos a priori com total certeza .
o estocástica - incluir incertezas nos dados através ,
normalmente
, da definição de cenários com uma
determinada probabilidade de ocorrência
localização no plano × localização na rede
Sistina de coordenadas
sem restrição do peso .
comporta nos arcos e
nós . transp .
rodoviário
à rede de estrada .
há varios caminhos
para ligar os pontos
A e B
, quase sempre
com distâncias dit.
BEBESSEMOS
distância → unidade de percurso
distância euclidiana
- DEM = (✗☐ - ✗AÍ+ Hrs -Yai
Distância cretina
coeficiente de correção - pode - se relacionar matem
.
as distâncias efetivas com as distâncias euclidianas
,
DAB ? DEAB
valor da distância
"
verdadeira
"
entre dois pontos
.
Dag = a + b × DEAB
distância Retangular
DRAB = / ✗a - XB / + IYA - YBI
localização de instalação única - Centro de gravidade
* =
[ ✓ irixi { ✓ irixi=/ =
[ vi.Ri[ viri
o problemas de localização em rede - são
, por
norma , problemas discretos , isto é , o número de
clientes e o número de potenciais vocalizações
narrou as instalações são em número finito
(embora , possivelmente , muito elevado )
problemas complexos
modelados utilizando métodos de otimização
.
L
problemas que se pretende
determinar o ótimo de
uma punção .
ingredientes de um problema
1- decisões : idrntimcar possíveis soluções ; dit .
das van
.
decisão
2- objetivos : der critério de avaliação capazes de mostrar um
a)
3- restrições : identimcar quais as condiaon.pl as decisões a serem
Tomadas .
método : ✗ = variáveis de decisão
opt
✗
2 = f- (×) Z = valor da sol . encont
f- = punção obstino
Ny . a g (X ) E
O
g = restrições
problema do p - centro
o dsgãivro é minimizar a distância máxima
entre clientes e um número fixo de instalações
de serviços previamente deprimido .
Neste problema
não interessa a quantidade de demanda de
cada ponto .
* determina a distância máxima de cobertura
associado a p instalações .
* viva vocalizar p de n centros de poema a
minimizar o custo máximo de alocação de
clientes para centros de backup .
problemas de p- medianas
↳ O objetivo do modelo ú determinar a localização
de rp instalações que minimiza o custo ( tempo ou
distância ) total do sishma e que garante que
toda
a demanda ú
talis luta .
O número de instalações , p,
ou localizar é nú - ouvindo .
estratégia de distribuição
distribuição direta ×
distribuição através
de um ou mais
de manias intermediários .
t 1
Àpos de sistemas de distribuição
a distribuição "
um para um " ou transferência
de produtos .
O veículo é totalmente carregado
no depósito da
fábrica ou num centro de distribuição
do varejista
(votação completa ) e transporta a carga
mora
um outro ponto do destino, podendo ser outro
centro de distribuição ,
uma rota , ou outra
instalação qualquer .
caminhão visita
um único cliente .
o distribuição de Íum nara muitos " ou compart.
O veículo é carregado no centro de distribuição
do varejista com mercadorias destinadas a
diversas horas ou
clientes
,
e executando um
roteiro de entregas predeterminado .
de
caminhão
visitou vários
clientes .
(a) Objetivo : menor custo operacional ( diminuição do
tempo da rota e do
número de veículos para o
aeimuimenro ) ;
(2) Objetivo : menor éumpo de operação (maior
velocidade média ou percurso, menores compras de
espera , tempo de carga / descarga etc ) .
→ sistema "um para muitos
"
de transferência
O problema espacial de dimensionamento de
coleta / distribuição apresenta algumas caracteres
.
násicas :
Dimensionamento ou sistemas de coleta /distribuição
° SCD 9
[ → quando não
sabemos a drmad
Onde podemos constante .
utilizar dimensionamento
prohabrhstico ?
→ fase ou projeto e planejamento : ainda não se
tem ideia precisa dos pontos de atendimento , então
adota - se valores estimados ,
a fim de possibilitar
a análise ou diversas alternativas .
o
dimensionamento determinístico :
relação entre :
o número necessário de veículos
o número de zonas
o periodicidade de visita o n° de clientes por
zonas .
pela pórmula matemática temos :
m = número de zonas na região
. -
t = intervalo de tempo l dias ) entre vusitas .
ex : t = 1 (visita diária ) , t = 7- lrisita
semanal)
T = total de dias úteis na semana
ex : T= 7 dias úteis /semana .
NR = n° de roteiros diários do veículo
Nv = n° de oráculos
em operação
9- = ni de paradas ou
visitas por roteiro
N = ni total de pontos a serem atendidos
num período t .
Sabe - se que : m = N/g-
se um oráculo trabalha
"T
"
dias úteis por semana,
realizando "Nr
" violinos por dia , parao então
" NR ✗T
" roteiros por semana .
Assim durante um
período " t
"
I sempre em dias
" realizará um
total de roteiros igual a :
n° total nu = m
de roteiros
: Nr ✗ T (%-) nr
,
-
PI cada
oráculo por período
Sistema " um para muitos
"
de transparência
probabilística :
→ apresentação de uma resolução de um sistema
de conta / distribuição na pose
de planejamento e
pronto .
&
inuressanr adotar estimativas
amotinadas
,
a fim de se criar
alternativas de implantação .
o A região geográumca é dividida em zonas :
↳ cada zona é servida por um oráculo e uma
equipe de serviço .
• Para cada oráculo há um roteiro úmuuindo
um número de paradas dentro da zona servida .
Os pontos de parada estão ordenados em uma
certa sequência .
↳ limpo ou ciclo : o serviço de cada oráculo
demanda um tempo
total desde a partida do
oráculo do dráosíeo áú seu
retorno
.
* atenção :
É necessário quantificar a distância média
percorrida , os diversos Tempo que
compõe o
tempo de ciclo e os
custos da nota associados
ao serviço .
Roteiro de análises
a- estimar os tempos e as distâncias
associado ao serviço .
2- analisar os quilos de restrição de
capacidade e tempo no serviço do
distrito
.
Estimativa ou tempos
e distâncias associados
ao serviço .
linha do Trmno
•
wfamjos.ioátomo; arma
.
I I
dvdoe .
entre
zonas
Templo de ciclo : total ( el descarga )
Te = ti + tv + Tp + Te ti = tu
TE = 2T + Tp + Tt→ úmero Total gasto pelo
f f oráculo no deslocamento
dhoiíw Tempo Total
entre os N pontos
é dvhoe gasto do oráculo
de atendimento .
parado no
atendimento dos
N pontos da zona .
Tempo parado nos clientes :
Tp = tô + tp + . . .
+ tp
"
E [TP] = E [N] . E [tp]
VAR [Tp ] = E [N] . VAR[tp]
+ É [tp] .
VAR [N]
tempo de viragem : ida + volta
.
Estimar as distâncias associadas ao serviço
De = d + Dz + do
d-→ distância percorrida pelo veículo
entre dois pontos qualquer na zona deatendimento
.
Dz = Ja + Ja + . _ . + J (N - a) N
E [ Da ] = E [N] . E [J]
VAR [Da] = E [N] .
VAR [J] + É [J] . VAR [ N]
E [De] = 2 E [de] + E [ Da]
VAR [De] = LUAR [d] + VAR[ De]
E [Dg] → extensão otimizada
de uma
rota que atende N pontos
N → número de pontos a serem
alimoídos por um oráculo em uma área A ;
A → área que comporta os N pontos a serem
atendidos por um oráculo
.
tu → uma constante de proporcionalidade
DO uituma dizemos que :
lim E [De ] / N = K
A
n → o
E[Da] = K NA para N → •
E [Da] = E [N ] . E [J ] ⇒ K NA = EEN] . E [J]
E [J] = K A
= K ÷ onde : N = 7A
N
I
E [J] = . f-42 K = 9765
Restrição de capacidade
W = UL
, + Nzt . - +Um
EEW] = E [N] . E Eu]
VAR [W] = E [N] .
VAR [w] + É [w] .
VAR [N]
nem Toda a capacidade do veículo ú
capacidade útil
.
C → a capacidade volumétrica do oráculo
P → percentual de perda do oráculo
n → nível de servicio
R → percentual de capacidade real do oráculo .
R = 1- - P
100
⇒ W E R ✗ e
TL = R ✗e - E [W ]
⇒ e = N × ow + E [W]
OW R
nível de serviço = 50 + N
determinar o número de clientes
E [W] = E [N] . E Eu]
VAR [W] = E [N] . VAR [w] +
Ê Eu] . VAR [N]
N = RC - E (w )
ow
n =
rc - ( E [N] . E Eu] )
E[N] . VAREu] + É [n] - VAR[N]
quando não
Estratégias de distribuição
-
um nível
de serviço : 3,99
ou perda desprezível
duas estratégias de distribuição :
a distribuição direta do fornecedor ou fabricante ao
varejo ou cliente final ,
o a distribuição passando por pontos de armazenagem
de estoque (depósitos / ass )
→ custos envolvidos
Exemplo de dislribuicrão direta :
Estoque na fábrica - fase 1-
O produto , imediatamente após a fabricação ,
vai se
acomodando na indústria de origem ,
constituindo um
primeiro estoque do processo .
máx
médio
Reserva
-330
RESACABARREFERÍAMOS→
adamOona→à↳YEEB
Em = ER + LL = A- ✗ tn
| 30 Ea = Em + ER
= Er + Lz
L
tamanho médio do lotes
ÊA -_ ¥ ( 1- +fr ) ER = tgfr , ER = f- (L) .
↓
fator reservou para fr = 0,5 , ER = 25% do lote da remessa .
Estoque em trânsito - fase 2
Em intervalos definidos o produto é transferido, a partir
do estoque inicial na indústria ,
mora o agente de
comercialização .
+
z
ÊT = f E (t) dt
+ o ltz - to)
Qi
ÊT =
30
L = fã tr
T : tempo de transferência
tri tempo entre remessas
Estoque no agente de comercialização
- fase 3
finalmente a mercadoria permanece estocada
no agente de comercialização até seu consumo rival .
Em = ER + L
E-
B =
Em + ER
= Er + Iz
2
ÊB = Em + ER
= Er +§ = ± ( 1-+fr )
2
fórmulas estoque
1
soma das 3 fases
custo de estoque
Q = produção mensal (t ou m3 )
4 = valor unitário do produto ( $ / t vou $ /m3 )
i = taxa de custo financiero /mês ( juros , despesas
de estocagem e mais outras despesas financeiras ) ;
CME = custo médio mensal em estoque ( $ ) ;
CE = custo de estoque por unidade produzida
($ /tou $ /m3)
CM E = 4 ✗ i ✗ E-
E = Êat Êt + ÊB = 2Er + L + QT
=
L 11 tfr ) + lt
30 30
ÕE = CME = Mx I ✗Ê = M ✗ i ✗ ( L + t.fr +AÍ )
Q Q
Q
Custo de estoque na fábrica (por tonelada ) :
Er = estoque de
ÊE = M X Ix (Er +± ) reserva
Q
Custo de estoque na transferência ( porTonelada) :
c-E = M ✗ i × (Qi 130 )
=
M ✗ I ✗T
Q 30
Q = produção mensal (t ou m3 )
4 = valor unitário do produto ( $ / t vou $ /m3 )
i = taxa de custo financiero /mês ( juros , despesas )
CME = custo médio mensal em estoque ( $ ) ;
CE = custo de estoque por unidade produzida
($ /t ou $ /m3)
T : tempo de transferência
tri tempo entre remessas
L : tamanho médio dos tolos de transparência entre A EB
Em : estoque máximo
EA : estoque ponto médio
ER : estoque reserva
K : remessa ( días )
v : valor da carga ( $ /t )
Transferência de produto
1- custo de carregar o produto na origem ;
2- custo em transporte ;
3- custo em descarregar o produto no destino.
custo total de Transparência :
custo de manuseio + custo deTransporte
O custo de manuseio do produto ( carga e descarga ,
pode ser expresso em punção das unidades , peso
ou volume a ser transportado .
Assim
,
CD ✗ W representa o custo de manuseio
de carga
mora o seu transporte , onde CD é o custo
de manuseio por peso , volume ou
unidade de
produto e W a carga a ser Transportada
.
carga a
custo ou manuseio = e, × W
ser transportada
↓
custo de
manuseio por peso,mid , vuef
o custo eixo : (cf - $ /A ) : amortização do coimtal,
investido no veículo; salário e obrigações
sociais
referentes ao motorista ; licenciamento do
veículo ;
seguro ; mairu rixa do custo de manutenção
(otrano) .
◦ custo variável ( eu - $ 1km ) : combustível i
luhhimcomlr do motor ; Pneus e câmaras de ari
lavagens e graxas ; parte variam do custo de
momuntrmaão ( peças de reposição ) . associado à
distância de transporte (de ) .
custo de transporte em um transparência :
CF ✗ To + CV × d
custo de manuseio : e☐ ✗ W (1)
custo de transporte : CF ✗ T + cv ✗ d l 2)
custo de Transferência : 1- + 2 = CD ✗ W + for (cf ✗
T + CV ✗ d)
dote econômico ( V )
é aquele que minimiza os custos médios totais .
Custo de transferência : Ct = ao + aa Wb
ao
,
ai , b → constantes
W - capacidade de carga de um veículo.
custo unitário médio : F- = ao +ao-w-wi.is 1R$ /t )
transparência
custo unitário médio : c-
e
= vi =
vi [ser + U + Qi
de estoque Q
so
]
adotou as relações a seguir entre a máxima
capacidade prática e o lote econômico U, onde
N é o enterro imediatamente superior a U /W .
N Ú o número de veículos de igual capacidade,
necessários para entrar a transMrêmáa .
(1) W = w se W ≤ máxima capacidade prática
(2) W = NYN se U > máxima capacidade prática
E
= O : lote econômico
ou
hipótese simpeirrcadora :
W = W e b = 1-
µ = ( ao ✗ Q
"2
vxi )
Õ = ao + ae + ✓× i ( 2x Er + U + Q ✗T
U Q 30
conclusões :
1) distância rixa : quanto maior
o valor do
produto , menor o lote
ótimo.
2) valor do produto rixo : quanto
maior a
distância, maior o
loko ótimo .
O Problema macro-logístico:
A) O produto, imediatamente após a fabricação, vai se acumulando na indústria de 
origem, constituindo um primeiro estoque do processo;
B) Em intervalos definidos o produto é transferido, a partir do estoque inicial na indústria, 
para um depósito de triagem e transferência (CD);
C) No depósito, a mercadoria é descarregada e verificada. O produto se acumula nos 
boxes à espera de distribuição. Aparecem custos de manipulação e de estocagem;
D) A seguir a mercadoria é distribuída aos seus destinatários. O processo envolve 
despesas de distribuição e estocagem em trânsito;
E) Finalmente a mercadoria permanece estocada no agente de comercialização até o seu 
consumo final.
utilizou o custo fixo de transparência para
o
dimensionamento do dote econômico .
eu = 1%:?)
"
Distribuição nos intermediário
direta × via depósito de triagem
se o valor absoluto da redução de custo com
a economia de escala na transparência por
maior que a soma dos custos de movimentação
nos depósitos intermediários , então via depósito
de triagem ( CD ) é a melhor opção .
Estoque :
C-e =
✓✗ i [ 2 ✗ Er + U + Qa ✗ ( T+ ta + tb)]Q
a 30
ta : tempo de coleta + triagem do produto
na origem : do momento da coleta na pábrica
até o despacho no depósito 11h ) .
tb : Tempo de triagem e distribuirão final ,
saindo do depósito 2 (h ) ;
Q
,
: produção / consumo mensal no pontos
A e B ltl mês ) vou 1m31 mês )
v :[consumo médio diário] . [untuvalo entre remessas]
U = a
✗ K ✗ t
30
Uma vez que o custo total por transferência via depósito não depende do Lote 𝑈, a 
indústria tenderá a optar pelo menor lote possível, já que, assim o fazendo, tornará mínimo 
o seu custo médio de estoque. Isto corresponde a se fazer 𝐾 = 1 na expressão acima
t : intervalo de Tempo entre remessas massivas
na zona de destino (dias ) .
U = Q
,
✗ tr
30
tr = K ✗t
Transporte
ÕT = CA + CD
,Dzt CB
Ca : custo médio de coleta mais triagem na origem
( $ /Tom vou $ / m3 ) ;
↳ Dz : custo unitário de transferência entre depósitos
1$ / ton ou $ /m ' )
CB : custo médio de triagem no depósito 2 e distribuição
final ( $ trono ou $ /m3 )
viii.Ei
ouro ?
Pode-se dizer que quanto maior o valor do produto é mais interessante despachá-lo mais 
rápido, devido ao juro de oportunidade. Desse modo, se a produção aumenta, para evitar 
um custo de estoque médio alto, a carga deve ser transferida de modo direto.
LEAL (2003) e NOVAES (1989) esclarecem que os custos não devem ser o único critério a 
ser considerado na escolha de uma alternativa de transferência de produtos. Outros 
fatores como segurança contra roubos e avariase a confiabilidade com relação ao tempo 
total de viagem podem pesar nas tomadas de decisão da melhor estratégia de 
transferência. Para isto utiliza-se uma análise multicritério associada com modelos de 
otimização cuja a função objetivo busca minimizar custos.
Análise de estratégia de distribuição
fiz- distribuição física
Teoria dos gratos e redes
notarão : G = ( v , E)
o ✓ = nós lou vértices )
◦ E = arista ( ou arcos ) entre maus de nós
.
◦ captura relacionamentos entre mares e objetos
◦ parâmetros de tamanho de gratos : N = / v1
,
me = | E |
.
✓ = 4 1-
,
2
, 3 , 4 ,
5
,
6
,
7
,
8 }
E = { 1- 2 , 1 - 3 , 2- 3 , 2 - 4 ,
2- 5
,
3 - 5
,
3- 7 , 3
- 8 ,
4- 5
, 6- S , 7- 8 }
N = 8
Me = 1-1-
o M e v são adjacentes ( vizinhos) em G se e somente se
existe uma aresta entre w e v em ↳
.
◦ O grau d ln ) de um vértice é o número de vizinhos de u.
1- e 3 são adjacentes
\ /
2 e 8 não são adjacentes
\
d (3) = 5
d (a ) = 2
>
M = 11
soma de ghouls = 11 . 2 = 22
propriedade importante :
para joao guapo dos graus de G é igual ao dobro
do número de ahrbtah .
conceitos básicos :
Loop : aresta que diga o mesmo vértice .
Aresta paralela : duas arestas que digam o mesmo
mar de vértices .
grupos simples : um guapo simples não possui nem
loops nem arestas paralelas .
↳
m ≤ n in - 1) 12 6
loops
desejando
→
Representação de gratos : ←
matriz de adjacência .
matriz N ✗ n com Awv = 1 se tu,
v)
ú uma aresta .
O duas representações para cada aresta.
O espaço proporcional a nt.
◦ checar se lu ,V1 é uma aresta custa tempo 0-11 ) .
O iidmliarcar utodas as arestas custa olimpo
e (ni )
vantagem : boa para grupos densos
/
desvantagem : tamanho independente do
número de arestas .
num grato linha ( n vértice w n - 1 arestas ) , a matriz
de adjacência é quase
Toda de zeros .
lista de adjacências : lista de orizmhos de cada vértice .
o duas representações mora cada aresta
o espacio mroporcional a Q (mt n )
o checar se tu , v1 é uma aresta custa íempo ⊕ (grau Iv) ) .
O uidentirvar notas as arestas custa tempo Q (min)
vantagem : boa para grafos esparsos .
nó - mova onde voei consegue ir , em ordem
vantagem : sensível ao número de arestas
.
matriz de incidências : matriz nx me com Ane = 1 se w está na
arista e .
° uma coluna para cada aresta
o espaço proporcional a n ✗ m
o utilizada em situações especiais
a matriz a de formulações de programação
matemática
.
vantagem : facilita operações matriciais
uma coluna para cada aresta
↓
EI
Definição : um caminho em um agravo não - orientado
G = ( ✓ , E) é uma sequência P de vértices v1
,
V2
,
. . . , VK - 1 , E
com a propriedade que cada par consecutivo, Vi , Vi + 1-
Ú ligado por uma aresta em E .
dvrinrcrão : um caminho é simples se todos os vértices
são distintos .
definição : um grupo não -orientado ú conexo
se para
cada par de áreas m e v
,
existe um caminho
entre U e v
.
caso contrário
,
eu é desconexo :
L
definição : um ciclo ú um caminho v1 , v2 , ve - 1, F-
no qual V1 = VK ,
K > 2
,
e os primeiros K- 1
várias são distintos .
acho c :
)
I - Z
- a - s - s - a
depimaão : a distância entre vértices s e t em um
ghafo G é o número
de arestas do caminho mais curto
entre s e t em G.
e
número
destameia ( 1, a ) = z
de arestas !
distância (6,3 ) = 2
distância 17,8 ) = 1-
duóiniaão : um garoto não orientado ú uma
árvore se ú conexo e não contém nem acho .
Teorema : Seja ↳ um grupo não orientado
com
N árticos . Quaisquer duas afirmações abaixo
implicam na ihrcrira
:
° G ú conexo
° ti não contém um ciclo
◦ G possuí n - 1- arestas
→ áouhe " enraizada
"
: Nada uma árvore T, escolha um
oãríiw raiz ou e " Oriente
"
cada arestas a partir de N .
importância : modelos com estrutura hierárquica
definição : um suhrghato é um subconjunto de
árvores e arestas de G que tomam um grato.
definição : uma componente conexa é isuhrghaoo
maximal conexo.
dvoimcsão : um área w é chamado de ponto de articulação
se quando removido ( junto com suas
arestas
adjacentes ) , aumenta o número do
componentes
conexas de ti .
dvoinvuão : uma aresta (w ,
v) é chamada de ponte
se quando removida , aumenta o
número
de componentes conexas de G .
definição : um grato completo é aquele em que todos
os pares de árticos são adjacentes .
Quantas arestas possui um ghapo completo ?
o Cada um dos vórtices ú incidente a n -1- arestas .
◦ porém nós estamos contando as arestas duas vezes !
o Logo , me = N IN - 1) | 2 .
◦ se um ghapo simples não Ú completo,
me < n In -1) / 2
n = 5
m = 515 - 1) / z
m = 10 ,/
Conectividade e burcas :
O problema da conectividade s - t : modos dois vértices s
e t
, existe um caminho entre s e t ?
O problema do caminho mais curto s -t : Dados dois
vértices s e t , qual é o tamanho ao caminho mais
curto entre s e t ?
Intuição da busca em largura ( BFS ) : Explore
a partir de S em Todas as dvecrães possíveis , adicionando
vértices um "
nível
"
por vez .
Algoritmo BFS (G ,
s )
lo = 4s }
L
, =
todos os orizinhos de lo .
↳ = todos os vértices que não pertencem à lo ou ↳ e
que têm uma aresta para um vértice de ↳ .
Li+ 1- = todos os vértices que não pertencem aos níveis
anteriores e que têm uma aresta para um vórtice de
lei .
Qual é a distância de S até um vértice em ti ?
Teorema : Para cada i , li contém todos os outros com
distância exatamente i de S . Existe um caminho de S
déí t se e somente se t aparece em algum nível
.
Aplicação 1 : Encontrar se existe um caminho do áeíucu
S até no vértice t :
◦ Faca BFS ( tus ) : se existe um caminho de S até t ,
este BFS irá visitar t
,
caso contrário não irá resetar
.
Aplicação 2 : O tamanho de um caminho de S até t :
o É o índice do nível de t calculado por BFS (G ,
s )
,
caso
haja um caminho de S até t .
definição : uma árvore de busca em largura
de G = (V , E) é árvore induzida pela BFS em ↳
.
◦ A raiz da árvore é o área de origem da BFS .
◦ um vértice n é um pai de v se ✓ surtado
amarásde W .
Ex .
: BFS (↳ i
' )
. .
. .
.
/ \ \ -
, -
Aplicação : lvrapros Bipartido
. . _ _ .
definição : um guapo não - orientado G = (vi E) ú
dão bipartido se os rios podem ser coloridos de
vurmelho e azul de forma que cada aresta
ligou um vórtice azul com um área vermelho .
aplicações :
a designação : máquinas × tantas
demo : se um grato G é bipartido,
ele não pode conter um ciclo de
tamanho ímpar .
prova : não é possível colorir um ciclo ímpar com duas
cores , logo o mesmo não é possível para G
conter um
ciclo ímpar .
Teorema : Seja G um ghapo conexo, e será lo , . . .
, LK
os níveis produzidos por BFS ( G
,
S ) . Se os níveis
forem coloridos de forma alternada , exatamente
uma das seguintes propriedades ú rudadiua :
o não há aresta ligando a mesma cor , então
↳ Ú bipartido .
◦ Existe uma aresta alegando a mesma cor , então
o grato G contém um ciclo ímpar e o grato
não ú bipartido .
→
pintar cada área,
porém quando legado
as suas arestas não
pode repetir cor .
que será bipartido !
Depilação : uma árvore de busca em phopudidadr de G = Iv ,E )
é a árvore induzida pela DFS em G
.
◦ A raiz da árvore é vértice de origem da DFS.
◦ um área w é um pai de v se v é visitado a partir de U .
Grafo orientado .
G = (V, A)
O arco Lu , v ) vai ao
Ártico w até o rértice v.
Grafos Orientados
busca Orientada : Dado um vórtice S
,
encontre Todos os
vértices alcançáveis a partir de S.
Caminho mais curto s - t orientado .
Dado dois vértices
S e t
, qual é o tamanho
do caminho mais curto de S
até t ?
dvrinvaão : várias w e v são mutuamente alcançáveis
se existe tanto um caminho de U para
✓ quanto um
caminho de v para u .
Mim negão : um grato é mortemente conexo se todos os
pares de vértices são mutuamente alcançáveis .
tema : seja S um vértice . G ú portamente conexo se
e somente se Todo vértice é alcançável a partir
du S e s é alcançável a partir de todos os áreas .
Como determinar se ↳ é portemenir conexo :
a escolha qualquer nó S .
◦ Retorne Sim se e somente se todos os rios
foramalcançados nas duas execuções de BFS .
→
← c-
→
--
definição : um grapo orientado acídia ( DAG ) é um ghafo
orientado que não contém ciclos .
definição : uma ordenação Topológica de uma DAG
G = ( v , E) é uma ordenação de seus
vértices v1
,
V2
,
. .
,
Vn
tal que para cada arco (vi , vj ) ,
temos i a j
Caminho mínimo :
Algoritmos :
◦ DizKstrou : menor caminho entre 2 árticos .
condições de parada pode ser alterada para
encontrar o menor caminho de 1 áreas
fonte fixo a todos os outros .
O Floyd : menor caminho entre Todos áreas .
Algoritmo de oiefkstra
estratégia :
* encontre o vértice mais próximo a S
, depois mais
próximo, depois o terceiro mais próximo e assim
por diante até encontrar t .
+ Observação chave : O menor caminho de s até o
K- ésimo vértice mais próximo I digamos , t ) pode ser
decomposto como sendo o caminho mais próximo
de S ao ir - ésimo vértice mais próximo lorde i < K )
mais uma arma do ir - ésino ao K- ésimo
vurtía .
Dados :
GLN ,E) : grato em que N = 41,2 , . .
,
N }
1- : nó inicial do caminho
n : nó final do caminho
cli
, j ) : comprimento do arco Ii , J ) E E / hipótese : C Ii , J ) ; o)
saída :
d (n) : menor distância do nó 1- ao nón
C : caminho mínimo entre o nó 1- e o nó n.
Namo 1- : Inácio
R = 41 } : inicialmente o nó 1- é rotulado
NR = 42 . .
. ir } : Os demais nós não são rotulados
DIM = 0 : distância do nó 1 ao nó 1- é zero
P lo ) = O : o nó 1- é o nó inicial
mora i E NR
dli ) = + x : a distância do nó 1- aos rios não
rotulados ú + o
PLI ) = n + 1- : o nó i não Tem predecessor
(Observe que não existe nó n+ 1- no grato )
a = 1- : último nó incluído em R
passo 2 : Para ctodo i e NR , determine dli ) = mínimo
4 ali ) , de (a ) + C (aii ) } e paga p ( i )
= a ,
caso
d ( i ) = d (a) + ela ,
i ) .
Se d ( i ) = + a para éodo ir e
NR
,
então pare
4 não existe caminho de 1- a qualquer um dos nós em NR } .
Se não ,
determine n e NR tal que d (r) = mínimo
4 d ( i ) , I E NR } . Exclua o
nó r de NR ( isto é , NR ← NR - (a) }
e inclua -o em R ( isto é ,
R ← R U 4 r } ) e parça a = eu
passo 3 : se a = n
,
então recupere o caminho mínimo c
a partir dos valores armazenados
em Pl . ) , iniciando por
NI = p (n) , em seguida , na
=P (M )
,
até que o nó 1- seja
atingido . Se não tudo é , a ≠ n ) , retorne ao passo 2 .
Algoritmo de Floyd -Warshall
definição : um vértice intermediário de caminho
simples p = 4 v1
,
V2 , . . , vn } Ú qualquer
área
diferente v1 ou Vn , ou seja,
um vértice do conjunto
4 v2 , . . _ ,
Vn - o } .
definição : W representa
uma matriz n × n com os
custos das arestas .
definição : dig
""
representa o custo do menor caminho
entre os vértices i e j usando vérticesintermediários
do conjunto 41,2 , _ .
. K }
tsepimaão : D
""
rmusenta uma
matriz com Todos os custos díg "
"
.
◦ um caminho mínimo não repete rérteas .
◦ para um caminho mínimo de i mora j
tal que
quaisquervértices intermediários no caminho são selecionados
do conjunto 41,2 , . . K }
,
haverá apenas z possibilidades :
o 1. tu não é um Ártico do caminho , portantoo
menor caminho Tem tamanho digl
" -"
O 2- K Ú um vértice do caminho
,
portanto o menorcaminhoitem otomano diet
" - "
+ dej
(K- 1)
◦ com isso podemos definir dir
""
como sendo a seguinte
relação ou recorrência
árvore geradora de custo mínimo
definição de árvore de cobertura mínima
* árvore geradora cuja soma do comprimento de seus
arcos é mínima em G ( N, A) .
* O grato não orientado G (N,A) constitui uma árvore
se for conexo e acídia ( sem ciclos ) .
→ consiste na determinação do conjunto de arcos que
vagam Todos os
rios de uma rede , de tal maneira
que a soma das suas distâncias é mínima .
Requer que o gravo / rede seja conexa .
Não deve
incluir ciclos !
Algoritmos : primo e kiusxal
Algoritmos :
Plum : Ideal quando o número de arestas é
muito superior ao número de vértices ( gratos densos )
Kruskal : Ideal quando o número de arestas não
é muito alto ( guapos esparsos ) , o que costuma ser
o caso mais comum .
Algoritmo de Pnim :
a árvore geradora ú construída a partir de um
arco pelo acréscimo de novos arcos , aumentando - se
ahhrhescênáa inicial até que Odos os nós sejam
incluídos .
Passo 1- : Fixar um nó arbitrariamente e escolher
o arco de comprimento mínimo nele incidente que
o liga ao nó adjacente mais
próximo .
passo 2 : se Ídolos os rios da rede estiveremconectados
pare , caso contrário prossiga .
passo 3 : Identificar o nó que possa ser ligado
da norma mais econômica aos já
existentes na
ahbovuscêmeia , juntando o arco
correspondente
à formação . volte ao passo 2 .
Algoritmo de Kruerkaf
O algoritmo pode desenvolver várias arhourcên -
cias simultaneamente até que uma só árvore
inclua todos os rios .
Algoritmo :
passo 1- : Ordenar por ordem vuercmtr os arcos
do genaro de acordo com as suas distâncias
.
nosso 2 : Tomar os primeiros n - 1 arcos que
não formam acho
, com os outros já escolhidos
na árvore , onde n é o número de nós .
O algoritmo Termina quando tiverem sido
selecionados os n - 1 arcos da árvore ou
quando Tuitarem sido examinados eidos os
arcos da rede .
Observação :
* Ordene as arestas
* Ordene as arestas de acordo c/ seus custos
* não pode formar ciclos
* tem que passar por todos os nós .
Problemas de Roteirização
* cadeia de suprimentos
Qualquer processo ou Distribuição física incorpora , mas
pontas
,
um roteiro de coleta e /ou distribuição , no
qual o ruído visita
,
de uma só vez , umdeterminadonúmero de clientes localizados numa zona
de uma região .
durimãao de rotas e roteirização :
coloca - se frenquentemente o problema de saber
qual a rota , ou rotas , que permitem prestar
determinado serviço a um conjunto de pontos
(clientes ) minimizando uma determinada função
Objetivo (distância total percorrida , Tempo de
percurso ou custo total ) .
Rota : define o percurso a ser realizado por
um oráculo para risilar os dientes a serem
servidos .
Problema de roteirização :
problema de distribuição no qual oráculos localizados
em um depósito central devem ser programados para
visitar clientes geograficamente dispersos ,
de modo,
ou atender as suas demandas .
As soluções para o
problema são requentemente restritas pela capacidade
dos oráculos .
A durinicrão das rotas de entrega de um produto
(duração
, percurso, dequêmeia ) tem influência :
D na politica de estoque da cadeia de suprimentos
D na constituição da prata
D no nível de serviço prestado ao
cliente
.
As decisões operacionais relativas aos transportes
devem incidir em dois aspectos :
D Otimização da Mota (minimização do número
de oráculos e maximização da utilização ) .
D Otimização das rotas ( divinação dos caminhos
mais curtos e das zonas de entregou ) .
Um problema real de roteirização é definido
por éons patous pumdãmlnlais :
D Decisões
D Objetivos
D Restrições
Decisões : variáveis de decisão
- Roteiro a ser percorrido por cada oráculo
- Qual oráculo é atribuído para cada cliente
- Qual a quantidade de carga iteansportada
para cada cliente da
rota
.
-
Tempo de início de atendimento do primeiro
cliente da rota .
Função Objetivo :
- minimização dos custos totais de distribuiçãoincluindocustos puros ( capital dos oráculos , salários ,
despesas de linchamento , seguros , taxas ,
etc )
e custos variáveis ( custos do oráculo
dnemdintrs
da distância percorrida)
- minimização da distância total percorrida .
- minimização do número írotal de veículos
- maximização da punção de utilidade ( nível
de
serviço e/ou prioridades dos clientes ) .
Restrições dos oráculos :
- limite da capacidade
- Limite com relação ao áureo de carga
- Operação de carga e descarga
- número e viipo de oráculos disponíveis .
Restrições dos clientes :
- janela de tempo dos clientes
-
atendimento total ou marcial das demandas
-
Tempo máximo permitido para a carga
e
descarga .
-
necessidade ou restrição de serviço em algum
dia especí rico da semana /mês .
- disponibilidade de área para estacionamentodo oráculo .
Aspectos que devemos considerar ao caracterizar
o problema :
tipo de operação :
◦ coleta
o entregou
a coleta e entregou simultaneamente
o Logística reversa
Tipo de carga :
o único ou carga de votação
◦ múltiplas cargas ou carga Mag
mentada
tipo de demanda :
o tsehrmí rustica
o Estocástica
Localização da demanda :
◦ Localizada somente nos arcos
◦ Localizada somente nos
nós
o Localizada nos nós e nos arcos
tamanho da prata :
o limitada
0 ilimitada
Tipo de notas :
o homogênea
◦ heterogênea
Deposito e localização de oráculos :
◦ um único depósito ou vários depósitos
o quantidade de produtos disponíveis no depósito
Central para entrega ao clientes .
O número de bases de origem e direino dos veículos
formadas de Thrahalho
:
◦ duração
o horário de almoço e outras interrupções
o permissão para oriagem com mais de um dia
de duração ,
o número de Tui pulantes por oráculos .
Pagamento dos tripulantes :
° Por jornada de trabalho
◦ Por produtividade
a jornada e horas extra
Estrutura da rede
o direcionada
◦ não direcionada
o misto
Horizonte de planejamento :
o curto prazo
◦ Longo prazo
Outras hipóteses :
o cada oráculo só pode visitar um cliente uma única vez
durante a rota.
◦ um cliente pertence a uma única rota ou a várias rotas .
◦ quando um oráculo visita um cliente da rota todos
no clientes da rota são viuíeados .
Rotas para um único veículo
: um único veículo
percorre todos os clientes i O problema consiste em
determinar qual a ordem de chiita aos clientes .
Rotas para multipros oráculos : múltiplos oráculos
servem multi rolos clientes ,
sendo que cada oráculo
Tem sua rota e seus clientes esneámãos .
normalmente a alocação de clientes ou oráculos é
limitada por restrições de capacidade do oráculo,
Tempo de percurso, distância percorrida ,
n° maximo
de parador .
Ingredientes de um problema :
◦ Decisões : identificar as possíveis soluções ; definição
das variáveis de decisão .
ex : localização dos CD , atribuição de oráculos , capacidade
◦ Objetivo : dirimir ovários de avaliação carazes de mostrar
que uma decisão I.ou conjunto de decisões ) ú phvróuoul
às outras
.
ex : minimizar autos
o restrições : identificar guiam as condicionantes para
as dvuãou a serem éomadas .
ex : lógicas , físicas (e. g , continuidade ) , técnicas
(e.g. , capacidade ) , Orçamentais , lvgàrl , metas
le -G. , nãlinrazer toda a demanda , cumprir
antúrios
ambientais )
.
p°=nóanã①
N = distância p/ cada nós
coluna : nó de chega
linha : nó de saída