Calculadora do Problema de Transporte (Canto Noroeste, Custo Mínimo e MODI)
Calcule a Solução Básica Inicial Viável pelos métodos do Canto Noroeste ou Custo Mínimo, e otimize os custos de transporte com o método MODI.
| D1 | D2 | D3 | Oferta | |
|---|---|---|---|---|
| S1 | ||||
| S2 | ||||
| S3 | ||||
| Demanda |
O Problema de Transporte: Canto Noroeste, Custo Mínimo e Método MODI
Guia acadêmico completo para modelagem de transporte, determinação de soluções básicas factíveis e otimização global com o algoritmo MODI (u-v).
1. Qual problema o Modelo de Transporte resolve?
O Problema de Transporte é uma especialização da Programação Linear formulada para encontrar o plano de distribuição de menor custo entre m origens de oferta (fábricas, armazéns) e n destinos de demanda (centros de distribuição, lojas). Quando a oferta total iguala a demanda total (∑ sᵢ = ∑ dⱼ), o sistema é dito balanceado. O objetivo é minimizar Z = ∑∑ cᵢⱼ xᵢⱼ respeitando as restrições de fluxo.
2. Metodologia de Resolução: Da Viabilidade Inicial ao Ótimo
Alocação sistemática partindo da célula (1, 1). Aloca min(s₁, d₁), esgota a linha ou coluna e desloca-se para a direita ou para baixo. Ignora custos unitários, servindo como uma solução viável rápida, mas raramente econômica.
Abordagem gulosa (greedy) que prioriza a rota livre de menor custo unitário cᵢⱼ. Ao alocar primeiro nos trechos mais baratos, geralmente produz um custo inicial muito próximo do ótimo global.
Equivalente dual do método Simplex para redes. Utilizando a igualdade uᵢ + vⱼ = cᵢⱼ nas células básicas, calcula os potenciais uᵢ e vⱼ. Em seguida, obtém os custos de oportunidade Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) para células vazias. Se todos os Δᵢⱼ ≥ 0, a solução é ótima; caso contrário, monta-se um ciclo fechado para redistribuir cargas.
3. Exemplo Acadêmico Resolvido: 3 Origens × 3 Destinos
Compare os métodos iniciais e confirme o valor ótimo exato obtido pela calculadora.
| Origin / Destination | Destination 1 (D₁) | Destination 2 (D₂) | Destination 3 (D₃) | Supply Capacity |
|---|---|---|---|---|
| Origem 1 (S₁) | R$ 8 | R$ 4 | R$ 12 | 100 |
| Origem 2 (S₂) | R$ 10 | R$ 5 | R$ 6 | 300 |
| Origem 3 (S₃) | R$ 7 | R$ 8 | R$ 15 | 300 |
| Demand Requirement | 300 | 200 | 200 | 700 |
A. Resolução pelo Canto Noroeste
Início em (S₁, D₁): aloca min(100, 300) = 100. S₁ esgota. Desce para (S₂, D₁): aloca min(300, 200) = 200. D₁ é atendido. Move para (S₂, D₂): aloca min(100, 200) = 100. S₂ esgota. Desce para (S₃, D₂): aloca min(300, 100) = 100. D₂ é atendido. Move para (S₃, D₃): aloca os 200 restantes.
B. Resolução pelo Custo Mínimo
1. Menor custo na célula (S₁, D₂) com R$ 4: aloca min(100, 200) = 100. S₁ esgota. 2. Próximo menor custo em (S₂, D₂) com R$ 5: aloca min(300, 100 restantes) = 100. D₂ é atendido. 3. Célula (S₂, D₃) com R$ 6: aloca min(200 restantes, 200) = 200. S₂ e D₃ são atendidos. 4. Célula (S₃, D₁) com R$ 7: aloca min(300, 300) = 300. S₃ e D₁ são atendidos.
C. Verificação de Otimalidade pelo Método MODI
Avaliando as células básicas (S₁, D₂), (S₂, D₂), (S₂, D₃) e (S₃, D₁), os índices de oportunidade Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) resultam todos maiores ou iguais a zero (Δᵢⱼ ≥ 0). Como não há valores negativos, a alocação de Custo Mínimo é confirmada como ótimo global.
Análise de Eficiência: Economia de R$ 2.900
A simples escolha do Método do Custo Mínimo reduz os gastos de R$ 7.100 para R$ 4.200 — economia direta de R$ 2.900 (redução de 40,8%) antes mesmo de iterar com circuitos de compensação.
4. Erros Comuns em Avaliações Acadêmicas
Esquecer de Balancear Oferta e Demanda
Se a oferta for maior que a demanda, crie um destino fictício com custo zero. Se a demanda for maior, adicione uma origem fictícia.
Degeneração da Base (Menos de m + n - 1 Células)
A base exige exatamente m + n - 1 células alocadas (aqui, 3 + 3 - 1 = 5). Caso ocorra empate e duas variáveis saiam simultaneamente, introduza um valor infinitesimal ε para viabilizar o cálculo de u e v.
Circuitos Fechados Inválidos
O circuito de melhoria só pode realizar curvas de 90 graus sobre células que já pertencem à base. Fazer vértices em células vazias invalida a operação.