mathematik - physik - informatik Seite zurück   Seite vor  

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

i=1 m j=1 n cij xij = Min! (7)
j=1 n xij = vi i=1,,m     und     i=1 m xij = bj j=1,,n (8)
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

i=1 m vi = j=1 n 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.

Gilt die Bedingung (10), so lässt sich eine zulässige Lösungsmenge bestimmen mit xij = vibjS .

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.



  Bert Xylander - 30. Dezember 2015
  'Optimierung in der Schule'
Seite zurück   Seite vor