Transportmatrizen (Die Decklinienmethode)

Der mathematische Hintergrund soll hier vernachlässigt und nur die algorithmische Vorschrift für die Anwendung des Verfahrens angegeben werden. Dabei erfolgt eine Bewertung der einzelnen Felder der Matrix auf formale Weise, die Interpretation der möglichen Lösungen setzt aber Sachkenntnis über das praktische Problem voraus.
Wir betrachten dazu im Folgenden ein Beispiel.

• Beispiel: Von vier Kiesgruben ist Baumaterial an fünf verschieden weit entfernte Baustellen zu liefern. Die Anzahl der zu fahrenden Mengenkilometer soll minimiert werden.

Bedingung für die Anwendung des Verfahrens ist die Übereinstimmung von zu transportierender Menge und Transportkapazität.
Wir wählen die folgenden Bezeichnungen:
$\begin{array}{l}{G}_i\text{:}Gesamtkiesmenge\text{der}\text{Grube}\text{i}\\ {\text{M}}_{\text{j}}\text{:}benötigteMengeaufderBaustelle{B}_j\\ e_{ij}\text{:}Entfernungvoninachj\\ m_{ij}\text{:}transportierteMengevoninachj\end{array}$

Zielstellung:
Der Aufwand A mit $A={\displaystyle \sum _{i,j}{e}_{ij}}{m}_{ij}$ soll ein Minimum werden.

Die Entfernungsmatrix E zu obigem Beispiel hat die folgende Gestalt:
$E=\left(\begin{array}{ccccc}{e}_{11}& e_{12}& e_{13}& e_{14}& e_{15}\\ e_{21}& e_{22}& e_{23}& e_{24}& e_{25}\\ e_{31}& e_{32}& e_{33}& e_{34}& e_{35}\\ e_{41}& e_{42}& e_{43}& e_{44}& e_{45}\end{array}\right)$

Die algorithmische Vorschrift zur Bewertung der Entfernungsmatrix kann folgendermaßen angegeben werden:

• Schritt 1. Stelle die Entfernungsmatrix E auf.
• Schritt 2. Prüfe, ob in der ersten Zeile mindestens ein Nullelement vorhanden ist.
  Wenn „nein“, dann suche in der Zeile das kleinste Element und subtrahiere es von den anderen.
  Wiederhole den Vorgang für alle Zeilen.
• Schritt 3. Prüfe, ob in der ersten Spalte mindestens ein Nullelement vorhanden ist.
  Wenn „nein“, dann suche in der Spalte das kleinste Element und subtrahiere es von den anderen.
  Wiederhole den Vorgang für alle Spalten.
• Schritt 4. Lassen sich alle $m_{ij}$ unter Beachtung der Nebenbedingungen (Mengen- und Transportkapazität) auf die Nullfelder verteilen?
  Wenn „ja“, dann ist das Optimum erreicht. Berechne den Wert der Zielfunktion A.
  Wenn „nein“, dann gehe weiter zu Schritt 5.
• Schritt 5. Die Tabelle wird folgendermaßen mit Decklinien versehen:
  In den nicht erfüllten Zeilen werden die Nullelemente gesucht und die zugehörigen Spalten überdeckt.
  In den nicht erfüllten Spalten werden die Nullelemente gesucht und die zugehörigen Zeilen überdeckt.
• Schritt 6. Sind noch Felder mit Nullelementen nicht überdeckt, dann versuche, mit möglichst wenigen Linien die restlichen Nullen zu überdecken.
• Schritt 7. Es gibt jetzt drei verschiedene Arten von Überdeckungen.
  Einfach überdeckte Felder: Der Wert bleibt erhalten.
  Nicht überdeckte Felder: Es wird der kleinste Wert gesucht und von den übrigen subtrahiert.
  Doppelt überdeckte Felder: Der vorher errechnete kleinste Wert wird zu diesen addiert.
• Schritt 8. Gehe wieder zu Schritt 4.

Wird die Bedingung
${\displaystyle \sum _{j=1}^5{M}_j}={\displaystyle \sum _{i=1}^5{G}_i}$
nicht erfüllt, dann kann durch Anlage eines fiktiven Lagers oder durch äußere Käufe die Anwendung des Verfahrens ermöglicht werden.

Bei der ungarischen Methode handelt es sich um ein exaktes Verfahren der Linearoptimierung (in Abgrenzung zu approximativen Verfahren).