AULA 4 - Otimização em Sistemas de Distribuição (34pág)

Prévia do material em texto

OTIMIZAÇÃO EM SISTEMAS 
DE DISTRIBUIÇÃO 
 
 
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. 
 
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 i é ai, em que 
 i = 1, 2, . . . , m. 
 
A demanda total do produto no ponto de venda j é bj, em que 
j = 1, 2, . . . , n. 
 
 
O custo de envio de uma unidade do produto do armazém i para a saída j é 
igual a cij, em que i = 1, 2, . . . , m e j = 1, 2, . . . , n. 
 
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. 
 
 
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: 
 
Xij = o tamanho da remessa do armazém i parao 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 é cij, 
e o tamanho da remessa é xij. Uma vez que assumimos que a função de custo é linear, o custo total dessa remessa é 
obtido por cijxij. 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 É: 
 
 
 
RESTRIÇÕES 
Considere o armazém i. A expedição total desse depósito é a soma xi1 + xi2 + ⋅ ⋅ ⋅ + xin. Em notação de soma, 
n isso é escrito como ∑ xij . Uma vez que o fornecimento total do armazém i é ai, a remessa total de saída não pode 
exceder ai, ou seja, devemos impor 
 
 
 
Considere agora o destino j. A remessa total que chega neste ponto de venda é a soma x1j + x2j + ⋅ ⋅ ⋅ + xmj. 
Na notação de soma, como vimos acima, isso é escrito como ∑xij. Uma vez que a demanda do destino j é bj, o total 
de entrada à remessa não deve ser inferior a bj. Ou seja, devemos impor 
 
 
 
Isso resulta em um conjunto de restrições funcionais m + n. Claro, como remessas físicas, os se xij′s devem ser não 
negativos. 
 
FORMULAÇÃO PL (PROGRAMAÇÃO LINEAR) 
Em resumo, chegamos à seguinte formulação: 
 
 
 
Sujeito a: 
 
 
 
UM EXEMPLO NUMÉRICO 
Em uma instância real do problema de transporte, precisamos especificar m e n, e substituir o ai′s, bj
′s, e cij′s com 
valores numéricos explícitos. Como um exemplo simples, suponha que recebamos: 
 
 
 
Então, a substituição desses valores na formulação acima leva ao seguinte problema explícito: 
 
 
 
 Sujeito a: 
 
 
 
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 
 
 
 
É 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: 
 
 
 
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 cij é listado em uma subcélula localizada no canto superior esquerdo da célula (i, j), e, finalmente, o 
valor de xij é inserido no canto inferior direito da célula (i, j). 
 
OBSERVAÇÕES 
 
01. 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 ai especificado e o bj 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. 
 
02. 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. 
 
03. 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 x11. Esta imediatamente 
implica que x11 servirá como uma variável básica. Além disso, uma vez que o restante da oferta da origem 1 se esgota 
como resultado desta tarefa, o conceito-chave neste ponto é também pensar nessa ação como designando x11 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 x21, obtendo o novo quadro a 
seguir: 
 
 
 
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 x22 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á: 
 
Portanto, o valor da função objetivo dessa solução é facilmente calculado como: 
 
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 cij 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 (c21), começamos alocando 50 unidades: 
 
 
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 (c12): 
 
Para fechar, atendemos ao destino c32: 
 
 
 
Portanto, o valor da função objetivo dessa solução é facilmente calculado como: 
 
 
 
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; 
 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: uma empresa 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: 
 
 
 
Sujeito a: 
 
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 x11, e vamos alocar 4.000 unidades, o que atenderá 
plenamente o cliente 1. Temos então: 
 
 
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á: 
 
 
 
MÉTODO DO MENOR CUSTO 
A variável básica será x11 porque apresenta o menor custo: 
A próxima será a x22: 
E finalizando: 
Portanto, temos o valor da função objetivo: 
 
 
 
 
 
SOLVER 
Montando a planilha básica: 
 
 Print do Microsoft Excel 
 
Vamos replicar as células na planilha: 
 
 paracontrolar 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)). 
 
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. 
 
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? 
 
 
 
 
 
 
 
 
 
 
 
VERIFICANDO O APRENDIZADO 
 
1. A Companhia Brasileira de Café, presente em três plantações bem localizadas, tritura os grãos de café até se tornarem 
pó. Semanalmente, o café em pó é embarcado com destino a quatro armazéns em diferentes cidades, para torrefação, 
distribuição e exportação. O custo de transporte, em unidades monetárias (u.m.), de uma tonelada de café da plantação i 
para o armazém j é dado pela seguinte tabela. 
 
 
 
 
As capacidades semanais das plantações 1, 2 e 3 são 40, 60 e 80 toneladas respectivamente, enquanto as necessidades 
dos armazéns 1, 2, 3 e 4 são, respectivamente, 50, 40, 30 e 60 toneladas. O objetivo da companhia consiste em 
determinar as quantidades de café que devem ser transportadas de cada uma das plantações para cada um dos armazéns 
minimizando o custo total de transporte. A parte da função objetivo sobre o Armazém 1 será igual a 
 
a) 9x11 + 8x12 + 3x13 + 4x14 
b) 9x11 + 7x21 + 3x13 + 4x31 
c) 7x11 + 6x12 + 2x13 + x14 
d) 8x11 + 7x21 + 5x13 
e) 5x11 + 4x21 + 7x13 + 9x31 
 
2. A Indústria MRF fabrica um único produto em quatro localidades: Curitiba, Campinas, Itabuna e Campos. O custo 
unitário de produção de cada localidade é respectivamente $35,50, $37,50, $39,00 e $36,25, e a capacidade anual de 
produção de cada planta é de 18.000, 15.000, 25.000 e 20.000 unidades. A empresa está planejando estabelecer sete 
centros de distribuição para atender a sua demanda. O custo unitário de transporte entre cada um dos locais apresenta-se 
na tabela a seguir, bem como a demanda de cada região: 
 
 
 
A empresa deseja determinar como atender a demanda de cada local com o menor custo de fabricação e de transporte, 
mas, como a demanda geral excede a capacidade de fabricação, deseja ter certeza de que pelo menos 80% das ordens 
recebidas por cada centro de distribuição sejam atendidas. Se utilizarmos o método do menor custo, a variável básica 
inicial será 
 
a) X11 
b) X16 
c) X42 
d) X22 
e) X34 
 
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 seguintematriz. 
 
 
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: 
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: 
 
 
 
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 
 
 
 
Caso a Oferta Total > Demanda Total 
 
 
 
Caso a Oferta Total < Demanda Total 
 
 
 
Para solucionar esse problema da empresa, vamo utilizar o Solver e, para tanto, montamos a seguinte planilha: 
 
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: 
 
 
 
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: 
 
 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. 
 
VERIFICANDO O APRENDIZADO 
 
1. O Miguel, a Ana e o Ricardo têm que fazer o trabalho prático da cadeira de Novas Tecnologias de Informação (NTI), do 
curso de Engenharia de Produção. O problema consiste em visitar três cidades do estado, de modo que a distância 
percorrida seja a menor possível, uma vez que cada um somente poderá ir a uma cidade. 
 
 
 
A distância percorrida será: 
 
a) 18 
b) 15 
c) 16 
d) 17 
e) 19 
 
2. Uma rede de farmácias possui depósitos nos bairros A, B e C. Os remédios comercializados devem ser distribuídos por 
filiais localizadas nos bairros D, E, F, G e H. As demandas de cada filial e a capacidade de fornecimento dos depósitos, em 
quilogramas, bem como os custos de transporte entre cada depósito e cada filial, também em quilogramas, constam da 
tabela a seguir: 
 
 
 
O modelo matemático que soluciona esse problema tem: 
 
a) Três inequações de “≥” e três de “=”. 
b) Três inequações de “≤” e três de “=”. 
c) Duas inequações de “≥”, uma de “≥” e três de “=”. 
d) Duas inequações de “≤”, uma de “≤” e três de “=”. 
e) Três inequações de “≥” e três de “≤”. 
 
 
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 estreitae 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 . 
 
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 formular e 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: 
 
 
 
Vejamos como formular o problemas do Parque Florestal na planilha a seguir: 
 
 
 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: =SOMAR PRODUTO(D4:D18;E4:E18). 
 
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. 
 
VERIFICANDO O APRENDIZADO 
 
1. (CESGRANRIO – 2012). A tabela a seguir apresenta o resultado da obtenção do caminho mínimo para o deslocamento 
entre diversas cidades. 
 
 
 
A partir dos dados da tabela, conclui-se que 
 
a) A menor distância entre as cidades A e F é de 15km. 
b) O menor caminho entre as cidades A e D é de 2km. 
c) Um viajante deverá passar obrigatoriamente na cidade C para percorrer o menor caminho entre as cidades 
A e F. 
d) Um viajante deverá se deslocar na sequência A – B – E – F para percorrer o menor caminho entre as cidades 
A e F. 
e) Um viajante terá que se deslocar por 5km para percorrer o menor caminho entre a cidade B e a cidade E. 
 
 
2. Dada a tabela a seguir, cujos valores representam os custos de deslocamento de “De” para “Para”, e que podemos 
designar apenas uma vez, a primeira iteração nos dará o seguinte valorde A-1: 
 
 
a) 37,7 
b) 4,1 
c) 10,3 
d) 1,9 
e) 10,4 
 
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: 
 Maximizar o 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. 
 
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. 
 
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 APRENDIZADO1. Observe o fluxo a seguir. 
 
 
O fluxo máximo entre S e T será pela rota 
 
a) S-A-B-C-T 
b) S-A-C-T 
c) S-B-A-C-T 
d) S-B-C-T 
e) S-A-C-B 
 
2. Observe o fluxo a seguir. 
 
 
 
a) s-a-c-t 
b) s-a-b-t 
c) s-b-c-t 
d) s-b-t 
e) s-a-b-c-t 
 
 
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.