27 de agosto de 2026

Problemas de transporte e redes

Da matriz de custos ao gargalo da rede

Desafio de abertura: uma empresa possui 2 fábricas, 3 depósitos e estradas com capacidades diferentes. O que deve ser decidido: quanto enviar, por qual caminho ou quanto a rede suporta?
Hoje
Modelar a decisão sem perder a realidade operacional.
Ao final
Escolher o modelo, formular, resolver e interpretar a solução.
Evidência
Você justificará um modelo para uma rede real.
Regra de ouro: antes do algoritmo, defina a pergunta, as unidades, os nós, os arcos e os balanços.

Roteiro visual da aula

1Alocar
Transporte clássico: origem → destino.
2Conectar
Transbordo: caminhos e hubs.
3Otimizar
Caminho mínimo e fluxo de custo mínimo.
4Dimensionar
Fluxo máximo e corte mínimo.
Checkpoint 1 — previsão: se uma rota barata ficar saturada, o custo total necessariamente deixará de ser ótimo? Anote sua hipótese; voltaremos a ela.

1. A mesma decisão em três lentes

custo 4custo 6custo 3custo 5 O1O2HD1D2
A matriz es compacta; a rede torna visíveis caminhos, capacidades e gargalos.
  • Transporte: quanto enviar de cada origem a cada destino.
  • Rede de transporte: por quais arcos o fluxo passa.
  • Fluxo máximo: qual volume a rede suporta.
  • Fluxo de custo mínimo: como enviar um volume fixado ao menor custo.

2. Anatomia de um modelo de rede

Elemento Pergunta operacional Símbolo
Nó de oferta quanto é gerado? \(b_k>0\)
Nó de demanda quanto é absorvido? \(b_k<0\)
Transbordo o que entra deve sair? \(b_k=0\)
Arco que ligação é permitida? \((i,j)\in A\)
Capacidade qual é o limite? \(u_{ij}\)
Custo quanto custa uma unidade? \(c_{ij}\)
Pergunte antes de modelar: qual período? qual unidade? há perdas, estoques, frota, prazos, ligações proibidas ou vários produtos?

3. Transporte clássico: formulação

Dados: oferta \(a_i\), demanda \(b_j\), custo direto \(c_{ij}\) e decisão \(x_{ij}\) = quantidade enviada de \(i\) para \(j\).

\[\min Z=\sum_i\sum_j c_{ij}x_{ij}\]

\[\sum_j x_{ij}=a_i\;\forall i;\qquad \sum_i x_{ij}=b_j\;\forall j;\qquad x_{ij}\geq0\]

Teste de sanidade: no modelo fechado, \(\sum_i a_i=\sum_j b_j\). Se não houver igualdade, a diferença precisa ter interpretação.

4. Exemplo guiado — do enunciado à matriz

Duas fábricas abastecem três depósitos:

D1 D2 D3 Oferta
F1 10 3 5 15
F2 12 7 9 25
Demanda 20 10 10 40
Leitura
F1 produz 15; F2, 25. D1 exige 20; D2, 10; D3, 10.
Decisão
Seis variáveis, uma para cada ligação permitida.
Alerta
Custo é unitário: não confundir com capacidade ou quantidade.

\(15+25=20+10+10=40\): caso balanceado.

5. Solução inicial — canto noroeste

O método garante viabilidade, mas ignora custos. Em cada passo, aloque o mínimo entre oferta e demanda.

Passo Célula Alocação Oferta restante Demanda restante
1 F1–D1 15 F1=0 D1=5
2 F2–D1 5 F2=20 D1=0
3 F2–D2 10 F2=10 D2=0
4 F2–D3 10 F2=0 D3=0

\[Z=15(10)+5(12)+10(7)+10(9)=440\]

Diagnóstico: viável não significa ótimo. A solução usou muito F1–D1, embora F1–D2 seja mais barato.

6. Solução inicial — menor custo

1 menor custo: F1–D2 = 3 → aloque 10.
2 próximo: F1–D3 = 5 → aloque 5.
3 F2–D3 = 9 → aloque 5.
4 F2–D1 = 12 → aloque 20.
D1 D2 D3 Oferta
F1 0 10 5 15
F2 20 0 5 25
Demanda 20 10 10 40

\[Z=10(3)+5(5)+20(12)+5(9)=340\]

Checkpoint 2: a heurística reduziu o custo de 440 para 340. Ainda falta provar optimalidade.

7. Optimalidade — stepping-stone

Para inserir uma célula vazia, forme um ciclo fechado com células ocupadas e alterne sinais \(+,-,+,-\).

Para F2–D2:

\[(F2,D2)^+\to(F2,D3)^-\to(F1,D3)^+\to(F1,D2)^-\]

\[\Delta=+c_{22}-c_{23}+c_{13}-c_{12}=7-9+5-3=0\]

\(\Delta=0\) indica uma solução ótima alternativa. Se \(\Delta<0\), a troca reduz o custo; se todos os ciclos têm \(\Delta\geq0\), a solução é ótima.

8. Optimalidade — multiplicadores

Associe \(u_i\) às linhas e \(v_j\) às colunas. Para células básicas:

\[u_i+v_j=c_{ij}\]

Para células não básicas:

\[\bar c_{ij}=c_{ij}-u_i-v_j\]

Minimização
Todos \(\bar c_{ij}\geq0\): ótimo.
Melhoria
Algum \(\bar c_{ij}<0\): introduzir essa célula.
Empate
Algum \(\bar c_{ij}=0\): pode haver ótimos alternativos.

No exemplo, tomando \(u_1=0\): \(v_2=3\), \(v_3=5\), \(u_2=4\), \(v_1=8\). Logo \(\bar c_{11}=2\) e \(\bar c_{22}=0\).

9. Quando o transporte fica desbalanceado?

Oferta > demanda
Origem fictícia? Não: destino fictício para estoque, sobra ou descarte, com custo interpretável.
Demanda > oferta
Origem fictícia para compra emergencial, atraso ou falta, com penalidade.

Alternativa com falta explícita \(q_j\):

\[\sum_i x_{ij}+q_j=b_j,\qquad \min\;\sum c_{ij}x_{ij}+\sum p_jq_j\]

O custo fictício representa uma consequência econômica. Escolhê-lo como zero pode criar uma decisão gerencial absurda.

10. Extensões que mudam o modelo

  • Ligação proibida: retirar \(x_{ij}\) ou impor \(x_{ij}=0\).
  • Capacidade de rota: \(x_{ij}\le u_{ij}\).
  • Custo fixo: \(x_{ij}\le u_{ij}y_{ij}\), com \(y_{ij}\in\{0,1\}\).
  • Frota/contêineres: variáveis inteiras.
  • Vários períodos: índice de tempo e estoque.
  • Vários produtos: \(\sum_k f^k_{ij}\le u_{ij}\), possivelmente em peso e volume.
Decisão didática: a restrição é local (um arco), global (um nó) ou temporal? Essa classificação orienta a formulação.

11. Transbordo: a matriz vira rede

O produto pode passar por centros intermediários. Para cada nó \(k\):

\[\sum_{i:(i,k)\in A}f_{ik}+b_k=\sum_{j:(k,j)\in A}f_{kj}\]
OH1H2Dofertaentrega
Origem: sai mais do que entra; destino: entra mais do que sai; hub: conserva fluxo.

12. Exemplo — transbordo com capacidades

Demanda de O para D: 50 unidades.

Arco custo capacidade
O–H1 4 40
O–H2 2 30
H1–D 3 40
H2–D 7 30

Caminhos: O–H1–D custa 7 e suporta 40; O–H2–D custa 9 e suporta 30.

Solução: 40 pelo caminho de custo 7 e 10 pelo caminho de custo 9. Custo total \(40(7)+10(9)=370\).
Por que não enviar tudo por H1? Porque a capacidade do caminho é o mínimo das capacidades dos seus arcos: o gargalo H1–D limita a 40.

13. Caminho mínimo

Enviar uma unidade de \(s\) a \(t\) ao menor custo é um caso particular de fluxo:

\[b_s=1,\quad b_t=-1,\quad b_k=0\;(k\neq s,t)\]

Dijkstra (custos não negativos):

1 rótulo de \(s=0\), demais \(\infty\). 2 escolha o menor rótulo não visitado. 3 relaxe sucessores. 4 guarde predecessores.

Menor distância não é necessariamente menor custo operacional: inclua pedágio, tempo, risco, emissões e confiabilidade na unidade de custo.

14. Fluxo máximo: a pergunta muda

Pergunta: qual é a maior quantidade que pode sair da fonte \(s\) e chegar ao sorvedouro \(t\), respeitando a capacidade de cada arco?

\[0\le f_{ij}\le u_{ij}\]

\[\sum_i f_{ik}=\sum_j f_{kj}\quad\text{para todo nó intermediário }k\]

\[\max v=\sum_j f_{sj}-\sum_i f_{is}\]

O objetivo não contém custo. Se custo e quantidade forem simultaneamente relevantes, use fluxo de custo mínimo ou uma formulação multiobjetivo.

15. Exemplo — localizar o gargalo antes de calcular

Capacidades da rede:

Arco s–A s–B A–t B–t A–B
Capacidade 10 8 5 10 6
108510sABt
Pergunta de previsão: qual conjunto de arcos parece limitar a chegada a t?

16. Ford–Fulkerson: aumentos e rede residual

A rede residual contém capacidade restante no sentido original e arco reverso com capacidade igual ao fluxo já enviado.

  1. \(s\to A\to t\): incremento \(\min(10,5)=5\); acumulado 5.
  2. \(s\to B\to t\): incremento \(\min(8,10)=8\); acumulado 13.
  3. \(s\to A\to B\to t\): residual \(\min(5,6,2)=2\); acumulado 15.
Resultado: fluxo 15. O corte \(\{s,A,B\}\to\{t\}\) tem capacidade \(5+10=15\), então, pelo teorema fluxo máximo–corte mínimo, 15 é máximo.
Arcos reversos importam: eles permitem desfazer parte de uma alocação e redirecionar o fluxo quando uma escolha inicial foi ruim.

17. Teorema fluxo máximo–corte mínimo

Um corte \((S,T)\) separa os nós, com \(s\in S\) e \(t\in T\):

\[C(S,T)=\sum_{i\in S,j\in T}u_{ij}\]

Para qualquer fluxo, \(v\le C(S,T)\). O teorema garante:

\[\text{fluxo máximo}=\text{capacidade do corte mínimo}\]
Tradução gerencial: o corte mínimo identifica quais ligações devem ser expandidas. Aumentar uma estrada fora do gargalo pode não alterar a capacidade global.

18. Fluxo de custo mínimo

Se a quantidade \(Q\) a enviar é conhecida, a pergunta é “como enviar ao menor custo?”:

\[\min\sum_{(i,j)\in A}c_{ij}f_{ij}\quad\text{sujeito a balanço e}\quad 0\le f_{ij}\le u_{ij}\]

Fluxo máximo
Quantidade é variável; custo não é o objetivo.
Custo mínimo
Quantidade é fixada; custo é minimizado.

Armadilha comum: escolher o algoritmo pelo nome do problema, sem verificar o objetivo real.

19. Outros problemas clássicos

Problema Estrutura Aplicação
Designação oferta/demanda unitárias, binária pessoas–tarefas
Circulação com limites inferiores \(\ell_{ij}\le f_{ij}\le u_{ij}\) nível mínimo de serviço
Multi commodity produtos compartilham capacidade distribuição simultânea
Localização–alocação abertura + transporte centros de distribuição
Custos fixos ativar rota/instalação decisão de projeto
Com vários produtos, custos fixos ou decisões de abertura, a integralidade automática do transporte pode desaparecer: talvez seja necessário um modelo inteiro misto.

20. Mapa de decisão do modelador

Há origens e destinos diretos?
→ Transporte clássico.
Há hubs ou etapas?
→ Transbordo/rede.
“Quanto a rede suporta?”
→ Fluxo máximo.
“Como enviar Q ao menor custo?”
→ Fluxo de custo mínimo.
Checkpoint 3: classifique: (a) maior número de veículos numa malha; (b) menor custo para entregar 500 t; (c) melhor fábrica–cliente sem hub; (d) melhor rota de uma ambulância. Respostas: fluxo máximo, custo mínimo, transporte, caminho mínimo.

21. Exercício em camadas — transporte clássico

D1 D2 D3 Oferta
O1 4 8 5 30
O2 6 3 7 20
Demanda 10 15 25 50

Camada 1 — diagnosticar: balanceamento, variáveis e hipóteses.

Camada 2 — construir: canto noroeste e menor custo; calcule os dois custos.

Camada 3 — testar: escolha uma célula vazia, forme um ciclo e calcule \(\Delta\).

Camada 4 — interpretar: o que muda se O2–D3 for proibida? E se a oferta de O1 cair para 20?

22. Exercício em camadas — fluxo máximo

Arcos e capacidades: \(s\to A=12\), \(s\to B=10\), \(A\to t=7\), \(B\to t=8\), \(A\to B=5\), \(A\to C=6\), \(B\to C=4\), \(C\to t=10\).

  1. Encontre dois caminhos aumentantes.
  2. Registre incremento e fluxo acumulado.
  3. Desenhe a rede residual após cada iteração.
  4. Encontre um corte e calcule sua capacidade.
  5. Explique por que aumentar \(s\to A\) pode não aumentar o fluxo máximo.
Critério de qualidade: uma resposta sem conservação de fluxo, limites ou justificativa do corte está incompleta.

23. Gabarito curto e autoavaliação

Transporte: para a matriz do exercício, uma solução pelo menor custo é: O2–D2 = 15, O1–D1 = 10, O1–D3 = 20, O2–D1 = 0, O2–D3 = 5; custo \(15(3)+10(4)+20(5)+5(7)=265\). Verifique se há melhoria por ciclos.

Fluxo máximo: o corte formado pelos arcos que chegam a \(t\) tem capacidade \(7+8+10=25\); portanto, nenhum fluxo supera 25. Construa um fluxo de valor 25 para provar que esse limite é atingível.

Consigo formular?
Nomeio nós, arcos, variáveis, objetivo e balanços.
Consigo validar?
Confiro unidades, conservação, capacidades e interpretação.
Consigo explicar?
Relaciono a solução a um gargalo ou decisão real.

24. Atividade aplicada — da rede real ao modelo

Em grupos, escolha uma rede de distribuição da instituição: fornecedores, almoxarifado, setores e rotas internas.

  • desenhe nós e arcos;
  • registre oferta, demanda, capacidade e custo;
  • escolha entre transporte, transbordo, caminho mínimo, fluxo máximo ou custo mínimo;
  • explicite duas hipóteses que precisam ser validadas;
  • identifique o gargalo e uma decisão de expansão.

Produto da atividade: um diagrama, uma formulação de até cinco linhas e uma conclusão gerencial de três frases.

Síntese final

  • Transporte aloca oferta entre destinos ao menor custo.
  • Redes representam caminhos, transbordos, capacidades e conservação.
  • Caminho mínimo escolhe uma rota; fluxo máximo dimensiona o volume.
  • Custo mínimo combina quantidade, capacidade e custo.
  • Corte mínimo transforma a solução em uma recomendação de investimento.
  • Extensões como custos fixos, frota, tempo e múltiplos produtos podem exigir programação inteira.
Saída da aula: um bom modelo não é apenas uma resposta numérica; é uma explicação verificável de como o sistema deve operar.

Referências essenciais

Nota ao professor: usar os checkpoints como pausas de previsão individual, discussão em pares e compartilhamento. Os exercícios seguem progressão: identificar → formular → resolver → interpretar.