PO UND 08 - MODELOS DE FLUXO EM REDES

Prévia do material em texto

03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 1/47
MODELOS DE FLUXO EM
REDES
APRESENTAÇÃO
Olá!
Fluxo em rede é um método de análise da programação linear que se destaca pela
minimização de uma função que depende do fluxo (custo/lucro) em uma rede. Há vários
modelos de fluxos em rede indicados para diversas aplicações. Isso permite o
desenvolvimento de algoritmos especializados com grandes vantagens computacionais.
Nesta Unidade de Aprendizagem, você vai estudar sobre os algoritmos u�lizados na
resolução de problemas de fluxo em rede, aprender métodos u�lizados nos problemas
clássicos, além de ver definições importantes para o estudo de fluxos em redes.
Bons estudos.
Ao �nal desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Definir a terminologia das redes.
Descrever modelos de fluxo em redes em diversas aplicações.

03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 2/47
Resolver problemas clássicos.
DESAFIO
Você trabalha em uma empresa construtora de aviões que pretende planejar a produção
de um motor durante os próximos quatro meses.
Veja os detalhes da produção:
Dadas as variações nos custos de produção, pode valer a pena produzir alguns motores um
ou mais meses antes das datas programadas para a entrega. Se optar por essa hipótese, os
motores serão armazenados até o mês de entrega, com um custo adicional de 0,015
milhões de dólares por mês.
Mediante o pedido do diretor de produção, formule o problema por meio do fluxo de
redes.

http://lrq.sagah.com.br/uasdinamicas/uploads/layouts/1016601962_15691124744b17c4760a9d06da0126635fcf2a08b3e6fc5f93.jpg
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 3/47
INFOGRÁFICO
As soluções de problemas clássicos de fluxos em rede são ob�das por meio de uma
variedade de algoritmos. Veja no infográfico algumas caracterís�cas de modelos de fluxos
em redes.
CONTEÚDO DO LIVRO
Alguns sistemas são abordados como redes, tais como: sistemas de produção/distribuição;
sistemas de tráfego urbano; sistemas de rodovias (transporte); sistemas de comunicação;
rede de dutos/tubulações; sistemas de localização; redes elétricas, entre outros sistemas.
No capítulo Modelos de fluxo em redes, do livro "Pesquisa Operacional", você vai ver os
fatores envolvidos na u�lização dos modelos de fluxo em redes.


03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 4/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 5/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 6/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 7/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 8/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 9/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 10/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 11/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 12/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 13/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 14/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 15/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 16/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 17/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 18/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 19/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 20/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 21/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 22/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 23/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 24/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 25/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 26/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 27/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 28/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 29/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 30/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 31/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 32/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 33/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/1529988634/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 35/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 36/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 37/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 38/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 39/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 40/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 41/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 42/47
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 43/47
DICA DO PROFESSOR
Neste vídeo, você vai ver como interpretar graficamente os problemas de transporte e
também de que forma o Microso� Excel pode auxiliar para encontrar a solução ó�ma para
esses problemas.
Conteúdo disponível na plataforma virtual de ensino. Con�ra!
EXERCÍCIOS
1) Em relação aos modelos de fluxo em rede, marque a alterna�va correta:
a) Fluxo em rede é um método de análise da programação não linear que se
destaca pela maximização de uma função que depende do fluxo (custo/lucro) em
uma rede.
b) Há poucos modelos de fluxos em rede indicados para aplicações limitadas.
c) Alguns sistemas são abordados como redes, como os sistemas de rodovias
(transport, por exemplo.
d) Alguns problemas de fluxo em rede, por ser formulado como um problema de
programação linear, podem ser resolvidos pelo método simplex, não sendo
possível a u�lização de algoritmos para a resolução desses problemas.
e) A geometria de uma rede não pode ser desenhada no plano.
2) Com base no que foi estudado sobre algoritmos, marque a alterna�va correta:
a) O uso de algoritmos na busca da solução serve para encontrar arcos de uma
rede.


03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 44/47
b) São usados, exclusivamente, para iden�ficar todos os componentes conexos de
uma dada rede.
c) O algoritmo de Kruskal é o único �po de algoritmo para a determinação de
árvores de valor mínimo.
d) O algoritmo de Dijsktra é u�lizado para resolver problemas do caminho mais
curto.
e) Em cada iteração do algoritmo, os nós são sempre rotulados temporariamente.
3) Observe as alterna�vas a seguir e indique a afirmação correta com relação ao
Algoritmo do Fluxo Máximo.
a) O algoritmo do Fluxo Máximo é um método baseado no Teorema de Fourier.
b) As cadeias são u�lizadas para transmi�r, o mínimo possível, fluxo de s para t.
c) Na Ro�na de Rotulação, para encontrar uma CFA, ao iniciar a rotulação do nó s,
um nó j não pode ser rotulado se um fluxo posi�vo pode ser enviado de s para j.
d) Na Ro�na de Rotulação, em geral, do nó i podemos rotular um nó j somente se
o arco que liga o nó i ao nó j é um arco que chega em j (arco forwar e sua
capacidade (fij < uij) é maior que o fluxo há nele.>
e) Para obter uma CFA, a ro�na de rotulação deve seguir até rotular o des�no t.
4) Com relação à resolução de problemas por meio de algoritmos, marque a alterna�va
correta:
a) O algoritmo de caminhos aumentados é um eficiente método disponível para
resolver problemas de fluxo mínimo. Esse algoritmo baseia-se em dois conceitos
intui�vos, uma rede residual e um caminho aumentado.
b) Um caminho aumentado é um caminho direcionado do escoadouro para a
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 45/47
origem na rede residual.
c) Capacidade residual de caminho aumentado é a denominação para o mínimo
dessas capacidades residuais, pois ele representa a quan�dade de fluxo que pode
ser adicionada de maneira viável ao caminho todo.
d) O algoritmo do caminho aumentado seleciona algum caminho entre os
caminhos encontrados e apresenta um fluxo diferente à sua capacidade residual ao
caminho na rede original.
e) A estratégia para garan�r que a solução final seja necessariamente ó�ma é o
fato de os caminhos para fluxos designados poderem impedir o emprego de uma
combinação melhor de designações de fluxo.
5) Observe o problema a seguir e marque a alterna�va correta. Apresentamos alguns
exemplos de redes, em que os nós s representam as ofertas, os nós t representam as
demandas, e os demais nós são nós de transbordo. Os valores em cada arco
representam, em geral, custos de transporte, distâncias ou tempos de viagem entre cada
par de nós. 
http://publica.sagah.com.br/publicador/objects/layout/222692010/2019-09-21-14-17-31-questao5.png?v=915570007
03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 46/47
a) Na Figura 2 temos o caso mais simples, em que há somente um nó de oferta e
um de demanda.
b) Não é possível termos restrições de capacidade nos nós.
c) Na Figura 1, temos diversos nós de oferta e de demanda.
d) Na Figura 2, há um nó de oferta que possui diversos centros de distribuição, que,
por sua vez, distribuem o produto pela rede até outros centros intermediários
(atacadistas ou armazéns) que abastassem o consumidor.
e) O que se busca nos problemas representados nas figuras é determinar o fluxo da
rede de modo que o custo, o tempo ou a distância total de transporte seja
minimizado ou que o fluxo total seja maximizado.
NA PRÁTICA
Os problemas de fluxos em redes são tradicionalmente aplicados para decidir o modo mais
eficiente de ligar várias localidades direta ou indiretamente, encontrar o caminho mais
curto entre duas cidades, definir o fluxo máximo em uma rede de tubulações que sa�sfaça
requisitos de suprimento e demanda em diferentes locais e programar as a�vidades de um
projeto. Veja um caso prá�co do uso do fluxo de redes para encontrar a menor distância
entre opções de cidades:
SAIBA +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do
professor:
Pesquisa operacional - Caminho mínimo.
Conteúdo disponível na plataforma virtual de ensino. Con�ra!


03/04/2020 https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886
https://sagahcm.sagah.com.br/sagahcm/sagah_ua_dinamica/impressao_ua/15299886 47/47
Alocação de fluxos de passageiros em uma rede de transporte público de grande porte
formulado como um problema de inequações variacionais.
Conteúdo disponível na plataforma virtual de ensino. Con�ra!
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9ª Edição. Porto Alegre:
AMGH, 2013
Conteúdo disponível na plataforma virtual de ensino. Con�ra!