introdução / exemplos progressivos
Da distribuição simples à otimização de rotas
Antes da formulação geral, examinaremos dois exemplos progressivos. O primeiro apresenta duas origens e dois destinos; o segundo amplia a rede para três depósitos. Em ambos, a solução básica inicial é construída pelo Método do Canto Noroeste e depois avaliada pelo Stepping Stone.
Dois depósitos e dois centros de consumo
Os depósitos D1 e D2 disponibilizam, respectivamente, 15 e 35 unidades. Os centros C1 e C2 demandam 20 e 30 unidades. Os custos unitários são apresentados na matriz.
| Origem | C1 | C2 | Oferta |
|---|---|---|---|
| D1 | 2,50 | 3,00 | 15 |
| D2 | 3,50 | 2,30 | 35 |
| Demanda | 20 | 30 | 50 |
Solução inicial — Canto Noroeste
| Origem | C1 | C2 | Oferta |
|---|---|---|---|
| D1 | 15 (2,50) | 0 (3,00) | 15 |
| D2 | 5 (3,50) | 30 (2,30) | 35 |
| Demanda | 20 | 30 | 50 |
Teste de otimalidade
A única célula não básica é x₁₂. O ciclo fechado é x₁₂(+) → x₁₁(−) → x₂₁(+) → x₂₂(−).
Três depósitos e dois centros de consumo
Adiciona-se o depósito D3, com capacidade de 40 unidades. As demandas passam a ser 40 unidades em C1 e 50 em C2, preservando o equilíbrio entre oferta e demanda.
| Origem | C1 | C2 | Oferta |
|---|---|---|---|
| D1 | 2,50 | 3,00 | 15 |
| D2 | 3,50 | 2,30 | 35 |
| D3 | 3,20 | 2,80 | 40 |
| Demanda | 40 | 50 | 90 |
Quadro inicial — Canto Noroeste
| Origem | C1 | C2 | Oferta |
|---|---|---|---|
| D1 | 15 (2,50) | 0 (3,00) | 15 |
| D2 | 25 (3,50) | 10 (2,30) | 35 |
| D3 | 0 (3,20) | 40 (2,80) | 40 |
| Demanda | 40 | 50 | 90 |
Avaliação das rotas não básicas
Para x₁₂, o ciclo x₁₂(+) → x₁₁(−) → x₂₁(+) → x₂₂(−) fornece:
Não é conveniente utilizar essa rota. Para x₃₁, o ciclo x₃₁(+) → x₂₁(−) → x₂₂(+) → x₃₂(−) fornece:
Como a variação é negativa, x₃₁ entra na base. O maior ajuste admissível é θ = min(25, 40) = 25.
Nova solução básica
| Origem | C1 | C2 | Oferta |
|---|---|---|---|
| D1 | 15 (2,50) | 0 (3,00) | 15 |
| D2 | 0 (3,50) | 35 (2,30) | 35 |
| D3 | 25 (3,20) | 15 (2,80) | 40 |
| Demanda | 40 | 50 | 90 |
Teste completo de otimalidade
As células não básicas são x₁₂ e x₂₁. Para x₁₂, o ciclo passa por x₁₁, x₃₁ e x₃₂. Para x₂₁, o ciclo passa por x₂₂, x₃₂ e x₃₁.
5.1 / caracterização geral
O problema de transporte
Uma organização dispõe de diferentes fontes de fornecimento e precisa distribuir um produto a diversos destinos. Cada fonte possui uma capacidade; cada destino apresenta uma demanda; e cada rota possui um custo unitário. O desafio é decidir quanto transportar em cada rota para atender às necessidades com o menor custo total possível.
Elementos da rede
Fontes: fábricas, centros de distribuição ou fornecedores.
Destinos: depósitos, mercados ou clientes.
Rotas: ligações possíveis, cada uma com seu custo unitário de transporte.
O modelo também inspira problemas de transbordo e designação de tarefas, embora esses casos exijam formulações próprias.
Quantidade enviada de cada fonte para cada destino.
Minimizar o custo agregado de todas as rotas utilizadas.
Respeitar capacidades, demandas e não negatividade.
5.2 / formulação matemática
Modelo clássico de transporte
Considere m fontes e n destinos. A fonte i fornece a quantidade aᵢ; o destino j requer bⱼ; e cᵢⱼ representa o custo de transportar uma unidade da fonte i ao destino j.
Quantidade transportada da fonte i para o destino j (variável de decisão).
Custo unitário da rota i → j.
Oferta disponível na origem e demanda do destino.
Função objetivo
Restrições
Estrutura da solução básica
Em um problema equilibrado, uma das m + n equações é redundante. Portanto, a matriz de restrições possui posto m + n − 1 e uma base contém esse número de variáveis. Em casos degenerados, algumas variáveis básicas podem ter valor zero.
5.3 / exemplo orientado
Duas fontes e três destinos
Considere duas fábricas com capacidades de 15 e 25 unidades e três mercados com demandas de 20, 10 e 10 unidades. Os custos unitários estão indicados no quadro.
| Fonte | Destino 1 | Destino 2 | Destino 3 | Oferta |
|---|---|---|---|---|
| Fábrica 1 | 10 | 3 | 5 | 15 |
| Fábrica 2 | 12 | 7 | 9 | 25 |
| Demanda | 20 | 10 | 10 | 40 |
5.4 / solução básica inicial
Construção de uma solução viável
Antes de testar a otimalidade, é conveniente encontrar uma distribuição que atenda às restrições. Dois procedimentos clássicos são apresentados a seguir.
Canto Noroeste
- Iniciar pela célula superior esquerda da tabela.
- Alocar o mínimo entre a oferta restante da linha e a demanda restante da coluna.
- Eliminar a linha ou coluna satisfeita e avançar para a próxima célula disponível.
- Repetir até satisfazer todas as ofertas e demandas.
Esse método não utiliza os custos para escolher as células; por isso, a solução inicial pode ser relativamente cara.
| Canto Noroeste | D1 | D2 | D3 | Oferta |
|---|---|---|---|---|
| F1 | 15 | 0 | 0 | 15 |
| F2 | 5 | 10 | 10 | 25 |
| Demanda | 20 | 10 | 10 |
Custo Mínimo
- Identificar a célula disponível com o menor custo unitário.
- Alocar o máximo possível sem exceder oferta ou demanda.
- Atualizar as quantidades remanescentes e retirar linhas ou colunas satisfeitas.
- Repetir até completar a distribuição.
O método considera os custos locais, mas não garante, isoladamente, a solução ótima global.
| Custo Mínimo | D1 | D2 | D3 | Oferta |
|---|---|---|---|---|
| F1 | 0 | 10 | 5 | 15 |
| F2 | 20 | 0 | 5 | 25 |
| Demanda | 20 | 10 | 10 |
5.5 / algoritmo de melhoria sucessiva
Do Canto Noroeste à solução ótima
Partindo de uma solução básica viável, o Stepping Stone permite melhorar sucessivamente a distribuição. O procedimento repete três operações: avaliar → selecionar → ajustar, até que nenhuma rota não básica possa reduzir o custo.
Procedimento iterativo
- Iniciar: construir a solução pelo Canto Noroeste; identificar as células básicas e calcular Z.
- Avaliar: para cada célula não básica, construir um ciclo fechado de deslocamentos horizontais e verticais entre células básicas. Alternar sinais + e −, começando com + na célula candidata, e calcular Δᵢⱼ pela soma algébrica dos custos.
- Testar: se todos os Δᵢⱼ ≥ 0, encerrar: a solução é ótima. Um Δᵢⱼ = 0 pode indicar solução ótima alternativa.
- Selecionar: escolher uma célula com Δᵢⱼ < 0 (por exemplo, a mais negativa).
- Ajustar: definir θ como a menor alocação nas posições de sinal − do ciclo; somar θ nas posições + e subtrair θ nas posições −.
- Atualizar: retirar da base uma célula que ficou nula, manter m + n − 1 variáveis básicas e retornar à avaliação.
Aplicação: quadro inicial pelo Canto Noroeste
Em cada célula, a quantidade alocada aparece em negrito e o custo unitário entre parênteses.
| Origem | D1 | D2 | D3 | Oferta |
|---|---|---|---|---|
| F1 | 15 (10) | 0 (3) | 0 (5) | 15 |
| F2 | 5 (12) | 10 (7) | 10 (9) | 25 |
| Demanda | 20 | 10 | 10 | 40 |
Iteração 1 — avaliar e selecionar
As células vazias são x₁₂ e x₁₃. Seus ciclos passam por células básicas e produzem:
As duas rotas permitem redução de custo. Escolhemos x₁₂ para entrar na base. O limite é θ = min(x₁₁, x₂₂) = min(15, 10) = 10.
| Após ajuste 1 | D1 | D2 | D3 | Oferta |
|---|---|---|---|---|
| F1 | 5 (10) | 10 (3) | 0 (5) | 15 |
| F2 | 15 (12) | 0 (7) | 10 (9) | 25 |
| Demanda | 20 | 10 | 10 | 40 |
Iteração 2 — nova oportunidade de melhoria
Reavaliando as células não básicas x₁₃ e x₂₂:
A rota x₁₃ entra na base. No ciclo x₁₃ (+), x₁₁ (−), x₂₁ (+), x₂₃ (−), temos θ = min(5, 10) = 5.
| Após ajuste 2 | D1 | D2 | D3 | Oferta |
|---|---|---|---|---|
| F1 | 0 (10) | 10 (3) | 5 (5) | 15 |
| F2 | 20 (12) | 0 (7) | 5 (9) | 25 |
| Demanda | 20 | 10 | 10 | 40 |
Teste final de otimalidade
Agora as células não básicas são x₁₁ e x₂₂:
| Etapa | Custo total | Redução acumulada |
|---|---|---|
| Canto Noroeste | 370 | 0 |
| 1ª melhoria | 350 | 20 |
| 2ª melhoria — ótimo | 340 | 30 |
5.6 / teste de otimalidade
Como verificar se a solução é ótima?
Para cada variável não básica, calcula-se o efeito de introduzir uma unidade adicional na rota, compensando os fluxos das demais células para manter o equilíbrio.
Stepping Stone — ciclos fechados
- Escolher uma célula não básica e construir um ciclo fechado por movimentos horizontais e verticais, passando pelas células básicas.
- Marcar alternadamente sinais + e − nos vértices, iniciando com + na célula avaliada.
- Somar os custos com seus sinais para obter a variação unitária ΔZ.
- Em minimização, uma variação negativa indica oportunidade de reduzir o custo; uma variação nula indica possível solução ótima alternativa.
Aplicação ao exemplo
Partindo da solução pelo Custo Mínimo, as células não básicas são x₁₁ e x₂₂.
Como nenhuma variação é negativa, a solução de custo Z = 340 é ótima. O valor zero para x₂₂ revela a possibilidade de uma segunda distribuição ótima.
Multiplicadores — MODI (potenciais u e v)
- Atribuir um potencial uᵢ a cada fonte e vⱼ a cada destino.
- Para cada célula básica, escrever uᵢ + vⱼ = cᵢⱼ.
- Fixar arbitrariamente um potencial em zero e calcular os demais.
- Para cada célula não básica, calcular Pᵢⱼ = cᵢⱼ − uᵢ − vⱼ.
- Em minimização, todos os Pᵢⱼ ≥ 0 confirmam a otimalidade.
5.7 / aplicação computacional
Resolução no Excel Solver e em Python
Planilha e Solver
- Organizar uma matriz 2 × 3 com as quantidades transportadas (variáveis de decisão).
- Registrar, em outra matriz, os custos unitários de cada rota.
- Calcular as somas das linhas (utilização das fontes) e colunas (atendimento dos destinos).
- Calcular o custo total com SOMARPRODUTO entre custos e quantidades.
- No Solver, minimizar o custo total, alterando as seis variáveis, impondo as cinco igualdades e a não negatividade; escolher o método Simplex LP.
Python com SciPy
O solver poderá retornar qualquer uma das distribuições ótimas. Os valores das variáveis podem diferir, mas o custo ótimo será 340.
checkpoint
Teste rápido
Qual condição é necessária para utilizar a formulação clássica equilibrada com igualdades?
Qual é a principal diferença entre os métodos do Canto Noroeste e do Custo Mínimo?
Em um problema de minimização, o que significa um custo reduzido negativo para uma célula não básica?
síntese final / roteiro de resolução
Resumo: do quadro inicial à solução ótima
O problema de transporte procura minimizar o custo de distribuição, respeitando as capacidades das origens e as demandas dos destinos. A resolução manual pode ser organizada em três operações repetidas: avaliar → selecionar → ajustar.
Definir xᵢⱼ, custos cᵢⱼ, ofertas aᵢ e demandas bⱼ. Conferir o equilíbrio entre oferta e demanda.
Obter uma solução viável pelo Canto Noroeste ou pelo Custo Mínimo. Calcular Z.
Para cada célula não básica, construir um ciclo fechado e calcular a variação unitária ΔZ.
Se houver ΔZ negativo, escolher uma rota de melhoria, preferencialmente a mais negativa.
Determinar θ pelo menor fluxo nas posições negativas, atualizar o quadro e repetir o teste.
Quando todas as variações forem não negativas, a solução é ótima. ΔZ = 0 pode indicar outra solução ótima.
| Exemplo | Canto Noroeste | Custo ótimo | Economia |
|---|---|---|---|
| 2 depósitos × 2 centros | 124,00 | 124,00 | 0,00 |
| 3 depósitos × 2 centros | 260,00 | 240,00 | 20,00 |
| Andrade: 2 fontes × 3 destinos | 370,00 | 340,00 | 30,00 |
Os exemplos e os métodos apresentados no desenvolvimento principal foram adaptados didaticamente da referência de Eduardo L. de Andrade, Pesquisa Operacional, a partir das páginas fornecidas, sem reprodução integral do texto original.