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.

3
3
D1D2D3Oferta
S1
S2
S3
Demanda
Otimização de Cadeia de Suprimentos e Redes

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

Solução Básica Factível Inicial (SBFI)
Método do Canto Noroeste (NWC)

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.

Solução Básica Factível Inicial (SBFI)
Método do Custo Mínimo (Least Cost)

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.

Algoritmo Exato de Otimalidade
Método MODI (Distribuição Modificada / u-v)

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.

Supply: Origens S₁, S₂, S₃ com capacidades de 100, 300 e 300 unidades.
Demand: Destinos D₁, D₂, D₃ com demandas de 300, 200 e 200 unidades.
Oferta Total = 700 unidades | Demanda Total = 700 unidades (Sistema Balanceado).
Origin / DestinationDestination 1 (D₁)Destination 2 (D₂)Destination 3 (D₃)Supply Capacity
Origem 1 (S₁)R$ 8R$ 4R$ 12100
Origem 2 (S₂)R$ 10R$ 5R$ 6300
Origem 3 (S₃)R$ 7R$ 8R$ 15300
Demand Requirement300200200700

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.

Custo Total Canto Noroeste = (100 × 8) + (200 × 10) + (100 × 5) + (100 × 8) + (200 × 15) = 800 + 2.000 + 500 + 800 + 3.000 = R$ 7.100.

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.

Custo Total Custo Mínimo = (100 × 4) + (100 × 5) + (200 × 6) + (300 × 7) = 400 + 500 + 1.200 + 2.100 = R$ 4.200.

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.

Custo Mínimo Ótimo Global = R$ 4.200 (Coincide perfeitamente com o motor de cálculo).

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.