Transportprobleme der Operations Research. Lösungsfindung durch den Simplex-Algorithmus und heuristische Verfahren


Hausarbeit, 2017

22 Seiten, Note: 1,0


Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Das Modell

3 Lösungsverfahren anhand eines konkreten Beispiels
3.1 Eröffnungsheuristiken
3.1.1 Die Nordwesteckenregel
3.1.2 Das Matrixminimumverfahren
3.2 Die Stepping-Stone-Methode
3.3 Excel-Solver-Verfahren (Simplex-Algorithmus)

4 Interpretation

5 Ausblick

6 Literaturverzeichnis

7 Tabellenverzeichnis

1 Einleitung

Die folgende Arbeit beschäftigt sich mit dem klassischen Transportproblem aus dem Bereich der Operations Research. Unter Operations Research versteht man die Entwicklung und den Einsatz mathematischer Modelle zur Unterstützung von Entscheidungsprozessen.1 Seit Einführung der Operations Research Anfang der 1940er Jahre haben sich verschiedene Verfahren bzw. Teilbereiche der mathematischen Modellierung entwickelt. Zu den wichtigsten Teilbereichen zählen heute u.a. die lineare Programmierung, die ganzzahlige lineare Optimierung, die dynamische Programmierung, das Entscheidungsbaumverfahren, die Netzplantechnik und heuristische Verfahren.2 Das Transportproblem und ihm verwandte Problemstellungen gehören zum bedeutenden Teilgebiet der linearen Programmierung und sind in den verschiedensten Bereichen in der betrieblichen Praxis zu finden.3 Stellt ein Unternehmen z.B. ein Produkt an verschiedenen Standorten her und möchte es an unterschiedliche Senken wie z.B. absatzorientiert gelegene Läger- bzw. Verkaufsstätten verschicken, so soll dies möglichst transportkostenoptimal erfolgen.

Die Arbeit wird so strukturiert sein, dass zunächst das mathematische Modell des klassischen Transportproblems dargestellt wird. Anschließend werden anhand eines konkreten Beispiels drei verschiedene heuristische Verfahren und ein exaktes Verfahren, welches auf Basis des Simplex-Algorithmus beruht, zur Ermittlung der optimalen Lösung vorgestellt. Am Schluss erfolgen eine Interpretation der berechneten Werte und ein Vergleich der verwendeten Methoden. Im darauf folgenden Abschnitt wird ein Ausblick über Erweiterungen des klassischen Transportmodells und dessen Rechenverfahren gegeben.

2 Das Modell

Das klassische Transportproblem ist ein Teilgebiet der linearen Optimierung und geht von folgender Grundstruktur aus:

Gegeben sind:

Abbildung in dieser Leseprobe nicht enthalten

Gesucht werden die Transportmengen , die von Anbieter zu Nachfrager transportiert werden.4 Das Transportmodell lässt sich dann allgemein wie folgt formulieren:

Hierzu gehören die folgenden Nebenbedingungen:

Abbildung in dieser Leseprobe nicht enthalten

3 Lösungsverfahren anhand eines konkreten Beispiels

Durch diese Formulierung als lineares Optimierungsproblem ist leicht zu erkennen, dass klassische Transportprobleme mit Hilfe des Simplex-Algorithmus gelöst werden können.5

Im Laufe der Zeit haben sich im Rahmen der linearen Optimierung vereinfachte Verfahren mit geringerem Rechenaufwand etabliert, mit deren Hilfe eine Lösung ermittelt werden kann, die der optimalen Lösung gleich kommt.

Diese einfacheren Verfahren lassen sich unterscheiden in heuristische Eröffnungsverfahren zur Bestimmung einer zulässigen Basislösung, i.Allg. jedoch noch keine optimale Lösung, und in Optimierungsverfahren, mit deren Hilfe die optimale Lösung iterativ aus der Basislösung ermittelt werden kann.

Zu den Eröffnungsverfahren gehören u.a. die Nordwesteckenregel, die Vogel‘sche Approximationsmethode und das Matrixminimumverfahren.

Die Stepping-Stone-Methode und die MODI-Methode bilden die Optimierungsverfahren.6

Im Folgenden werden nun die Nordwesteckenregel, das Matrixminimumverfahren und die Stepping-Stone-Methode anhand eines konkreten Beispiels verdeutlicht. Anschließend erfolgt eine Lösung des Problems mit Hilfe des Programms Excel-Solver, welches auf Basis der Simplex-Methode beruht.

Beispiel: Stromversorgung

Ein Energieversorgungsunternehmen besteht aus drei Stromkraftwerken K1, K2 und K3, welche den Energiebedarf der Städte S1, S2, S3 und S4 decken müssen.

Die folgende Grafik gibt an, wieviel Strom die Kraftwerke jeweils produzieren können (in Kilowattstunden), welche Nachfrage bei den vier Städten herrscht und wieviel es kostet, den Strom von Kraftwerk zur Stadt zu transportieren (in €/Mio. Kilowattstunden).7

An dieser Stelle sei zu erwähnen, dass diese Fallstudie eine Beispielaufgabe aus dem Studienbuch „Grundlagen Operations Research“ ist. Allerdings sind hier die Produktionswerte der Kraftwerke nicht bei je 50 Mio. KWh, sondern bei je 40 Mio. KWh, sodass die gesamte Produktionsmenge der gesamten Nachfragemenge entspricht. Denn nur dann handelt es sich um ein klassisches Transportproblem, auf das die genannten Rechenmethoden anwendbar sind. Die nachfolgende Grafik stellt das Ausgangstableau für die weiteren Berechnungen dar:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Beispiel Elektrizität, Quelle: Eigene Darstellung in Anlehnung an Reimpell 2015, S. 84

3.1 Eröffnungsheuristiken

3.1.1 Die Nordwesteckenregel

Der Name der Nordwestecken-Methode hat seine Berechtigung insofern, als dass in der Transportmatrix von links oben (Nordwestecke) nach rechts unten (Südostecke) fortschreitend die Transportmengen ermittelt werden.8

Zur Bestimmung einer ersten Lösung wird nun eine ähnliche Matrix wie die Ausgangsmatrix aufgebaut, wobei in einer zusätzlichen Zeile die Verbrauchsmengen und in einer zusätzlichen Spalte die Produktionsmengen für Nebenrechnungen aufgenommen werden.9

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Nordwesteckenregel (Schritt 1), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 58

Die Verteilung beginnt in der Nordwestecke. Stadt S1 benötigt 40 Einheiten, diese kann Stromkraftwerk K1 vollständig liefern. Dieser Wert (40) wird daraufhin oben links in die Tabelle eingetragen. Stromkraftwerk K1 kann somit den anderen drei Städten nichts mehr liefern, sodass in der ersten Zeile rechts neben der 40 jeweils eine Null eingetragen wird. Da die Stromnachfrage der Stadt S1 zudem vollkommen befriedigt ist, wird in der Spalte S1 unter der 40 ebenfalls jeweils eine Null eingetragen. Die Tabelle sieht nun folgendermaßen aus:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Nordwesteckenregel (Schritt 2), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 59

Anschließend wird mit der Verteilung in der zweiten Zeile wiederum soweit wie möglich im Westen begonnen. Die Stadt S2 benötigt 20 Einheiten, die sie vom Kraftwerk K2 erhält. K2 kann anschließend noch 20 Einheiten an die Stadt S3 verschicken. Somit ist der Bedarf von Stadt S2 gedeckt und die Produktionskapazität von Stromkraftwerk K2 vollständig erschöpft. Die Stadt S3 benötigt jetzt noch 10 Einheiten, was zu folgendem Tableau führt:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4: Nordwesteckenregel (Schritt 3), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 59

Nun wird die Produktion vom Stromkraftwerk K3 verteilt. Die Stadt S3 erhält von Kraftwerk K3 10 Einheiten und die Stadt S4, welche eine Nachfrage von 30 Einheiten hat, wird mit den 30 verbleibenden Einheiten von Kraftwerk K3 versorgt, sodass die Gesamtproduktion verteilt ist und alle Verbraucher die benötigten Mengen erhalten.10

Dies führt zu abschließender Tabelle:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5: Nordwesteckenregel (Schritt 4), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 59

Die Gesamttransportkosten werden nun so berechnet, indem die Transportmengen mit den entsprechenden Transportkosten pro Einheit aus Tabelle 1 multipliziert werden:

Abbildung in dieser Leseprobe nicht enthalten

Mit Hilfe der Nordwesteckenregel wurde nun eine erste Ausgangslösung ermittelt, die zu Transportkosten von insgesamt 1020 Euro / Mio. KWh Strom führt.

3.1.2 Das Matrixminimumverfahren

Das zweite heuristische Eröffnungsverfahren zur Aufstellung einer Ausgangslösung, die wie die Lösung der Nordwesteckenregel noch nicht perfekt sein muss, ist das Matrixminimumverfahren. Bei dieser Methode haben nicht nur die Verbrauchsmengen, sondern auch die Transportkosten je Einheit eine hohe Relevanz.

Die Ausgangsmatrix für die einzelnen Rechenschritte ist ein Tableau analog zur Tabelle 2 aus der Nordwesteckenregel:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 6: Matrixminimumverfahren (Schritt 1), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 60

Gesucht wird nun das Minimum in der Kostentabelle. Diesem kleinsten Wert nach wird nun die entsprechende Transportmenge zugeordnet.11 Da in diesem Fall zwei Kostenminima mit jeweils sechs Euro existieren, darf zwischen einem der Werte als Startfeld gewählt werden. An dieser Stelle wurde mit dem Feld begonnen, also mit den Transportkosten für den Transport von Stromkraftwerk K3 zur Stadt S3. Entsprechend dem Namen der Matrixminimum-Methode wird nun von K3 maximal viel zu S3 geliefert. Die Nachfrage von S3 liegt bei maximal 30 Einheiten, diese können von K3 voll geliefert werden. Danach ist die Nachfrage von S3 komplett befriedigt und K3 verbleibt eine Lieferkapazität von 10 Einheiten. Nun wird der nächst kleinere Wert aus der Kostenmatrix gesucht. Dies ist das Feld mit ebenfalls sechs Euro an Transportkosten. K3 liefert demnach noch 10 Einheiten an S4, was zu folgender Zwischentabelle führt:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 7: Matrixminimumverfahren (Schritt 2), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 60

Die nächst kleineren Werte in der Kostentabelle sind die Felder und mit je sieben Euro. Da die Stadt S3 aber schon vollständig mit Strom versorgt wurde, bleibt nur noch das Feld übrig. Die Stadt S4 hat noch einen Bedarf von 20 Einheiten, welcher vom Kraftwerk K1 gedeckt wird. Daraufhin ist die Stadt S4 ebenfalls mit der geforderten Menge an Strom versorgt. Die Zwischenmatrix sieht wie folgt aus:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 8: Matrixminimumverfahren (Schritt 3), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 60

Das Feld mit den nun niedrigsten Transportkosten ist das Feld mit neun Euro. Die restlichen 20 Einheiten von K1 werden deshalb an S2 geliefert. Damit ist die Produktionskapazität vom ersten Stromkraftwerk erschöpft und die Stadt S2 ist mit ausreichend Strom versorgt. Nun bleibt nur noch Kraftwerk K2 als Stromlieferant übrig. Dessen 40 Einheiten werden an die Stadt S1 geliefert, sodass auch deren Nachfrage befriedigt ist. Somit wurde auch mit diesem Verfahren die gesamte Produktion auf die gesamte Nachfrage verteilt.12

Nach der Matrixminimum-Methode ergibt sich folgende Abschlusstabelle:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 9: Matrixminimumverfahren (Schritt 4), Quelle: Eigene Darstellung in Anlehnung an Lutz 1998, S. 61

Zur Ermittlung der gesamten Transportkosten werden auch hier die jeweiligen Mengen mit den entsprechenden Transportkosten pro Einheit multipliziert:

Abbildung in dieser Leseprobe nicht enthalten

Mit Hilfe des Matrixminimumverfahrens wurde nun eine zweite Ausgangslösung berechnet, die zu Transportkosten von insgesamt 1000 Euro / Mio. KWh Strom führt. Das Verfahren erbrachte also in diesem Beispiel eine bessere Anfangslösung als die Nordwesteckenregel.13

3.2 Die Stepping-Stone-Methode

Im Gegensatz zur Nordwesteckenregel und dem Matrixminimumverfahren ist die Stepping-Stone-Methode eine Überprüfung, ob eine gefundene Ausgangslösung im Rahmen der Transportproblematik Verbesserungspotenzial besitzt oder nicht.14 Hierbei wird die Ausgangslösung schrittweise geprüft und verbessert, bis die optimale Lösung gefunden wurde. Diese Schritte Prüfung und Verbesserung werden dann solange wiederholt, bis keine Verbesserungen mehr möglich sind.15 Die Stepping-Stone-Methode kann sowohl auf die Ausgangslösung der Nordwesteckenregel als auch auf die Lösung des Matrixminimumverfahrens angewandt werden.

Da eine Optimierung beider Lösungen für diese Hausarbeit zu umfangreich wäre, wird im folgenden Verlauf nur die Ausgangslösung der Nordwesteckenregel mit Hilfe der Stepping-Stone-Methode verbessert. Der Übersicht und dem besseren Verständnis halber zeigt die folgende Tabelle nochmal die Abschlusstabelle der Nordwesteckenregel mit den entsprechenden Mengen und Transportkosten je Einheit:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 10: Stepping-Stone-Methode (Schritt 1), Quelle: Eigene Darstellung in Anlehnung an Ellinger 2003, S. 81

Die Stepping-Stone-Methode bedeutet eine Bewertung der freien Felder, also die Felder, in denen keine Mengeneinheiten stehen und wo folglich kein Transport stattfindet. In diesem Beispiel sind dies die Felder K1-S2, K1-S3, K1-S4, K2-S1, K2-S4, K3-S1 und K3-S2.

Nun wird versucht, jedes nicht belegte Feld mit einer Einheit zu belegen. Ergäben sich hierdurch Einsparungen im Vergleich zur Basislösung, wäre gezeigt, dass diese nicht optimal wäre, und es könnte als nächster Schritt die Verbesserung der Lösung vorgenommen werden.16

[...]


1 Vgl. Ellinger et al. 2003, S. 1

2 Vgl. ebd., S.11-14

3 Vgl. ebd., S. 75

4 Vgl. Kistner 2003, S. 206

5 Vgl. Lutz 1998, S. 57

6 Vgl. Domschke et al. 2015, S. 88-89

7 Vgl. Reimpell 2015, S. 84

8 Vgl. Domschke et al. 2015, S. 89

9 Vgl. Lutz 1998, S. 59

10 Vgl. Lutz 1998, S. 59

11 Vgl. Lutz 1998, S. 60

12 Vgl. Lutz 1998, S. 59

13 Vgl. Lutz 1998, S. 61

14 Vgl. Ellinger et al. 2003, S. 81

15 Vgl. ebd. S. 79

16 Vgl. Ellinger et al. 2003, S. 80

Ende der Leseprobe aus 22 Seiten

Details

Titel
Transportprobleme der Operations Research. Lösungsfindung durch den Simplex-Algorithmus und heuristische Verfahren
Hochschule
Fachhochschule Südwestfalen; Abteilung Meschede
Note
1,0
Autor
Jahr
2017
Seiten
22
Katalognummer
V704562
ISBN (eBook)
9783346200488
ISBN (Buch)
9783346200495
Sprache
Deutsch
Schlagworte
Operations Research, klassische Transportproblem, Nordwesteckenregel, Matrixminimumverfahren, Stepping-Stone-Methode
Arbeit zitieren
Mario Burgard (Autor:in), 2017, Transportprobleme der Operations Research. Lösungsfindung durch den Simplex-Algorithmus und heuristische Verfahren, München, GRIN Verlag, https://www.grin.com/document/704562

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Transportprobleme der Operations Research. Lösungsfindung durch den Simplex-Algorithmus und heuristische Verfahren



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden