Unidade 04 - fluxo em redes

Prévia do material em texto

- -1
PESQUISA OPERACIONAL
UNIDADE 4 - FLUXO EM REDES
Rayane Ester Felício Santiago
- -2
Introdução
Quando pensamos em fluxo em redes, a primeira coisa que vem à cabeça está relacionada ao transporte, aquilo
que pode ir de um ponto a outro em uma rede, o que pode ser direcionado de uma origem a um destino por meio
de uma rede. Esse pensamento é totalmente lógico, pois o fluxo em redes representa tudo isso.
A palavra fluxo quer dizer aquilo que se movimenta de modo contínuo, ou o escoamento contínuo de algo que 
segue um curso. O segundo conceito é o mais conveniente para o uso durante o aprendizado desta unidade, na
qual veremos justamente como funciona o escoamento de algo ao longo de uma rede – é o que determina o curso
desse fluxo.
Os arcos de uma rede podem orientar e designar a direção para o qual um fluxo seguirá, desde sua origem até o
seu destino; portanto, relacionar o fluxo em redes ao transporte é algo totalmente natural, já que a intenção aqui
será, justamente, determinar o fluxo ideal para que algo seja transportado de uma origem a um destino, seja para
garantir maior eficiência de um processo, seja para reduzir um custo, entre outros.
O fluxo por meio de um arco é permitido apenas na direção que esse arco determina e quando está próximo à
origem. Os arcos tendem a apontar de forma a se afastarem do nó, enquanto no destino os arcos tendem a se
aproximar do nó. Mas, observando todos esses critérios, será que dá para conhecer o fluxo máximo que uma rede
pode suportar?
Há alguns casos em que precisamos determinar o custo mínimo para transportar o máximo possível, portanto
algumas restrições devem ser respeitadas. Qual será a forma de encontrar uma solução ótima de fluxo em uma
rede de forma a respeitar essas restrições e garantir o menor custo? E quando há determinada quantidade de
unidades na origem, elas devem ser distribuídas de forma ótima ao longo da rede até o destino, seria possível
determinar esse fluxo?
Essa unidade responderá a todas essas questões, utilizando exemplos práticos que auxiliem a entender a teoria e
os cálculos envolvidos. Você está pronto para ver tanta coisa interessante? Então, bons estudos!
1.1 Caracterização do problema
Para que um fluxo em redes seja executado, algumas condições devem ser respeitadas e a primordial é observar
a orientação, o valor do arco no qual esse fluxo passará, os valores das origens e dos destinos. Esse tipo de
problema é de programação linear (PL), pois devemos definir a função objetivo que determinará se devemos
maximizar o retorno ou minimizar o custo, por exemplo, em uma rede. As restrições dizem respeito aos valores
disponíveis nas origens e necessitados nos destinos. Conforme Lachtermarcher (2016), o fluxo por redes resolve
problemas de programação linear (PPL) específicos, porém de uma forma mais eficiente que o método Simplex
tradicional.
Por definição, o fluxo em uma rede ( é determinado por uma função de em Isso quer dizer que aN,A) A Z 0. 
função (Z) atribui um valor não negativo a cada arco da rede, porém deve-se atentar para o fundamento básico
do problema de fluxo em rede: os valores de cada nó, que representam as restrições da rede.
Para se respeitar as restrições, é necessário observar os em cada nó. Como? Supondo que representaexcessos Y
uma parte de e um fluxo, chamaremos de o complemento de ( ) e ( ) a soma dos valores de N x Y’ Y Y’ = N-Y x Y’, Y x
no conjunto de arcos que entram em . Analogamente, ( ) é a soma dos valores de no conjunto de arcosY x Y, Y’ x 
que saem de Desse modo, temos que o de em é a diferença entre o que entra e o que sai de :Y. excesso x Y Y
x( ) - ( ).Y’, Y x Y, Y’
- -3
1.1.1 Tipos de problemas de fluxo
O fluxo em redes é aplicado para diversos tipos de problemas, mas seu uso mais comum é para problemas de
transporte, que visa minimizar o custo para o envio de algo da origem ao destino (função objetivo), mas que vise
satisfazer os limites de fornecimento e demanda, que em redes são as capacidades dos arcos (restrições). O
problema de transportes também pode solucionar problemas que não possuem nenhuma relação com
transportes, como: programação de estoque, controle de empregos, criação de cronograma de produção, entre
outros (TAHA, 2008).
Outro tipo de problema que pode ser solucionado com base no fluxo em redes é o de roteamento, em que os
designados são encaminhados para realizar tarefas e sua aplicação pode ser para designar um número de
pessoas para fazê-la, mas também pode ser aplicado a máquinas, carros e, até mesmo, os períodos que serão
destinados à realização de certa tarefa (HILLIER; LIEBERMAN, 2013).
1.2 Problema de transporte
De modo geral, o problema de transportes trata de determinar o custo mínimo para que seja realizado o envio de
um produto de algumas origens (fábricas) para seus destinos (centros de distribuição – CDs). Porém, não basta
minimizar o custo: deve-se respeitar que as fábricas não podem enviar uma quantidade maior de mercadoria do
que é capaz de produzir e os CDs não poder receber mais do que a sua demanda, por exemplo (TAHA, 2008;
ANDRADE, 2009; LACHTERMARCHER, 2016).
A representação geral de um problema de transportes pode ser demonstrada na rede da Figura a seguir, em que
há origens em destinos, sendo que as origens e os destinos estão representados por nós, já as rotas quem n 
fazem a ligação entre as origens e os destinos são representadas pelos arcos ( ). Os arcos apresentam asi, j
seguintes informações: o custo de envio da mercadoria, por unidade ( ), e quantas unidades são enviadas ( ).cij xij
A quantidade que sai da origem é representada por e a demanda em no destino é . O problema devei ai j bj
satisfazer as restrições de suprimento e demanda e determinar o fluxo que minimizará o custo total doxij
transporte.
VOCÊ QUER LER?
O professor Paulo Feofiloff, da Universidade de São Paulo, desenvolveu uma apostila que traz
os conceitos tratados nesta unidade de forma mais teórica. É possível complementar a
literatura e os conhecimentos acerca de fluxos em redes e dos problemas mais comuns sobre
esse assunto. Essa apostila pode enriquecer os seus conhecimentos e está disponível no :link
https://www.ime.usp.br/~pf/flows/mynotes/FluxoEmRedes.pdf.
- -4
Figura 1 - Rede geral para o problema de transportes.
Fonte: TAHA, 2008, p. 85.
Trocando em miúdos: temos que transportar o produto final de várias fábricas nas quais são produzidos para
vários CDs onde são necessários. Conhecendo o quanto cada fábrica pode produzir ( ), o quanto cada CD precisaai
( ) e o custo para transportar cada unidade produzida ( ), temos condição de definir quantas unidades devembj cij
ser enviadas de cada fábrica para cada CD ( ), de modo a minimizar o custo desse envio.xij
1.2.1 Modelo linear do problema de transporte
A PL é aplicada para resolução de um problema de transportes, pois teremos uma variável de decisão ( ) quexij
determinará a quantidade a ser transportada de uma origem até o destino, teremos um objetivo, que é minimizar
o custo de transporte entre as origens até os destinos ( ), e temos as restrições para a realização dessecij
transporte. O exemplo a seguir, retirado da obra de Silva (2010) nos ajudará a entender e montar o PPLet al. 
para problemas de transporte.
Veja a rede a seguir, que mostra as origens e as disponibilidades de produtos nessas origens (nós da esquerda) e
os destinos, bem como as necessidades de produtos desses destinos (nós da direita). A rede também nos mostra
o custo de transporte de cada unidade entre cada origem e cada destino.
- -5
Figura 2 - Exemplo de rede para o problema de transportes.
Fonte: SILVA et al., 2010, p. 96.
A rede pode ser traduzida no simples quadro a seguir, onde temos as origens, os destinos, as disponibilidades
das origens e as necessidades dos destinos.
Como o objetivo é minimizar o custo de transporte, a função objetivo, para esse caso, é descrita da seguinte
forma:
Min = 10X11 + 12X12 + 20X21 + 8X22 + 6X31+ 15X32C
Sendo que 10X11, por exemplo, é o custo do transporte unitário da origem 1ao destino 1 multiplicado pela
quantidade a ser transportada da origem 1 ao destino 1.
As restrições para esse problema devem obedecer às quantidades retiradas em cada origem, que devem ser
iguais às suas disponibilidades. Além disso, as quantidades que chegarão a cada destino devem ser iguais às suas
necessidades. Desse modo, as restrições podem ser esquematizadas da seguinte forma:
O modelo para esse problema de transportes fica do seguinte modo:
- -6
O modelo para esse problema de transportes fica do seguinte modo:
Min = 10X11 + 12X12 + 20X21 + 8X22 + 6X31+ 15X32C
Sujeito a:
No caso estudado, podemos dizer que o sistema está em equilíbrio, porque a disponibilidade das origens é
exatamente igual à necessidade nos destinos. Quando não há produtos suficientes para satisfazer à demanda,
temos um sistema não equilibrado e, para resolvê-lo, devemos adicionar uma origem fictícia; analogamente,
quando há mais disponibilidade nas origens do que demanda nos destinos, podemos criar um destino fictício.
Os custos de cada unidade acrescentada nas origens ou nos destinos fictícios são zero e as quantidades que são
transportadas de origens fictícias ficam faltando nos destinos, enquanto as quantidades transportadas para
destinos fictícios ficam, na verdade, armazenadas nas origens. Entenderemos como isso funciona observando o
quadro a seguir, que mostra um sistema não equilibrado.
Para que o sistema fique novamente em equilíbrio, criaremos uma origem fictícia, que receberá a diferença entre
necessidade e disponibilidade: 95-90 = 5. O quadro desse sistema em equilíbrio fica da seguinte forma:
Uma possível solução para esse problema é mostrada no quadro a seguir, no qual os valores nas células
representam as unidades transportadas de cada origem para cada destino.
VAMOS PRATICAR?
Com base no conceito de origem e destino fictício, observe a seguinte situação e determine se
uma origem ou um destino fictício deve ser adicionado.
Fornecimento: A1 = 10, A2 = 5, A3 = 4, A4 = 6.
Demanda: B1 = 10, B2 = 5, B3 = 7, B4 = 9.
Lembre-se de justificar sua resposta.
- -7
Observando o quadro, é possível notar que todas as disponibilidades foram enviadas para os destinos e todas as
necessidades foram recebidas das origens. Com essa solução, os valores XA2 =1 e XA3 = 4 não chegam aos
destinos, pois partiram de uma origem fictícia, criada apenas para equilibrar o sistema, portanto o destino 2
recebe apenas 44 unidades, e o destino 3 apenas 11.
1.2.2 O algoritmo dos transportes
Como já dito, o problema de transportes é um PPL. O procedimento para sua solução consiste em duas etapas: a
primeira é calculada a solução básica inicial, e a segunda é observado o critério da otimalidade.
A solução básica inicial é constituída por um conjunto de valores que determina a quantidade a ser transportada
e deve obedecer às seguintes condições: satisfazer as restrições de origem e destino e não apresentar circuitos
entre as variáveis básicas (não deve haver uma poligonal fechada ligando variáveis básicas). Para encontrar a
solução básica, podemos utilizar dois métodos: o método do canto noroeste e o método das penalidades.
1º método (canto noroeste): a partir da célula superior esquerda, devemos transportar o máximo possível da
origem ao destino, de forma que a linha e a coluna correspondentes a essa célula fiquem iguais a zero. O próximo
transporte terá como objetivo zerar a coluna e a linha da célula mais próxima à anterior (à direita ou abaixo)
(ANDRADE, 2009).
Exemplo: encontre a solução básica inicial do seguinte quadro, que representa um problema de transportes e 
que já conta com uma origem fictícia.
No primeiro transporte, devemos enviar o máximo de unidades para zerar as disponibilidades e as necessidades
(linhas e colunas). O primeiro transporte está representado no quadro a seguir.
VOCÊ SABIA?
O problema de transporte também pode ser resolvido pelo método Simplex, mas, por ser um
tipo especial de PPL, pode ser solucionado utilizando cálculos simplificados, porém contendo
as mesmas fases do Simplex. Todavia, se você quiser modelar o PPL e resolver pelo Simplex, a
solução ótima também será encontrada.
- -8
Note que o máximo que poderia ser enviado no primeiro transporte, obedecendo à regra do canto noroeste,
eram 18 unidades, que fez com que o valor da coluna 1 fosse zerado e a linha 1 passou a ter o valor 2. Os demais
transportes serão apresentados a seguir.
Os transportes realizados e mostrados no quadro foram os relacionados a seguir. Clique nos itens.
Transporte 1
X11 = 18 (disponibilidade da primeira linha = 2).
Transporte 2
X12 = 2 (disponibilidade da primeira linha = 0, disponibilidade da segunda coluna = 38).
Transporte 3
X22 = 30 (disponibilidade da segunda linha = 0, disponibilidade da segunda coluna = 8).
Transporte 4
X32 = 8 (disponibilidade da terceira linha = 12, disponibilidade da segunda coluna = 0).
Transporte 5
X33 = 12 (disponibilidade da terceira linha = 0, disponibilidade da terceira coluna = 15).
Transporte 6
X43 = 15 (disponibilidade da quarta linha = 0, disponibilidade da terceira coluna= 0).
As variáveis mostram as quantidades que devem ser enviadas das origens aos destinos, de forma que as
restrições de disponibilidade e necessidade fossem cumpridas.
- -9
2º método das penalidades: tem como objetivo fazer o transporte na linha ou coluna que apresente a maior 
penalidade (diferença entre as células de menor custo em cada linha ou coluna). Fazendo o transporte na célula
de menor custo, esse método consegue garantir que não haja aumento de custo igual à penalidade (ANDRADE,
2009).
Clique nos itens e veja as etapas para concretização desse método.
1º passo
Calcule a penalidade para cada linha e para cada coluna e escolha a linha ou coluna que tenha a maior penalidade
(em caso de empate, escolha arbitrariamente).
2º passo
Eleja a célula de menor custo unitário e transporte a maior quantidade possível, de modo a zerar a linha ou a
coluna dessa célula. Elimine a linha ou a coluna zerada.
3º passo
Retorne ao primeiro item até que todas as linhas e todas as colunas tenham sido zeradas.
Realizaremos um exemplo prático para entender melhor esse método, com base no seguinte quadro, que
apresenta um problema de transporte.
VOCÊ QUER VER?
Para entender melhor como funciona o método do canto noroeste para encontrar a solução
inicial de um problema de transportes, assista à aula do professor Matusalém. Essa aula é bem
rápida e nela o professor explica os passos apresentados aqui de forma bem dinâmica para um
problema semelhante (MARTINS, 2014). Disponível em:
https://www.youtube.com/watch?v=4SSacL3ATuY
CASO
Determine a solução inicial utilizando o método das penalidades para o seguinte problema de
transportes já modelado como um PPL:
MinC = 5X11 + 3X12 + 2X21 + 1X22
Sujeito a:
https://www.youtube.com/watch?v=4SSacL3ATuY
- -10
Transporte 1: calcule a penalidade para cada linha e para cada coluna e escolha a maior. 
Agora, realizaremos o transporte da maior quantidade possível na célula com o menor custo, de modo a zerar a
linha ou a coluna:
A linha 4 teve sua disponibilidade zerada, portanto será eliminada e seguiremos com o segundo transporte.
Transporte 2: escolha o da maior penalidade: 
Transporte na célula com menor custo:
A coluna 1 teve sua disponibilidade zerada e será eliminada. Os demais transportes serão realizados do mesmo
- -11
A coluna 1 teve sua disponibilidade zerada e será eliminada. Os demais transportes serão realizados do mesmo
modo e, ao final, a solução inicial usando o método das penalidades ficará da seguinte forma:
Vejamos, agora, o critério da otimalidade.
1.2.3 Critério da otimalidade
Assim como em um PPL comum, resolvido com o auxílio do método Simplex, um problema de transporte deve
ser verificado para observar se a solução inicial pode ser melhorada. Isso se faz, analogamente ao Simplex,
observando os coeficientes das variáveis não básicas (VNB) na função objetivo. Para tanto, é necessário escrever
a função objetivo nos termos das VNB,sendo que elas devem ser todas positivas, pois, enquanto existirem
variáveis negativas, significa que o sistema ainda pode ser melhorado. Melhorar o sistema consiste em:
• entrar com uma VNB;
• tirar uma variável básica (VB) para que a VNB entre.
Realizando esse processo, necessitamos agora passar por algumas etapas que serão explicadas uma a uma, como
base no exemplo retirado da obra de Silva (2010, p. 105).et al., 
Exemplo: calcule o plano de transporte de menor custo para o problema que está representado no quadro a 
seguir.
Podemos perceber que o sistema está em equilíbrio, portanto podemos calcular a . Pelosolução básica inicial
método do canto noroeste, essa solução fica da seguinte forma:
No , devemos primeiramente saber se uma VNB pode ser melhorada; para isso, seucritério da otimalidade
coeficiente deve ser negativo. Sabendo que o coeficiente de uma VB é 0, multiplicaremos cada restrição de linha
por e cada restrição de coluna por somaremos às variáveis de custo da função objetivo e igualaremos a-Ui -Vj, 
zero, que é o coeficiente de uma VB. A solução do sistema pode ser obtida atribuindo um valor arbitrário para
uma das incógnitas ( e ) e calculando o valor das outras. Esses valores permitem calcular o coeficiente dasUi Vj
VNB do seguinte modo:
Para VB: Cij-Ui-Vj,= 0.
•
•
- -12
Para VB: Cij-Ui-Vj,= 0.
Para VNB: Cij-Ui-Vj,= coeficiente.
Desse modo, temos:
Agora, temos sete variáveis e seis equações. Atribuiremos um valor arbitrário a uma das variáveis: U1 =0.
Substituindo o valor de U1, podemos encontrar o valor das outras variáveis:
V1 = 6;
V2 = 5;
U2 = 7;
U3 = 4;
V3 = 1;
U4 = 3.
Os coeficientes das VNB serão calculados como mostrado abaixo:
A solução não é ótima, pois ainda há coeficientes de VNB negativos. O próximo passo é entrar com a VNB que
tenha o maior valor negativo absoluto no sistema (X23) e montar um circuito de compensação entre as VB a
partir da variável que entra.
Esse circuito tem o objetivo de manter as restrições de linha e coluna e é feito partindo da variável que entra e
seguindo de maneira alternativa na direção da linha e da coluna subtraindo e somando o valor da entrada até o
retorno à variável de entrada. Para esse problema, o circuito pode ser visualizado no quadro abaixo.
A variável que entra deve ter o maior valor possível para garantir que nenhuma VB se torne negativa, porém
VOCÊ O CONHECE?
O problema de transporte foi estudado pela primeira vez entre os anos de 1941 e 1942 por
Kantorovich e Koopmans. Esses holandeses estudaram esse tipo de problema de forma
independente e, para sua solução, utilizaram métodos geométricos. É importante ressaltar que
Tjalling Charles Koopmans ajudou a desenvolver a teoria da PL em 1939 e, por isso, ganhou o
Prêmio Nobel de Economia.
- -13
A variável que entra deve ter o maior valor possível para garantir que nenhuma VB se torne negativa, porém
nula. Para o exemplo que estamos tratando, a variável que entra chamado de β na tabela terá valor 2. Desse
modo, a solução passa a ser a seguinte:
Note que a VB X33 deixou o sistema, e agora a variável X23 que era uma VNB passou a ser uma VB. Feito tudo
isso, identificaremos se a solução é ótima ou se há VNB que pode ser melhorada, voltando ao primeiro passo, que
é encontrar os coeficientes das novas VNB:
Colocando U1 = 0, temos:
V1 = 6;
V2 = 5;
U2 = 7;
U3 = 4;
V3 = -6;
U4 = 10.
E os coeficientes das VNB são:
A solução ainda não é ótima, e a VNB X42 entra no sistema, pois tem o maior coeficiente negativo em termos de
valor absoluto. O circuito de compensação fica da seguinte forma:
Note que o circuito não passa pelos valores que já estão ‘compensados’, ou seja, que já obedecem a uma restrição
de linha e de coluna. O valor da variável que entra (β) será 13, pois assim será possível eliminar uma VB ainda
cumprindo as restrições. A nova solução fica:
A variável X43 saiu do sistema para a entrada da variável X42, e agora é uma VNB. Voltaremos ao início e
- -14
A variável X43 saiu do sistema para a entrada da variável X42, e agora é uma VNB. Voltaremos ao início e
identificaremos se a solução é ótima.
Atribuindo 0 a U1, temos:
V1 = 6;
V2 = 5;
U2 = 7;
U3 = 4;
V3 = -6;
U4 = 1.
Os coeficientes das VNB ficam assim:
A variável X31 ainda possui coeficiente negativo, mostrando que a solução ainda não é ótima, portanto, ela entra
no sistema. O circuito de compensação fica da seguinte forma:
Agora teremos β = 8, para que o sistema seja capaz de anular uma VB e não torne nenhum valor negativo. A
solução ficará da seguinte forma:
Voltando à etapa inicial, observaremos se a solução é ótima com as novas VB:
Fazendo U1 = 0, temos:
V2 =5;
U2 = 7;
V3 = -6;
U3 = 4;
V1 = 3;
U4 = 1.
- -15
V1 = 3;
U4 = 1.
Os coeficientes das VNB serão:
Essa solução é ótima, pois as VNB não possuem coeficientes negativos que podem ser melhorados. A forma ótima
de transporte para esse problema fica assim:
10 unidades da origem 1 ao destino 2;
5 unidades da origem 2 ao destino 2;
15 unidades da origem 2 ao destino 3;
8 unidades da origem 3 ao destino 1;
4 unidades da origem 3 ao destino 2;
13 unidades da origem 4 ao destino 2.
O custo total desse transporte será: C = 5.10 + 12.5 + 6.15 + 7. 8+ 9.4 + 6.13 = 370.
1.3 Problemas de fluxo
Durante a resolução dos problemas de fluxo em redes, como o problema de transportes, alguns impedimentos
podem surgir, dificultando os cálculos ou a aplicação dos algoritmos. Portanto, veremos alguns exemplos de
problemas de fluxo nesta seção e como resolvê-los.
1.3.1 O problema da degenerescência
Esse problema se trata de casos em que haja menos variáveis básicas do que o necessário para a solução do
problema, resultando em menos equações do que as desejadas. No algoritmo para problemas de transportes,
vimos que igualando os coeficientes das VB a zero, o resultado é sempre uma variável a mais do que o número de
equações, porém o que fazer se tiverem duas ou três equações a menos do que o número de variáveis?
Nesse caso, a solução é degenerada e não conseguimos encontrar um conjunto único de valores para U e V;
portanto, devemos criar variáveis básicas auxiliares das quais permitirão que o número de equações seja um a
menos do que o número de variáveis. Essas variáveis devem ter um valor muito próximo de zero, para que não
alterem as restrições de origem e destino, e elas não podem formar circuito com as variáveis básicas originais do
problema.
Exemplo: o quadro abaixo apresenta a solução inicial de um problema retirado de Silva (2010, p. 111): et al. 
Aplicando o teste da otimalidade, percebe-se que esse sistema possui cinco equações e sete variáveis, então uma
variável auxiliar (A) deve ser acrescentada em uma célula que não forme circuito com outras VB, da seguinte
forma:
- -16
O acréscimo da variável auxiliar A fez com que o sistema passasse a ter sete variáveis e seis equações, e o
problema continua a ser resolvido até encontrar a solução ótima.
1.3.2 O caso da maximização
Esse caso acontece em modelos de PL que possuem objetivo de maximização, mas também podem ser tratados
como problema de transportes. Um exemplo disso é um problema que busca maximizar os lucros obtidos nas
vendas de mercadorias compradas nas origens e comercializadas nos destinos.
Como o modelo de transportes minimiza o objetivo, os problemas de maximização devem transformar o objetivo
em minimização e isso pode ser feito multiplicando a função objetivo por -1 e, do mesmo modo, trocando o sinal
dos custos de transporte. Outra forma de resolver esse problema é trabalhar com um novo modelo, em que os
custos unitários de transporte sejam os complementos dos preços originais para algum valor fixo, que deve ser o
maior valor da tabela original.
1.3.3 A impossibilidade de transporte
Pode acontecer casos em que não seja possível realizar o transporte de uma origem para determinado destino.
Quando isso ocorrer, devemos colocar um símbolo na célula em que o transporte está impossibilitado: podemos
chamar esse símbolo de ∆, que representa um número muito grande. Assim, quando construirmosa solução
básica inicial, evitamos essa célula na qual o transporte está impossibilitado.
Já que o número ∆ é muito grande, ao calcular os coeficientes das VNB, esse coeficiente jamais será negativo e,
então, ela nunca se tornará uma VB, impedindo que o custo desse transporte seja contabilizado.
1.4 Problema de roteamento
Esse tipo de problema de fluxo em rede também pode ser chamado de problema de designação e resolve
situações em que exatamente uma unidade da origem deve ser enviada para o destino. Aplica-se, por exemplo, a
problemas em que um conjunto de funcionários deve ser enviado cada um para a execução de uma tarefa, ou
casos em que máquinas devem ser enviadas cada uma para um posto de trabalho. De acordo com Taha (2008),
algumas condições devem ser satisfeitas no problema de roteamento:
o número de designados e o número de tarefas é o mesmo e é representado por ;n
a cada designado deve ser atribuída exatamente uma tarefa;
cada tarefa deve ser realizada exatamente por um designado;
há um custo associado a cada designado ( ) executando uma tarefa ( ).i j
O objetivo para esse problema é determinar como cada roteamento deve ser feito de forma a minimizar o custo
total. As três primeiras condições são bem restritivas e, se não forem satisfeitas no problema inicial, podemos
reformulá-lo para que satisfaça essas condições. Isso se faz criando designados e tarefas fictícias (HILLIER;
LIEBERMAN, 2013).
- -17
1.4.1 Algoritmo para o problema de roteamento
O algoritmo para resolução do problema de roteamento deve seguir alguns passos para definir qual a melhor
tarefa para cada designado. Utilizaremos um exemplo retirado da obra de Silva (2010, p. 123), paraet al.
explanar cada passo do algoritmo para resolução do problema.
Exemplo: o quadro a seguir representa os custos de transporte de uma máquina dos locais de depósito (L) para 
as fábricas onde deverão ser instaladas (F). Designe uma máquina para cada fábrica com o menor custo total
possível.
O para resolução do problema é de cada linha o seu menor valor e, em seguida, fazer oprimeiro passo subtrair
mesmo procedimento com as colunas. Desse modo, cada linha e cada coluna deverá apresentar pelo menos um
elemento nulo, da seguinte forma:
Primeiro subtrair o menor valor de cada linha:
Depois subtrair o menor valor de cada coluna:
O é origens para destinos em que aparece o elemento nulo. Cada designação efetuadasegundo passo designar
invalida os outros elementos nulos da linha e da coluna do elemento designado. Se a designação se completa, o
problema está resolvido. Para o exemplo tratado, a designação é realizada conforme a tabela a seguir, em que os
elementos marcados por retângulo foram designados, e os demais elementos nulos foram riscados.
VOCÊ O CONHECE?
Após utilizar a ferramenta Solver do Excel para solucionar um problema de designação, o
resultado encontrado permitiu a seguinte solução:
X1→Y3; X2→Y1; X3→Y2; X4→Y5; X5→Y4.
Custo total de transporte: 180.
Sabendo que o problema se tratava de um grupo de vendedores, cada um localizado em uma
cidade (X) que deveriam ser designados para realizar suas vendas, cada um em outra cidade
(Y), escreva a interpretação da solução encontrada.
- -18
A designação ainda não está completa, pois não houve designação de L3 para F3, portanto um terceiro passo
deve ser realizado e esse consiste em os zeros da tabela com o menor número de linhas possível,cobrir
realizando as seguintes etapas:
marcar as linhas sem designação;
marcar as colunas com zeros nas linhas marcadas;
marcar as linhas com designação nas colunas marcadas;
voltar a marcar as colunas com zeros nas linhas marcadas até que não haja mais possibilidade de marcar novas
linhas ou colunas;
riscar as linhas não marcadas e as colunas marcadas.
Para o problema tratado, a etapa de cobertura dos zeros é representada no quadro abaixo:
Feito isso, o é escolher o , entre todos os valores não cobertos, e subtrair esse valorquarto passo menor valor
de todos os elementos do quadro. A reposição que deve ser realizada nas linhas e colunas que possuem zeros, de
modo que se impeça o aparecimento de custos negativos deve seguir os seguintes critérios:
os elementos não cobertos ficam diminuídos do valor escolhido;
os elementos nas interseções da cobertura ficam acrescentados do valor escolhido;
os demais elementos permanecem iguais.
No exemplo utilizado, o valor escolhido deve ser o 2, que é o menor dentre os não cobertos. As subtrações e as
reposições são representadas a seguir:
Feito isso, voltaremos ao segundo passo e faremos uma nova designação para identificar se cada origem
designará uma máquina para cada destino. O quadro a seguir mostra como essa designação ficará.
Agora, cada origem designou uma máquina para cada destino. A solução final é a seguinte:
L1 → F1
L2 →F2
L3 →F4
L4 →F3
O custo total desse transporte é: 10 + 12 + 13 + 15 = 50.
- -19
Síntese
Aprendemos nesta unidade a caracterizar o problema de fluxo em redes, quais os possíveis problemas de fluxo,
entender como funciona e como soluciona o problema de transportes e o problema de roteamento.
Nesta unidade, você teve a oportunidade de:
• entender como funciona o fluxo em redes e como ele pode ser usado para resolver diversos problemas;
• observar a notação matemática que caracteriza um problema de fluxo;
• aprender sobre quais os problemas mais comuns que podem ser resolvidos com fluxos em rede;
• aprender sobre o clássico problema de transporte, como funciona sua aplicação e quais as etapas para a 
sua solução;
• observar os impedimentos mais comuns à solução de um problema de fluxo;
• aprender sobre o problema de roteamento, vimos sua aplicação nua situação prática e como solucionar 
esse tipo de problema.
Bibliografia
ANDRADE, E. L. : métodos e modelos para análise de decisões. 4. ed. Rio deIntrodução à pesquisa operacional
Janeiro: LTC, 2009.
FEOFILOFF, P. . São Paulo: USP, 2018. Disponível em: https://www.ime.usp.br/~pf/flowsFluxo em redes
/mynotes/FluxoEmRedes.pdf. Acesso em: 18 ago. 2019.
HILLIER, F. S.; LIEBERMAN, G. J. . 9. ed. São Paulo: McGraw-Hill, 2013.Introdução à pesquisa operacional
LACHTERMACHER, G. . 5. ed. Rio de Janeiro: LTC, 2016.Pesquisa operacional na tomada de decisões
MARTINS, M. V. : o problema do transporte – método do canto noroeste – exemplo 1. 31Pesquisa operacional
de maio de 2014. Disponível em: https://www.youtube.com/watch?v=4SSacL3ATuY. Acesso em: 18 ago. 2019.
SILVA, E. M. : para os cursos de administração e engenharia. 4. ed. São Paulo: Atlas,et al. Pesquisa operacional 
2010.
TAHA, H. A. . 8. ed. São Paulo: Pearson, 2008.Pesquisa operacional
•
•
•
•
•
•
	Introdução
	1.1 Caracterização do problema
	1.1.1 Tipos de problemas de fluxo
	1.2 Problema de transporte
	1.2.1 Modelo linear do problema de transporte
	1.2.2 O algoritmo dos transportes
	1.2.3 Critério da otimalidade
	1.3 Problemas de fluxo
	1.3.1 O problema da degenerescência
	1.3.2 O caso da maximização
	1.3.3 A impossibilidade de transporte
	1.4 Problema de roteamento
	1.4.1 Algoritmo para o problema de roteamento
	Síntese
	Bibliografia