aula05

Prévia do material em texto

5ºAula
Redes
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de:
•  aprender sobre os problemas de rede e sua forma de resolução;
•  entender e resolver os problemas de caminho mínimo;
•  compreender e resolver os problemas de fluxo máximo;
•  entender como modelar os problemas de rede e resolver no Excel Solver.
Prezados(as) alunos(as),
Nesta quinta aula, focaremos em um ramo bem específico 
da Pesquisa Operacional, que são as redes. Esta aula se assemelha 
a aula 4 referente ao problema do transporte e suas variantes, 
com a diferença de que aqui temos a adição de múltiplas fontes 
consumidoras, fornecedoras e de intermediários. Será dado o 
foco na modelagem e resolução via Excel Solver. 
Bons estudos!
42Pesquisa Operacional
Seções de estudo
1 – O problema de redes
2 – Caminho mínimo
3 – Problema do fl uxo máximo
1 - O problema de redes
De acordo com Lachtermacher (2016), problemas que 
consideram múltiplas fontes, centros consumidores e locais 
intermediários por onde os produtos simplesmente passam 
são denominados problemas de rede de distribuição. Os 
problemas de transporte podem ser considerados uma 
simplifi cação do problema de rede de distribuição de custo 
mínimo, em que as localizações intermediárias não existem. O 
exemplo a seguir, baseado em Lachtermacher (2016), ilustra 
um típico caso de problema de rede de distribuição.
1.1 – Exemplo de problema de 
redes
Caso LCL Carros Brasil Ltda. A montadora de veículos 
LCL Carros Brasil Ltda. está iniciando suas operações no 
país com duas fábricas: uma na Bahia e outra em São Paulo. 
A LCL está estudando uma forma de distribuição de seus 
carros para as diversas revendas, localizadas nos estados de 
Goiás, Rio de Janeiro, Minas Gerais, Paraná, Santa Catarina 
e Rio Grande do Sul, de modo a minimizar o custo total de 
distribuição (Figura 1). As capacidades instaladas de cada 
uma das fábricas, as demandas das revendas, bem como os 
custos unitários de transporte entre fábricas e revendas são 
mostrados no diagrama da Figura 2.
Figura 1 - Localização das fábricas e distribuidores da 
LCL Carros Brasil.
Fonte: Lachtermacher (2016). 
Figura 2 - Diagrama da rede do caso LCL Carros Brasil.
Fonte: Lachtermacher (2016).
Em uma primeira e rápida análise, concluímos facilmente 
que as variáveis de decisão do modelo serão as quantidades 
de veículos enviadas de cada fábrica a cada distribuidor, 
e a função-objetivo será a minimização do custo total de 
transporte. No entanto, o problema apresenta dois detalhes 
especiais: o número de carros demandados é maior do que a 
capacidade de produção da empresa e alguns distribuidores 
(de Minas Gerais e de Santa Catarina) também podem enviar 
carros que receberam das fábricas para outros distribuidores, 
possivelmente suas fi liais (LACHTERMACHER, 2016).
Existem duas maneiras básicas de resolver esse tipo 
de problema. A primeira consiste em inserir uma unidade 
dummy que iguale a oferta e a demanda totais. Se a oferta for 
maior que a demanda, a variável dummy será colocada como 
uma unidade de demanda ligada às unidades de oferta. De 
forma inversa, se a demanda for maior que a oferta, a variável 
dummy representará um novo ponto de oferta para atender à 
demanda excedente. Em ambos os casos, todas as restrições 
serão consideradas igualdades. 
A segunda forma de resolver problemas de distribuição 
é seguir a regra do fl uxo balanceado para cada nó (unidade) 
da rede. Por essa regra, não há necessidade da inserção de 
variáveis do tipo dummy; o desequilíbrio entre a oferta total 
e a demanda total é tratado por meio de restrições de maior 
ou igual ou de menor ou igual. A Tabela 1 resume a forma de 
aplicação da regra do fl uxo balanceado.
Tabela 1 - Regra do fl uxo balanceado
Hipótese do problema Tipo de restrição para cada nó
Oferta > Demanda Entradas − Saídas ≥ Oferta ou demanda
Oferta < Demanda Entradas − Saídas ≤ Oferta ou demanda
Oferta = Demanda Entradas − Saídas = Oferta ou demanda
Fonte: Elaborado pelo autor. 
Resolveremos o caso da LCL Carros Brasil pelos dois 
métodos. A Figura 2 mostra a diferença entre a capacidade de 
produção da empresa (oferta) e o número de carros requeridos 
pelos estados (demanda). Nesse caso, há uma oferta de 1.100 
veículos e uma demanda de 1.400. Assim, o primeiro passo 
para resolver esse problema pela primeira alternativa é inserir 
uma unidade de oferta dummy com disponibilidade de 300 
veículos e conectada a todos os nós de demanda com custo 
zero de transporte (Figura 3).
Figura 3 - Diagrama de rede do caso LCL Carros Brasil 
— 1ª alternativa.
Fonte: Lachtermacher (2016).
43
De acordo com esse primeiro método de modelagem, 
o problema que será inserido na planilha Excel tem os 
parâmetros a seguir. Variáveis de decisão 
•	x13 — número de carros enviados da BA para MG. 
•	x14 — número de carros enviados da BA para o RJ. 
•	x15 — número de carros enviados da BA para GO. 
•	x23 — número de carros enviados de SP para MG. 
•	x24 — número de carros enviados de SP para o RJ. 
•	x26 — número de carros enviados de SP para o PR. 
•	x27 — número de carros enviados de SP para SC. 
•	x28 — número de carros enviados de SP para o RS. 
•	x34 — número de carros enviados de MG para o RJ. 
•	x35 — número de carros enviados de MG para GO. 
•	x78 — número de carros enviados de SC para o RS. 
•	x93 — número de carros que MG deixará de receber. 
•	x94 — número de carros que o RJ deixará de receber. 
•	x95 — número de carros que GO deixará de receber. 
•	x96 — número de carros que o PR deixará de receber. 
•	x97 — número de carros que SC deixará de receber. 
•	x98 — número de carros que o RS deixará de receber.
 
Função-objetivo Min 25x13 + 30x14 + 40x15 + 20x23 + 
15x24 + 20x26 + 35x27 + 50x28 + 20x34 + 20x35 + 20x78
Montaremos as restrições conforme a seguinte lógica: o 
número de carros que chegam ao nó menos o montante que 
sai deve ser igual à oferta (negativa) ou à demanda (positiva) 
do nó. 
Restrições de fluxo 
– x13 – x14 – x15 = – 500 nó 1 
– x23 – x24 – x26 – x27 – x28 = – 600 nó 2 
x13 + x23 + x93 – x34 – x35 = + 200 nó 3 
x14 + x24 + x34 + x94 = + 350 nó 4 
x15 + x35 + x95 = + 150 nó 5 
x26 + x96 = + 300 nó 6 
x27 + x97 – x78 = + 150 nó 7 
x28 + x78 + x98 = + 250 nó 8 
2x93 – x94 – x95 – x96 – x97 – x98 = –300 nó 9 
A Figura 4 mostra uma das maneiras de o problema ser 
modelado no Excel. Para inserir a condição de que o fluxo 
líquido de cada nó (quantidade que chega menos quantidade 
que sai) deve ser igual à respectiva demanda (positiva) ou 
oferta (negativa), utilizaremos a função SomaSe do Excel (ou 
SumIf, em inglês). Essa função serve para somar as células 
especificadas por determinado critério, que pode ser um 
número, uma expressão (> 100, por exemplo) ou um texto. 
No nosso problema, a função SomaSe nos ajudará a calcular 
o fluxo líquido de cada nó com base em seus critérios de 
identificação.
Na Figura 4, a célula I16 representa a função-objetivo, 
e as células E4 a E20, as variáveis de decisão do modelo. 
As células H4 a H12 representam os LHS das restrições de 
fluxo, e as células I4 a I12, os RHS (lado direito da equação de 
restrição) das células. A Tabela 2 mostra as fórmulas utilizadas 
nas células que representam cada LHS (lado esquerdo da 
equação) das restrições e na célula que denota a função-
objetivo. 
Figura 4 - Modelagem da rede do caso LCL Carros Brasil 
— 1o método.
Fonte: Lachtermacher (2016).
Tabela 2 - Fórmulas utilizadas nas restrições do problema 
de redes de distribuição
Função-objetivo Célula Fórmula referente a função objetivo
z I16 =SOMARPRODUTO(D4:D14;E14:E14)
Restrição Célula Resultado da restrição 
Nó 1 H4 =SOMASE($C$4:$C$20;G4;$E$4:$E$20)-
SOMASE($B$4:$B$20;G4;$E$4:$E$20)
Nó2 H5 =SOMASE($C$4:$C$20;G5;$E$4:$E$20)-
SOMASE($B$4:$B$20;G5;$E$4:$E$20)
Nó 3 H6 =SOMASE($C$4:$C$20;G6;$E$4:$E$20)-
SOMASE($B$4:$B$20;G6;$E$4:$E$20)
Nó 4 H7 =SOMASE($C$4:$C$20;G7;$E$4:$E$20)-
SOMASE($B$4:$B$20;G7;$E$4:$E$20)
Nó 5 H8 =SOMASE($C$4:$C$20;G8;$E$4:$E$20)-
SOMASE($B$4:$B$20;G8;$E$4:$E$20)Nó 6 H9 =SOMASE($C$4:$C$20;G9;$E$4:$E$20)-
SOMASE$B$4:$B$20;G9;$E$4:$E$20)
Nó 7 H10 =SOMASE($C$4:$C$20;G10;$E$4:$E$20)-
SOMASE($B$4:$B$20;G10;$E$4:$E$20)
Nó 8 H11 =SOMASE($C$4:$C$20;G11;$E$4:$E$20)-
SOMASE($B$4:$B$20;G11;$E$4:$E$20)
Nó 9 H12 =SOMASE($C$4:$C$20;G12;$E$4:$E$20)-
SOMASE($B$4:$B$20;G12;$E$4:$E$20)
Fonte: Elaborado pelo autor.
Uma vez feita a modelagem, devemos estabelecer os 
parâmetros e as opções do Solver (Figura 5) e otimizá-lo. 
A Figura 6 apresenta a solução ótima do problema. Nela 
verificamos que a forma mais econômica de a LCL Carros 
Brasil atender a seus distribuidores é enviando 200 carros da 
fábrica da Bahia para Minas Gerais, 150 da Bahia para o Rio 
de Janeiro, 150 da Bahia para Goiás, 200 de São Paulo para o 
Rio de Janeiro, 300 de São Paulo para o Paraná e 100 de São 
Paulo para Santa Catarina.
 De acordo com Lachtermacher (2016), nem todos 
os distribuidores poderiam ter suas demandas completamente 
atendidas, pois a demanda total é maior do que a capacidade 
de produção da companhia. Os distribuidores que não devem 
44Pesquisa Operacional
ter sua demanda total suprida, de acordo com a solução ótima 
apresentada pelo Solver, são os dos estados de Santa Catarina 
e do Rio Grande do Sul. Santa Catarina deixará de receber 50 
carros, e o Rio Grande do Sul, 250 carros. 
Figura 5 - Condições do Solver para o caso LCL Carros 
Brasil — 1a alternativa.
Fonte: Elaborado pelo autor.
Figura 6 - Solução ótima para o caso LCL Carros Brasil 
— 1ª alternativa.
Fonte: Lachtermacher (2016). 
Para resolver o problema da montadora de veículos LCL 
Carros Brasil pela outra forma (sem inclusão de variáveis 
dummy), modelaremos o problema tratando as restrições 
como de menor ou igual, já que a oferta total é menor do que 
a demanda total. A modelagem do problema, portanto, será 
a seguinte:
Variáveis de decisão 
•	 x13 — número de carros enviados da BA para MG. 
•	 x14 — número de carros enviados da BA para o RJ. 
•	 x15 — número de carros enviados da BA para GO. 
•	 x23 — número de carros enviados de SP para MG. 
•	 x24 — número de carros enviados de SP para o RJ. 
•	 x26 — número de carros enviados de SP para o PR. 
•	 x27 — número de carros enviados de SP para SC. 
•	 x28 — número de carros enviados de SP para o RS. 
•	 x34 — número de carros enviados de MG para o RJ. 
•	 x35 — número de carros enviados de MG para GO. 
•	 x78 — número de carros enviados de SC para o RS. 
•	 Função-objetivo Min 25x13 + 30x14 + 40x15 + 20x23 
+ 15x24 + 20x26 + 35x27 + 50x28 + 20x34 + 20x35 + 
20x78
A montagem das restrições segue a lógica utilizada na 
modelagem anterior, e elas serão do tipo menor ou igual, 
representadas abaixo. 
– x13 – x14 – x15 ≤ –500 nó 1 
– x23 – x24 – x26 – x27 – x28 ≤ – 600 nó 2 
x13 + x23 – x34 – x35 ≤ 200 nó 3 
x14 + x24 + x34 ≤ 350 nó 4 
x15 + x35 ≤ 150 nó 5
x26 ≤ 300 nó 6 
x27 – x78 ≤ 150 nó 7 
x28 + x78 ≤ 250 nó 8 
A Figura 7 mostra o problema de transporte da LCL 
Carros Brasil, modelado de acordo com a 2a alternativa. A 
célula I16 representa a função-objetivo, e as células E4 a 
E14, as variáveis de decisão do modelo. As células H4 a H11 
representam os LHS das restrições de fl uxo, e as células I4 
a I11, os RHS das células. A Tabela 3 mostra as fórmulas 
utilizadas nas células que representam os LHS das restrições e 
na célula que denota a função-objetivo. A Figura 8 representa 
os parâmetros e as opções do Solver utilizados no problema.
Figura 7 - Modelagem do caso LCL Carros Brasil — 2a 
alternativa.
Fonte: Lachtermacher (2016).
Tabela 3 - Fórmulas utilizadas nas restrições do problema 
de redes de distribuição — 2a alternativa
Função-objetivo Célula Fórmula referente a função objetivo
z I16 =SOMARPRODUTO(D4:D14;E14:E14)
Restrição Célula Resultado da restrição 
Nó 1 H4 =SOMASE($C$4:$C$14;G4;$E$4:$E$14)-
SOMASE($B$4:$B$14;G4;$E$4:$E$14)
Nó2 H5 =SOMASE($C$4:$C$14;G5;$E$4:$E$14)-
SOMASE($B$4:$B$14;G5;$E$4:$E$14)
Nó 3 H6 =SOMASE($C$4:$C$14;G6;$E$4:$E$14)-
SOMASE($B$4:$B$14;G6;$E$4:$E$14)
Nó 4 H7 =SOMASE($C$4:$C$14;G7;$E$4:$E$14)-
SOMASE($B$4:$B$14;G7;$E$4:$E$14)
45
Nó 5 H8 =SOMASE($C$4:$C$14;G8;$E$4:$E$14)-
SOMASE($B$4:$B$14;G8;$E$4:$E$14)
Nó 6 H9 =SOMASE($C$4:$C$14;G9;$E$4:$E$14)-
SOMASE($B$4:$B$14;G9;$E$4:$E$14)
Nó 7 H10
=SOMASE($C$4:$C$14;-
G10;$E$4:$E$14)-SOMASE($B$4:$B$14;-
G10;$E$4:$E$14)
Nó 8 H11
=SOMASE($C$4:$C$14;-
G11;$E$4:$E$14)-SOMASE($B$4:$B$14;-
G11;$E$4:$E$14)
Fonte: Elaborado pelo autor.
Figura 8 – Condições do Solver para o caso LCL Carros 
Brasil — 2a alternativa.
Fonte: Elaborado pelo autor.
Observando a Figura 9, que mostra o resultado da 
otimização do problema, notamos que a solução ótima 
apresentada pelo Solver nesse modelo é exatamente igual à 
solução da modelagem anterior, que incluía a variável dummy. 
É indiferente utilizarmos um ou outro método de modelagem; 
o modelador deve escolher o que mais lhe convém. No 
caso de soluções múltiplas, os resultados poderiam até ser 
diferentes, isto é, um método poderia chegar a uma solução 
ótima, e o método alternativo a outra solução, porém ambas 
apresentando o mesmo valor ótimo.
Figura 9 - Solução ótima para o caso LCL Carros Brasil 
— 2ª alternativa.
Fonte: Lachtermacher (2016).
2 - Caminho mínimo
O problema do caminho mínimo representa um caso 
especial de problemas de rede, em que os arcos signifi cam a 
distância entre dois pontos (nós). Quando desejamos achar 
a rota que une esses pontos com a menor distância entre 
as possíveis, temos um problema do tipo menor caminho. 
Esse tipo de problema pode ser generalizado e aplicado à 
distribuição de energia elétrica, GPS, entre outros.
Em problemas de menor caminho haverá sempre dois 
tipos de nós especiais, chamados de origem e destino. Entre 
um nó de origem e um nó de destino geralmente existem nós 
intermediários, que podem representar cidades que conectam 
rodovias, subestações com problemas de distribuição de 
energia, e assim por diante.
Para exemplifi car, vamos estudar o caso da Dourados 
Adornos & Tecidos. A fábrica de artigos de decoração 
Dourados Adornos & Tecidos, localizada em Lambari, 
Minas Gerais, deve entregar grande quantidade de peças 
na cidade de Baependi, no mesmo estado. A empresa quer 
saber qual caminho seu caminhão de entregas deve fazer para 
minimizar a distância total percorrida. A Figura 10 mostra 
o mapa rodoviário da região do estado em que se situam as 
duas cidades, e a Figura 5.28 mostra o mapa esquemático e as 
distâncias entre as cidades na forma de rede.
Figura 10 - Mapa rodoviário que liga as cidades de 
Lambari a Baependi.
Fonte: Lachtermacher (2016).
Figura 11 – Representação em rede do caso Dourados 
Adornos & Tecidos.
Fonte: Lachtermacher (2016).
46Pesquisa Operacional
A modelagem do problema terá variáveis binárias do tipo 
xij, indicando o sentido da cidade i para a cidade j. Se o valor 
da variável for igual a um, signifi ca que aquele trecho deve ser 
percorrido. De forma inversa, se o valor da variável for igual 
a zero, a estrada que liga a cidade i à cidade j não deverá ser 
utilizada.
Variáveis de decisão 
•	 x12 — trecho Lambari (1) — Três Corações (2). 
•	 x13 — trecho Lambari (1) — São Lourenço (3). 
•	 x15 — trecho Lambari (1) — Caxambu (5). 
•	 x24 — trecho Três Corações (2) — São Thomé das 
Letras (4). 
•	 x35 — trecho São Lourenço (3) — Caxambu (5). 
•	 x46 — trecho São Thomé das Letras (4) — Baependi 
(6). 
•	 x56 — trecho Caxambu (5) — Baependi (6). 
De acordo com Lachtermacher (2016), a função-objetivo 
visa minimizar a distância percorrida pelo caminhão. Logo, se 
as variáveis de decisão assumem zero ou um, a multiplicação 
destas pelas distâncias entre as respectivas cidades será zero, 
caso a estrada não seja utilizada, e igual à distância entre as 
cidades, se ela for utilizada. Portanto, o somatório desses 
produtos será a distância percorrida, isto é, a função-objetivo, 
que matematicamente pode ser representada por: 
Min Z = 41x12 + 44x13 + 50x15 + 37x24 + 27x35 + 45x46 
+ 4x56
A demanda de Baependi será de um caminhão(+1) 
e a oferta de Lambari será de um caminhão (–1). Todas as 
outras cidades intermediárias terão demanda e oferta iguais 
a zero. Dessa forma, as restrições de fl uxo podem ser 
matematicamente representadas por: 
– x12 – x13 – x15 = – 1 nó 1 
x12 – x24 = 0 nó 2 
x13 – x35 = 0 nó 3 
x24 – x46 = 0 nó 4 
x15 + x35 – x56 = 0 nó 5 
x46 + x56 = + 1 nó 6 
Uma das possíveis modelagens desse problema na 
planilha Excel é mostrada na Figura 12. A célula E12 
representa a função-objetivo, e as células E4 a E10, as variáveis 
de decisão do modelo. As células H4 a H9 representam os 
LHS das restrições de fl uxo, e as células I4 a I9, os RHS das 
células. A Tabela 4 mostra as fórmulas utilizadas nos LHS das 
restrições e na célula que denota a função-objetivo.
Figura 12 – Modelagem do caso da Dourados Adornos 
& Tecidos.
Fonte: Elaborado pelo autor.
Tabela 4 - Fórmulas utilizadas no caso da Dourados 
Adornos & Tecidos.
Função-objetivo Célula Fórmula referente à função objetivo
z E12 =SOMARPRODUTO(D4:D10;E4:E10)
Restrição Célula Resultado da restrição 
Nó 1 H4 =SOMASE($C$4:$C$10;G4;$E$4:$E$10)-
SOMASE($B$4:$B$10;G4;$E$4:$E$10)
Nó2 H5 =SOMASE($C$4:$C$10;G5;$E$4:$E$10)-
SOMASE($B$4:$B$10;G5;$E$4:$E$10)
Nó 3 H6 =SOMASE($C$4:$C$10;G6;$E$4:$E$10)-
SOMASE($B$4:$B$10;G6;$E$4:$E$10)
Nó 4 H7 =SOMASE($C$4:$C$10;G7;$E$4:$E$10)
SOMASE($B$4:$B$10;G7;$E$4:$E$10)
Nó 5 H8 =SOMASE($C$4:$C$10;G8;$E$4:$E$10)-
SOMASE($B$4:$B$10;G8;$E$4:$E$10)
Nó 6 H9 =SOMASE($C$4:$C$10;G9;$E$4:$E$10)-
SOMASE($B$4:$B$10;G9;$E$4:$E$10)
Fonte: Elaborado pelo autor.
Figura 13 – Modelagem no solver
Fonte: Elaborado pelo autor.
Figura 14 - Solução do exemplo.
Fonte: Elaborado pelo autor.
As condições especifi cadas para os parâmetros e as 
opções do Solver estão evidenciadas na Figura 13. A Figura 14 
47
mostra a solução ótima do problema. Segundo ela, o caminho 
pela malha rodoviária da região que resulta na menor distância 
entre as cidades de Lambari e Baependi é o que passa pelo 
município de Caxambu. Dessa forma, o caminhão de entregas 
da LCL Adornos & Tecidos deve sair de Lambari, seguir a 
estrada que leva até Caxambu (x15 = 1) e, de lá, partir para 
Baependi (x56 = 1), percorrendo uma distância total de 54 
quilômetros (50 km de Lambari a Caxambu e mais 4 km de 
Caxambu a Baependi).
3 - Problema do fl uxo máximo
O tipo de problema de fl uxo máximo é utilizado quando 
queremos maximizar a quantidade de fl uxo de um ponto 
de origem para um ponto de destino e estamos sujeitos a 
restrições de capacidade de fl uxo nos arcos. Esses problemas 
geralmente envolvem o fl uxo de materiais como água, óleo, 
gás, energia por uma rede de tubos ou cabos, mas também 
podem representar o fl uxo máximo de carros em uma malha 
rodoviária, de produtos em linhas de produção, e assim por 
diante.
 Para exemplifi car, tomemos o exemplo da empresa 
distribuidora de gás GasoBras Ltda. deseja determinar a 
quantidade máxima de metros cúbicos por segundo de gás 
que pode bombear da estação de Campos para o centro 
consumidor do Rio de Janeiro pela rede de gasodutos 
existentes. A Figura 15 ilustra a estrutura da rede de 
distribuição e apresenta a capacidade de fl uxo máximo nos 
trechos (em metros cúbicos por segundo). 
Figura 15 – Redes de gasodutos que ligam Campos ao 
Rio de Janeiro.
Fonte: Lachtermacher (2016).
Figura 16 – Rede com inclusão do arco artifi cial.
 
Fonte: Lachtermacher (2016).
De acordo com Lachtermacher (2016), para resolver esse 
problema, utilizaremos um pequeno artifício: adicionaremos 
um arco virtual ligando o nó B ao nó A (Figura 16). A função-
objetivo, portanto, será a maximização do fl uxo de gás que 
passa de B para A. Como o fl uxo de B para A na realidade não 
existe, o valor do fl uxo no arco artifi cial representará o total 
de gás que pode chegar ao Rio de Janeiro vindo de Campos 
por mais de um caminho simultaneamente.
Variáveis de decisão 
•	 xA1 — m3/s de gás que saem de A e chegam à 
Estação 1. 
•	 xA2 — m3/s de gás que saem de A e chegam à 
Estação 2. 
•	 x13 — m3/s de gás que saem da Estação 1 e chegam 
à Estação 3. 
•	 x14 — m3/s de gás que saem da Estação 1 e chegam 
à Estação 4. 
•	 x24 — m3/s de gás que saem da Estação 2 e chegam 
à Estação 4. 
•	 x3B — m3/s de gás que saem da Estação 3 e chegam 
em B. 
•	 x4B — m3/s de gás que saem da Estação 4 e chegam 
em B. 
•	 xBA — m3/s de gás que saem de B e chegam em A 
(arco artifi cial). 
Função-objetivo Max xBA 
A composição das restrições seguirá as seguintes 
condições: 
•	 O fl uxo em cada arco deverá ser maior ou igual a 
zero. 
•	 O fl uxo em cada arco deverá ser menor ou igual à 
capacidade do arco. 
•	 O fl uxo que chega a cada nó deverá ser igual ao 
fl uxo que sai dele. 
•	 O fl uxo do arco artifi cial (desconhecido) deve 
ser grande o bastante para assumir qualquer valor 
possível, já que este será maximizado.
Restrições de capacidade 
•	 xA1 ≤ 40 xA2 ≤ 30
•	 x13 ≤ 30 x14 ≤ 20 
•	 x24 ≤ 30 x3B ≤ 20 
•	 x4B ≤ 40 xBA ≤ 9.999 
Restrições de fl uxo 
xBA – (xA1 + xA2) = 0 nó A 
xA1 – (x13 + x14) = 0 nó 1 
xA2 – (x24) = 0 nó 2 
x13 – (x3B) = 0 nó 3 
x14 + x24 – (x4B) = 0 nó 4 
x3B + x4B – (xBA) = 0 nó B
Uma das possíveis modelagens desse problema na 
planilha Excel é mostrada na Figura 17. A célula E13 
representa a função-objetivo, e as células E4 a E11, as variáveis 
de decisão do modelo. As células H4 a H9 representam os 
LHS das restrições de fl uxo, e as células I4 a I9, os RHS das 
células. A Tabela 5 mostra as fórmulas utilizadas nos LHS 
das restrições e na célula que denota a função-objetivo. As 
condições especifi cadas para os parâmetros e as opções do 
Solver estão evidenciadas na Figura 18. 
48Pesquisa Operacional
Figura 17 – Modelagem no caso da GasoBras
Fonte: Lachtermacher (2016).
Figura 18 – Estratégia com o Solver no caso da GasoBras
Fonte: Elaborado pelo autor.
Tabela 5 – Fórmulas utilizadas no caso da GasoBrass
Função-objetivo Célula Fórmula referente à função objetivo
Max xBA E13 =E11
Restrição Célula Resultado da restrição 
Nó 1 H4 =SOMASE($C$4:$C$11;G4;$E$4:$E$11)-SO-
MASE$B$4:$B$11;G4;$E$4:$E$11)
Nó2 H5 =SOMASE($C$4:$C$11;G5;$E$4:$E$11)-SO-
MASE($B$4:$B$11;G5;$E$4:$E$11)
Nó 3 H6 =SOMASE($C$4:$C$11;G6;$E$4:$E$11)-SO-
MASE($B$4:$B$11;G6;$E$4:$E$11)
Nó 4 H7 =SOMASE($C$4:$C$11;G7;$E$4:$E$11)-SO-
MASE($B$4:$B$11;G7;$E$4:$E$11)
Nó 5 H8 =SOMASE($C$4:$C$11;G8;$E$4:$E$11)-SO-
MASE($B$4:$B$11;G8;$E$4:$E$11)
Nó 6 H9 =SOMASE($C$4:$C$11;G9;$E$4:$E$11)-SO-
MASE($B$4:$B$11;G9;$E$4:$E$11)
Fonte: Elaborado pelo autor.
Figura 19 – Solução do problema da GasoBras
Fonte: Lachtermacher (2016).
A Figura 19 evidencia a solução ótima apresentada 
pelo Solver para o problema da GasoBras. Como podemos 
observar, em função dos limites de fl uxos dos gasodutos, o 
fl uxo máximo que pode chegar ao Rio de Janeiro é de 60 
metros cúbicos de gás por segundo.
Ao chegar ao fi nal da quinta aula, vamos recordar o 
que aprendemos:
Retomando a aula
1 – O problema de redes
Nessa seção, fomos apresentados ao problema de 
redes, que pode ser considerado um problema de transporte 
mais complexo, com inúmeros fornecedores, transbordos e 
destinos fi nais, sendo por essas características que é necessário 
ser estudado separadamente.
2 – Caminho mínimo
Nessa segunda parte de nosso estudo, vimos uma 
aplicação clássica de problema de redes, que é o problema 
do caminho mínimo. Vimos exemplo de como resolver esse 
problema através do Excel, bem em linha com a realidade do 
dia a dia de um engenheiro.
3 – Problema do fl uxo máximo
Finalmente, na última etapa, vimos o problema do 
fl uxo máximo, que pode ser entendido como o inverso do 
problema do caminho mínimo da segunda seção. Nessa seção 
também foi apresentado uma maneira de resolução através do 
Microsoft Excel. 
Hillier, F.S. e Lieberman G.J., Introdução à Pesquisa 
Operacional, 8ª. edição. São Paulo: McGraw-Hill, 2006.
Lachtermacher, G. Pesquisa operacional na tomada de 
decisões, 5ª. edição. São Paulo: Prentice Hall, 2016.
Taha, H. A.. PesquisaOperacional. 8ª edição. São Paulo: 
Pearson, 2008.
Vale a pena ler
Vale a pena