Otimização em Sistemas Logísticos modulo 4

Prévia do material em texto

DESCRIÇÃO
Os gastos com logística e o impacto nos custos de distribuição de uma empresa. Otimização de processos logísticos, na
busca do menor custo, da melhor rota de distribuição etc.
PROPÓSITO
Possibilitar ao aluno a aplicação de técnicas para a otimização de sistemas de distribuição.
PREPARAÇÃO
Antes de iniciar o estudo deste tema, tenha em mãos uma calculadora, preferencialmente que execute cálculo de
exponenciais. Como apoio para a solução dos problemas que serão apresentados, se possível, tenha um computador com
aplicativo Microsoft Excel ou Apache OpenOffice.
OBJETIVOS
MÓDULO 1
Identificar os problemas de transporte
MÓDULO 2
Identificar os problemas de redes de distribuição
MÓDULO 3
Descrever o problema do menor caminho
MÓDULO 4
Descrever o problema do fluxo máximo
BEM-VINDO À OTIMIZAÇÃO EM SISTEMAS DE
DISTRIBUIÇÃO
MÓDULO 1
 Identificar os problemas de transporte
IMPORTÂNCIA DA OTIMIZAÇÃO DE PROBLEMAS DE
TRANSPORTE
CONCEITOS
Os sistemas de transporte movem mercadorias entre origens e destinos usando veículos e equipamentos como
caminhões, tratores, reboques, tripulações, paletes, contêineres, carros e trens. O transporte representa o papel principal
e o elemento mais importante na logística devido ao seu custo considerável.
Um sistema de transporte é uma organização que projeta, organiza, instala e agenda pedidos de frete-transporte durante
um determinado período limitado com restrições técnicas ao menor custo possível.
 SAIBA MAIS
O transporte muitas vezes representa entre um terço e dois terços dos custos totais de logística, ou seja, entre 9% e 10%
do PIB (Produto Interno Bruto) na Europa e entre 10% e 20% do preço do produto; portanto, é inegável a importância da
otimização do transporte. No Brasil, em função do modal adotado (rodoviário na maioria) e das más condições de nossas
estradas, o custo logístico representa entre 12% e 15% do nosso PIB.
O transporte é essencial para mover qualquer remessa em um sistema logístico, como matérias-primas das fontes ao
fabricante, produtos semiacabados entre fábricas e produtos para varejistas e clientes. Hoje em dia, com o crescimento da
ciência e da tecnologia, aumentando o consumo e o comércio global, destaca-se o papel do transporte em todos os
processos.
Há um alto nível de competição entre fabricantes e operadores logísticos quanto a qualidade do atendimento ao cliente.
Outros fatores competitivos críticos são: prazos de entrega, atrasos e custos de transporte, bem como a necessidade
permanente de aumentar a eficiência, confiabilidade, segurança e reatividade nos sistemas de serviço.
EXEMPLO
Vamos considerar o seguinte exemplo: uma cadeia consiste em vários clientes, distribuidores e fabricantes (ver figura). Os
clientes encontram-se no primeiro nível, enquanto no segundo existem centros de armazenamento/distribuição que
transportam vários produtos para os clientes e, no terceiro, fabricantes (produtores) que fornecem os produtos para os
centros.
A demanda não atendida de cada cliente em cada período é considerada em espera; no entanto, todas as demandas dos
clientes insatisfeitos devem, eventualmente, ser satisfeitas.
PROBLEMA DE TRANSPORTE COMO UMA REDE
Suponha que uma empresa tenha m depósitos e n lojas de varejo. Um único produto deve ser enviado dos armazéns para
os pontos de venda. Cada armazém tem um determinado nível de abastecimento, e cada loja tem um determinado nível
de demanda. Também estão definidos os custos de transporte entre cada armazém e ponto de venda e estes custos são
considerados lineares.
As premissas são:
O fornecimento total do produto do armazém é , em que .
A demanda total do produto no ponto de venda é , em que .
O custo de envio de uma unidade do produto do armazém para a saída é igual a , em que
.
O custo total de uma remessa é linear no tamanho da remessa.
O interesse é determinar um esquema de transporte ideal entre os armazéns e os pontos de venda, sujeitos às restrições
de oferta e demanda especificadas. Graficamente, um problema de transporte é frequentemente visualizado como uma
rede com m nós de origem, n nós coletores e um conjunto de m x n "arcos direcionados". Isto é representado na figura a
seguir.
i ai  i  =  1,  2, .  .  . ,  m
j bj j  =  1,  2, .  .  . ,  n
i j cij
i  =  1,  2, .  .  . ,  m e j  =  1,  2, .  .  . ,  n
Prosseguimos agora com uma formulação de programação linear desse problema.
VARIÁVEIS DE DECISÃO
Um esquema de transporte é uma especificação completa de quantas unidades do produto devem ser enviadas de cada
armazém para cada destino. Portanto, as variáveis de decisão são:
 = O TAMANHO DA REMESSA DO ARMAZÉM I PARA O
DESTINO J, ONDE I = 1, 2,. . ., M E J = 1, 2,. . ., N. ESTE É UM
CONJUNTO DE VARIÁVEIS M X N.
FUNÇÃO OBJETIVO
Considere a remessa do armazém i para o destino j. Para qualquer i e qualquer j, o custo de transporte por unidade é , e
o tamanho da remessa é . Uma vez que assumimos que a função de custo é linear, o custo total dessa remessa é
obtido por . Somando todos os i e todos os j, podemos obter o custo geral de transporte para todas as combinações
de armazém-destino.
OU SEJA, NOSSA FUNÇÃO OBJETIVO É:
xij
cij
xij
cijxij
MINIMIZAR 
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
RESTRIÇÕES
Considere o armazém i. A expedição total desse depósito é a soma . Em notação de soma,
isso é escrito como . Uma vez que o fornecimento total do armazém i é , a remessa total de saída não pode
exceder , ou seja, devemos impor
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Considere agora o destino j. A remessa total que chega neste ponto de venda é a soma .
Na notação de soma, como vimos acima, isso é escrito como . Uma vez que a demanda do destino j é , o total de
entrada à remessa não deve ser inferior a . Ou seja, devemos impor
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Isso resulta em um conjunto de restrições funcionais m + n. Claro, como remessas físicas, os se devem ser não
negativos.
FORMULAÇÃO PL (PROGRAMAÇÃO LINEAR)
Em resumo, chegamos à seguinte formulação:
 
m
∑
i=1
n
∑
j=1
cij × xij
xi1  +  xi2  +   ⋅   ⋅   ⋅   +  xin
n
∑
j=1
 xij ai
ai
n
∑
j=1
xij  ≤  ai     para  i = 1,  2,   … ,  m
x1j  +  x2j  +   ⋅   ⋅   ⋅   +  xmj
n
∑
j=1
xij bj
bj
n
∑
j=1
xij  ≥  bj     para  j = 1,  2,   … ,  n
xij
′s
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Sujeito a:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
UM EXEMPLO NUMÉRICO
Em uma instância real do problema de transporte, precisamos especificar m e n, e substituir o , , e com
valores numéricos explícitos. Como um exemplo simples, suponha que recebamos:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Então, a substituição desses valores na formulação acima leva ao seguinte problema explícito:
Minimizar  
m
∑
i=1
n
∑
j=1
cij × xij
n
∑
j=1
xij  ≤  ai     para  i = 1,  2,   … ,  m
n
∑
j=1
xij  ≥  bj     para  j = 1,  2,   … ,  n
xij   ≥  0  para  i  =  1,  2,  .  .  .  ,  m e j  =  1,  2,  .  .  .  ,  n
ai
′s bj
′s cij
′s
m  =  3 e n  =  2;  
a1  =  45,  a2  =  60 e a3  =  15;  
b1  =  50 e b2  =  60;
c11  =  3,  c12  =  2,  c21  =  1,  c22  =  5,  c31  =  2 e c32  =  4.  
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Sujeito a:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
 ATENÇÃO
Colocamos o sinal de “=” no lugar do “≥”, porque a capacidade de entrega é 130 (45 + 60 + 35), superior à demanda 110
(50 + 60), o que indica que a demanda terá que ser atendida.
Para um exemplo de um esquema de transporte explícito, vamos admitir
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
É facilmente visto que essa solução proposta satisfaz todas as restrições e, portanto, é viável. Em palavras,a solução
exige o envio de 20 unidades do armazém 1 para ao destino 1, 20 unidades de armazém 1 ao destino 2, 20 unidades do
armazém 2 ao destino 1, e, finalmente, 5 unidades do armazém 3 para o destino 2.
O custo total de transporte associado a esse esquema pode ser calculado como:
Minimize  3x11  +  2x12  +  x21  +  5x22  +  2x31  +  4x32
x11  +  x12  ≤  45
x21  +  x22  ≤  60
x31  +  x32  ≤  35
x11  +  x21  +  x31  =  50
x12  +  x22  +  x32  =  60
xij  ≥  0  para  i  =  1,  2,  3 e j  =  1,  2.
x11  =  20,  x12  =  20,  x21  =  20,  x22  =  35,  x31  =  10 e x32  =  5
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Você poderá observar que obtemos uma solução, não necessariamente a solução ótima. Vamos agora ver dois métodos
de resolução e depois com o Solver, como um adendo.
TABLEAU DE TRANSPORTE
O tableau Simplex serve como um formato muito compacto para representar e manipular programas lineares. No mesmo
sentido, apresentamos agora uma representação de tableau para problemas de transporte que estão na forma padrão.
Para um problema com m origens e n destinos, o quadro será uma tabela com m linhas e n colunas. Especificamente,
cada origem terá uma linha correspondente, e cada destino, uma coluna correspondente. Para facilidade de referência,
devemos nos referir à célula que está localizada na interseção da i-ésima linha e da j-ésima coluna como célula (i, j).
Os parâmetros do problema serão inseridos em várias partes da tabela no formato abaixo.
Cada linha é rotulada com seu nome da origem correspondente na margem esquerda, e cada coluna é rotulada com o
nome do destino correspondente na margem superior. O fornecimento da origem i está listado na margem direita da i-
ésima linha, e a demanda no destino j está listada na margem inferior da j-ésima coluna.
 ATENÇÃO
O custo de transporte é listado em uma subcélula localizada no canto superior esquerdo da célula (i, j), e, finalmente, o
valor de é inserido no canto inferior direito da célula (i, j).
3  ×  20  +  2  ×  20  +  1  ×  20  +  5  ×  35  +  2  ×  10  +  4  ×  5  =  335.
cij
xij
OBSERVAÇÕES
01
02
03
Na maioria dos aplicativos, as remessas têm valores inteiros. Ignoramos esse requisito em nossa formulação. No entanto,
você vai descobrir que se o especificado e o especificado são inteiros, então o ótimo para a solução de um problema
de transporte produzido pelo algoritmo Simplex também tem valor inteiro.
Em aplicações com excesso de oferta, geralmente é desejável presumir que há um custo de retenção de estoque para
unidades que não são enviadas para fora. Se for esse o caso, podemos facilmente acomodar os custos de manutenção de
estoque como parte da função objetivo.
Quando a oferta total é menor do que a demanda total, ainda é possível criar um problema de transporte equilibrado. A
ideia é criar uma fonte fictícia e deixar que ela tenha um suprimento igual à diferença entre a demanda total e a oferta
total. Ao fazer isso, pode ser razoável avaliar um custo de penalidade de falta para unidades enviadas (ficticiamente) da
fonte fictícia para qualquer coletor.
REGRA DO CANTO NOROESTE
Para melhor entendimento, vamos pegar o exemplo anterior e inicialmente montar um tableau.
Suponha que comecemos o processo de atribuição com a célula (1, 1) como a célula de entrada. Uma vez que esta é a
nossa primeira tentativa em uma atribuição, o suprimento restante da origem 1 é de 45 e a demanda restante no destino 1
é de 50.
De acordo com a discussão, devemos, portanto, atribuir 45 na célula (1, 1) como o valor de . Esta imediatamente
implica que servirá como uma variável básica. Além disso, uma vez que o restante da oferta da origem 1 se esgota
ai bj
x11
x11
como resultado desta tarefa, o conceito-chave neste ponto é também pensar nessa ação como designando como a
variável básica.
 ATENÇÃO
Tendo acabado de preencher sua cota, devemos, portanto, evitar outra variável básica. Mecanicamente, isso é conseguido
riscando a primeira linha. Fazer isso resultará em um novo quadro com uma linha a menos, que servirá então como ponto
de partida para a continuação do mesmo procedimento de atribuição.
Observe que, para facilitar o processo de fazer novas atribuições, devemos agora reduzir o restante da demanda no
destino 1 a 5, de 50. Isso completa o ciclo de atribuição. Em resumo, nosso primeiro ciclo de atribuições resulta no quadro
revisado a seguir:
O fato de exatamente uma linha ou coluna ser removida na conclusão de um ciclo de atribuição é crítico, na medida em
que é a estipulação adicional que garante que um número correto de variáveis básicas será gerado no final de todo o
processo de atribuição.
Para compreender essa afirmação totalmente, vamos agora iterar nosso procedimento para a conclusão. Suponha que a
célula (2, 1) seja escolhida como a próxima célula de entrada. Então, vamos atribuir 5 como , obtendo o novo quadro a
seguir:
x11
x21
Neste ponto, as células restantes são (2, 2) e (3, 2). Suponha que a célula (2, 2) seja escolhida como a próxima célula de
entrada. Então, depois de atribuir 55 como e passar por outra rodada de atualizações de rotina, nós obtemos:
Suponha que optemos por inserir 5 na célula (3, 2); então, o novo quadro será:
x22
Portanto, o valor da função objetivo dessa solução é facilmente calculado como:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Veja que obtemos novamente uma solução, que não necessariamente é a solução ótima desejada.
MÉTODO DO MENOR CUSTO
A única diferença entre o método do menor custo e o método do canto noroeste está na escolha das variáveis de entrada.
Aqui, a estratégia é sempre selecionar a célula com o menor valor entre todas as células como a célula de entrada. Os
laços são, como sempre, quebrados arbitrariamente. Agora, examinaremos brevemente uma implementação dessa nova
estratégia.
Vamos começar com o quadro inicial. Como o menor custo é igual a 1 ( ), começamos alocando 50 unidades:
45  ×  3  +  5  ×  1  +  55  ×  5  +  5  ×  4  =  435
cij
c21
Com isso, o destino 1 foi atendido e as demais origens não podem atendê-lo. Portanto, o próximo passo será atender o
destino 2, e saímos do custo 2 ( ):
Para fechar, atendemos ao destino :
c12
c32
Portanto, o valor da função objetivo dessa solução é facilmente calculado como:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Atendemos os destinos com um custo de 200, solução melhor do que a obtida pelo método do canto noroeste.
SOLVER
Vamos agora resolver este problema utilizando o Solver, disponível no Microsoft Excel ou Apache OpenOffice. Para tanto,
inicialmente vamos montar uma planilha com os dados do problema apresentado.
 Print do Microsoft Excel
Vamos replicar as células na planilha:
para controlar o total enviado por cada armazém;
para controlar o total recebido por cada destino;
45  ×  2  +  50  ×  1  +  15  ×  4  =  200
uma célula para o cálculo da função objetivo.
 Print do Microsoft Excel
Observe os seguintes pontos:
Pintamos de amarelo as células das variáveis, ou seja, indicamos a solução de quanto cada armazém enviou para cada
destino.
Em “Enviado” somamos a quantidade que cada armazém entregará (célula G14 = E14 + D14).
Em “Recebido” somamos a quantidade que cada destino receberá (célula E17 = E14 + E15 + E16).
Calculamos o objetivo na célula I10 (=SOMARPRODUTO(E6:F8;E14:F16)).
PORTANTO, NO SOLVER COLOCAREMOS:
Definir objetivo: I10.
Marcar o botão “Min”.
Alterando células variáveis: E14:F16.
Adicionando restrição 1: G14:G16 ≤ G6:G8.
Adicionando restrição 2: E17:F17 = E9:F9.
Adicionando restrição 3: E14:F16 = int.
Optando por: LP Simplex.
A tela do Solver ficará assim:
 Print do Microsoft Excel
Clicando em Resolver, obtemos:
 Print do Microsoft Excel
 ATENÇÃO
Veja que obtemos a solução ótima, que coincidiu com a achada no Menor Custo.
EXEMPLO
Vamos agora ver outro exemplo para fixar os conceitos: umaempresa tem disponibilidade de três fábricas para produzir
um componente vendido a cinco atacadistas. Os custos de transporte das fábricas para os clientes são mostrados a
seguir:
Origem Cliente A Cliente B Cliente C
Fábrica I 0,04 0,08 0,10
Fábrica II 0,07 0,05 0,11
Fábrica III 0,11 0,08 0,08
Tabela de custos de transporte das fábricas para os clientes.
Elaborada por: Mauro Rezende Filho
Previsões de vendas indicam que as demandas mensais são de: 4.000 unidades do cliente A; 2.200 do B; 3.000 do C. As
capacidades máximas de produção mensal são de 5.500 na fábrica I, 8.000 na fábrica II, e 10.000 na III. Pede-se a
otimização do sistema de transporte.
Vamos inicialmente montar a tabela com os dados apresentados:
Origem Cliente A Cliente B Cliente C Capacidade
Fábrica I 0,04 0,08 0,10 5.500
Fábrica II 0,07 0,05 0,11 8.000
Fábrica III 0,11 0,08 0,08 10.000
Demanda 4.000 2.200 3.000
Tabela com capacidades máximas de produção mensal.
Elaborada por: Mauro Rezende Filho
O próximo passo será escrever o modelo matemático:
MINIMIZAR
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Sujeito a:
0, 04x11  +  0, 08x12  +  0, 10x13  +  0, 07x21  +  0, 05x22 +
0, 11s23  +  0, 11x31  +  0, 08x32  +  0, 08x33
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
MÉTODO DO CANTO NOROESTE
Vamos então montar o tableau de transporte.
Utilizando o método, a primeira variável básica será a célula , e vamos alocar 4.000 unidades, o que atenderá
plenamente o cliente 1. Temos então:
x11  +  x12  +  x13  ≤  5500
x21  +  x22  +  x23  ≤  8000
x31  +  x32  +  x33  ≤  10000
x11  +  x21  +  x31  =  4000
x12  +  x22  +  x32  =  2200
x31  +  x32  +  x33  =  3000
xij são inteiros para i  =  1,  2,  3 e j  =  1,  2
xij  ≥  0 para i  =  1,  2,  3 e j  =  1,  2
x11
O próximo passo será completar a fábrica 1 atendendo o cliente 2:
Vamos então completar o cliente 2:
E fechando as estregas temos:
Portanto, o valor da função objetivo será:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
MÉTODO DO MENOR CUSTO
A variável básica será porque apresenta o menor custo:
A próxima será a :
E finalizando:
Portanto, temos o valor da função objetivo:
0, 04  ×  4000  +  0, 08  ×  1500  +  0, 05  ×  700  +  0, 11  ×  3000  =  645
x11
x22
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
SOLVER
Montando a planilha básica:
 Print do Microsoft Excel
Vamos replicar as células na planilha:
para controlar o total enviado por cada fábrica;
para controlar o total recebido por cada cliente;
uma célula para o cálculo da função objetivo.
 Print do Microsoft Excel
Observe os seguintes pontos:
Pintamos de amarelo as células das variáveis, ou seja, indicamos a solução de quanto cada armazém enviou para cada
destino.
Em “Enviado” somamos a quantidade que cada armazém entregará (célula G12 = SOMA(D12:F12)).
Em “Recebido” somamos a quantidade que cada destino receberá (célula D15 = SOMA(D12:D14)).
0, 04  ×  4000  +  0, 05  ×  2200  +  0, 08  ×  3000  =  510
Calculamos o objetivo na célula I9 (=SOMARPRODUTO(D4:F6;D12:F14).
Portanto, no Solver colocaremos:
Definir objetivo: I9.
Marcar o botão “Min”.
Alterando células variáveis: D12:D14.
Adicionando restrição 1: G12:G14 ≤ G4:G6.
Adicionando restrição 2: D15:F15 = D7:F7.
Adicionando restrição 3: D12:D14= int.
Optando por: LP Simplex.
A tela do Solver ficará assim:
 Print do Microsoft Excel
Clicando em Resolver obtemos:
 Print do Microsoft Excel
Neste primeiro módulo do tema, falamos sobre os problemas de transporte. No módulo dois, falaremos sobre os
problemas de redes de distribuição. Antes disso, vamos colocar em prática os conhecimentos adquiridos até aqui por meio
de algumas atividades.
MÃO NA MASSA
TEORIA NA PRÁTICA
Uma empresa tem disponibilidade para construir três fábricas para produção de um componente vendido a cinco
atacadistas a um preço fixo de entrega de R$2,00 por unidade. Os custos de transporte das fábricas para os clientes são
mostrados a seguir:
Origem Cliente A Cliente B Cliente C Cliente D Cliente E
Fábrica I 0,04 0,08 0,10 0,14 0,15
Fábrica II 0,07 0,05 0,11 0,11 0,15
Fábrica III 0,11 0,08 0,08 0,11 0,15
Previsões de vendas indicam que as entregas mensais serão de: 4.000 unidades ao cliente A; 2.200 ao B; 3.000 ao C;
3.500 ao D; e 4.000 ao cliente E. As capacidades máximas de produção mensal são de: 5.500 na fábrica I; 8.000 na
fábrica II; e 10.000 na III. Os custos diretos para produzir cada unidade são de R$2,00 na fábrica I, R$1,90 na fábrica II e
R$1,50 na fábrica III. Os custos fixos são de R$500,00 na fábrica I, R$900,00 na fábrica II e R$1.800,00 na fábrica III. Qual
o lucro da operação?
RESOLUÇÃO
UMA APLICAÇÃO DE TRANSPORTE
VERIFICANDO O APRENDIZADO
MÓDULO 2
 Identificar os problemas de redes de distribuição
OS PROBLEMAS DE REDES DE DISTRIBUIÇÃO
CONCEITOS
Situações de distribuição de produtos que consideram uma ou mais fontes de origem, centros de distribuição e locais
intermediários por onde materiais e produtos apenas passam são denominados problemas de rede de distribuição. Os
problemas de transporte podem ser considerados uma simplificação do problema de rede de distribuição de menor custo.
UM PROBLEMA DE TRANSPORTE É RECONHECIDO QUANDO
PRECISAMOS ENVIAR UNIDADES DE UM PRODUTO POR UMA
REDE DE MODAIS (OU ÚNICO MODAL) QUE CONECTAM UM
DETERMINADO LOCAL OU GRUPO DE LOCAIS DE ENTREGA.
O propósito, além de minimizar o custo de transportar bens de um local para outro, é proceder de forma que as
necessidades de cada área de destino sejam conhecidas e todo local de remessa opere dentro de sua capacidade. As
soluções devem ser construídas por pessoas, não necessariamente com formação específica nas áreas de matemática ou
programação linear.
Para a solução de problemas de rede de distribuição na cadeia logística (problema de transporte), neste módulo, será
utilizado um caso em que aplicaremos o método Kuhn, e também veremos como utilizar a ferramenta Solver, disponível no
Excel e no Apache OpenOffice.
MÉTODO KUHN - O ALGORITMO HÚNGARO
O problema da atribuição trata da atribuição de máquinas para tarefas, trabalhadores para empregos, jogadores de futebol
para posições e assim por diante. O objetivo é determinar a atribuição ideal que, por exemplo, minimiza o custo total ou
maximiza a eficácia da equipe. O problema de atribuição é um problema fundamental na área de otimização combinatória.
 SAIBA MAIS
Um dos métodos mais eficazes para resolver problemas de atribuição veio de Kuhn. Seu algoritmo foi baseado no trabalho
do matemático húngaro Egerváry, por isso, também é conhecido como o algoritmo húngaro ou algoritmo Kuhn.
O algoritmo húngaro consiste em quatro etapas. As duas primeiras são executadas uma vez, enquanto as etapas 3 e 4
são repetidas até que uma atribuição ideal seja encontrada. A entrada do algoritmo é uma matriz quadrada n por n com
apenas elementos não negativos.
ETAPA 1
Subtrair os mínimos da linha - Para cada linha, encontre o menor elemento e subtraia-o de cada elemento dessa linha.
ETAPA 2
Subtrair os mínimos da coluna - Da mesma forma, para cada coluna, encontre o menor elemento e subtraia-o de cada
elemento dessa coluna.
ETAPA 3
Cubra todos os zeros com um número mínimo de linhas - Cubra todos os zeros na matriz resultante usando um número
mínimo de linhas horizontais e verticais. Se n linhas forem necessárias, existe uma atribuição ótima entre os zeros, então
o algoritmo para. Se menos de n linhas forem necessárias, continue com a Etapa 4.
ETAPA 4
Crie zeros adicionais - Encontre o menor elemento (chame-o de k) que não é coberto por uma linha na Etapa 3. Subtraia k
de todos os elementos descobertos e adicione k a todos os elementos cobertos duas vezes.
Para entender a aplicação do método, vamos ver um exemplo. Considere que quatro caminhões (J1, J2, J3 e J4) precisam
ser conduzidos por quatro motoristas(W1, W2, W3 e W4), uma tarefa por motorista. A matriz abaixo mostra o custo de
designar um determinado motorista para um determinado caminhão. O objetivo é minimizar o custo total do serviço.
Etapa 1: Subtrair os mínimos da linha
Começamos subtraindo o mínimo da linha de cada linha. O menor elemento na primeira linha é, por exemplo, 69.
Portanto, subtraímos 69 de cada elemento na primeira linha. A matriz resultante será.
Etapa 2: Subtrair os mínimos da coluna
Da mesma forma, subtraímos o mínimo da coluna de cada coluna, gerando a seguinte matriz.
Etapa 3: Cubra todos os zeros com um número mínimo de linhas
Agora determinaremos o número mínimo de linhas (horizontais ou verticais) necessárias para cobrir todos os zeros na
matriz. Todos os zeros podem ser cobertos com 3 linhas/colunas.
Como o número de linhas necessárias (3) é menor do que o tamanho da matriz (n = 4), continuamos com a Etapa 4.
Etapa 4: Crie zeros adicionais
Primeiro, descobrimos que o menor número descoberto é 6. Subtraímos esse número de todos os elementos descobertos
e o adicionamos a todos os elementos cobertos duas vezes. Isso resulta na seguinte matriz.
Agora voltamos para a Etapa 3.
Etapa 3: Cubra todos os zeros com um número mínimo de linhas.
Novamente, determinamos o número mínimo de linhas necessárias para cobrir todos os zeros na matriz. Agora, são
necessárias 4 linhas:
Como o número de linhas necessárias (4) é igual ao tamanho da matriz (n = 4), existe uma atribuição ótima entre os zeros
na matriz. Portanto, o algoritmo para.
ATRIBUIÇÃO IDEAL
Os zeros a seguir cobrem uma atribuição ideal:
Isso corresponde à seguinte atribuição ótima na matriz de custo original:
Assim, o motorista 1 deve dirigir o caminhão 3, o motorista 2 o caminhão 2, o motorista 3 o caminhão 1, e o motorista 4 o
caminhão 4. O custo total dessa atribuição ideal é de:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
ATENÇÃO:
Quando a matriz não é quadrada (m x n) devemos inserir linhas ou colunas para transformá-la em uma matriz quadrada
(m x m ou n x n) com valores zero. Veja a matriz:
69  +  37  +  11  +  23  =  140
Temos então uma matriz 4x3, e transformamos em uma 4x4:
E agora aplicamos normalmente o método.
REDE DE DISTRIBUIÇÃO
Uma rede de distribuição pode ser vista como o fluxo de mercadorias de um produtor ou fornecedor para um consumidor
final. A rede é composta por depósitos, centros de distribuição e sistemas de transporte que suportam a movimentação
das mercadorias até chegarem ao consumidor final. O processo de garantir que o consumidor receba o produto do
fabricante é feito por meio de vendas diretas ou seguindo uma rede de varejo.
 SAIBA MAIS
Dependendo do tamanho de uma empresa ou negócio, as redes de distribuição variam em estrutura e tamanho. Empresas
como a Amazon ou a Apple provavelmente possuem redes de distribuição, transporte e sistemas de logística mais
sofisticados e complicados.
Ao definir a estrutura de uma rede de distribuição, os fatores mais cruciais são as demandas de produto do cliente final, a
experiência do cliente, a variedade e a disponibilidade do produto, o tempo de resposta e, finalmente, a possibilidade de
devolução do produto.
As redes de distribuição se transformam com o tempo, à medida que os negócios se expandem e visam atingir mais
consumidores. Portanto, eles precisam ser configurados de forma que permita a otimização a longo prazo. Para
determinar a rede de distribuição e a cadeia de suprimentos ideais e eficientes, a satisfação da demanda do cliente entra
em jogo.
A satisfação da demanda geral do cliente deve ser feita com custos baixos e níveis de serviço exigidos. Requer
planejamento estratégico, gerenciamento e planejamento especializados da cadeia de suprimentos.
Esse é um sistema clássico de otimização, pois precisamos entregar as mercadorias no menor custo para atender a
demanda requerida.
Vamos ver um exemplo para melhor entendimento.
EXEMPLO
A YDVQS Brasil terá duas fábricas, uma em Salvador e outra em Santo André, e está estudando a forma de distribuição
de seus carros para as diversas revendas de Minas Gerais, nas cidades de Juiz de Fora, Belo Horizonte, Barbacena e
Tiradentes.
A seguir, é apresentada a rede de revendas, seus custos de transporte unitários, as demandas das revendas e as
capacidades das fábricas. Determine como a entrega de veículos deve ser realizada pelas fabricas às revendas.
Para que tenhamos um fluxo balanceado, devemos considerar as seguintes hipóteses:
Caso de Oferta Total = Demanda Total
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Caso a Oferta Total > Demanda Total
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Caso a Oferta Total < Demanda Total
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Para solucionar esse problema da empresa, vamos utilizar o Solver e, para tanto, montamos a seguinte planilha:
[
total de entradas
no nó
] – [
total de saídas 
 no nó
]=[
Oferta/Demanda
do nó
]
[
total de entradas
no nó
] – [
total de saídas 
 no nó
]≥[
Oferta/Demanda
do nó
]
[
total de entradas
no nó
] – [
total de saídas 
 no nó
]≤[
Oferta/Demanda
do nó
]
 Print de tela do Microsoft Excel
Observe que montamos os nós de entrega (fábricas) e destinos (concessionárias) numerando-os e colocando a oferta
como um valor negativo e a demanda como um valor positivo, ou seja, saídas como negativas e entradas como positivas:
Quadro de oferta e demanda
Elaborado por Mauro Rezende Filho
Observe também que criamos todas as possíveis rotas (de – para) com o respectivo custo de frete:
 Quadro com os custos de frete
E finalmente as células das variáveis pintadas de amarelo claro (quantidades a serem entregue) e a função objetivo (custo
total de entrega). Vamos agora explicar algumas formulações para a solução ser encontrada:
CÉLULAS DE J5 A J10
Nas células de J5 a J10 (Fluxo Líquido) desejamos controlar o fluxo de movimentação de unidades e, para tanto,
utilizamos uma função do Excel (SOMASE), que permite que o fluxo se mantenha balanceado:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
CÉLULA K14
Na célula K14: =SOMA(K5:K10), verificamos as saídas menos as entradas para determinar a restrição de controle do
fluxo. Como o resultado está negativo, há mais oferta do que demanda, ou seja, oferta > demanda.
CÉLULA K15
Na célula K15: =SOMARPRODUTO(F5:F15;G5:G15), calculamos a função objetivo multiplicando a quantidade a ser
entregue pelo seu respectivo custo.
Podemos então montar o Solver:
 Print de tela do Microsoft Excel
Clicando em Resolver, obtemos:
Célula J5 ≔ SOMASE
⎛
⎜⎜
⎝
$D$5 : $D$15; H5; $G$5 : $G$15

nós  de
⎞
⎟⎟
⎠
− SOMASE
⎛
⎜⎜
⎝
$B$5 : $B$15; H5; $G$5 : $G$15

nós  de
⎞
⎟⎟
⎠
 
 Print de tela do Microsoft Excel
Obtivemos então o custo total de transporte, bem como a quantidade enviada por cada local.
Neste segundo módulo, falamos sobre os problemas de redes de distribuição. No módulo seguinte, falaremos sobre o
problema do menor caminho. Antes disso, fique atento para solucionar as questões a seguir, utilizando os conhecimentos
que adquiridos até aqui.
MÃO NA MASSA
TEORIA NA PRÁTICA
Alabama Atlantic é uma empresa madeireira que possui três fontes de madeira e cinco mercados a serem abastecidos. A
disponibilidade anual de madeira nas fontes 1, 2 e 3 é de 15, 20, e 15 milhões de metros de tábua preparada
respectivamente. A quantidade que pode ser vendida anualmente nos mercados 1, 2, 3, 4 e 5 é de 11, 12, 9, 10 e 8
milhões de metros de tábua preparada respectivamente.
No passado, a empresa despachava a madeira de trem. No entanto, como os custos de frete vêm aumentando, a
alternativa de utilizar navios para fazer parte das entregas está sendo analisada. Essa alternativa vai exigir que a empresa
invista em algunsnavios. Exceto por esses custos de investimento, os custos de envio em milhares de dólares por milhão
de metros de tábua preparada por ferrovia e por água (quando viável) seriam os seguintes para cada rota:
O investimento de capital (em milhares de dólares) em navios, para cada milhão de metros de tábua preparada por navio
ao longo de cada rota, é:
Considerando a expectativa de vida útil dos navios e o valor do dinheiro no tempo, o custo anual uniforme equivalente
desses investimentos é um décimo do valor indicado na tabela. O objetivo é determinar o plano geral de envio que
minimiza o custo anual uniforme equivalente total (incluindo custos de envio). Você é o chefe da equipe com a tarefa de
determinar esse plano de envio seguindo três opções.
Opção 1: Continue enviando exclusivamente por trem.
Opção 2: Mude para o transporte exclusivamente por água (exceto onde apenas o trem é viável).
Opção 3: Envie por via ferroviária ou fluvial, dependendo de qual será o custo para a rota específica.
Apresente seus resultados para cada opção. Compare.
RESOLUÇÃO
UMA ANÁLISE DE MODAIS DIFERENTES
VERIFICANDO O APRENDIZADO
MÓDULO 3
 Descrever o problema do menor caminho
O PROBLEMA DO MENOR CAMINHO
CONCEITOS
Um dos desenvolvimentos mais interessantes em pesquisa operacional (PO) nos últimos anos tem sido o avanço
extraordinariamente rápido tanto na metodologia quanto na aplicação de modelos de otimização para redes. Uma série de
inovações algorítmicas tiveram um grande impacto, bem como ideias da ciência da computação sobre estruturas de dados
e manipulação eficiente de dados.
Consequentemente, algoritmos e softwares agora estão disponíveis e sendo usados para resolver grandes problemas
rotineiramente, que seriam completamente intratáveis duas ou três décadas atrás.
EXEMPLO
Um parque florestal foi recentemente reservado para uma quantidade limitada de passeios e caminhadas com mochila.
Carros não são permitidos no parque, mas há uma estrada estreita e sinuosa e um sistema para bondes e jipes dirigidos
pelos guardas-florestais.
Esse sistema viário é mostrado (sem as curvas) na figura a seguir, em que o local O é a entrada do parque, e as outras
letras designam a localização dos postos dos guardas florestais (e outras instalações limitadas). Os números indicam as
distâncias dessas estradas sinuosas em quilômetros.
O parque contém um centro de entretenimento na estação T. Um pequeno número de bondes é usado para transportar os
turistas da entrada do parque para a estação T e vice-versa. A gestão do parque enfrenta atualmente três problemas. Um
é determinar qual rota da entrada do parque até a estação T tem a menor distância total para a operação dos bondes.
A questão a resolver será como mapear as várias viagens para maximizar o número de viagens que podem ser feitas por
dia sem violar os limites de qualquer caminho de pedestres.
PROBLEMA DE CAMINHO MAIS CURTO
Embora várias outras versões do problema do caminho mais curto (incluindo algumas para redes) tenham sido
desenvolvidas, vamos nos concentrar na seguinte versão, mais simples.
CONSIDERE UMA REDE NÃO DIRECIONADA E CONECTADA
COM DOIS NÓS ESPECIAIS CHAMADOS ORIGEM E DESTINO.
ASSOCIADA A CADA UM DOS LINKS (ARCOS NÃO
DIRECIONADOS) ESTÁ UMA DISTÂNCIA NÃO NEGATIVA. O
OBJETIVO É ENCONTRAR O CAMINHO MAIS CURTO (O
CAMINHO COM O MÍNIMO DE DISTÂNCIA TOTAL) DA ORIGEM
AO DESTINO.
Um algoritmo relativamente simples será utilizado para resolver esse problema. A essência deste procedimento se
desdobra desde a origem, identificando sucessivamente o caminho mais curto a cada um dos nós da rede na ordem
crescente de suas distâncias (mais curtas) da origem, resolvendo assim o problema quando o nó de destino é alcançado.
ALGORITMO PARA O PROBLEMA DO CAMINHO MAIS CURTO
Objetivo da
enésima iteração:
Encontrar o enésimo nó mais próximo da origem (a ser repetido por n 1, 2, . . .) até que o
enésimo nó mais próximo seja o destino.
Entrada para a
enésima iteração:
n - 1 nós mais próximos da origem (resolvido nas iterações anteriores), incluindo seu
caminho mais curto e distância da origem (esses nós, mais a origem, serão chamados de
nós resolvidos, e os outros são nós não resolvidos).
Candidatos ao
enésimo nó mais
próximo:
Cada nó resolvido diretamente conectado por um link a um ou mais nós não resolvidos
fornece um candidato — o nó não resolvido com o link de conexão mais curto (os laços
fornecem candidatos adicionais).
Cálculo do
enésimo nó mais
próximo:
Para cada nó resolvido e seu candidato, adicione a distância entre eles e a distância do
caminho mais curto, da origem até esse nó resolvido. O candidato com a menor distância
total é o nó enésimo mais próximo (laços fornecem nós resolvidos adicionais), e o caminho
mais curto é o que gera essa distância.
APLICANDO O ALGORITMO
A administração do Parque Florestal precisa encontrar o caminho mais curto a partir da entrada do parque (nó O) para o
centro de entretenimento (nó T) por meio do sistema viário mostrado na figura. A aplicação do algoritmo acima produz os
resultados mostrados na tabela a seguir, em que o empate para o segundo nó mais próximo permite pular diretamente
para buscar o quarto mais próximo nó seguinte.
Tabela aplicando o algoritmo.
Elaborada por: Mauro Rezende Filho
01
A primeira coluna (n) indica a contagem de iterações.
02
A segunda simplesmente lista os nós resolvidos para iniciar a iteração atual após deletar os nós irrelevantes (aqueles não
conectados diretamente a nenhum nó não resolvido).
03
A terceira dá, então, os nós candidatos para o enésimo nó mais próximo (os nós não resolvidos com o link de conexão
mais curto para um nó resolvido).
04
A quarta coluna calcula a distância do caminho mais curto da origem para cada um desses nós candidatos (ou seja, a
distância para o nó resolvido mais o link de distância ao nó candidato).
05
O nó candidato com a menor distância é o enésimo nó mais próximo da origem, conforme listado na quinta coluna.
06 E 07
As duas últimas colunas resumem as informações para esse nó resolvido mais recente, necessário para prosseguir para
as iterações subsequentes (ou seja, a distância do caminho mais curto da origem até esse nó e o último link para esse
caminho mais curto).
Após a conclusão do trabalho apresentado na tabela, o caminho mais curto do destino até a origem pode ser rastreado de
volta por meio da última coluna da tabela como qualquer T→D→E→B→A→O ou T→D→B→A→O.
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
PORTANTO, AS DUAS ALTERNATIVAS PARA O CAMINHO MAIS
CURTO DA ORIGEM AO DESTINO FORAM IDENTIFICADAS
COMO O→A→B→E→D→T E O→A→B→D→T, COM UMA
DISTÂNCIA TOTAL DE 13 QUILÔMETROS EM CADA CAMINHO.
MÉTODO DA FORÇA BRUTA
Esse método também é bem simples e consiste em listar todos os possíveis caminhos e escolher o mais curto. Note que,
para redes pequenas, será de fácil aplicação; entretanto, para grandes redes, será um tanto trabalhoso. A tabela a seguir
mostra a aplicação do método:
Tabela de aplicação do método da força bruta
Elaborada por: Mauro Rezende Filho
USANDO O SOLVER PARA FORMULAR E RESOLVER
PROBLEMAS DE CAMINHO MAIS CURTO
Esses algoritmos fornecem uma maneira particularmente eficiente de resolver grandes problemas de caminho mais curto.
No entanto, alguns pacotes de software de programação matemática não incluem esses algoritmos. Do contrário, eles
geralmente incluirão o método simplex de rede, que é outra boa opção para esses problemas.
Uma vez que o problema do caminho mais curto é um tipo especial de problema de programação linear, o método simplex
geral também pode ser usado quando opções melhores não estão disponíveis. Embora não seja tão eficiente quanto
esses algoritmos especializados em grandes problemas de caminhos mais curtos, é bastante adequado para problemas
de redes pequenos.
 SAIBA MAIS
O Solver, que se baseia no método simplex geral, fornece uma maneira conveniente de formulare resolver problemas de
caminho mais curto com dezenas de arcos e nós.
Uma rota da origem ao destino é interpretada como um “fluxo” de 1 no caminho escolhido pela rede. As decisões a serem
tomadas são quais arcos devem ser incluídos no caminho a ser percorrido. Um fluxo de 1 é atribuído a um arco se estiver
incluído, enquanto o fluxo é 0 se não estiver incluído. Assim, as variáveis de decisão são:
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Vejamos como formular o problema do Parque Florestal na planilha a seguir:
xij={
0 se o arco i→j não for incluído
1 se o arco i→j for incluído        
 Print de tela do Microsoft Excel
AS FÓRMULAS SÃO:
Célula G4: =SOMASE($C$4:$C$18;F4;$E$4:$E$18)-SOMASE($B$4:$B$18;F4;$E$4:$E$18): e arrastar até a G10.
Célula H13: =SOMARPRODUTO(D4:D18;E4:E18).
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
Montando o Solver:
 Print de tela do Microsoft Excel
E a solução:
 Print de tela do Microsoft Excel
Neste terceiro módulo do tema, falamos sobre o problema do menor caminho. No próximo módulo, falaremos sobre o
problema do fluxo máximo. Antes disso, fique atento e realize os exercícios a seguir utilizando os conhecimentos que você
adquiriu até aqui.
MÃO NA MASSA
TEORIA NA PRÁTICA
Uma petrolífera deseja fazer uma rota para a entrega de produtos (alimentos, medicamentos, peças de reposição etc.)
para suas plataformas de petróleo. Pelo GPS, é conhecida a localização cartesiana de cada uma. O objetivo é fazer as
entregas percorrendo a menor distância total aproximada. A tabela a seguir apresenta as coordenadas cartesianas de
cada plataforma. Qual será a distância mínima estimada?
RESOLUÇÃO
UMA APLICAÇÃO DE DISTRIBUIÇÃO DE PRODUTOS
VERIFICANDO O APRENDIZADO
MÓDULO 4
 Descrever o problema do fluxo máximo
O PROBLEMA DO FLUXO MÁXIMO
INTRODUÇÃO
A seguir, veja algumas aplicações típicas do problema de fluxo máximo:
Maximizar o fluxo por meio da rede de distribuição de uma empresa, de suas fábricas para seus clientes.
Maximizar o fluxo por meio da rede de suprimentos de uma empresa, para seus fornecedores.
Maximizar o fluxo de óleo por meio de um sistema de oleodutos.
Maximizar o fluxo de água por meio de um sistema de aquedutos.
Maximizar o fluxo de veículos em uma rede de transporte.
 EXEMPLO
Para algumas dessas aplicações, o fluxo por meio da rede pode se originar em mais de um nó e terminar em mais de um
nó, mesmo porque no problema de fluxo máximo é permitido ter apenas uma única fonte e um único recebedor. Por
exemplo, a rede de distribuição da empresa geralmente tem várias fábricas e clientes.
Uma reformulação inteligente é usada para fazer com que tal situação se ajuste ao problema de fluxo máximo. Essa
reformulação envolve a expansão da rede original para incluir uma fonte fictícia, uma rota falsa e alguns novos arcos. A
fonte fictícia é tratada como o nó que origina todo o fluxo que, na realidade, se origina de algum dos outros nós.
PARA CADA UM DESSES OUTROS NÓS, UM NOVO ARCO É
INSERIDO, LEVANDO DA FONTE FICTÍCIA A ESSE NÓ. A
CAPACIDADE DESSE ARCO É IGUAL AO FLUXO MÁXIMO QUE,
NA REALIDADE, PODE SE ORIGINAR NESSE NÓ. DA MESMA
FORMA, O RECEPTOR FICTÍCIO É TRATADO COMO O NÓ QUE
ABSORVE TODO O FLUXO QUE, NA REALIDADE, TERMINA EM
ALGUNS DOS OUTROS NÓS.
Portanto, um novo arco é inserido a partir de cada um desses outros nós para o coletor fictício, no qual a capacidade
desse arco é igual a fluxo máximo que, na realidade, pode terminar nesse nó. Por causa de todas essas mudanças, todos
os nós na rede original agora são nós de transbordo; então, a rede expandida tem a única fonte necessária (a fonte
fictícia) e um único receptor(fictício) para ajustar o problema de fluxo máximo.
MÉTODO FORD-FULKERSON
O método Ford-Fulkerson, também conhecido como algoritmo de caminho aumentado, é uma abordagem eficaz para
resolver o problema de fluxo máximo. O método Ford-Fulkerson depende de dois conceitos principais:
Rede residual.

Caminhos de aumento.
Agora, vamos entendê-los.
REDE RESIDUAL
É um grafo que possui os mesmos vértices da rede original com uma ou duas arestas para cada aresta da rede original,
indicando o fluxo adicional possível pela rede. Para cada aresta, calcularemos o fluxo adicional da seguinte maneira.
FLUXO ADICIONAL = CAPACIDADE DA BORDA - O FLUXO DA
BORDA
Então, para criar uma rede residual, vamos pegar nossa rede original e atualizar a capacidade de cada aresta com o fluxo
adicional correspondente a ela. Em seguida, também adicionaremos bordas reversas para indicar a quantidade de fluxo
atualmente passando pelas bordas da rede original.
Para deixar isso mais claro, vejamos o exemplo a seguir.
Para cada seta, o primeiro valor representa o valor do fluxo; o segundo, a capacidade da rota.
EXEMPLO
Vamos considerar a aresta C-D. Aqui, o fluxo é 11 e a capacidade da rota é 14. Portanto, se calcularmos o fluxo adicional
para essa borda, obtemos 14 - 11 = 3. Na rede residual, podemos atualizar a capacidade da rota C-D como 3 e, em
seguida, adicionar uma borda reversa com valor 11 (valor de fluxo da rede original) entre C e D.
Da mesma forma, podemos repetir isso para todas as arestas, obtendo como rede residual:
CAMINHO DE AUMENTO
Dada uma rede de fluxo G = (V, E), o caminho crescente é um caminho simples de s para t no gráfico residual
correspondente da rede de fluxo.
Vamos utilizar esse método usando o exemplo a seguir.
Etapa 1: Defina o fluxo de cada borda para 0.
Etapa 2: Encontre um caminho de aumento na rede residual selecionando o caminho s-A-D-t. Em seguida, identifique a
capacidade de gargalo (fluxo máximo) para o caminho selecionado. Observe que, ao longo desse caminho, a capacidade
de gargalo é 8. Agora, sem violar a restrição de capacidade, atualize os valores de fluxo das bordas no caminho de
aumento. Obteremos a seguinte rede de fluxo e a rede residual:
Etapa 3: Selecione o caminho de aumento s-C-D-t. Agora, a capacidade de gargalo é 2.
Etapa 4: Selecione o caminho de aumento s-A-B-t. Agora, e capacidade de gargalo é 2.
Etapa 5: Selecione o caminho de aumento s-C-D-B-t. Agora, e capacidade de gargalo é 6.
Etapa 6: Selecione o caminho de aumento s-C-D-A-B-t. Agora, e capacidade de gargalo é 1.
Observe! Agora não há mais caminhos deixados de s para t no gráfico residual. Portanto, não há possibilidade de
adicionar fluxo. Isso significa que o método Ford-Fulkerson está completo e estamos prontos para encontrar o fluxo
máximo.
UMA VEZ QUE O FLUXO MÁXIMO É IGUAL AO FLUXO QUE SAI
DA FONTE, NESSE EXEMPLO, O FLUXO MÁXIMO É 10 + 9 = 19.
Aprendemos o método Ford-Fulkerson para encontrar fluxos máximos. Existem várias aplicações de problemas de fluxo
máximo, como gráficos bipartidos, eliminação de beisebol, programação de voos etc. Esse é um algoritmo muito
importante que aumentará suas habilidades de codificação.
USANDO O EXCEL PARA FORMULAR E RESOLVER
PROBLEMAS DE FLUXO MÁXIMO
A maioria dos problemas de fluxo máximo que surge na prática é consideravelmente maior e, ocasionalmente, muito maior
do que o problema apresentado. Alguns problemas têm milhares de nós e arcos. O algoritmo de caminho aumentado que
acabamos de apresentar é muito mais eficiente do que o método simplex geral para resolver problemas tão grandes.
No entanto, para problemas de tamanho modesto, uma alternativa razoável e conveniente é usar o Excel e seu Solver
baseado no método simplex geral.
Vamos então resolver um problema pelo Solver:
Considere as localidades abaixo conectadas por oleodutos. Cada oleoduto tem uma capacidade de transmissão (m³/s)
indicada. O objetivo é enviar a maior quantidade possível de óleo, desde A até B. A oferta de A e a demanda de B são
ilimitadas.
COMO RESOLVER O PROBLEMA?
Adicionar um arco artificial ligando o ponto de saída (A) ao ponto de chegada (B).
Utilizar a regra de balanceamento de redes.
O Valor de Oferta/Demanda em cada nó é igual a zero.
A função objetivo muda:
Maximizaro fluxo no arco artificial criado (fluxo grande).
Restrições adicionais:
As grandezas associadas aos arcos são o fluxo máximo em cada trecho da rede, portanto, restrições no modelo.
Veja a montagem da planilha:
 Print de tela do Microsoft Excel
AS FÓRMULAS SERÃO:
Célula G4: =SOMASE($C$4:$C$11;F4;$E$4:$E$11)-SOMASE($B$4:$B$11;F4;$E$4:$E$11): e copiar até G9.
Célula H12: =E11.
Células E4:E11: variáveis de decisão.
 Atenção! Para visualização completa da equação utilize a rolagem horizontal
O Solver deve ser montado da seguinte forma:
 Print de tela do Microsoft Excel
Obtemos a solução:
 Print de tela do Microsoft Excel
Neste tema, falamos sobre alguns problemas logísticos como os problemas de transporte, de redes de distribuição, do
menor caminho e o problema do fluxo máximo. Coloque em prática os conhecimentos adquiridos nas atividades a seguir.
MÃO NA MASSA
TEORIA NA PRÁTICA
Uma distribuidora de energia elétrica com duas centrais geradoras (E1 e E2) precisa estudar a melhor rota para abastecer
um novo consumidor com duas fábricas (W1 e W2). É necessário, então, determinar o fluxo máximo de energia que
poderá transmitir para elaborar o contrato de fornecimento. O fluxo a seguir apresenta as possíveis conexões entre o que
é distribuído e o consumidor, bem como a capacidade de transferência por rota.
Qual valor deverá constar em contrato?
RESOLUÇÃO
UM PROBLEMA DE DISTRIBUIÇÃO DE ENERGIA
ELÉTRICA
VERIFICANDO O APRENDIZADO
CONCLUSÃO
CONSIDERAÇÕES FINAIS
Vimos uma série de métodos para a otimização em sistemas logísticos, todos buscando a solução ótima para o problema
apresentado. Um mal planejamento logístico pode impactar negativamente nas margens de contribuição de uma empresa.
Portanto, criar estratégias de otimização de custos no processo logístico deve ser uma das prioridades de qualquer
empresa de transporte.
No primeiro módulo, aprendemos sobre problemas de transporte, variáveis de decisão, formulação de programação linear,
como montar um tableau de transporte, utilizar a regra do canto noroeste, o método do menor custo e o Solver. No
segundo, aprendemos a utilizar o método Kuhn para chegar à distribuição ideal em redes de distribuição.
No Módulo 3, vimos o problema do menor caminho aplicando o algoritmo e o método da força bruta. No último módulo,
vimos como resolver problemas de fluxo máximo utilizando o método Ford-Fulkerson.
 PODCAST
Agora, o especialista Mauro Rezende Filho encerra o tema falando sobre os principais tópicos abordados.
AVALIAÇÃO DO TEMA:
REFERÊNCIAS
BALLOU, R. H. Business logistics management. 3. ed. Londres: Prentice Hall, 1992.
BARNHART, G.; LAPORTE, G. (eds.). Handbook in operation research and management science: transportation.
Amsterdam: Elsevier, 2007, vol. 14, 783 p.
GHIANI, G.; LAPORTE, G.; MUSMANNO, R. (eds.). Introduction to logistics systems planning and control. Nova York:
John Wiley & Sons, 2004.
RUSHTON, A.; CROUCHE, P. H.; BAKER, P. The handbook of logistics and distribution management. 3. ed.
Londres/Filadélfia: Kogan Page Limited, 2006.
WATER, D. Inventory control and management. 2. ed. Chichester: John Wiley & Sons, 2003.
EXPLORE+
Para que você possa se aprofundar mais no assunto estudado, recomendamos navegar nos sites:
Portal de Periódicos da Capes.
Biblioteca Digital de Domínio Público.
CONTEUDISTA
Mauro Rezende Filho
 CURRÍCULO LATTES
javascript:void(0);