Nord-West-Ecken-Verfahren

Das Nord-West-Ecken-Verfahren ist ein heuristisches Verfahren aus dem Operations Research, das eine zulässige Ausgangslösung für das Transportproblem liefern soll. Von dieser Lösung aus startet der Optimierungsalgorithmus des Transportproblems.

Algorithmus

Dabei schaut man von der oberen linken Ecke der Matrix ausgehend, ob man in dem aktuellen Feld eine Kapazität ausschöpfen oder einen Bedarf befriedigen kann.

$c(i,j)=min(B(j),K(i))$

Wenn der Bedarf dieser Zeile gedeckt ist, sucht man in der Spalte abwärts nach dem nächsten Feld, bei dem eins der beiden Kriterien erfüllt werden kann. Wurde die Kapazität der Spalte ausgeschöpft, dann sucht man in der Zeile weiter. Wurde beides voll belegt, dann geht man ein Feld diagonal nach rechts unten weiter.

Effizienz

Das Nord-West-Ecken-Verfahren liefert ein Ausgangstableau, das häufig sehr viele weitere Iterationen des Lösungsalgorithmus bis zur optimalen Lösung erfordert.

Beispiel

Das Verfahren wird anhand des Beispiels im Artikel über das Transportproblem gezeigt. Grundlage ist das Gleichungssystem

$x_{11}+x_{12}+x_{13}=16$

$x_{21}+x_{22}+x_{23}=14$

$x_{11}+x_{21}=15$

$x_{12}+x_{22}=5$

$x_{13}+x_{23}=10$

wobei es zwei Angebote A₁ und A₂ und drei Bedarfsanmeldungen B₁, B₂ und B₃ gibt. x_ij bezeichnet hier die von i nach j gelieferte Menge. Man kann das Gleichungssystem tabellarisch zusammenfassen als
${\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}&\\\hline A_{1}&x_{11}&x_{12}&x_{13}&16\\A_{2}&x_{21}&x_{22}&x_{23}&14\\\hline &15&5&10&30\\\end{array}}$

Für die Nord-West-Eckenlösung wird nun zuerst möglichst viel in die Nord-West-Ecke gepackt. A₁ liefert also 15 Einheiten an B₁. A₁ hat noch eine Einheit übrig, die an B₂ geliefert wird. Den restlichen Bedarf von B₂ deckt A₂ mit 4 Einheiten. A₂ hat noch 10 Einheiten übrig, welche an B₃ gehen. Man erhält nun
${\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}&\\\hline A_{1}&15&1&0&16\\A_{2}&0&4&10&14\\\hline &15&5&10&30\\\end{array}}$

Durch die Ausgangslösung wurde eine gültige Basislösung erreicht. Die Variablen mit positiven Mengen sind die Basisvariablen, Variablen mit Null sind Nichtbasisvariablen. Das ersieht man auch, wenn man das obige Gleichungssystem als Tableau hinschreibt:
${\begin{array}{ccccccc}x_{11}&x_{12}&x_{13}&x_{21}&x_{22}&x_{23}&b\\\hline 1&1&1&0&0&0&16\\0&0&0&1&1&1&14\\1&0&0&1&0&0&15\\0&1&0&0&1&0&5\\0&0&1&0&0&1&10\\\end{array}}$

Werden die Vektoren unter x₁₁, x₁₂, x₂₂ und x₂₃ zu Basisvektoren umgeformt, ergibt sich das Tableau
${\begin{array}{ccccccc}x_{11}&x_{12}&x_{13}&x_{21}&x_{22}&x_{23}&b\\\hline 1&0&0&1&0&0&15\\0&0&-1&1&1&0&4\\0&1&1&-1&0&0&1\\0&0&1&0&0&1&10\\0&0&0&0&0&0&0\\\end{array}}$

welches die Nord-West-Eckenlösung wiedergibt.

Literatur

• Gert Heinrich: Operations Research, Oldenbourg, 2. Auflage, S. 59–61.web
• Bodo Runzheimer: Operations Research 1: Lineare Planungsrechnung und Netzplantechnik, S. 96–98.web