Wegen x ijt > 0; <s = 1, 2, . . . , r gibt es Werte d > 0, so daß alle Koeffi zienten von in (3.22) nicht negativ sind. Wegen (3.18), (3.19) existiert wenigstens ein x kl vjv > 0. Wählen wir d — d 0 so, daß d 0 = min ; für alle s mit x k t l jt > 0 (3.24) s x isj» x iv3v gilt, dann verschwindet ein Koeffizient von (3.22), und zwar der von Für alle x hÜ x iyjv kl kl x iij> x iy3v sind die Koeffizienten (x iijt — d 0 x*^ > 0 und für alle x£ l jt < 0 sind sie wegen d 0 > 0 auch positiv. Durch diese Wahl von d = d 0 haben wir somit eine neue zulässige Basis lösung erhalten, die sich von der vorigen dadurch unterscheidet, daß jetzt x iv j r = 0 ist und daß die Variable x kl nun mit einem positiven Wert, nämlich mit d 0 belegt worden ist. Die Werte der übrigen positiven Komponenten sind = (x it j t — d 0 ^j^. Wird das Minimum d 0 = —^7— für mehrere v ange- X iy jv nommen, dann werden alle zugehörigen Koeffizienten von (3.22) null. Die neue zulässige Basislösung ist dann degeneriert. Da wir angenommen haben, daß keine degenerierte zulässige Basislösung existieren soll, kann dieser Fall nicht eintreten. Durch (3.23) sind die Gesamttransportkosten für die neue zulässige Basis lösung gegeben. Diese betragen z* = z 0 - d 0 (c kt - c H ) . (3.25) Da wir c k i > c kl angenommen haben, gilt wegen d 0 > 0 also 2* < z 0 . Damit ist der Satz 2 vollständig bewiesen. Zusammenfassend können wir sagen: Ist c k i > c k i (oder c kt — c ki > 0), dann erhält man durch Belegen von x kt mit der Zahl d 0 > 0 und gleichzeitiger Abänderung der übrigen positiven Kompo nenten der ursprünglichen zulässigen Basislösung zur Erfüllung der Neben bedingungen eine neue zulässige Basislösung, deren Gesamttransportkosten um d 0 (c kt — c k i) geringer sind als die der ursprünglichen Lösung. Man erkennt, daß die größte Verbesserung dann erreicht wird, wenn die Unbekannte x kt neu mit einem positiven Wert belegt wird, für die d 0 (Cki ~ Cki) = niax d 0 (c i} - c tj ) für alle i, j mit c,j — > 0 ist. Da aber d 0 je nach der neu zu belegenden Variablen verschiedene Werte annimmt, erfordert dieses Kriterium umfang-
