Ein Algorithmus zum Transportproblem in zwei Variationen

Ein Algorithmus zur Ermittlung einer suboptimalen Lösung für das geschlossene Transportproblem durch Berechnung und Auswertung der Kostendifferentialquotienten in zwei Variationen

Das geschlossene Transportproblem läßt sich folgendermaßen beschreiben: I Produktionsstandorte sollen J Abnehmerzentren mit einem Transportgut beliefern, so daß die Gesamttransportkosten möglichst minimal werden. Die Transportkosten je Mengeneinheit von jedem Produktionsstandort zu jedem Abnehmerzentrum sind bekannt. Die Summe der Bedarfe der Abnehmerzentren sei dabei gleich der Summe der Aufkommen der Produktionsstandorte. Gesucht ist die jeweils von jedem Produktionsstandort zu jedem Abnehmerzentrum zu transportierende Menge des Transportgutes.
Der Algorithmus ist ein Eröffnungsverfahren, d. h. es wird eine zulässige Ausgangslösung erzeugt, aus der nachfolgend (z.B. mittels MODI-Methode) die optimale Lösung ermittelt werden kann. Der hier vorgestellte Algorithmus liefert im Gegensatz zu vielen anderen bekannten Verfahren stets eine Lösung, die nie schlechter als der Mittelwert aller möglichen Lösungen ist. Das wird abschließend an einem Beispiel demonstriert.

Mathematisches Modell

gegeben:
	I	Anzahl der Produktionsstandorte
	J	Anzahl der Abnehmerzentren
	a_i	Aufkommen des Produktionsstandortes i ( i = 1...I )
	b_j	Bedarf des Abnehmerzentrums j ( j = 1...J )
	c_ij	Kosten für den Transport einer Mengeneinheit vom
		Produktionsstandort i zum Abnehmerzentrum j
	X	Gesamttransportmenge
gesucht:
	x_ij	Transportmenge vom
		Produktionsstandort i zum Abnehmerzentrum j

Nebenbedingungen:

Zielfunktion:

1 Der Algorithmus bei Verwendung von Gleichgewichtsdifferentialen

1.1 Berechnung der Gleichgewichtslösung

Unter einer Gleichgewichtslösung soll im folgenden eine Lösung verstanden werden, bei welcher die Transportmenge von einem Produktionsstandort i zu einem Abnehmerzentrum j jeweils proportional zum Aufkommen des Produktionsstandortes i und zum Bedarf des Abnehmerzentrums j ist. Daraus folgt

x_ij = ( a_i · b_j ) / X ,

wodurch die Nebenbedingungen

erfüllt werden.

1.2 Berechnung der Matrix der Kostendifferentialquotienten

Es wird für alle i und j untersucht, wie sich eine differentielle Änderung der Transportmenge x_ij um dx_ij bei der Gleichgewichtslösung auf die differentielle Änderung der Gesamttransportkosten auswirkt. Eine primäre differentielle Änderung eines Transportmengenelements muß dabei durch die sekundäre differentielle Änderung aller anderen Transportmengenelemente kompensiert werden, so daß die differentiell veränderte Gleichgewichtslösung eine hinsichtlich der Nebenbedingungen zulässige Lösung bleibt (siehe Abbildung).

Aus einer primären differentiellen Änderung der Transportmenge x_ij um dx_ij erhält man für die sekundären differentiellen Änderungen der Transportmengen, die zum gleichen Produktionsstandort oder Abnehmerzentrum gehören:

Für die differentiellen Änderungen der übrigen Transportmengen gilt näherungsweise:

Diese differentiellen Änderungen der Transportmengen können als Gleichgewichtsdifferentiale bezeichnet werden, da die differentiellen Änderungen der Transportmengen proportional zu den entsprechenden Transportmengen sind.
Für die Kostendifferentialquotienten K'_ij , d. h. für die Ableitung der Gesamttransportkosten nach der primär geänderten Transportmenge, erhält man:

Durch Einsetzen der Gleichung, die zur Berechnung der Transportmengen bei der Gleichgewichtslösung verwendet wurde, erhält man:

1.3 Algorithmus zur Ermittlung der Transportmengen

Berechnung der Hilfsgrößen:
Berechnung der Matrix der Kostendifferentialquotienten:
Anwendung der Matrix-Minimum-Methode, wobei statt der Transportkosten c_ij die Transportkostendifferentialquotienten K'_ij zu verwenden sind.

2 Der Algorithmus bei Verwendung von konstanten Differentialen

2.1 Berechnung der Matrix der Kostendifferentialquotienten

Es wird für alle i und j untersucht, wie sich eine differentielle Änderung der Transportmenge x_ij um dx_ij bei einer zulässigen Lösung auf die differentielle Änderung der Gesamttransportkosten auswirkt. Eine primäre differentielle Änderung eines Transportmengenelements muß dabei durch die sekundäre differentielle Änderung aller anderen Transportmengenelemente kompensiert werden, so daß die differentiell veränderte Gleichgewichtslösung eine hinsichtlich der Nebenbedingungen zulässige Lösung bleibt (siehe Abbildung).

Die differentielle Änderung der Transportmengen soll dabei unabhängig von der Transportmenge selbst sein. Die primäre differentielle Änderung eines Transportmengenelements kann dabei rückwärts aus den sekundären differentiellen Änderung aller anderen Transportmengenelemente berechnet werden.
Bei einer primären differentiellen Änderung der Transportmenge x_ij um dx_ij erhält man für die sekundären differentiellen Änderungen der Transportmengen:

Für die primäre differentielle Änderung der Transportmenge x_ij um dx_ij erhält man:

Für die Kostendifferentialquotienten K'_ij bei Verwendung der konstanten Transportmengendifferentiale, erhält man:

Für die Auswertung kann der reduzierte Kostendifferentialquotient K'_ij^red verwendet wurden, da der erste Term in K'_ij konstant ist und damit keinen Beitrag liefert.

2.2 Algorithmus zur Ermittlung der Transportmengen

Berechnung der Hilfsgrößen:
Berechnung der Matrix der reduzierten Kostendifferentialquotienten:
Anwendung der Matrix-Minimum-Methode, wobei statt der Transportkosten c_ij die reduzierten Transportkostendifferentialquotienten K'_ij^red zu verwenden sind.

Man erhält in der Regel eine bessere Lösung, wenn nach der Bestimmung eines Transportmengenelements die reduzierten Kostendifferentialquotienten für die Restmatrix jeweils wieder neu berechnet werden.

3 Beispiel

Die Daten des folgenden Beispiels werden zunächst mittels Matrix-Minimum-Methode und anschließend durch den hier vorgestellten Algorithmus ausgewertet. Die Daten wurden dabei bewußt so gewählt, daß man mittels Matrix-Minimum-Methode zu einer schlechten Lösung kommt.

3.1 Matrix-Minimum-Methode:

Matrix der c_ij - Werte:

i \ j	1	2	3	a_i
1	3	4	5	10
2	10	7	6	1
3	12	15	100	10
b_j	10	1	10	X=21

c₁₁ = 3 => x₁₁ = 10
c₂₃ = 6 => x₂₃ = 1
c₃₂ = 15 => x₃₂ = 1
x₃₃ = 9

Gesamtkosten: K = 10 · 3 + 1 · 6 + 1 · 15 + 9 · 100 = 951

3.2 Methode der Kostendifferentialquotienten bei Verwendung von Gleichgewichtsdifferentialen

Matrix der c_ij - Werte:

Matrix der K'_ij - Werte:

i \ j	1	2	3	a_i
1	3	4	5	10
2	10	7	6	1
3	12	15	100	10
b_j	10	1	10	X=21

i \ j	1	2	3	A_i
1	70,7	37,4	-77,5	1764
2	45,0	19,5	-48,6	3507
3	-78,9	-40,9	86,3	23835
B_j	3360	4137	22176	C=12357

Anwendung der Matrix-Minimum-Methode auf die K'_ij - Werte:

K'₃₁ = -78,9 => x₃₁ = 10
K'₁₃ = -77,5 => x₁₃ = 10
x₂₂ = 1

Gesamtkosten: K = 10 · 12 + 10 · 5 + 1 · 7 = 177

3.3 Methode der Kostendifferentialquotienten bei Verwendung von konstanten Differentialen

Matrix der c_ij - Werte:

Matrix der (reduzierten) K'_ij - Werte:

i \ j	1	2	3	a_i
1	3	4	5	10
2	10	7	6	1
3	12	15	100	10
b_j	10	1	10	-

i \ j	1	2	3	A_i
1	-84	-78	-324	12
2	-54	-84	-348	23
3	-348	-324	186	127
B_j	25	26	111	-

Anwendung der Matrix-Minimum-Methode auf die K'_ij - Werte:

K'₃₁ = -348 => x₃₁ = 10
K'₂₃ = -348 => x₂₃ = 1
K'₁₃ = -324 => x₁₃ = 9
x₁₂ = 9

Gesamtkosten: K = 10 · 12 + 1 · 6 + 9 · 5 + 1 · 4 = 175
(Damit wurde sofort die optimale Lösung gefunden.)

(c) Lutz Tautenhahn 1996, 1999