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.
| D1 | D2 | D3 | Oferta | |
|---|---|---|---|---|
| S1 | ||||
| S2 | ||||
| S3 | ||||
| Demanda |
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
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.
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.
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.
| Origin / Destination | Destination 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 Requirement | 300 | 200 | 200 | 700 |
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.
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.
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.
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.