Glossar · approach
Northwest-Corner-Regel
Die einfachste klassische Heuristik, um eine erste zulässige Basislösung des Transportproblems zu erzeugen: vom oberen-linken Ende der Kostenmatrix ausgehend so viel wie möglich der aktuellen Zelle zuweisen und nach rechts oder nach unten verschieben, bis Angebot und Nachfrage erschöpft sind.
Northwest Corner RuleNWCNordwest-Ecken-Regel
Die Northwest-Corner-Regel ist die einfachste klassische Heuristik zur Erzeugung einer ersten zulässigen Basislösung des Transportproblems: Starte in der oberen-linken (Nordwest-) Ecke der Kostenmatrix, weise der aktuellen Zelle so viel wie möglich zu (das Minimum aus verbleibendem Angebot oder verbleibender Nachfrage), bewege dich dann nach rechts (wenn noch Angebot übrig ist) oder nach unten (wenn noch Nachfrage übrig ist) und wiederhole, bis alle Zeilen- und Spaltensummen erfüllt sind. Die resultierende Lösung ist zulässig, aber meist weit vom Optimum entfernt — sie ignoriert die Kostenmatrix vollständig und arbeitet nur nach Position. Das Optimum wird durch MODI / Stepping-Stone oder direkt durch Simplex erreicht. Pädagogischer Wert: Sie zeigt das Konzept der 'zulässigen Basis-Startlösung' hinter Simplex und ist ein Sprungbrett zu klügeren Starts wie der Vogel-Approximationsmethode (VAM). Ausführlich bei Bazaraa-Jarvis-Sherali (2010).
Örnek
3 Werke (Kapazitäten 20, 30, 25 Tonnen) × 4 Kunden (Bedarf 15, 20, 18, 22 Tonnen). NWC startet links oben: Zelle (1,1) erhält min(20,15)=15 t; dann (1,2) erhält min(5,20)=5 t; (2,2) erhält min(30,15)=15 t; (2,3) erhält min(15,18)=15 t; (3,3) erhält min(25,3)=3 t; (3,4) erhält min(22,22)=22 t. Insgesamt 75 t zugeordnet; die Startlösung steht, dann Optimierung mit MODI oder Simplex.