Wir erhalten hier vorerst *&11 ~ 1 ; 12 = ’ *^22 = 1 • Dann ist aber a 2 = b 3 = 3 . Es ist also a: 2 3 = 3 zu setzen, und die zweite Zeile und die dritte Spalte sind anzuhaken. Das Verfahren geht nun weiter mit der Bestimmung von min (a 3 , b t ). Wir haben hier eine degenerierte Lösung erhalten, die nur m + n — 2 = 3 + 5 — 2 = 6 positive Komponenten enthält. Man überlegt sich leicht, daß sich die im Laufe des Verfahrens entstehenden neuen a { und bj durch Partialsummen der ursprünglichen ausdrücken lassen. Degeneration kann andererseits höchstens dann eintreten, wenn für irgend ein festes v und ein festes /i das neue a v gleich dem neuen b /t ist, wenn also die im Ausgangsort v noch vorrätige Restmenge gleich ist dem Restbedarf des Bestimmungsortes /.i. Degeneration kann also höchstens dann eintreten, wenn wenigstens eine Partialsumme der gleich ist einer Partialsumme der bj. In unserem in Tab. 5 untersuchten Beispiel ist a i + «2 == + ^2 + ^3 = 7 • Bei der Nordwesteckenregel haben wir die Einheitstransportkosten c,j der Aufgabe überhaupt nicht benutzt. Dieses Verfahren liefert somit unabhängig von den c^j für alle Probleme gleicher Dimension (m, n) und mit gleichen a,- und bj die gleiche Ausgangslösung. Es erscheint aber als vorteilhaft, schon bei der Bestimmung der Ausgangslösung im Hinblick auf die geforderte Mini mierung der Gesamttransportkosten, auf die Einheitstransportkosten zu achten. Die folgenden beiden Verfahren zur Bestimmung einer zulässigen Basislösung besetzen deshalb nach bestimmten Gesichtspunkten ausgewählte Felder, zu denen kleine Einheitstransportkosten gehören, mit positiven Werten. Es muß jedoch ausdrücklich bemerkt werden, daß man von keiner dieser Methoden beweisen kann, daß sie im allgemeinen eine Ausgangslösung mit geringeren Transportkosten liefert als die Nordwesteckenregel oder eines der anderen Verfahren. 3.2.2. Methode des Zeilenminimums Für diese Methode zur Bestimmung einer ersten zulässigen Basislösung, die wir uns wieder in Tab. 2 durchgeführt denken, benötigen wir jetzt die in Tab. 1 gegebenen Einheitstransportkosten. Wir bestimmen das kleinste Element c xk der ersten Zeile in Tab. 1. (Gibt es mehrere c 13 - = c lk , dann wählen wir das Element mit dem kleinsten Spaltenindex.) a) Ist a, <; b k , dann setzen vir in Tab. 2 in das Feld für x lk die Zahl a k ein, ersetzen b k durch b k — a x und haken in Tab. 1 die Zeile 1 an.
