Nord-West-Ecken-Verfahren

Nord-West-Ecken-Verfahren Definition

Das Nord-West-Ecken-Verfahren bestimmt eine zulässige Lösung des Transportproblems (d.h. eine mögliche Zuordnung von Transportmengen zwischen Quell- und Zielorten).

Das ist nur eine mögliche Lösung, keine optimale (kostengünstigste); das Transportproblem wird dadurch nicht gelöst, das Ergebnis kann aber anschließend an einen anderen Algorithmus zum Weiterrechnen gegeben werden (damit dieser sich leichter tut).

Alternative Begriffe: Nord-West-Ecken-Methode, Nord-West-Ecken-Regel, Nordwest-Ecken-Methode, Nordwesteckenregel.

Beispiel

Beispiel: Nord-West-Ecken-Verfahren

Das Beispiel zum Transportproblem war:

Es gibt 3 Quellorte Q1, Q2 und Q3, die z.B. jeweils folgende Mengen produzieren bzw. liefern (können), z.B. 100, 200 und 300 Stück.

Es gibt 3 Zielorte Z1, Z2 und Z3, die jeweils eine bestimmte Menge benötigen: 250, 200 und 150 Stück (Liefer- und Nachfragemengen stimmen in Summe überein: 600 Stück).

Die Entfernungen zwischen den Quell- und Zielorten in km sind:

Entfernungstabelle
Z1 Z2 Z3
Q1 1 8 6
Q2 5 3 7
Q3 9 4 2

Die Tabelle hat 9 Felder. Für 5 Felder (Anzahl der Quellorte + Anzahl der Zielorte - 1 = 3 + 3 - 1 = 5) wird ausgehend von der nord-westlichen Ecke (links oben in der Tabelle) hin zur süd-östlichen Ecke (rechts unten) mit der maximalen Transportmenge geplant.

Diese Transportmengen werden hier in Klammern gesetzt:

Entfernungstabelle
Z1 Z2 Z3
Q1 1 (100) 8 6
Q2 5 (150) 3 (50) 7
Q3 9 4 (150) 2 (150)

Erläuterung

Links oben beginnen: Q1 liefert die maximale Menge von 100 Stück an Z1 (damit ist seine Lieferkapazität von 100 erschöpft, Z1 hat nur 100 von 250 benötigten bekommen).

Q2 liefert die maximale noch ausstehende Menge von 150 Stück an Z1 (damit ist seine Lieferkapazität von 200 um 150 gemindert), Z1 hat damit in Summe 250, d.h. alle benötigten Stück, bekommen.

Q2 liefert 50 Stück an Z2 (soviel er noch kann).

Q3 liefert die maximale noch ausstehende Menge von 150 Stück an Z2 (damit hat Z2 nun seine benötigten 200 Stück in Summe) und Q3 liefert seine restlichen 150 Stück an Z3.

Alle produzierten Güter wurden verteilt, alle haben ihre benötigten Stückzahlen bekommen; das ist deshalb eine mögliche, zulässige Lösung. Sie ist nicht kostenoptimal (die Entfernungen in km wurden bei der Methode gar nicht berücksichtigt).