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
Transport- und Zuordnungsprobleme > Lineare Zuordnungsprobleme:

Ungarische Methode

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 06.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Dynamik) Gradlinige Bewegung eines Massenpunktes
- Dieses 60-minütige Gratis-Webinar behandelt die geradlinige Bewegung eines Massenpunktes.
[weitere Informationen] [Terminübersicht]

Die Ungarische Methode ist dazu gedacht lineare Zurodnungsprobleme zu lösen. Für die Anwendung der Ungarischen Methode wird zunächst eine Spalten- und Zeilenweise Reduktion der Kostenmatrix durchgeführt. 

Methode

Ungarische Methode

1. Reduktion der Ausgangsmatrix. Spalten-und zeilenweise Reduktion der Ausgangsmatrix.

2. Es wird mit derjenigen Spalte und Zeile begonnen, welche nur eine Null enthält. Diesem Feld wird dann $x_{ij} = 1$ zugeordnet, indem die Null umrandet wird. Danach werden die weiteren Nullen in der Matrix betrachtet. Dabei werden weitere Zuordnungen so vorgenommen, dass am Ende jede Spalte und jede Zeile nur eine Zuordnung aufweist.

Sind $n$ Zurodnungen gefunden, so ist die Lösung optimal. Sind weniger als $n$ Zuordnungen gefunden, geht es weiter mit Schritt 3.

3. Es wird nun wie folgt vorgegangen:

  • (a) Markiere alle Zeilen, die keine Zuordnung (Umrandung) aufweisen.
  • (b) Markiere alle Spalten, welche Null-Elemente in den bereits markierten Zeilen aufweisen.
  • (c) Markiere alle nicht-markierten Zeilen, welche Null-Elemente in den markierten Spalten aufweisen. 
  • Wiederhole b - c solange bis keine Markierungen mehr erfolgen.
  • Zeichne eine Linie durch alle nicht-markierten Zeilen und durch alle markierten Spalten. 

4. Die Matrixelemente müssen nun wie folgt angepasst werden. Das kleinste nicht mit einer Linie überdeckte Element wird von den anderen nicht von einer Linie überdeckten Elementen abgezogen und zu den doppelt überdeckten Elementen (dort wo sich Linien schneiden) addiert. Die einfach überdeckten Elemente bleiben unverändert.

5. Es wird wieder bei Schritt 2 begonnen.

Die Vorgehensweise bei der Ungarischen Methode soll anhand des nachfolgenden Beispiel aufgezeigt werden.

Anwendungsbeispiel: Ungarische Methode

Ungarische Methode Beispiel

Beispiel

Ein Logistikunternehmen benötigt an 5 Orten $j$ je einen Lastwagen. Diese sollen von den Ausgangsorten $i$ auf diese 5 Orten so verteilt werden, dass die Fahrtkosten minimal werden. In der Tabelle sind die Kilometer von dem Ort $i$ zum Ort $j$ angegeben. Die Zuordnung soll so stattfinden, dass die Kilometerzahl minimiert wird. 

Es wird die Ungarische Methode angewandt um das Zurodnungsproblem zu lösen. 

1. Es wird zunächst eine Reduktion der Ausgangsmatrix vorgenommen, indem zunächst die Zeilen betrachtet werden und hier das kleinste Element einer Zeile von den anderen Elemente der Zeile abgezogen werden. Danach wird die Spalte betrachtet und das kleinste Element der Spalte von den anderen Elementen der Spalte abgezogen.

Ungarische Methode Reduktion der Kostenmatrix


2. Es wird mit derjenigen Spalte und Zeile begonnen, welche nur eine Null enthält. Diesem Feld wird dann $x_{ij} = 1$ zugeordnet, indem die Null umrandet wird.

Ungarische Methode Zuordnung


Danach werden die weiteren Nullen in der Matrix betrachtet. Dabei werden weitere Zuordnungen so vorgenommen, dass am Ende jede Spalte und jede Zeile nur eine Zuordnung aufweist.

Ungarische Methode Zuordnung

Da $n = 5$ und nur 4 Zuordnungen gefunden worden sind, geht es weiter mit Schritt 3.

Bei 3. Schritt wird nun wie folgt vorgegangen. Es werden nun alle Nullen (auch die zugeordneten) versucht mit so wenig Strichen wie möglich zu streichen. Dabei wird wie folgt vorgegangen:

  • a) Markiere alle Zeilen, die keine Zuordnung (Umrandung) aufweisen.
  • (b) Markiere alle Spalten, welche Null-Elemente in den bereits markierten Zeilen aufweisen.
  • (c) Markiere alle nicht-markierten Zeilen, welche Null-Elemente in den markierten Spalten aufweisen. 
  • Wiederhole b - c solange bis keine Markierungen mehr erfolgen.
  • Zeichne eine Linie durch alle nicht-markierten Zeilen und durch alle markierten Spalten. 
Ungarische Methode streichen von Nullen


4. Die Matrixelemente müssen nun wie folgt angepasst werden. Das kleinste nicht mit einer Linie überdeckte Element (hier: 1) wird von den anderen nicht von einer Linie überdeckten Elementen abgezogen und zu den doppelt überdeckten Elementen (dort wo sich Linien schneiden) addiert. Die einfach überdeckten Elemente bleiben unverändert.

Ungarische Methode Koeffizienten bestimmen


Es wird wieder bei Schritt 2 begonnen. Die Schritte 2-3 ergeben die folgende Matrix:

Ungarische Methode streichen von Nullen


Danach wird Schritt 4 durchgeführt. Die Matrixelemente müssen nun wie folgt angepasst werden. Das kleinste nicht mit einer Linie überdeckte Element (hier: 1) wird von den anderen nicht von einer Linie überdeckten Elementen abgezogen und zu den doppelt überdeckten Elementen (dort wo sich Linien schneiden) addiert. Die einfach überdeckten Elemente bleiben unverändert.

Ungarische Methode Koeffizienten bestimmen


Es wird wieder mit Schritt 2 begonnen. Nach Schritt 2, also Zuordnung der Nullen, ergibt sich eine eine optimale Lösung, da $n = 5$ Zuordnungen gefunden werden:

Ungarische Methode Zuordnung

Die optimale Lösung sieht also wie folgt aus:

Ein Wagen von Ort 1 nach Ort 4.

Ein Wagen von Ort 2 nach Ort 2.

Ein Wagen von Ort 3 nach Ort 3.

Ein Wagen von Ort 4 nach Ort 5.

Ein Wagen von Ort 5 nach Ort 1.


Die Kilometeranzahl beträgt demnach:

$2 + 3 + 4 + 7 + 5 = 21 km$.

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