ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 1
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse

Das klassische Transportproblem

WebinarTerminankündigung aus unserem Online-Kurs Thermodynamik:
 Am 13.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Thermodynamik) Innere Energie, Wärme, Arbeit
- Innerhalb dieses 60-minütigen Webinares wird der 1. Hauptsatz der Thermodynamik für geschlossene Systeme behandelt und auf die innere Energie, Wärme und Arbeit eingegangen.
[weitere Informationen] [Terminübersicht]

Transportprobleme weisen eine spezielle Struktur auf, für welche spezielle Lösungsverfahren entwickelt worden sind. Diese speziellen Lösungsverfahren sollen in den folgenden Abschnitt ausführlich beschrieben werden. Die Anwendung der Simplex-Algorithmen ist für diese Probleme zwar möglich, aber sehr rechenaufwendig. Im Weiteren wird das klassische Transportproblem ohne Kapazitätsbeschränkungen aufgezeigt. 

Bei Transportprobleme müssen bestimmte Mengen eines Produktes $x_{ij}$ von mehreren Angebotsorten $a_i$ zu mehreren Nachfrageorten $b_j$ so transportiert werden, so dass die Gesamtkosten minimiert werden. Es müssen die folgenden Bedingungen erfüllt sein:

  • Die transportierten Mengen müssen größer oder gleich Null sein: $x_{ij} \ge 0$.
  • Das Gesamtangebot muss gleich der Gesamtnachfragen sein: $\sum a_i = \sum b_j$. Ist dieser Fall nicht gegeben, so muss ein fiktiver Angebots- bzw. Nachfrageort eingeführt werden, welcher die Überschussnachfrage bzw. -angebot aufnimmt. 
  • Es sind nicht-negative Transportkosten $c_{ij}$ gegeben. Transportkosten für den Transport von bzw. zu einem fiktiven Ort werden Null gesetzt. Ist der Transport zwischen zwei Orten nicht möglich, so werden die dortigen Transportkosten unendlich gesetzt.

Mathematische Formulierung des Problems

Die Transportkosten $c_{ij}$ sollen miminiert werden. Die Zielfunktion $z$ lautet demnach:

$z = \sum_{j = 1}^n \sum_{i = 1}^m c_{ij} x_{ij}$    $\rightarrow$ min!

Dabei ergeben sich die Gesamtkosten, indem die Transportmenge für jeden Weg mit den dazugehörigen Kosten multipliziert werden. Es ergibt sich dann die Summe der Kosten pro Transportweg. Werden dann die Kosten aller Transportwegen miteinander addiert, so ergeben sich die Gesamtkosten des Problems. Diese sollen unter Einhaltung der nachfolgenden Bedingungen minimiert werden:

$\sum_{j = 1}^n x_{ij} = a_i$       $i = 1,2,...,m$

$\sum_{i = 1}^m x_{ij} = b_j$       $j = 1,2,...,n$

$\sum a_i = \sum b_j$

$x_{ij} \ge 0$

Die erste und zweite Nebenbedingung bedeuten, dass das komplette Angebot abgerufen und die komplette Nachfrage befriedigt werden soll. Die dritte Nebenbedingung beschreibt, dass das Angebot und die Nachfrage übereinstimmen müssen und die letzte Nebenbedingung, dass nur nicht-negative Transportmengen gegeben sein dürfen. Wird die Ganzzahligkeit der Transportmengen gefordert, so gilt:

Methode

$x_{ij} \in \mathbb{N}$             Ganzzahligkeit der Transportmengen

Das Problem kann zum eine in eine Kostenmatrix und zum anderen in eine Mengenmatrix eingetragen werden:

Transportproblem Kostenmatrix
Kostenmatrix
Transportproblem Mengenmatrix
Mengenmatrix

Es wird nun in den folgenden Abschnitten gezeigt, wie man ein klassischen Transportproblem lösen kann. Hiefür müssen die folgenden Schritte durchgeführt werden:

1. Ausgleichsprüfung

Es muss zunächst geprüft werden, ob die Angebotsmenge $\sum a_i$ gleich der Nachfragemenge $\sum b_j$ entspricht. Ist dies nicht der Fall, so müssen fiktive Angebots- bzw. Nachfrageorte eingefügt werden, welche diese fehlende Menge aufnehmen. Ist $\sum a_i < \sum b_j$, so muss ein Angebotsort zugefügt werden mit der Menge $a'_i = \sum b_j - a_i$. Ist $\sum b_j < \sum a_i$, so muss ein Nachfrageort zugefügt werden mit der Menge $b'_j = \sum a_i - \sum b_j$. 

2. Reduktion der Kostenmatrix

Die Reduktion der Kostenmatrix (vor allem bei Anwendung der Stepping-Stone-Methode) führt zu einem geringeren Rechenaufwand. 

3. Bestimmung einer zulässigen Ausgangslösung

Es muss eine zulässige Ausgangslösung bestimmt werden. Hierfür stehen die folgenden Verfahren zur Verfügung:

- Nordwestecken-Verfahren (Mengenmatrix) 

- Zeilenminimum, Spaltenmimum, Matrixminimum (Mengen- und Kostenmatrix)

- Vogelsches Approximationsverfahren (Kostenmatrix)

4. Bestimmung der optimalen Lösung

Nachdem eine zulässige Lösung bestimmt worden ist, kann die optimale Lösung ermittelt werden. Hierfür können die folgenden zwei Verfahren angewandt werden:

- Stepping-Stone-Methode

- die Modi-Methode.

Beispiel: Transportproblem

Beispiel

Die xy-AG produziert ein Produkt in drei Fabriken. Anschließend erfolgt der Transport durch LKW's an fünf Warenhäuser. Die Transportkosten stellen einen zentralen Kostenpunkt dar, weshalb das Unternehmen die Transportkosten so weit wie möglich reduzieren möchte. Die nachfolgende Tabelle zeigt die geschätzten Kosten pro LKW-Ladung der kommenden Saison zwischen den einzelnen Fabriken und Warenhäuser:

Transportproblem Beispiel

Das Produkt soll nun so auf die 5 Warenhäuser verteilt werden, dass die Transportkosten minimal sind!

In den folgenden Abschnitten werden die obigen 4 Schritte zur Lösung des Transportproblems ausführlich dargestellt.

Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 1

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
    • Einleitung zu Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung eines Maximierungsproblems
        • Einleitung zu Grafische Lösung eines Maximierungsproblems
        • Beispiel: Grafische Lösung eines Maximierungsproblems
      • Umformung in die Standardform (Maximierungsproblem)
      • Umformung in die Normalform (Maximierungsproblem)
      • Simlpex-Algorithmus: Einführung
        • Einleitung zu Simlpex-Algorithmus: Einführung
        • Primales Simlpexverfahren
          • Einleitung zu Primales Simlpexverfahren
          • Primales Simplexverfahren: Anfangstableau aufstellen
          • Primales Simplexverfahren: Pivotspalte/-zeile/-element
          • Primales Simplexverfahren: 1. Simplexschritt
          • Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)
          • Beispiel: Maximierungsproblem / grafische Lösung
          • Beispiel: Maximierungsproblem / Primales Simplexverfahren
        • Duales Simplexverfahren
          • Einleitung zu Duales Simplexverfahren
          • Duales Simplexverfahren: Pivotzeile/-spalte/-element
          • Duales Simplexverfahren: Simplexschritte
        • Die Big-M-Methode des primalen Simplexverfahrens
          • Einleitung zu Die Big-M-Methode des primalen Simplexverfahrens
          • Die Big-M-Methode: Einfügen von künstlichen Variablen
          • Die Big-M-Methode: Künstliche Variablen als Basisvariablen
          • Big-M-Methode: Simplexschritt durchführen
          • Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)
          • Big-M-Methode: Weitere Simplexschritte (optimale Lösung)
      • Kanonische Form, Standardform, Normalform
      • Zusammenfassung: Maximierungsproblem
    • Minimierungsproblem
      • Einleitung zu Minimierungsproblem
      • Dualität - Primalproblem als Maximierungsproblem
      • Dualität - Primalproblem als Minimierungsproblem
      • Dualität - Dualproblem in Primalproblem
      • Beispiel: Primalproblem als Minimierungsproblem
      • Minimierungsproblem- Big-M/dualer Simplex
      • Zusammenfassung: Minimierungsproblem
    • Sonderfälle bei Optimierungsmodellen
      • Einleitung zu Sonderfälle bei Optimierungsmodellen
      • Beispiel: Minimierungsproblem ohne optimal Lösung
    • Sensitivitätsanalyse
      • Einleitung zu Sensitivitätsanalyse
      • Änderung der Zielfunktionskoeffizienten
        • Einleitung zu Änderung der Zielfunktionskoeffizienten
        • Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten
      • Änderung der Restriktionen
    • Obere und untere Schranken bei Variablen
      • Untere Schranken
      • Obere Schranken
        • Einleitung zu Obere Schranken
        • Beispiel: Primaler Simplexalgorithmus
        • Beispiel: Vielzahl an beschränkten Variablen
    • Revidierter Simplex-Algorithmus
      • Einleitung zu Revidierter Simplex-Algorithmus
      • Beispiel: Revidierter Simplex-Algorithmus
  • Transport- und Zuordnungsprobleme
    • Das klassische Transportproblem
      • Einleitung zu Das klassische Transportproblem
      • Ausgleichsprüfung
      • Reduktion der Kostenmatrix
      • Eröffnungsverfahren
        • Einleitung zu Eröffnungsverfahren
        • Nord-Westecken-Verfahren
        • Rangfolgeverfahren
          • Einleitung zu Rangfolgeverfahren
          • Spaltenfolgeverfahren
          • Zeilenfolgeverfahren
          • Matrixminimumverfahren
        • Vogelsches-Approximations-Verfahren
      • Optimierungsverfahren
        • Einleitung zu Optimierungsverfahren
        • Stepping-Stone-Methode
        • MODI-Methode
    • Lineare Zuordnungsprobleme
      • Definition: Zuordnungsprobleme
      • Ungarische Methode
  • Netzplantechnik
    • Einführung Netzplantechnik
    • Ablaufplanung
      • Einleitung zu Ablaufplanung
      • Strukturplanung
      • Netzplanerstellung
    • Zeitplanung
      • Einleitung zu Zeitplanung
      • Beispiel 1: Vorgangsknotennetzplan
      • Beispiel 2: Vorgangsknotennetzplan
    • Kostenplanung
    • Kapazitätsplanung
  • Graphentheorie
    • Einführung: Graphentheorie
    • Kürzeste Wege
      • Einleitung zu Kürzeste Wege
      • Dijkstra-Algorithmus
      • Fifo-Algorithmus
  • 74
  • 11
  • 42
  • 144
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 22.06.2016:
    "top!! ;)"

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 05.12.2015:
    "Super erklärt !! "

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen