Das Transportproblem
Gegeben sei ein homogener Stoff, der zu transportieren ist. Homogen bedeutet dabei beliebig
oft teilbar.
Es seien Versandorte mit den jeweiligen Vorräten
,
und es seien Empfangsorte mit dem Bedarf
gegeben.
Es bezeichne die Menge des Stoffs, die von dem Versandort
zum Empfangsort transportiert
werden soll; es seien die Kosten, die beim Transport des Stoffs
von nach pro Mengeneinheit entstehen.
Die Modellierung dieses
Transportproblems ergibt ein lineares Optimierungsproblem.
Transportproblem: Gesucht sind die zu transportierenden Mengen
, so dass
|
(7)
|
|
|
und
|
|
|
(8)
|
|
(9)
|
Zur Interpretation der Ausdrücke: (7) ist
die Zielfunktion, die verlangt, dass die Transportkosten aller Wege so gering
wie möglich sind. (8) verlangt, dass alle Vorräte verbraucht und alle
Bedarfsgrößen gedeckt werden. (9) kennzeichnet, dass keine
Rücktransporte möglich sind.
Unter der Bedingung
|
(10)
|
heisst das Transportproblem ausgeglichenes Transportproblem. Die
Bedingung (10) ist notwendig und hinreichend für die Existenz einer
Lösung des vorliegenden linearen Optimierungsproblems.
Gilt die Bedingung (10), so lässt sich eine zulässige Lösungsmenge
bestimmen mit
.
Bei Voraussetzung der Ganzzahligkeit der Werte
und
besitzt das Transportproblem sogar stets eine ganzzahlige optimale Lösung, unabhängig von den Koeffizienten der
Zielfunktion, den Transportkosten .
|