Benutzerin:Gabriele Hornsteiner/Transport

Ein spezielles Teilgebiet der Linearen Optimierung ist das Transportproblem. Im Standardmodell geht man von m vielen Lieferanten eines Gutes und von n vielen Empfängern aus. Die gesamte Menge des lieferbaren Gutes ist im Standardmodell gleich der Menge der angeforderten Güter.

Lenken wir unseren Blick im Standardmodell nach Oberfranken. Die mittelständische Firma Grünauf betreibt jeweils in Lichtenfels, Kulmbach und Münchberg einen Markt für Heimwerker- und Gartenbedarf. Erden und Pflanzen bekommt sie vor allem von einem Großhändler geliefert, der in Hof und Bad Staffelstein Auslieferungslager betreibt. Die Märkte benötigen wegen der unerwartet früh begonnen Gartensaison kurzfristig Nachschub an torffreier Gartenerde. Diese Gartenerde ist in 80-l-Säcken abgefüllt. Lichtenfels fordert 50 Säcke. Es werden benötigt in Kulmbach 80 und in Münchberg 70 Säcke. Das Lager in Hof kann sofort 90 Säcke liefern, Bad Staffelstein hat 110 Säcke vorrätig

Im Folgenden kürzen wir die Städte mit ihrem Anfangsbuchstaben ab und stellen die Lieferverflechtungen in einer Tabelle zusammen:

Titel1

     | L  K   M  |Summe
-----------------------
H    |x11 x12 x13 | 90
B    |x21 x22 x23 |110
-----------------------
Summe|50  80  70 |200

In der untersten Zeile der Tabelle sind die angeforderten Mengen der Kunden angegeben, ganz rechts die lieferbaren Mengen der Lager. Die xij im Korpus der Tabelle geben die Zahl der Säcke an, die ein Lager an einen Markt liefert. In der Zeile stehen üblicherweise die Lieferanten, in der Spalte die Empfänger. Es ist beispielsweise x23 die Zahl der Säcke, die Bad Staffelstein an Münchberg liefern würde. Diese sollen ermittelt werden und es stellt sich nun die Aufgabe, die die Lieferungen mit den Säcken so zusammenzustellen, dass die Kosten der Lieferung möglichst gering gehalten wird. Dazu benötigen wir noch die Kosten, die pro Sack anfallen. Wir haben diese Kosten pro Einheit des gelieferten Gutes in der folgenden Tabelle nach Lieferant und Kunde zusammengefasst:

Titel2

  |L K M
--------
H |5 4 2
B |1 8 9

4 bedeutet beispielsweise, dass der Transport eines Sackes von Hof nach Kulmbach 4 Euro kostet. Die Kosten mögen etwas hoch erscheinen, aber das Beispiel soll einfach gehalten werden, um es besser verständlich zu machen. Nun stellen wir alle relevanten Informationen in einer weiteren Tabelle zusammen, die dann als Grundlage für die Berechnungen dienen soll.

Titel3

  | L  K  M 
----------------
H | 5  4  2 | 90
B | 1  8  9 |110
----------------
   50 80 70

Die Aufgabenstellung entspricht dem klassischen Transportproblem. Wir sehen, dass hier die gesamte gelieferte Menge gleich der gesamten angeforderten Menge ist. Es sollen also die Mengenvorgaben genau erfüllt sein. Nun modellieren wir ein lineares System.

Titel4

Gelieferte Mengen:

• H: $x_{11}+x_{12}+x_{13}=90$
• B: $x_{21}+x_{22}+x_{23}=110$

Angeforderte Mengen:

• L: $x_{11}+x_{21}=50$
• K: $x_{12}+x_{22}=80$
• L: $x_{13}+x_{23}=70$

Wir haben ein System mit 6 Variablen und 5 Gleichungen. Wir sehen, dass dieses System keinen vollen Rang hat und wir somit unendlich viele Lösungen erhalten würden, wenn wir es ohne weitere Vorgaben lösen würden. Da wir aber die Kosten minimieren wollen, werden wir Lösungen suchen, die unseren Wunsch schrittweise erreichen. Auch hier werden wir wieder ausgehend von einer kanonischen Koeffizientenmatrix mit einer Basislösung beginnen und schrittweise Nichtbasisvariablen mit Basisvariablen vertauschen, bis das Optimum erreicht ist. Wir haben also wieder ein Simplexproblem vor uns, wobei allerdings hier die Beschränkungen exakt erfüllt sein müssen.

Titel5

Wir erstellen uns zunächst ein Tableau der Problemstellung:

    x11 x12 x13 x21 x22 x23  b
-------------------------------
H | 1   1   1   0   0   0   90
B | 0   0   0   1   1   1  110
L | 1   0   0   1   0   0   50
K | 0   1   0   0   1   0   80
M | 0   0   1   0   0   1   70

Die Einsen wurden hier rot dargestellt und es fällt hier ein charakteristisches Muster der Einsen auf. Diese spezielle Anordnung ermöglicht eine Vereinfachung des Suchverfahrens, das ganzzahlige Lösungen unter Erfüllung der Restriktionen garantiert.

Zunächst stellt sich das Problem der Anfangslösung. Da wir eine Minimierungsaufgabe vor uns haben, können wir die gesuchten Mengen xij nicht einfach Null setzen, da wir dann unter die zulässigen Werte geraten. Es wird daher eine Anfangskonstellation gebildet, die die Restriktionen erfüllt. Für die Anfangslösung sind verschiedene Verfahren im Gebrauch. Eine relativ einfache ist das Nord-West-Ecken-Verfahren. Damit kann es mitunter länger dauern, bis eine optimale Lösung gefunden wird, aber der Ablauf ist gut nachvollziehbar. Für die händische Erstellung der Anfangslösung verwenden wir ein Tableau analog zu dem weiter oben.

Wir verteilen nun die zu liefernden Güter. Wir beginnen links oben (daher der Namen Nord-West…) und arbeiten uns zeilenweise nach rechts unten durch. Es wird zuerst oben links so viel wie erlaubt in die Zelle eingetragen. Dann wird in die benachbarte rechte Zelle wieder so viel wie erlaubt eingetragen usw. Ist die Liefermenge des ersten Lieferanten erschöpft, wird in der betreffenden Spalte auf die nächstuntere Zeile gesprungen und ab da wird die Liefermenge des zweiten Lieferanten analog zu oben verteilt, dann geht es zum nächsten Lieferanten usw.

Titel6

Wir erstellen nun die Anfangslösung. Zuerst ist die Tabelle leer:

    L  K  M 
--------------
H | 0  0  0 |  90
B | 0  0  0 | 110
---------------------
   50 80 70 | 200

Nun wird zuerst möglichst viel in die Nord-West-Ecke gepackt. H liefert also 50 Einheiten an L.

    L  K  M 
--------------
H |50  0  0 |  90
B | 0  0  0 | 110
---------------------
   50 80 70 | 200

H hat noch 40 Säcke übrig, die an K geliefert werden.

    L  K  M 
--------------
H |50 40  0 |  90
B | 0  0  0 | 110
---------------------
   50 80 70 | 200

Den restlichen Bedarf von K deckt B mit 40 Einheiten.

    L  K  M 
--------------
H |50 40  0 |  90
B | 0 40  0 | 110
---------------------
   50 80 70 | 200

B hat noch 70 Einheiten übrig, welche an M gehen. Man erhält nun

    L  K  M 
--------------
H |50 40  0 |  90
B | 0 40 70 | 110
---------------------
   50 80 70 | 200

Durch die Anfangslösung wurde eine gültige Basislösung erreicht. Die Variablen mit positiven Mengen sind die Basisvariablen, Variablen mit Null sind Nichtbasisvariablen.

Titel7

Werden die Vektoren unter x₁₁, x₁₂, x₂₂ und x₂₃ zu Basisvektoren umgeformt, ergibt sich das Tableau

x11 x12 x13 x21 x22 x23  b

--------------------------

 1   0   0   1   0   0  50

 0   0  -1   1   1   0   4

 0   1   1  -1   0   0   1

 0   0   1   0   0   1  10

 0   0   0   0   0   0   0

welches die Nord-West-Eckenlösung wiedergibt.

Titel8

Nun beginnt die Suche nach eine optimalen Lösung. Wir wollen die Stepping-Stone-Methode verwenden, die zwar ein wenig angestaubt ist, aber den Vorgang der Suche eher verständlich macht. Wir beginnen:

Es sind zwei Nichtbasisvariablen vorhanden, in Zelle 13 und Zelle 21. Welche wird in eine Basisvariable umgewandelt? Wir untersuchen zuerst für Zelle 13, wie sie die Kosten pro Einheit ändern, wenn Hof nach Münchberg einen Sack liefert. Es wird also versuchsweise der Inhalt von Zelle 13 um Eins erhöht: x13=1. Wenn Hof einen Sack nach Münchberg liefert, kann es nur noch einen Sack weniger nach Kulmbach liefern. Dann muss Bad Staffelstein einen Sack mehr nach Kulmbach liefern und einen Sack weniger nach Münchberg. Man sieht, wie sich die Änderungen kreisförmig fortpflanzen.

Wir notieren die Veränderungen oben rechts in der betreffenden Zelle:

  | L |  K  |  M  |
----------------------
H |5/ |4/   |2/   |
  | 50|-1 40|+1  0| 90
----------------------
B |1/ |8/   |9/   |
  |  0|+1 40|-1 70|110
----------------------
  |  0|   40|   70|200

Wir können jetzt die Änderung der Transportkosten ermitteln: Je nach Vorzeichen werden die Transportstückkosten addiert oder subtrahiert. Die Änderung ist

     +   -   +   -
dK = 2 – 4 + 8 – 9 = -3

Wenn also H einen Ballen nach M liefert, verringern sich die Kosten pro Einheit um 3 €.

Es gibt aber noch eine zweite Zelle, die 0 enthält, die Zelle 21. Jetzt untersuchen wir, wie sich Transportkosten ändern, wenn B einen Ballen nach M liefert. Analog zu oben bilden wir einen Kreis

  |  L  |  K  | M |
----------------------
H |5/   |4/   |2/ |
  |-1 50|+1 40|  0| 90
----------------------
B |1/   |8/   |9/ |
  |+1  0|-1 40| 70|110
----------------------
  |   50|   80| 70|200

          +   -   +   -
z11: dK = 1 – 8 + 4 – 5 = -8.

Hier sinken die Kosten um 8 Euro, wenn B einen Ballen mehr an L liefert. Diese Aktion würde also die Kosten stärker senken als die vorhergehende. Wir werden nun so viele Ballen wie möglich von B nach L schicken. Aber wir müssen verhindern, dass nicht einige Liefermengen negativ werden. Würden wir etwa 60 Säcke von B nach L schicken, müsste H -10 Säcke nach L schicken, damit die Restriktionen gewahrt bleiben – Was aber die Nichtnegativitätsbedingungen verletzt. Deshalb werden alle Mengen untersucht, die ein – haben. Der kleinste Wert wird als neue Liefermenge verwendet: x21 = 40.

Es wird jetzt von allen Zellen mit –1 der Wert 40 abgezogen und auf alle Zellen mit +1 wird 40 aufaddiert. Wir erhalten

  | L | K | M |
------------------
H |5/ |4/ |2/ |
  | 10| 80|  0| 90
------------------
B |1/ |8/ |9/ |
  | 40| 0 | 70|110
------------------
  | 50| 80| 70|200

mit den Gesamtkosten

$5\cdot 10+4\cdot 80+2\cdot 0+1\cdot 40+8\cdot 0+9\cdot 70=1040$ €.

Können wir die Lösung verbessern? Wir untersuchen wieder die Nichtbasisvariablen. Zuerst die Zelle 13. Wenn wir wieder den Kreis wie oben machen wollen, sehen wir, dass hier auf einer Ecke des Kreises, in x22, eine Nichtbasisvariable liegt. Da würde bedeuten, dass wir bei einer Änderung der Liefermengen zwei Nichtbasisvariablen auf einmal in Basisvariablen umwandeln würden, was nicht vorgesehen ist. Da wir also keine Entsprechung für x12 verwenden können, erweitern wir den Kreis und springen auf x11, von da auf x21 und dann x23:

  |  L  | K |  M  |
----------------------
H |5/   |4/ |2/   |
  |-1 10| 80|+1  0| 90
----------------------
B |1/   |8/ |9/   |
  |+1 40|  0|-1 70|110
----------------------
  |   50| 80|   70|200

Das überspringen einer Basisvariablen hat keinen Einfluss auf das Ergebnis. Wir erhalten als Änderung der Kosten

          +   -   +   -
z13: dK = 2 – 5 + 1 – 9 = -11.

Die Untersuchung der Zelle x22 ergibt das Tabelle

  |  L   |   K  | M  |
----------------------
H |5/    |4/    |2/  |
  |+1  10|-1  80|   0| 90
----------------------
B |1/    |8/    |9/  |
  |-1  40|+1   0|  70|110
----------------------
  |    50|    80|  70|200

mit der Kostenänderung

          +   -   +   -
z22: dK = 8 – 4 + 5 – 1 > 0.

Hier ist keine Verbesserung der Kostensituation ersichtlich. Wir machen also Zelle 13 mit dem erheblichen Einsparpotenzial von 11 € zur nächsten Basisvariablen. Es können nur maximal 10 Säcke herumgeschoben werden, so dass H nun 10 Säcke nach M liefert, also

Titel8a

  |   L  | K |  M  |
----------------------
H |5/    |4/ |2/    |
  |-10 10| 80|+10  0| 90
----------------------
B |1/    |8/ |9/    |
  |+10 40|  0|-10 70|110
----------------------
  |    50| 80|    70|200

mit der neuen Liefertabelle

  | L | K | M |
------------------
H |5/ |4/ |2/ |
  |  0| 80| 10| 90
------------------
B |1/ |8/ |9/ |
  | 50| 0 | 60|110
------------------
  | 50| 80| 70|200

mit den Gesamtkosten

$5\cdot 0+4\cdot 80+2\cdot 10+1\cdot 50+8\cdot 0+9\cdot 60=930$ €.

Können wir die Lösung verbessern?

Zelle 11:

  |  L   |  K  |  M   |
----------------------
H |5/    |4/   |2/    |
  |+1   0|   80|-1  10| 90
----------------------
B |1/    |8/   |9/    |
  |-1  50|    0|+1  60|110
----------------------
  |    50|   80|    70|200

mit

     +   -   +   -
dK = 5 – 1 + 9 – 2 > 0.

Hier ist keine Verbesserung möglich. Wir versuchen Zelle 22:

  |  L  |  K   |  M   |
----------------------
H |5/   |4/    |2/    |
  |    0|-1  80|+1  10| 90
----------------------
B |1/   |8/    |9/    |
  |   50|+1   0|+1  60|110
----------------------
  |   50|    80|    70|200

dK = 8 – 9 + 2 – 4 = -3. 

Wir haben hier noch einmal Einsparpotenzial. Die maximal mögliche Zahl der Säcke beträgt 60 und schieben

  |  L  |  K   |  M   |
----------------------
H |5/   |4/    |2/    |
  |    0|-60 80|+60 10| 90
----------------------
B |1/   |8/    |9/    |
  |   50|+60  0|-60 60|110
----------------------
  |   50|    80|    70|200,

so dass sich die neue Tabelle

  | L | K | M |
------------------
H |5/ |4/ |2/ |
  |  0| 20| 70| 90
------------------
B |1/ |8/ |9/ |
  | 50| 60|  0|110
------------------
  | 50| 80| 70|200

ergibt. Die Gesamtkosten sind nun

$5\cdot 0+4\cdot 20+2\cdot 70+1\cdot 50+8\cdot 60+9\cdot 0=750$ €.

Ist die Lösung noch verbesserungsfähig?

Zelle 11:

  |  L   |  K   |  M  |
----------------------
H |5/    |4/    |2/   |
  |+1   0|-1  20|   70| 90
----------------------
B |1/    |8/    |9/   |
  |-1  50|-1  60|    0|110
----------------------
  |    50|   80|    70|200

dK = 5 – 1 + 8 – 4 > 0.

Zelle 23:

  |  L  |  K   |  M   |
--------------------------
H |5/   |4/    |2/    |
  |    0|+1  20|-1  70| 90
--------------------------
B |1/   |8/    |9/    |
  |   50|-1  60|+1   0|110
--------------------------
  |   50|    80|    70|200

dK = 9 – 2 + 4 – 8 > 0.

Hier sind keine Verbesserungen mehr möglich. Es ergibt sich als optimale Liefertabelle

  | L | K | M |
------------------
H |5/ |4/ |2/ |
  |  0| 20| 70| 90
------------------
B |1/ |8/ |9/ |
  | 50| 60|  0|110
------------------
  | 50| 80| 70|200

wie oben mit den Gesamtkosten 750.