Modell

Ein von m Erzeugern in den Mengen produziertes Erzeugnis soll zu n Verbrauchern mit dem Bedarf transportiert werden. Die Kosten des Transportes einer Produkteinheit vom Erzeuger E_i zum Verbraucher V_j betragen . Von E_i werden x_ij Produkteinheiten zu V_j transportiert. Gesucht ist eine, die Transportkosten minimierende Aufteilung der Erzeugnisse auf die Verbraucher. Es wird vorausgesetzt, daß die Gesamtkapazität der Erzeuger gleich dem Gesamtverbrauch ist, d.h.

Man bildet die Kostenmatrix und die Verteilungsmatrix :

Ist die Bedingung (18.23) nicht erfüllt, dann werden zwei Fälle unterschieden:

1. Für wird ein fiktiver Verbraucher V_n+1 mit dem Bedarf und den Transportkosten c_i,n+1 = 0 eingeführt.
2. Für wird ein fiktiver Erzeuger E_m+1 mit der Kapazität und den Transportkosten c_m+1,j = 0 eingeführt. Zur Bestimmung eines optimalen Verteilungsplanes ist das folgende Optimierungsproblem zu lösen:

   Das Minimum dieses Problems wird in einer Ecke des zulässigen Bereiches angenommen. Von den m+n Nebenbedingungen sind m + n - 1 linear unabhängig, so daß eine Ecke im nicht entarteten Fall, der hier vorausgesetzt werden soll, m + n - 1 positive Komponenten x_ij besitzt. Die folgende Bestimmung eines optimalen Verteilungsplanes wird als Transportalgorithmus bezeichnet.