|
|
klassisches Transportproblem
I. Charakterisierung: Standardproblem des Operations Research (OR), das ein spezielles Transportproblem ist. - Problembeschreibung: Es existiert eine Menge von Orten (Vorratsorte), an denen jeweils ein gewisser Gütervorrat vorhanden ist; sowie eine Menge von Orten (Bedarfsorte), an denen jeweils ein gewisser Güterbedarf vorhanden ist. Sämtliche Vorräte und Bedarfe beziehen sich auf die gleiche Güterart (homogene Güter). Zur Befriedigung der Bedarfe sollen Güter von den Vorratsorten zu den Bedarfsorten transportiert werden. Sämtliche Vorräte sollen aufgebraucht, sämtliche Bedarfe befriedigt werden, d. h. die an allen Vorratsorten insgesamt vorhandene Gütermenge stimmt mit der an den Bedarfsorten insgesamt nachgefragten Gütermenge überein. Von jedem Vorratsort existiert zu jedem Bedarfsort genau ein Transportweg, der keinen anderen Vorrats- bzw. Bedarfsort berührt; Vorratsorte bzw. Bedarfsorte sind untereinander nicht verbunden. Die Ausführung der Transporte verursacht Kosten; auf jedem Transportweg verhalten sich die Transportkosten proportional zu der darauf transportierten Gütermenge. Kapazitätsbeschränkungen der Transportmittel werden nicht wirksam (unkapazitiertes Transportproblem); zu kapazitiertem Transportproblem vgl. V. Gesucht ist ein Transportplan, der unter diesen Bedingungen angibt, wie viele Mengeneinheiten des Gutes jeweils auf den verschiedenen Wegen transportiert werden sollen, wobei möglichst geringe Gesamttransportkosten angestrebt werden.
II. Mathematische Formulierung: Minimiere
wobei I = Indexmenge der Vorratsorte (hier: I = {1, 2, ... , n}); J = Indexmenge der Bedarfsorte (hier: J = {1, 2, ... , n}); ai = Vorratsmenge am Vorratsort i (i I); bj = Bedarfsmenge am Bedarfsort j (j J); cij = Kosten für den Transport einer Mengeneinheit des Transportgutes vom Vorratsort i (i I) zum Bedarfsort j (j J); xij = (zu bestimmende) Anzahl der vom Vorratsort i (i I) zum Bedarfsort j (j J) zu transportierende Gütermengeneinheiten; x0 = Gesamtkosten aller Transporte.
Das Optimierungssystem ((1), (2), (3), (4), (5)) nennt man auch klassisches Transportsystem, die Restriktion (5) auch Gleichgewichtsrestriktion.
III. Eigenschaften: 1. Genau eine beliebige Gleichung des Restriktionssystems ((2), (3)) ist überflüssig und kann ersatzlos gestrichen werden. - 2. Das Restriktionssystem ((2), (3), (4)) ist genau dann lösbar, wenn (5) gilt. - 3. Ist das Restriktionssystem ((2), (3), (4)) lösbar, so besitzt das Optimierungssystem ((1), (2), (3), (4)) auch eine optimale Lösung. - 4. Sind sämtliche rechten Seiten ai und bj von (2) bzw. (3) ganzzahlig, so ist auch jede Basislösung von ((2), (3)) ganzzahlig.
IV. Lösungsverfahren: 1. Die klassische Simplexmethode und ihre Varianten sind grundsätzlich anwendbar, führen aber im Vergleich zu speziellen, für k. T. entwickelte Lösungsverfahren zu einem höheren Rechenaufwand. - 2. Spezielle, wenig rechenaufwendige Eröffnungsverfahren, die zulässige, aber i. d. R. keine optimalen Basislösungen liefern, sind z. B. das Nordwestecken-, Kostenminimum- und Spaltenminimumverfahren. Bessere, oft nahezu optimale Lösungen lassen sich mit Hilfe des allerdings rechenaufwendigeren Vogelschen Approximationsverfahrens ermitteln. - 3. Spezielle Optimierungsverfahren, die eine zulässige, etwa mit Hilfe eines Eröffnungsverfahrens gefundene Lösung voraussetzen und daraus iterativ eine optimale Lösung ermitteln, sind etwa das Stepping-Stone-Verfahren oder MODI-Verfahren.
V. Kapazitätsbeschränkungen (kapazitiertes k. T.) lassen sich in die mathematische Formulierung einarbeiten, indem die betreffenden Nichtnegativitätsrestriktionen (4) durch
(mit xij > 0) ersetzt werden, wobei xij eine untere und ij eine obere Schranke für den Wert der Variablen xij bedeutet. Untere Schranken xij können durch einfache Modifikationen, mit denen man das Optimierungssystem wieder in ein k.T. überführt, berücksichtigt werden. In den speziellen Lösungsverfahren lassen sich obere Schranken ij durch entsprechende Verfahrensmodifikationen berücksichtigen.
VI. Ein linerares Zuordnungssystem liegt vor, wenn die Restriktionen (4) durch
ersetzt sind und außerdem gilt:
(Sämtliche rechten Seiten von (2) und (3) gleich Eins; die Anzahl | I | der Elemente in I stimmt mit der Anzahl | J | der Elemente in J überein.)
VII. Ökonomische Anwendungen: klassisches Transportproblem T. bilden die Grundstruktur einer Vielzahl von Transportproblemen der Praxis ab. Sie dienen in diesem Zusammenhang v. a. als Vorbild bei der Modellierung derartiger Probleme. Darüber hinaus lassen sich auch für gewisse andere Planungsprobleme (z. B. Transit-Transportproblem, Umladeproblem, Transportproblem mit Schlupf, lineares Zuordnungsproblem) formulierte lineare Optimierungssysteme in k. T. überführen.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
