Damit ergibt sich ni n m n Z = £ S c ij x ij — Z u i a i~ 2 v j bj ■ i = l j = l i = l j = l Hierin hängen die letzten beiden Summen gar nicht von den Veränderlichen x { j ab. Es kann deshalb z nur dann minimal sein, wenn gleichzeitig auch m n z = 2 S x ij i = l j=l minimal ist. Damit ist Satz 1 bewiesen. Wir setzen jetzt voraus, daß alle zulässigen Basislösungen unserer Aufgabe nicht degeneriert sind. Der Degenerationsfall kann, wie wir gesehen haben, höchstens dann eintreten, wenn wenigstens eine Partialsumme der a t - gleich einer Partialsumme der bj ist. Zur Realisierung unserer Voraussetzung brauchen wir also nur die Verschiedenheit aller Partialsummen der zu allen Partial summen der bj zu verlangen. (Wir bemerken, daß die vollständigen Summen nach Voraussetzung einander gleich sind.) Wir transformieren nun die Kostentabelle unserer Transportaufgabe so, daß die zu den positiven Komponenten der vorhandenen zulässigen Basis lösung gehörenden Cjj durch c 4 ' ; - = 0 ersetzt werden. (Am Anfang benutzen wir die nach einer der vorn besprochenen Methoden gewonnene Ausgangs lösung.) Wir müssen dazu die Zahlen u^, i — 1, 2, . . ., m und Vf, j = 1, 2, . . . ,n so bestimmen, daß für die betreffenden c i; - die Beziehungen Uj + Vj = Cjj (3.9) gelten. Das Gleichungssystem (3.9) besteht aus r = m + n — 1 Gleichungen für die m + n Unbekannten u it Vj. Es läßt sich zeigen, daß dieses System stets lösbar ist, wobei eine der Unbekannten beliebig gewählt werden kann. Die Berechnung der und Vj führen wir zweckmäßig in einer Tabelle durch. Wir legen dazu ein Tab. 2 ähnliches Schema an. In dieses tragen wir in die den positiven Komponenten der zulässigen Basislösung entsprechenden Felder die zugehörigen Cfj aus Tab. 1 ein. Anstelle der Vorratsspalte bzw. der Bedarfszeile bringen wir jetzt eine «^-Spalte bzw. eine t^-Zeile an, in die später die berechneten u { und Vj eingetragen werden. Wir gehen nun wie folgt vor: Es wird = 0 gesetzt (genau so kann man ein beliebiges oder Vj gleich d setzen, wobei d eine beliebige reelle Zahl ist). In der ersten Zeile der Tabelle muß wenigstens ein Feld besetzt sein, denn in der zulässigen Basislösung muß mindestens ein x^ > 0 vorkommen. Sind c 15 „; v n in der ersten Zeile eingetragen, dann ermitteln wir die Vj„ gemäß (3.9) zu Vj v v * Jetzt suchen wir unter den Spalten j r alle diejenigen aus, in denen außer in der ersten Zeile noch wenigstens ein weiteres Feld besetzt ist. (Man kann zeigen, daß wenigstens eine solche Spalte existiert.) Es seien dies die Spalten 3 FEH: A 317
