Modelos de Fluxo em Redes

Prévia do material em texto

Modelos de Fluxo em Redes
APRESENTAÇÃO
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 utilizados na resolução 
de problemas de fluxo em rede, aprender métodos utilizados nos problemas clássicos, além de 
ver definições importantes para o estudo de fluxos em redes.
Bons estudos.
Ao final 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.•
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.
INFOGRÁFICO
As soluções de problemas clássicos de fluxos em rede são obtidas por meio de uma variedade de 
algoritmos. Veja no infográfico algumas características de modelos de fluxos em redes. 
Conteúdo interativo disponível na plataforma de ensino!
 
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 utilização dos modelos de fluxo em redes.
Boa leitura.
PESQUISA
OPERACIONAL
Organizador: 
Rodrigo Rodrigues
Catalogação na publicação: Poliana Sanchez de Araujo – CRB 10/2094
R696p Rodrigues, Rodrigo.
 Pesquisa operacional / Rodrigo Rodrigues. – 
 Porto Alegre : SAGAH, 2017.
 121 p. : il. ; 22,5 cm. 
 ISBN 978-85-9502-004-7
 1. Pesquisa operacional – Engenharia de 
 produção. I. Título. 
CDU 658.5
Modelos de fluxos em rede
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Definir a terminologia das redes.
 � Descrever modelos de fluxo em redes em diversas aplicações.
 � Resolver problemas clássicos.
Introdução
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. 
Neste texto, você vai estudar sobre os algoritmos utilizados na reso-
lução de problemas de fluxo em rede, aprender métodos utilizados nos 
problemas clássicos, além de ver definições importantes para o estudo 
de fluxos em redes. 
Terminologia das redes
Alguns sistemas são abordados como redes: 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.
U N I D A D E 2
Em fluxos em rede há alguns problemas que são clássicos e tentam res-
ponder a certas questões, por exemplo: 
 � Problema do caminho mínimo (PCM): qual é a melhor forma de per-
correr uma rede indo de um dado ponto a outro, com o menos custo 
possível? 
 � Problema de fluxo máximo (PFM): é uma rede com arcos capacitados? 
Como e qual é o máximo de fluxo possível de se enviar de um dado 
ponto a outro da rede, respeitando a capacidade dos arcos?
 � Problema de fluxo com custo mínimo (PFCM): considerando um dado 
custo por unidade de fluxo em uma rede (nos seus arcos) com arcos 
capacitados e que precisamos enviar unidades de fluxo alocadas em 
determinados nós (oferta/produção) para outros nós (demanda/consumo), 
como fazê-lo com o menor custo possível?
Alguns problemas de fluxo em rede, por serem formulados como um pro-
blema de programação linear, podem ser resolvidos pelo método simplex, de 
modo que qualquer um dos pacotes utilizados por esse método também poderá 
ser usado. Entretanto, é possível a utilização, com eficiência, de algoritmos 
para a resolução desses problemas.
Algoritmos 
Pelo fato de o problema do fluxo máximo, por exemplo, ser formulado como um 
problema de programação linear, pode-se resolvê-lo pelo método simplex, de 
modo que qualquer um dos pacotes de software de programação linear possa ser 
usado. Contudo, um algoritmo de caminhos aumentados, eficiente, encontra-
-se disponível para resolver esse tipo de problema. Esse algoritmo baseia-se 
em dois conceitos intuitivos, uma rede residual e um caminho aumentado.
Segundo Hillier e Lieberman (2013), um caminho aumentado é um caminho 
direcionado da origem para o escoadouro na rede residual, de modo que nele 
todo arco tenha capacidade residual estritamente positiva. Capacidade residual 
de caminho aumentado é a denominação para o mínimo dessas capacidades 
residuais, pois ele representa a quantidade de fluxo que pode ser adicionada 
de maneira viável ao caminho todo. Desse modo, cada caminho aumentado 
fornece uma oportunidade de se aumentar ainda mais o fluxo pela rede original. 
Pesquisa operacional76
O algoritmo do caminho aumentado seleciona algum caminho desses e 
apresenta um fluxo igual à sua capacidade residual ao caminho na rede original. 
Esse processo continua até que não haja mais caminho aumentado, de modo 
que o fluxo, partindo da origem e indo para o escoadouro, não possa ser mais 
aumentado. A estratégia para garantir que a solução final seja necessariamente 
ótima é o fato de os caminhos para fluxos designados não poderem impedir 
o emprego de uma combinação melhor de designações de fluxo.
Resumindo, cada iteração do algoritmo consiste nas três etapas indicadas 
a seguir.
Algoritmo do caminho aumentado para o problema 
do fluxo máximo
1. Identifique um caminho aumentado encontrando algum caminho di-
recionado da origem para o escoadouro na rede residual, tal que cada 
arco desse caminho tenha capacidade residual estritamente positiva. (Se 
não existir algum caminho aumentado, os fluxos de rede já constituem 
um padrão de fluxo ótimo.)
2. Identifique a capacidade residual c* desse caminho aumentado encon-
trando o mínimo das capacidades residuais dos arcos nesse caminho. 
Aumente o fluxo nesse caminho de c*.
3. Diminua de c* a capacidade residual de cada arco nesse caminho au-
mentado. Aumente de c* a capacidade residual de cada arco na direção 
oposta nesse caminho aumentado. Retorne à etapa 1.
Quando a etapa 1 for executada, em geral há uma série de caminhos aumen-
tados alternativos para se escolher. Embora a estratégia algorítmica para fazer 
essa seleção seja importante para a eficiência de implementações em grande 
escala, não iremos nos aprofundar nesse tópico relativamente especializado. 
O uso de algoritmos na busca da solução serve para encontrar nós de uma 
rede com determinadas características. Muitas variantes estão nos algoritmos de 
fluxo máximo e fluxo com caminho mais curto. As aplicações mais comuns são:
 � Encontre todos os nós que estão ligados a um dado nó origem por meio 
de um caminho direcionado e vice-versa.
 � Identifique todos os componentes conexos de uma dada rede.
 � Determine se uma dada rede é bipartida.
 � Encontre um ciclo direcionado em uma rede.
77Modelos de fluxos em rede
Árvore de valor mínimo
Existem diferentes e importantes tipos de algoritmos para a determinação 
de árvores de valormínimo. Aqui será apresentado apenas o algoritmo de 
Kruskal, devido à sua simplicidade. Antes disso, definiremos grafo: estrutura 
que corresponde a um par de conjuntos G = (N, E), em que N é um conjunto 
de entidades. Por exemplo, essas entidades podem estar associadas a pontos, 
locais, pessoas, áreas geográficas; e E é um conjunto em que seus elementos 
são ligações ou inter-relações entre os elementos de N, que podem ser estradas, 
parentescos e fronteiras entre áreas geográficas.
Algoritmo de Kruskal 
Dado um grafo G = (N,E) não orientado e valorado para a construção de uma 
árvore de valor mínimo, parte-se do grafo trivial G = (N,0), que é constituído 
apenas pelos nós do grafo original G, acrescentando-se iterativamente a aresta 
de menor valor que não forma ciclo com as já escolhidas. O comprimento 
mínimo será obtido pela soma dos valores associados às arestas da árvore 
resultante do procedimento descrito anteriormente. Na Figura 1, estão um 
grafo, sua árvore mínima e o valor do comprimento mínimo associado. 
Figura1. Grafo e uma árvore parcial mínima.
Pesquisa operacional78
Caminho mais curto 
A determinação de um caminho mais curto em um grafo, devido à sua apli-
cabilidade prática, é um problema importante em várias áreas, como na área 
de logística, por exemplo. O comprimento de um caminho P é definido como 
sendo a soma dos comprimentos de todos os arcos de P. O problema é encon-
trar o caminho mais curto, de um nó inicial s para um nó terminal t. Aqui se 
considera um grafo valorado simples (isto é, sem laços e arcos paralelos) G 
com n nós que pode ser descrito por uma matriz Dnxn= [dij], em que:
Em geral, dij ≠dji, e a desigualdade do triângulo não precisa ser satisfeita, 
ou seja, dij + djk pode ser menor que dik. 
Então, se a desigualdade do triângulo é satisfeita, para todo i, j e k, o 
problema seria trivial, pois o arco direto (x, y) seria o caminho mais curto 
do vértice x ao y. 
Vejamos, a seguir, o algoritmo de Dijkstra, que foi um dos primeiros a 
serem propostos para resolver problemas do caminho mais curto. Sua aplicação 
se dá quando os comprimentos de cada arco são dij ≥ 0. O algoritmo não se 
aplica nos casos em que os comprimentos são negativos.
Algoritmo de Dijkstra
O algoritmo de Dijkstra usa uma técnica de rotulação dos nós a partir de s, 
o nó inicial do caminho. Há dois tipos de rotulação: temporária e definitiva. 
O valor do nível em que um nó j é rotulado definitivamente, a partir de s, é 
exatamente o comprimento do caminho mais curto entre s e j. Em cada iteração 
do algoritmo, alguns nós são rotulados temporariamente e outros definitiva-
mente, assim, aplica-se o algoritmo até se conseguir rotular definitivamente 
o nó terminal do caminho, que é o nó t (BOAVENTURA NETTO, 2003).
79Modelos de fluxos em rede
Aplicação do algoritmo de Dijkstra
 � Passo 1 (Inicialização): rotule definitivamente (RD) o nó s a um nível 
0 e rotule temporariamente (RT) os demais nós a um nível ∞. 
 � Passo 2: todo nó j ainda não rotulado definitivamente deve receber 
uma nova rotulação temporária cujo valor será: min [valor da rotulação 
temporária atual de j, valor da rotulação definitiva de i + dij], onde i é 
o nó rotulado definitivamente na iteração anterior. 
 � Passo 3: rotule definitivamente o nó i associado ao menor valor de 
rótulos encontrados no Passo 1. 
 � Passo 4: repita .
Os Passos 1 e 2 até conseguir rotular definitivamente o nó terminal do 
caminho t. O valor da rotulação definitiva do nó t corresponderá ao compri-
mento do caminho mais curto entre s e t. Para determinar quais são os nós 
intermediários do caminho mais curto entre s e t, trabalhe do final do caminho 
para o começo (backtracking) da seguinte forma: 
a) A partir do nó t, procure achar qual foi o primeiro nó responsável pelo 
seu valor de rótulo definitivo. Suponha que tenha sido o nó k. Ele é 
denominado de nó Pai do nó t. 
b) Procure achar qual foi o primeiro nó i, do Passo 2, responsável pelo 
valor de rótulo definitivo de k. 
c) Aplique o mesmo procedimento para encontrar o nó Pai do nó k e repita-
-o, sucessivamente, até encontrar o nó inicial s, como sendo o nó Pai, 
responsável pelo valor do rótulo definitivo de algum nó intermediário. 
d) Os nós assim determinados irão compor o caminho mais curto. 
Veja o grafo da Figura 2 e determine o caminho mais curto entre os nós 
B (será o nó s) e G (será o nó t). Determine, também, o comprimento total 
mínimo do caminho.
Pesquisa operacional80
Figura 2. Rede do exemplo para a aplicação do algoritmo de Dijkstra.
Figura 3. Algoritmo de Dijkstra aplicado ao grafo da Figura 2.
Na resolução, adota-se um vetor de dimensão 1 x 7 para mostrar os níveis de 
rotulações temporárias (RT) e definitivas (RD) dos nós, enquanto caminha-se 
para a solução ótima, como na Figura 3. 
81Modelos de fluxos em rede
As rotulações definitivas são colocadas dentro de um quadrado, e o último 
nível de rotulação definitiva do vetor é indicado por √. 
A solução ótima é: 
O comprimento total mínimo = valor do nível de rotulação 
definitiva do nó terminal G = 7 e o caminho mais curto 
(obtido do fim para o começo) é G ← E ← C ← B. 
Fluxo máximo 
Na análise do desempenho de um grafo valorado, com frequência é necessário 
calcular o valor ótimo de uma função do fluxo entre dois vértices: o vértice 
fonte e o vértice t, conhecido como destino. 
Agora, apresentamos uma situação em que há apenas um tipo de fluxo no 
grafo, que pode ser eletricidade, água, informação ou tráfego, por exemplo. 
Na literatura especializada, esse caso é conhecido como The One-Commodity 
Flow Problem, e o grafo é denominado rede. 
Seja βi o conjunto de nós ligados ao nó i por arcos orientados no sentido 
de chegada em i, e αi o conjunto de nós ligados ao nó i por arcos orientados 
no sentido de saída de i.
Uma função fij definida em E com valores reais é dita ser um fluxo para 
um grafo orientado G = (N, E) se:
Em que uij é a capacidade do arco (i,j), ou seja, a quantidade máxima de 
fluxo que pode ser remetida de i para j. A condição (2) representa a hipótese 
da conservação de fluxo na rede, porém há estudos referentes a redes em que 
indicam que podem haver ganhos ou perdas de fluxo. 
F é o valor do fluxo que pode ser enviado da fonte 
s ao destino t, por meio da rede G = (N, E). 
Pesquisa operacional82
É importante notar que o valor máximo de F é limitado pelas capacidades 
associadas a cada arco da rede e determinado por corte, uma propriedade 
fundamental de uma rede. Um corte é um conjunto de arcos que, se forem 
removidos de uma rede, desconectam um conjunto de nós dos demais. Na 
Figura 4, percebe-se que o corte formado pelos arcos (2, 4) e (3, 4) desconectam 
o nó 4 dos nós 1, 2 e 3. 
Figura 4. Exemplo de corte.
Nos problemas de fluxo máximo o interesse é colocar cortes que separem 
nó fonte do nó destino. O valor do corte, ou a capacidade do corte, é a soma 
das capacidades dos arcos do corte (em uma dada direção). Na Figura 4, o 
valor do corte é igual a u24 + u34. 
O algoritmo descrito a seguir se baseia em um princípio muito simples. 
Seja X um subconjunto de N tal que s ∉ X e t ∈ X. O conjunto AX de arcos que 
tem orientação de chegada em nós de X e origem em nós que não pertencem 
a X, por definição, é um corte na rede G. 
Se c(AX) é o valor desse corte, então, o valor máximo de fluxo F que pode 
ser enviado de s para t satisfaz F ≤ c (AX). Isso significa que o fluxo máximo 
em uma rede é limitado pelo valor do corte de menor capacidade que nada 
mais é do que a própria capacidade. 
Está estabelecido, então, um dos mais importantes resultados na teoria de 
fluxos em redes, que é o teorema que veremos a seguir. 
83Modelos de fluxos em rede
Teorema do fluxo máximo e corte mínimo 
Em redes com fonte e destino únicos, o fluxo viável máximo que pode ser 
enviado da fonte ao destino t é igual ao valor do corte mínimo (corte com 
menor capacidade entre os cortes da rede). Para ilustrar, podemos verificar 
que o fluxo máximo na rede da Figura5 é 3. Os números que aparecem ao 
lado dos arcos representam suas capacidades nas direções especificadas pelas 
setas. O corte mínimo consiste dos arcos (s,2) e (3,t) e tem valor igual a 3.
Figura 5. Corte mínimo.
Observe que o problema fluxo máximo em uma rede pode ser expresso 
como um problema de programação linear: seja o fluxo fij em uma rede G = 
(N, E), em que N = {s, 2,...,t} e uij é a capacidade do arco (i,j). O valor desse 
fluxo é F se 
Então temos a seguinte formulação: 
Pesquisa operacional84
Desse modo, pode ser aplicado o método simplex na resolução de um 
problema de fluxo máximo. Apresentamos, a seguir, um algoritmo mais 
eficiente, que usa um procedimento de rotulação e gera uma sequência de 
fluxos crescentes até atingir o máximo. 
Com o teorema do corte mínimo e fluxo máximo podemos encontrar o fluxo máximo 
determinando a capacidade de todos os cortes e escolhendo o de capacidade mínima. 
Embora isso nos dê o valor máximo de F, não é possível especificar como o fluxo 
circula pela rede.
Algoritmo do fluxo máximo 
Esse método é baseado no teorema de Ford e Fulkerson e busca encontrar uma 
cadeia por meio da qual um fluxo positivo possa ser enviado da fonte s ao 
destino t. Essas cadeias são denominadas de cadeias de fluxo ampliável (CFA).
As cadeias são utilizadas para transmitir, o máximo possível, fluxo de s 
para t. O processo é repetido até não ser mais possível encontrar alguma CFA, 
o que indica que encontramos o fluxo máximo.
Rotina de Rotulação – encontrar uma CFA 
Iniciamos a rotulação do nó s. Um nó j pode ser rotulado se um fluxo positivo 
pode ser enviado de s para j. Em geral, do nó i podemos rotular um nó j se 
uma das seguintes condições for satisfeita: 
1. O arco que liga o nó i ao nó j é um arco que chega em j (arco forward) 
e sua capacidade ( fij < uij) é maior que o fluxo que há nele. 
2. O arco que liga o nó i ao nó j é um arco que sai de j (arco backward) e 
o fluxo nele é maior que zero ( fij > 0). 
Continua-se nessa rotina até rotular o destino t, obtendo assim uma CFA.
85Modelos de fluxos em rede
Fases do algoritmo 
1. Inicialização: obtenha um fluxo viável em todos os arcos, ou seja, um 
fluxo que atenda às restrições de capacidade nos arcos e de conservação 
de fluxo nos nós. 
2. Obtenha uma CFA, iniciando em s e terminando em t. Vá para a Fase 
3. Caso não seja possível, PARE! O fluxo máximo foi encontrado. 
3. Calcule o fluxo máximo δ, que pode ser enviado pela última CFA obtida. 
Aumente de δ o fluxo nos arcos forward da cadeia e decresça o fluxo de 
δ nos arcos backward. 
Volte a Fase 2.
Determine o fluxo máximo F da fonte s ao destino t na rede a seguir (Fig. 
6), em que os números ao lado dos arcos representam suas capacidades. 
Figura 6. Rede para o exemplo.
Inicialização: faça fij = 0 em todos os arcos. Veja a Tabela 1:
Pesquisa operacional86
(Continua)
Passo 1 - Vamos 
encontrar uma CFA de 
s para t. Então, rotule 
inicialmente s (rótulos 
são representados 
por asteriscos).
De s, rotule o nó 1, pois 
(s, 1) é um arco forward, 
levando um fluxo fs1 ≤ 
us1= 7. Do nó 1 rotule o 
nó 2 pelo arco forward 
(1,2) e, finalmente, 
rotule o destino t.
Desse modo, obtém-se 
a CFA, formada somente 
por arcos forward.
Os números nos 
arcos indicam o fluxo 
máximo permitido 
em cada um deles.
Assim, o máximo 
valor de fluxo para 
essa CFA é 3.
Isso aumenta F de 
3 unidades, e o 
fluxo sobre todos os 
arcos (forward) da 
cadeia aumenta de 3 
unidades também.
Passo 2 - Repetindo a 
rotina de rotulação, você 
chega a uma nova CFA.
Agora o fluxo máximo 
permitido é 4. 
Com isso, aumenta 
o fluxo F pela rede 
para 7 unidades.
 
Passo 3 - O nó 1 não 
pôde ser rotulado 
a partir de s, pois o 
arco (s,1) é forward 
e fs1 = us1 = 7. 
Isso aumenta o fluxo 
total F de 5 unidades, 
como mostra no 
próximo passo.
Partindo-se de s, 
rotule o nó 2, mas não 
será possível rotular 
t a partir dele, pois o 
arco (2,t) já alcançou 
sua capacidade. 
Mas o nó 1 pode ser 
rotulado a partir de 
2, pois o arco (1,2) é 
backward contendo um 
fluxo positivo. E, a partir 
do vértice 1, rotule t. 
Tabela 1. Teoremas do fluxo de rede.
87Modelos de fluxos em rede
1. Pode-se usar o teorema de Ford e Fulkerson para provar que o fluxo 
máximo é realmente F = 15. Basta considerar o corte que separa os 
vértices rotulados dos não rotulados na última linha. Isso fornece os 
arcos (s,1) e (2,t), cuja capacidade (valor) é 15. Observe que o arco 
(1,2) não pertence ao corte. Como F não pode exceder a capacidade de 
nenhum corte que separe s de t, o valor de F = 15 é o máximo fluxo 
possível. O corte mostrado na última linha é o corte mínimo. 
2. Para encontrar o fluxo máximo em uma rede G = (N, E) não orientada, 
primeiro converta-a em uma rede orientada equivalente e, então, aplique 
o algoritmo.
Passo 4 - Agora, tem-se 
uma CFA com dois 
arcos forward (s,2) e (1,t) 
e um backward (1,2). 
Para aumentar o 
fluxo por essa cadeia, 
aumente o fluxo nos 
arcos forward e decresça 
no arco backward. O 
máximo valor que se 
pode aumentar em F 
é de 3 unidades, e o 
novo fluxo na rede é 
fornecido a seguir.
Apesar do nó 2 poder 
ser rotulado a partir de s, 
nunca rotule o destino t. 
Desse modo, nenhuma 
outra CFA pode ser 
encontrada. Essa 
figura representa a 
configuração ótima 
de fluxo na rede, 
com fluxo máximo 
de 15 entre s e t.
Tabela 1. Teoremas do fluxo de rede.
(Continuação)
Pesquisa operacional88
A maioria dos problemas do fluxo máximo que surgem na prática é consideravelmente 
extensa. Alguns deles têm milhares de nós e arcos. O algoritmo do caminho aumentado 
é muito mais eficiente que o método simplex genérico para resolver esses problemas de 
grandes dimensões. Entretanto, para problemas de tamanho modesto, uma alternativa 
adequada seria o usar o Solver com base no método simplex genérico do Excel.
89Modelos de fluxos em rede
1. Em relação aos modelos de fluxo em 
rede, marque a alternativa 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 
(transporte), 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 
utilizaçã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 alternativa correta:
a) O uso de algoritmos na 
busca da solução serve para 
encontrar arcos de uma rede.
b) São usados, exclusivamente, para 
identificar todos os componentes 
conexos de uma dada rede.
c) O algoritmo de Kruskal é 
o único tipo de algoritmo 
para a determinação de 
árvores de valor mínimo.
d) O algoritmo de Dijsktra é 
utilizado 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 alternativas 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 utilizadas 
para transmitir, o mínimo 
possível, fluxo de s para t.
c) Na Rotina 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 positivo pode 
ser enviado de s para j.
d) Na Rotina 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 forward) 
e sua capacidade (fij < uij) é 
maior que o fluxo que há nele.
e) Para obter uma CFA, a rotina 
de rotulação deve seguir 
até rotular o destino t.
4. Com relação à resolução de 
problemas por meio de algoritmos, 
marque a alternativa correta: 
a) O algoritmo de caminhosaumentados é um eficiente 
método disponível para 
resolver problemas de fluxo 
mínimo. Esse algoritmo 
baseia-se em dois conceitos 
intuitivos, uma rede residual 
e um caminho aumentado.
b) Um caminho aumentado é 
Pesquisa operacional90
um caminho direcionado 
do escoadouro para a 
origem na rede residual.
c) Capacidade residual de caminho 
aumentado é a denominação 
para o mínimo dessas 
capacidades residuais, pois ele 
representa a quantidade 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 garantir 
que a solução final seja 
necessariamente ótima é 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 alternativa 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.
 
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ó1s.
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.
91Modelos de fluxos em rede
BOAVENTURA NETTO, P. O. Teoria e Modelos de Grafos. São Paulo: Edgard Blucher 
Ltda, 2003.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto Alegre: 
AMGH, 2013. E-book. 
Leituras recomendadas
ANDRADE, M.C.Q. Criação no processo decisório. Rio de Janeiro: LTC, 1980. 
GOLDBARG, M. C.; LUNA, H. P. L. Otimização combinatória e programação linear: mo-
delos e algoritmos. Rio de Janeiro: Campus, 2000.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. Rio de Janeiro: 
Campus, 2002.
Pesquisa operacional92
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.
DICA DO PROFESSOR
Neste vídeo, você vai ver como interpretar graficamente os problemas de transporte e também 
de que forma o Microsoft Excel pode auxiliar para encontrar a solução ótima para esses 
problemas.
Conteúdo interativo disponível na plataforma de ensino!
Conteúdo interativo disponível na plataforma de ensino!
EXERCÍCIOS
1) Em relação aos modelos de fluxo em rede, marque a alternativa 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 (transporte), 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 
utilizaçã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 alternativa correta: 
A) O uso de algoritmos na busca da solução serve para encontrar arcos de uma rede.
B) São usados, exclusivamente, para identificar todos os componentes conexos de uma dada 
rede.
C) O algoritmo de Kruskal é o único tipo de algoritmo para a determinação de árvores de 
valor mínimo.
D) O algoritmo de Dijsktra é utilizado 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 alternativas 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 utilizadas para transmitir, o mínimo possível, fluxo de s para t.
C) Na Rotina 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 positivo pode ser enviado de s para j.
D) Na Rotina 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 forward) e sua capacidade (fij < uij) é 
maior que o fluxo que há nele.
E) Para obter uma CFA, a rotina de rotulação deve seguir até rotular o destino t.
4) Com relação à resolução de problemas por meio de algoritmos, marque a alternativa 
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 intuitivos, uma 
rede residual e um caminho aumentado.
B) Um caminho aumentado é um caminho direcionado do escoadouro para a origem na rede 
residual.
C) Capacidade residual de caminho aumentado é a denominação para o mínimo dessas 
capacidades residuais, pois ele representa a quantidade 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 garantir que a solução final seja necessariamente ótima é o fato de os 
caminhos para fluxos designados poderem impedir o emprego de uma combinação melhor 
de designações de fluxo.
Observe o problema a seguir e marque a alternativa 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. 
5) 
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 
http://publica.sagah.com.br/publicador/objects/layout/222692010/2019-09-21-14-17-31-questao5.png?v=915570007
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 satisfaça requisitos 
de suprimento e demanda em diferentes locais e programar as atividades de um projeto. Veja um 
caso prático do uso do fluxo de redes para encontrar a menor distância entre opções de cidades:
Conteúdo interativo disponível na plataforma de ensino!
 
SAIBA MAIS
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do 
professor:
Pesquisa operacional - Caminho mínimo.
Conteúdo interativo disponível na plataforma de ensino!
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 interativo disponível na plataforma de ensino!
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9ª Edição. Porto 
Alegre: AMGH, 2013