aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/munkres
diff options
context:
space:
mode:
authorfabioviecelli <80270098+fabioviecelli@users.noreply.github.com>2021-09-08 09:23:56 +0200
committerfabioviecelli <80270098+fabioviecelli@users.noreply.github.com>2021-09-08 09:23:56 +0200
commit910a4f556d89d75ee07384a2a3fb963334552264 (patch)
tree53f346e2de59d4bf1365535b709f0a2e8ebffba1 /buch/papers/munkres
parentErgänzungen (diff)
parenteditorial edits clifford (diff)
downloadSeminarMatrizen-910a4f556d89d75ee07384a2a3fb963334552264.tar.gz
SeminarMatrizen-910a4f556d89d75ee07384a2a3fb963334552264.zip
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'buch/papers/munkres')
-rw-r--r--buch/papers/munkres/main.tex2
-rw-r--r--buch/papers/munkres/teil0.tex12
-rw-r--r--buch/papers/munkres/teil1.tex67
-rw-r--r--buch/papers/munkres/teil2.tex14
-rw-r--r--buch/papers/munkres/teil3.tex50
5 files changed, 99 insertions, 46 deletions
diff --git a/buch/papers/munkres/main.tex b/buch/papers/munkres/main.tex
index 201e70b..ecc7072 100644
--- a/buch/papers/munkres/main.tex
+++ b/buch/papers/munkres/main.tex
@@ -4,7 +4,7 @@
% (c) 2020 Hochschule Rapperswil
%
\chapter{Das Zuordnungsproblem und der Munkres-Algorithmus\label{chapter:munkres}}
-\lhead{Das Zuordnungsproblem und der Munkres-Algorithmus}
+\lhead{Der Munkres-Algorithmus}
\begin{refsection}
\chapterauthor{Marc Kühne}
diff --git a/buch/papers/munkres/teil0.tex b/buch/papers/munkres/teil0.tex
index 0578429..efdf816 100644
--- a/buch/papers/munkres/teil0.tex
+++ b/buch/papers/munkres/teil0.tex
@@ -6,5 +6,13 @@
\section{Einleitung\label{munkres:section:teil0}}
\rhead{Einleitung}
-Im Bereich der Unternehmensplanung (Operations Research) gibt es verschiedene Fragestellungen. Eine davon ist das sogenannte Transportproblem. Zum Transport einheitlicher Objekte von mehreren Angebots- zu mehreren Nachfrageorten ist ein optimaler, d. h. kostenminimaler Plan zu finden, wobei die vorhandenen und zu liefernden Mengen an den einzelnen Standorten gegeben sowie die jeweiligen Transportkosten pro Einheit zwischen allen Standorten bekannt sind.
-Nun gibt es im Bereich des klassischen Transportproblems Sonderfälle. Ein Sonderfall ist z.B. das Zuordnungsproblem.
+Im Bereich der Unternehmensplanung (Operations Research) gibt es verschiedene Fragestellungen.
+\index{Unternehmensplanung}%
+\index{Operations Research}%
+Eine davon ist das sogenannte Transportproblem.
+\index{Transportproblem}%
+Zum Transport einheitlicher Objekte von mehreren Angebots- zu mehreren Nachfrageorten ist ein optimaler,
+d.~h.~kostenminimaler Plan zu finden, wobei die vorhandenen und zu liefernden Mengen an den einzelnen Standorten gegeben sowie die jeweiligen Transportkosten pro Einheit zwischen allen Standorten bekannt sind.
+Nun gibt es im Bereich des klassischen Transportproblems Sonderfälle.
+Ein Sonderfall ist z.~B.~das Zuordnungsproblem.
+\index{Zuordnungsproblem}%
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index aad45cc..0c23c7c 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -3,21 +3,28 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Beschrieb des Zuordnungsproblems
+\section{Das Zuordnungsproblems
\label{munkres:section:teil1}}
-\rhead{Problemstellung}
+\rhead{Zuordnungsproblem}
Das Spezielle an einem Zuordnungsproblem ist, dass es an jedem Ort nur eine Einheit angeboten bzw. nachgefragt wird. Es werden hier nicht Mengen möglichst kostenminimal von einem zum anderen
-Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.B. Personen oder Bau-Maschinen auf bestimmte Orte, Stellen oder Aufgaben.
-Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde der Munkres-Algorithmus, auch die Ungarische Methode genannt, entwickelt. Diese Methode ist ein weiteres Hauptthema dieses Kapitels.
+Ort transportiert, sondern es geht um die kostenminimale Zuordnung von z.~B.~Personen oder Bau-Maschinen auf bestimmte Orte, Stellen oder Aufgaben.
+Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde der Munkres-Algorithmus, auch die ungarische Methode genannt, entwickelt. Diese Methode ist ein weiteres Hauptthema dieses Kapitels.
+\index{Munkres-Algorithmus}%
+\index{ungarische Methode}%
\subsection{Zuordnungsproblem an einem konkreten Beispiel
\label{munkres:subsection:bonorum}}
Als Beispiel betrachten wir den Fall, wo ein Bauunternehmer einen Bauingenieur beauftragt, eine optimale Transportroute für die Umplatzierung seiner Kräne zu eruieren. Das heisst, die Transportstrecke für die Umplatzierung seine Kräne
soll möglichst klein werden.
Die Frage lautet: Wie sind die Kräne umzusetzen, damit deren Transportstrecke minimal wird? Bei der normalen Optimierung dürfen normalerweise beliebige reelle Werte $\mathbb{R}$ angenommen werden.
-Beim Beispiel mit den Kräne gibt es aber ein Problem. Bei der Suche nach der optimalen Lösung darf nur die Methode der ganzzahligen Optimierung gewählt werden. Materialien kann man aufteilen, jedoch Maschinen nicht. Die Bauarbeiter auf der neuen Baustelle benötigen einen ganzen Kran und nicht nur einen halben Kran. Es muss immer ein ganzer Kran (Anzahl 1) von A nach B oder gar kein Kran (Anzahl 0) verschoben werden.
-Für solche Optimierungsprobleme für reelle Variablen sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art und Weise lösbar. Doch das Problem bleibt, wie in der Illustration oben ersichtlich. Es kann mit ganzzahligen Punkten kein Optimum erzielt werden. Das Ziel ist es an das Optimum so nah wie möglich heranzukommen und dies ist eine vergleichsweise träge und langsame Angelegenheit.
+\index{Optimierung}%
+Für solche Optimierungsprobleme für reelle Variablen sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art und Weise lösbar.
+
+Beim Beispiel der Kräne gibt es aber ein Problem. Bei der Suche nach der optimalen Lösung darf nur die Methode der ganzzahligen Optimierung gewählt werden. Materialien kann man aufteilen, jedoch Maschinen nicht. Die Bauarbeiter auf der neuen Baustelle benötigen einen ganzen Kran und nicht nur einen halben Kran. Es muss immer ein ganzer Kran (Anzahl 1) von $A$ nach $B$ oder gar kein Kran (Anzahl 0) verschoben werden.
+\index{ganzzahlige Optimierung}%
+\index{Optimierung, ganzzahlig}%
+Es entsteht das Problem, wie in der Illustration~\ref{munkres:Vr2} ersichtlich. Es kann mit ganzzahligen Punkten kein Optimum erzielt werden. Das Ziel ist es an das Optimum so nah wie möglich heranzukommen und dies ist eine vergleichsweise träge und langsame Angelegenheit.
\begin{figure}
\centering
@@ -30,11 +37,11 @@ Für solche Optimierungsprobleme für reelle Variablen sind verschiedene Verfahr
\subsection{Zuordnungsproblem abstrakt
\label{munkres:subsection:bonorum}}
-In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1
+In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1:
\begin{equation}
-a_{i}=b_{j}=1
+a_{i}=b_{j}=1.
\end{equation}
-Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix
+Das Ziel ist, die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix
\[
A
=
@@ -47,21 +54,41 @@ a_{n1}&a_{n2}&\dots &a_{nn}
\in \mathbb{R}^{n,n}
\]
kann der Faktor Kosten mit in die Rechnung eingebracht werden.
-In den Zellen dieser Matrix sind die Zahlen $a_{i,j}$ dargestellt, welche den Weg in z.B. Kilometer beschreiben.
-Sie entstehen, wenn man z.B. einem Kran $i$ dem Einsatzort $j$ zuordnet.
+In den Zellen dieser Matrix sind die Zahlen $a_{i,j}$ dargestellt, welche den Weg in z.~B.~Kilometer beschreiben.
+Sie entstehen, wenn man z.~B.~einem Kran $i$ dem Einsatzort $j$ zuordnet.
\subsection{Alternative Darstellungen des Zuordnungsproblems
\label{munkres:subsection:bonorum}}
\subsubsection{Netzwerk}
-Ein (Fluss- oder Transport-) Netzwerk (engl. network) ist ein zusammenhängender Graph, bei dem jede Kante einen Fluss aufnehmen kann und jede Kante eine Kapazität für den Fluss hat. Die Menge des Flusses auf einer Kante kann die Kapazität der Kante nicht überschreiten. Ein Fluss muss die Einschränkung erfüllen, dass die Menge des Flusses in einen Knoten gleich der Menge des Flusses aus ihm heraus ist. Ein Fluss-Netzwerk (engl. flow network) ist ein Netzwerk, dessen Kanten zusätzlich Kosten pro Mengeneinheit des Flusses zugeordnet sind. Typischerweise will man einen Fluss durch die Kanten bestimmen, der den Einschränkungen des Netzwerks genügt und dessen Gesamtkosten minimal sind. Im Bild 21.2 dargestellt sind in den eckigen Klammern links die externen Flüsse $[1]$ für jeden Kran und in den eckigen Klammern rechts eine $[-1]$ für jeden Baustellenort. Die Kosten sind entlang der Kanten als Zahlen in Klammern dargestellt.
+Ein Fluss- oder Transportnetzwerk (engl.~network) ist ein zusammenhängender Graph, bei dem jede Kante einen Fluss aufnehmen kann und jede Kante eine Kapazität für den Fluss hat.
+\index{Flussnetzwerk}%
+\index{Transportnetzwerk}%
+\index{zusammenhängend}%
+\index{Fluss}%
+\index{Kapazität}%
+Die Menge des Flusses auf einer Kante kann die Kapazität der Kante nicht überschreiten.
+Ein Fluss muss die Einschränkung erfüllen, dass die Menge des Flusses
+in einen Knoten gleich der Menge des Flusses aus ihm heraus ist.
+Ein Flussnetzwerk (engl.~flow network) ist ein Netzwerk, dessen Kanten zusätzlich Kosten pro Mengeneinheit des Flusses zugeordnet sind.
+\index{Flussnetzwerk}%
+Typischerweise will man einen Fluss durch die Kanten bestimmen, der den Einschränkungen des Netzwerks genügt und dessen Gesamtkosten minimal sind.
+Im Bild~\ref{munkres:netzwerkdarstellung}
+dargestellt sind in den eckigen Klammern links die externen Flüsse $[1]$ für jeden Kran und in den eckigen Klammern rechts eine $[-1]$ für jeden Baustellenort. Die Kosten sind entlang der Kanten als Zahlen in Klammern dargestellt.
\subsubsection{Matrix}
-Im Bild 21.3 ist eine typische $4\times 4$ Matrix dargestellt. Die Zeilen A1 bis A4 betreffen z.B. vier bestehende Maschinenlager eines Unternehmers. In den Spalten B1 bis B4 sind vier neue Baustellenorte zugewiesen. Die Zahlen in der Matrix bedeuten z.B. die Distanz in Kilometer von dem jeweiligen Lager zur jeweiligen Baustelle.
+Im Bild~\ref{munkres:matrixdarstellung}
+ist eine typische $4\times 4$ Matrix dargestellt. Die Zeilen A1 bis A4 betreffen z.~B.~vier bestehende Maschinenlager eines Unternehmers. In den Spalten B1 bis B4 sind vier neue Baustellenorte zugewiesen. Die Zahlen in der Matrix bedeuten z.~B.~die Distanz in Kilometer von dem jeweiligen Lager zur jeweiligen Baustelle.
\subsubsection{Bitpartiter Graph}
Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen
-zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Zwischen zwei Gruppen von Objekten wird hierbei eine eindeutige Zuordnung hergestellt. Der Graph ist in Abbildung 21.4 ersichtlich.
+zwischen den Elementen zweier Mengen.
+\index{bipartit}%
+\index{Graph, bipartit}%
+Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen.
+Zwischen zwei Gruppen von Objekten wird hierbei eine eindeutige Zuordnung hergestellt.
+Der Graph ist in Abbildung~\ref{munkres:bipartit}
+ersichtlich.
\begin{itemize}
-\item 3 = Anzahl der Knoten aus Menge A.
-\item 3 = Anzahl der Knoten aus Menge B.
+\item $3 =\mathstrut$Anzahl der Knoten aus Menge $A$.
+\item $3 =\mathstrut$Anzahl der Knoten aus Menge $B$.
\end{itemize}
@@ -69,19 +96,19 @@ zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung v
\centering
\includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung}
\caption{Typische Netzwerkdarstellung eines Zuordnungsproblems.}
-\label{munkres:Vr2}
+\label{munkres:netzwerkdarstellung}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=5cm]{papers/munkres/figures/Matrixdarstellung}
-\caption{Typische 4x4 Matrixdarstellung eines Zuordnungsproblems.}
-\label{munkres:Vr2}
+\caption{Typische $4\times 4$ Matrixdarstellung eines Zuordnungsproblems.}
+\label{munkres:matrixdarstellung}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=5cm]{papers/munkres/figures/bipartiter_graph}
\caption{$K_{3,3}$ vollständig bipartiter Graph mit 3 Knoten pro Teilmenge.}
-\label{munkres:Vr2}
+\label{munkres:bipartit}
\end{figure}
diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex
index 2fe24f8..e4e968a 100644
--- a/buch/papers/munkres/teil2.tex
+++ b/buch/papers/munkres/teil2.tex
@@ -3,10 +3,16 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Schwierigkeit der Lösung (Permutationen)
+\section{Schwierigkeit der Lösung
\label{munkres:section:teil2}}
-\rhead{Schwierigkeit der Lösung (Permutationen)}
+\rhead{Schwierigkeit der Lösung}
-Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet.
-Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer $n$×$n$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigende Permutationen.
+Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung.
+Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet.
+\index{Transversale einer Matrix}%
+Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird.
+
+In einer $n\times n$-Matrix gibt es genau so viele Möglichkeiten, die Zeilen- bzw.~Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$.
+Ausser bei kleinen Matrizen ist es daher nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden.
+Schon bei einer $10\times 10$-Matrix gibt es nahezu 3.63 Millionen ($10!=3628800$) zu berücksichtigende Permutationen.
diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index fd25a74..500216a 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -3,9 +3,9 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Der Munkres-Algorithmus (Ungarische Methode)
+\section{Der Munkres-Algorithmus oder die ungarische Methode
\label{munkres:section:teil3}}
-\rhead{Der Munkres-Algorithmus (Ungarische Methode)}
+\rhead{Ungarische Methode}
Mit der ungarischen Methode können also Optimierungsprobleme gelöst
werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen.
@@ -16,33 +16,51 @@ Gesamtgewinn maximiert werden kann.
\subsection{Geschichte
\label{munkres:subsection:malorum}}
Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht.
+\index{Kuhn, Harold}%
Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus
weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker
basierte: Dénes Kőnig und Jenő Egerváry.
+\index{Kőnig, Dénes}%
+\index{Egerváry, Jenő}%
+\index{Munkres, James}%
James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest,
dass der Algorithmus (stark) polynomiell ist.
-Seitdem ist der Algorithmus auch als Kuhn-Munkres oder
+Seitdem ist der Algorithmus auch als Kuhn-Munkres- oder
Munkres-Zuordnungsalgorithmus bekannt.
+\index{Kuhn-Munkres-Zuordnungsalgorithmus}%
+\index{Munkres-Zuordnungsalgorithmus}%
Die Zeitkomplexität des ursprünglichen Algorithmus war $O(n^4)$,
später wurde zudem festgestellt, dass er modifiziert werden kann,
um eine $O(n^3)$-Laufzeit zu erreichen.
\subsection{Besondere Leistung der Ungarischen Methode
\label{munkres:subsection:malorum}}
-Die Ungarische Methode ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem
+Die ungarische Methode ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem
+\index{Optimierungsalgorithmus, kombinatorisch}%
in polynomieller Zeit löst.
Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms
-wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei die ''Grösse'' des Problems.
+\index{polynomielle Laufzeit}%
+wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei die ``Grösse'' des Problems.
\subsection{Unterschiedliche Anzahl von Quellen und Zielen
\label{munkres:subsection:malorum}}
-Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. Das ist z. B. dann der Fall, wenn drei Mitarbeiter vier verschiedene Eignungstests absolvieren müssen. In diesem Fall wird in der Ungarischen Methode die Matrix künstlich mittels einer Dummy Position zu einem Quadrat ergänzt. Dummy-Positionen werden dann mit der größten vorhandenen Zahl aus der Matrix besetzt. Beispielsweise wird eine $3\times 4$ zu einer $4\times 4$-Matrix.
+Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt.
+Das ist z.~B.~dann der Fall, wenn drei Mitarbeiter vier verschiedene Eignungstests absolvieren müssen.
+In diesem Fall wird in der Ungarischen Methode die Matrix künstlich mittels einer Dummy-Position zu einem Quadrat ergänzt.
+Dummy-Positionen werden dann mit der größten vorhandenen Zahl aus der Matrix besetzt.
+Beispielsweise wird eine $3\times 4$ zu einer $4\times 4$-Matrix.
\subsection{Beispiel eines händischen Verfahrens
\label{munkres:subsection:malorum}}
+\begin{figure}
+\centering
+\includegraphics[width=8cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png}
+\caption{Händisches Beispiel des Munkres Algorithmus, minimaler Transportweg.}
+\label{munkres:Vr2}
+\end{figure}
Die ungarische Methode kann in einem einfachen händischen Beispiel erläutert werden. Wir gehen von der Kostenmatrix $A$ aus. Diese Matrix wird in mehreren Schritten immer weiter reduziert. Anschliessend erfolgen mehrere Zuordnungen. Hierbei ist zu beachten, dass jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt. Es gibt Situationen, in denen man nichts mehr tun muss, um eine optimale Zuordnung zu finden. Eine optimale Zuordnung ohne zusätzliche Kosten ist eine Auswahl genau eines Feldes in jeder Zeile und Spalte, welches 0 enthält. Das Ziel des Algorithmus ist also, die Matrix so zu ändern, dass genügend Nullen in der Matrix vorkommen. Es ist zudem wichtig, dass man nach jeder Modifikation der Matrix testet, ob man bereits eine Zuordnung machen kann, also genügend Nullen hat.
-Das Vorgehen wird in den nachfolgenden Schritten 1-6 beschrieben und auch in der Abbildung 21.5 dargestellt.
+Das Vorgehen wird in den nachfolgenden Schritten 1--6 beschrieben und auch in der Abbildung 21.5 dargestellt.
\begin{enumerate}
\item Man beginnt mit der Zeilen-Reduktion. Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl, jeweils in rot markiert, wird bei allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab, die man hat, um eine Baustelle zu erreichen. Man erkennt, dass die Nullen mit zwei Linien abdeckbar sind. Das heisst es gibt zwei Spalten bei denen noch keine Zuordnungen möglich sind.
@@ -56,22 +74,22 @@ Dieser Schritt 3 muss so oft wiederholt werden, bis genügend viele Nullen in de
\item In Schritt 4 sollen jetzt möglichst viele Nullen markiert werden, welche freistehend sind.
Freistehend bedeutet, dass sowohl in der jeweiligen Zeile und Spalte keine andere markierte Null vorhanden ist.
-\item Alle markierten Nullen werden jetzt in eine 1 umgewandelt. Die restlichen Ziffern in der Matrix, exklusiv die einsen, sollen jetzt ignoriert und durch eine Null ersetzt werden.
+\item Alle markierten Nullen werden jetzt in eine 1 umgewandelt. Die restlichen Ziffern in der Matrix, exklusiv die Einsen, sollen jetzt ignoriert und durch eine 0 ersetzt werden.
-\item Zu guter Letzt werden überall wo eine 1 steht, die Zahlen aus der Ausgangsmatrix eingefügt. Nach Einsetzen der Zahlen können die in rot markierten Zahlen aufsummiert werden. Man erhält den minimalsten Transportweg von total 13 Kilometer.
+\item Zu guter Letzt werden überall wo eine 1 steht, die Zahlen aus der Ausgangsmatrix eingefügt. Nach Einsetzen der Zahlen können die in rot markierten Zahlen aufsummiert werden. Man erhält den minimalen Transportweg von total 13 Kilometer.
\end{enumerate}
\begin{figure}
\centering
-\includegraphics[width=8cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png}
-\caption{Händisches Beispiel des Munkres Algorithmus, minimalster Transportweg.}
+\includegraphics[width=3cm]{papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png}
+\caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne }
\label{munkres:Vr2}
-\end{figure}
+\end{figure}
\subsection{Zuordnung der Kräne
\label{munkres:subsection:malorum}}
-Als Resultat des Munkres-Algorithmus werden in Abbildung 21.6 nebst dem minimalsten Transportweg auch die optimalste Zuweisung der Kräne auf die neuen Standorte ersichtlich.
+Als Resultat des Munkres-Algorithmus werden in Abbildung 21.6 nebst dem minimalen Transportweg auch die optimale Zuweisung der Kräne auf die neuen Standorte ersichtlich.
Es können die folgenden Zuordnungen aus der Matrix abgelesen werden:
\begin{itemize}
\item Der Kran von Baustelle A1 soll zur Baustelle B2.
@@ -80,9 +98,3 @@ Es können die folgenden Zuordnungen aus der Matrix abgelesen werden:
\item Der Kran von Baustelle A4 soll zur Baustelle B1.
\end{itemize}
-\begin{figure}
-\centering
-\includegraphics[width=3cm]{papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png}
-\caption{Händisches Beispiel des Munkres Algorithmus, Zuweisung der Kräne }
-\label{munkres:Vr2}
-\end{figure} \ No newline at end of file