|
Das Transportproblem
Gegeben sei ein homogener Stoff, der zu transportieren ist. Homogen bedeutet dabei beliebig
oft teilbar.
Es seien m Versandorte mit den jeweiligen Vorräten vi
(i = 1,…,m), und es seien n Empfangsorte mit dem Bedarf
bj
(j = 1,…,n) gegeben.
Es bezeichne xij die Menge des Stoffs, die von dem Versandort
i zum Empfangsort j transportiert
werden soll; es seien cij die Kosten, die beim Transport des Stoffs
von i nach j pro Mengeneinheit entstehen.
Die Modellierung dieses
Transportproblems ergibt ein lineares Optimierungsproblem.
Transportproblem: Gesucht sind die zu transportierenden Mengen
xij, so dass
m
∑
i = 1
|
n
∑
j = 1
|
cij xij
= Min!
|
(7)
|
n
∑
j = 1
|
xij = vi
|
i = 1,…,m
|
und
|
m
∑
i = 1
|
xij = bj
|
j = 1,…,n
|
(8)
|
n
∑
j = 1
|
xij ≥ 0
|
i = 1,…,m
|
j = 1,…,n
|
(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
m
∑
i = 1
|
vi
|
=
|
n
∑
j = 1
|
bj
|
=:
|
S
|
(10)
|
heisst das Transportproblem ausgeglichenes Transportproblem. Die
Bedingung (10) ist notwendig und hinreichend für die Existenz einer
Lösung des vorliegenden linearen Optimierungsproblems. Eine zulässige Lösung
bei Gültigkeit von (10) ist z.B.
xij =
(vi·bj)/S.
Bei Voraussetzung der Ganzzahligkeit der Werte
v1,…,vm und
b1,…,bn besitzt das Transportproblem
sogar stets eine ganzzahlige optimale Lösung, unabhängig von den Koeffizienten der
Zielfunktion, den Transportkosten cij.
|