Calculadora del Problema de Transport (Cantonada Nord-oest, Cost Mínim i MODI)

Calcula la Solució Bàsica Factible Inicial amb els mètodes de la Cantonada Nord-oest o Cost Mínim, i optimitza la distribució amb el mètode de potencials MODI.

3
3
D1D2D3Oferta
S1
S2
S3
Demanda
Optimització de Xarxes i Cadena de Subministrament

El Problema de Transport: Cantonada Nord-oest, Cost Mínim i Mètode MODI

Guia acadèmica completa per modelar xarxes de distribució, trobar solucions bàsiques factibles inicials i assolir el mínim global amb l'algorisme MODI (u-v).

1. Quin problema resol el Model de Transport?

El Problema de Transport és una especialització de la Programació Lineal dissenyada per determinar el pla d'enviament més econòmic entre m orígens d'oferta (fàbriques, magatzems) amb capacitats conegudes, i n destinacions de demanda (botigues, mercats) amb necessitats fixades. Quan l'oferta total és igual a la demanda total (∑ sᵢ = ∑ dⱼ), el model és balancejat. L'objectiu matemàtic és minimitzar el cost total Z = ∑∑ cᵢⱼ xᵢⱼ subjecte a restriccions de conservació de flux.

2. Metodologia de Resolució: De la Factibilitat Inicial a l'Òptim

Solució Bàsica Factible Inicial (SBFI)
Mètode de la Cantonada Nord-oest (NWC)

Assignació geomètrica que comença a la cel·la superior esquerra (1, 1). Assigna min(s₁, d₁), esgota fila o columna i avança cap a la dreta o cap avall. No té en compte els costos de transport, proporcionant una base ràpida però rarament òptima.

Solució Bàsica Factible Inicial (SBFI)
Mètode del Cost Mínim (Least Cost)

Algorisme voraç (greedy) que prioritza assignar la quantitat màxima possible a la ruta lliure amb menor cost unitari cᵢⱼ. En utilitzar primer les rutes més econòmiques, sol aproximar-se notablement a l'òptim global.

Algorisme Exacte d'Optimalitat
Mètode MODI (Distribució Modificada / u-v)

Versió dual del mètode Simplex aplicada a xarxes. Mitjançant la condició uᵢ + vⱼ = cᵢⱼ a les cel·les bàsiques (ocupades), calcula els multiplicadors uᵢ i vⱼ. Seguidament avalua els costos d'oportunitat Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) a les cel·les buides. Si tots els Δᵢⱼ ≥ 0, la solució és òptima global. Si n'hi ha de negatius, es construeix un cicle tancat (stepping-stone) per redistribuir unitats.

3. Exemple Acadèmic Resol: 3 Orígens × 3 Destinacions

Compara els mètodes inicials i verifica la solució òptima exacta del nostre motor.

Supply: Orígens S₁, S₂, S₃ amb capacitats de 100, 300 i 300 unitats.
Demand: Destinacions D₁, D₂, D₃ amb demandes de 300, 200 i 200 unitats.
Oferta Total = 700 unitats | Demanda Total = 700 unitats (Model Equilibrat).
Origin / DestinationDestination 1 (D₁)Destination 2 (D₂)Destination 3 (D₃)Supply Capacity
Origen 1 (S₁)8 €4 €12 €100
Origen 2 (S₂)10 €5 €6 €300
Origen 3 (S₃)7 €8 €15 €300
Demand Requirement300200200700

A. Desenvolupament per Cantonada Nord-oest

Comencem a (S₁, D₁): assignem min(100, 300) = 100. S₁ queda esgotat. Baixem a (S₂, D₁): assignem min(300, 200) = 200. D₁ queda satisfet. Ens movem a (S₂, D₂): assignem min(100, 200) = 100. S₂ queda esgotat. Baixem a (S₃, D₂): assignem min(300, 100) = 100. D₂ queda satisfet. Ens movem a (S₃, D₃): assignem els 200 restants.

Cost Total Cantonada Nord-oest = (100 × 8) + (200 × 10) + (100 × 5) + (100 × 8) + (200 × 15) = 800 + 2.000 + 500 + 800 + 3.000 = 7.100 €.

B. Desenvolupament per Cost Mínim

1. Menor cost global a la cel·la (S₁, D₂) amb 4 €: assignem min(100, 200) = 100. S₁ s'esgota. 2. Següent menor cost disponible a (S₂, D₂) amb 5 €: assignem min(300, 100 restants) = 100. D₂ queda satisfet. 3. Cel·la (S₂, D₃) amb 6 €: assignem min(200 restants, 200) = 200. S₂ i D₃ queden satisfets. 4. Cel·la (S₃, D₁) amb 7 €: assignem min(300, 300) = 300. S₃ i D₁ queden satisfets.

Cost Total Cost Mínim = (100 × 4) + (100 × 5) + (200 × 6) + (300 × 7) = 400 + 500 + 1.200 + 2.100 = 4.200 €.

C. Verificació d'Optimalitat amb MODI

En avaluar les cel·les bàsiques (S₁, D₂), (S₂, D₂), (S₂, D₃) i (S₃, D₁), els índexs marginals Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) resulten tots majors o iguals a zero (Δᵢⱼ ≥ 0). No hi ha costos d'oportunitat negatius; per tant, la solució de Cost Mínim és l'òptim global exacte.

Cost Òptim Global = 4.200 € (Coincideix exactament amb el resultat de la calculadora).

Anàlisi d'Eficiència: Estalvi de 2.900 €

Triant el mètode de Cost Mínim enfront de la Cantonada Nord-oest, el cost baixa de 7.100 € a 4.200 €, assolint un estalvi immediat de 2.900 € (un 40,8 % de reducció) abans de començar les iteracions.

4. Errors Freqüents d'Estudiants en Exàmens

⚠

No Comprovar el Balanç Oferta-Demanda

Si l'oferta total supera la demanda, s'ha d'afegir una destinació fictícia amb cost de transport zero. Si la demanda supera l'oferta, cal afegir un origen fictici.

⚠

Degeneració a la Base (Menys de m + n - 1 Cel·les)

Qualsevol base necessita exactament m + n - 1 cel·les ocupades (aquí, 3 + 3 - 1 = 5). Si s'esgoten fila i columna alhora, cal assignar una quantitat infinitesimal ε a una cel·la buida per poder calcular els potencials uᵢ i vⱼ.

⚠

Tirar Camins Tancats Incorrectes a MODI

El cicle tancat stepping-stone només pot fer canvis de sentit (girar 90 graus) en cel·les bàsiques ocupades. Girar en cel·les buides invalida el pivotatge Simplex.