Nord-Westecken-Verfahren

Das Nord-West-Ecken-Verfahren führt zu einer zulässigen Ausgangslösung für Transportprobleme. Hierbei wird die Mengenmatrix herangezogen. Das Ziel dieses Verfahrens ist es, die Angebotsmenge so auf die Warenhäuser zu verteilen, dass deren Nachfrage komplett abgedeckt wird. Die Kosten des Transports werden hierbei nicht berücksichtigt. Die Minimierung der Kosten erfolgt dann später bei den Optimierungsverfahren. Die Mengenmatrix für das Beispiel sieht wie folgt aus:

Innerhalb der Matrix werden die Kosten der redzuierten Kostenmatrix (sofern eine Reduktion vorgenommen worden ist, sonst der Ausgangskostenmatrix) an die obere rechte Ecke geschrieben. Dies dient der Übersicht halber bei der späteren Summation der Kosten. Die Mengen die transportiert werden sind zunächst leer und werden mittels des folgenden Algorithmus bestimmt:

Nach Anwendung des Algorithmus für das Nord-West-Ecken-Verfahren ergibt sich das folgende Tableau mit zulässiger Ausgangslösung:

Es wurde wie folgt vorgegangen:

Für $x_{11}$:

$a_1 > b_1$ (900 > 300). Schritt 1: $x_{11} = b_1 = 300$. Waagerecht weiter.

Für $x_{12}:

$a_1 - x_{11} > b_2$ (600 > 500). Schritt 1: $x_{12} = b_2 = 500$. Waagerecht weiter.

Für $x_{13}$:

$a_1 - x_{11} - x_{12} < b_3$ (100 < 400). Schritt 2: $x_{13} = a_1 - x_{11} - x_{12} = 100$. Senkrecht weiter.

Für $x_{23}$:

$a_2 > b_3 - x_{13}$ (800 > 300). Schritt 1: $x_{23} = b_3 - x_{12} = 300$. Waagerecht weiter.

Für $x_{24}$:

$a_2 - x_{23} < b_4$ (500 < 600). Schritt 2: $x_{24} = a_2 - x_{23} = 500$. Senkrecht weiter.

Für $x_{34}$:

$a_3 > b_4 - x_{24}$ (400 > 100). Schritt 1: $x_{34} = b_4 - x_{24} = 100$. Waagerecht weiter.

Für $x_{35}$:

$a_3 - x_{34} = b_5$ (300 = 300). Schritt 3: $x_{35} = a_3 - x_{34} = b_5 = 300$. ENDE

Es ist immer wichtig, dass nachdem eine Transportmenge von der Fabrik zum Warenhaus festgelegt worden ist, diese beim weiteren Vorgehen zu berücksichtigen, denn die Angebots- und Nachfragemenge verringert sich um diese festgelegte Transportmenge. So ist zum Beispiel bei der Festlegung von $x_{11} = 300$ Mengen für die weitere Betrachtung die Angebotsmenge $a_1$ um diese Menge zu reduzieren, da von Fabrik 1 diese 300 Mengen schon für den Nachfrageort 1 verplant sind. Genauso wird auch für den Nachfrageort 1 für die nachfolgenden Betrachtungen diese Menge von der Nachfragemenge $b_1$ abgezogen. Je mehr Mengen bereits festgelegt wurden, desto mehr Mengen müssen berücksichtigt werden. Zur besseren Übersicht kann man die Angebots- und Nachfragemenge auch an der Seite durchstreichen und die aktuelle Menge daneben schreiben:

Es liegt nun eine zulässige Ausgangslösung vor. Die gesamten reduzierten Transportkosten für diese Ausgangslösung betragen:

$K_R = 300 \cdot 0 + 500 \cdot 10 + 100 \cdot 30 + 300 \cdot 0 + 500 \cdot 30 + 100 \cdot 20 + 300 \cdot 60 = 43.000$.

Hierbei handelt es sich um die Kosten der reduzierten Kostenmatrix. Diese können zum Vergleich der anderen Eröffnungsverfahren herangezogen werden. Für die anderen Eröffnungsverfahren (die nun folgen) müssen zum Vergleich der zulässigen Ausgangslösung dann aber ebenfalls die reduzierten Kosten herangezogen werden. Das Eröffnungsverfahren mit den geringsten Kosten besitzt die beste Ausgangslösung.

Die tatsächlichen Kosten (Ausgangskostenmatrix) für den obigen Transport betragen:

$K = 300 \cdot 140 + 500 \cdot 130 + 100 \cdot 170 + 300 \cdot 140 + 500 \cdot 180 + 100 \cdot 170 + 300 \cdot 190 = 330.000$.