aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/munkres
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-08-03 07:37:42 +0200
committerGitHub <noreply@github.com>2021-08-03 07:37:42 +0200
commitf31aca6129f3c84f1ed4f59378fd31cbdc58ec3b (patch)
tree97c32dbdcbcc888a9030d149f5a765f006fcd631 /buch/papers/munkres
parent1. Version Kapitel Rotation und Spiegelung (diff)
parentMerge pull request #60 from Kuehnee/master (diff)
downloadSeminarMatrizen-f31aca6129f3c84f1ed4f59378fd31cbdc58ec3b.tar.gz
SeminarMatrizen-f31aca6129f3c84f1ed4f59378fd31cbdc58ec3b.zip
Merge branch 'master' into master
Diffstat (limited to 'buch/papers/munkres')
-rw-r--r--buch/papers/munkres/figures/Matrixdarstellung.pngbin0 -> 46310 bytes
-rw-r--r--buch/papers/munkres/figures/Netzwerkdarstellung.pngbin0 -> 307876 bytes
-rw-r--r--buch/papers/munkres/figures/Ungarische_Methode_Beispiel.pngbin0 -> 1179631 bytes
-rw-r--r--buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.pngbin0 -> 117508 bytes
-rw-r--r--buch/papers/munkres/figures/beispiel_munkres.pngbin0 -> 245951 bytes
-rw-r--r--buch/papers/munkres/figures/bipartiter_graph.pngbin0 -> 246867 bytes
-rw-r--r--buch/papers/munkres/figures/ganzzahlige_punkte.pngbin0 -> 257390 bytes
-rw-r--r--buch/papers/munkres/main.tex26
-rw-r--r--buch/papers/munkres/teil0.tex20
-rw-r--r--buch/papers/munkres/teil1.tex106
-rw-r--r--buch/papers/munkres/teil2.tex35
-rw-r--r--buch/papers/munkres/teil3.tex140
-rw-r--r--buch/papers/munkres/teil4.tex9
-rw-r--r--buch/papers/munkres/teil5.tex8
14 files changed, 201 insertions, 143 deletions
diff --git a/buch/papers/munkres/figures/Matrixdarstellung.png b/buch/papers/munkres/figures/Matrixdarstellung.png
new file mode 100644
index 0000000..91a376d
--- /dev/null
+++ b/buch/papers/munkres/figures/Matrixdarstellung.png
Binary files differ
diff --git a/buch/papers/munkres/figures/Netzwerkdarstellung.png b/buch/papers/munkres/figures/Netzwerkdarstellung.png
new file mode 100644
index 0000000..6c20bf4
--- /dev/null
+++ b/buch/papers/munkres/figures/Netzwerkdarstellung.png
Binary files differ
diff --git a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png
new file mode 100644
index 0000000..fb4d061
--- /dev/null
+++ b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel.png
Binary files differ
diff --git a/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png
new file mode 100644
index 0000000..73217d3
--- /dev/null
+++ b/buch/papers/munkres/figures/Ungarische_Methode_Beispiel_Zuw.png
Binary files differ
diff --git a/buch/papers/munkres/figures/beispiel_munkres.png b/buch/papers/munkres/figures/beispiel_munkres.png
new file mode 100644
index 0000000..2303708
--- /dev/null
+++ b/buch/papers/munkres/figures/beispiel_munkres.png
Binary files differ
diff --git a/buch/papers/munkres/figures/bipartiter_graph.png b/buch/papers/munkres/figures/bipartiter_graph.png
new file mode 100644
index 0000000..87c164c
--- /dev/null
+++ b/buch/papers/munkres/figures/bipartiter_graph.png
Binary files differ
diff --git a/buch/papers/munkres/figures/ganzzahlige_punkte.png b/buch/papers/munkres/figures/ganzzahlige_punkte.png
new file mode 100644
index 0000000..5689825
--- /dev/null
+++ b/buch/papers/munkres/figures/ganzzahlige_punkte.png
Binary files differ
diff --git a/buch/papers/munkres/main.tex b/buch/papers/munkres/main.tex
index 4dd20fa..e5282dc 100644
--- a/buch/papers/munkres/main.tex
+++ b/buch/papers/munkres/main.tex
@@ -3,34 +3,18 @@
%
% (c) 2020 Hochschule Rapperswil
%
-\chapter{Thema\label{chapter:munkres}}
-\lhead{Thema}
+\chapter{Das Zuordnungsproblem und der Munkres-Algorithmus\label{chapter:munkres}}
+\lhead{Das Zuordnungsproblem und der Munkres-Algorithmus}
\begin{refsection}
-\chapterauthor{Hans Muster}
+\chapterauthor{Marc Kühne}
-Ein paar Hinweise für die korrekte Formatierung des Textes
-\begin{itemize}
-\item
-Absätze werden gebildet, indem man eine Leerzeile einfügt.
-Die Verwendung von \verb+\\+ ist nur in Tabellen und Arrays gestattet.
-\item
-Die explizite Platzierung von Bildern ist nicht erlaubt, entsprechende
-Optionen werden gelöscht.
-Verwenden Sie Labels und Verweise, um auf Bilder hinzuweisen.
-\item
-Beginnen Sie jeden Satz auf einer neuen Zeile.
-Damit ermöglichen Sie dem Versionsverwaltungssysteme, Änderungen
-in verschiedenen Sätzen von verschiedenen Autoren ohne Konflikt
-anzuwenden.
-\item
-Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren
-Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern.
-\end{itemize}
\input{papers/munkres/teil0.tex}
\input{papers/munkres/teil1.tex}
\input{papers/munkres/teil2.tex}
\input{papers/munkres/teil3.tex}
+\input{papers/munkres/teil4.tex}
+\input{papers/munkres/teil5.tex}
\printbibliography[heading=subbibliography]
\end{refsection}
diff --git a/buch/papers/munkres/teil0.tex b/buch/papers/munkres/teil0.tex
index de522c7..0578429 100644
--- a/buch/papers/munkres/teil0.tex
+++ b/buch/papers/munkres/teil0.tex
@@ -3,20 +3,8 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Teil 0\label{munkres:section:teil0}}
-\rhead{Teil 0}
-Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
-nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam
-erat, sed diam voluptua \cite{munkres:bibtex}.
-At vero eos et accusam et justo duo dolores et ea rebum.
-Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum
-dolor sit amet.
-
-Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
-nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam
-erat, sed diam voluptua.
-At vero eos et accusam et justo duo dolores et ea rebum. Stet clita
-kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit
-amet.
-
+\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.
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index f4f5e39..d22b57f 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -3,53 +3,71 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Teil 1
+\section{Beschrieb des Zuordnungsproblems
\label{munkres:section:teil1}}
\rhead{Problemstellung}
-Sed ut perspiciatis unde omnis iste natus error sit voluptatem
-accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
-quae ab illo inventore veritatis et quasi architecto beatae vitae
-dicta sunt explicabo.
-Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit
-aut fugit, sed quia consequuntur magni dolores eos qui ratione
-voluptatem sequi nesciunt
+
+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.
+
+\subsection{Zuordnungsproblem an einem konkreten Beispiel
+\label{munkres:subsection:bonorum}}
+Man hat 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 angenommen werden $\mathbb{R}$.
+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 $\mathbb{Z}$. 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 von A nach B oder gar kein Kran verschoben werden. Also 1 oder 0.
+Für solche Optimierungsproblem für reelle Varianten sind verschiedene Verfahren entwickelt worden, die im Allgemeinen auch sehr effizient sind. Das reelle Problem ist also in einer einfachen Art uns 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.
+
+\begin{figure}
+\centering
+\includegraphics[width=5cm]{papers/munkres/figures/ganzzahlige_punkte}
+\caption{Problem der Ganzzahligkeit.}
+\label{munkres:Vr2}
+\end{figure}
+
+
+\subsection{Zuordnungsproblem abstrakt
+\label{munkres:subsection:bonorum}}
+
+In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1
+\begin{equation}
+a_{i}=b_{j}=1
+\end{equation}
+Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix $\mathbb{A}$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann der Faktor Kosten mit in die Rechnung eingebracht werden.
+In der Zelle dieser Matrix sind $a_{i,j}$ die Wege dargestellt, die entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet.
+
+\subsection{Alternative Darstellungen des Zuordnungsproblems
+\label{munkres:subsection:bonorum}}
+\begin{equation}
+Netzwerk
+\end{equation}
+\begin{equation}
+Matrix
+\end{equation}
\begin{equation}
-\int_a^b x^2\, dx
-=
-\left[ \frac13 x^3 \right]_a^b
-=
-\frac{b^3-a^3}3.
-\label{munkres:equation1}
+Bitpartiter Graph
\end{equation}
-Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet,
-consectetur, adipisci velit, sed quia non numquam eius modi tempora
-incidunt ut labore et dolore magnam aliquam quaerat voluptatem.
-
-Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis
-suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur?
-Quis autem vel eum iure reprehenderit qui in ea voluptate velit
-esse quam nihil molestiae consequatur, vel illum qui dolorem eum
-fugiat quo voluptas nulla pariatur?
-
-\subsection{De finibus bonorum et malorum
-\label{munkres:subsection:finibus}}
-At vero eos et accusamus et iusto odio dignissimos ducimus qui
-blanditiis praesentium voluptatum deleniti atque corrupti quos
-dolores et quas molestias excepturi sint occaecati cupiditate non
-provident, similique sunt in culpa qui officia deserunt mollitia
-animi, id est laborum et dolorum fuga \eqref{000tempmlate:equation1}.
-
-Et harum quidem rerum facilis est et expedita distinctio
-\ref{munkres:section:loesung}.
-Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil
-impedit quo minus id quod maxime placeat facere possimus, omnis
-voluptas assumenda est, omnis dolor repellendus
-\ref{munkres:section:folgerung}.
-Temporibus autem quibusdam et aut officiis debitis aut rerum
-necessitatibus saepe eveniet ut et voluptates repudiandae sint et
-molestiae non recusandae.
-Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis
-voluptatibus maiores alias consequatur aut perferendis doloribus
-asperiores repellat.
+Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen
+zwischen den Elementen zweier Mengen.
+Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen.
+\begin{figure}
+\centering
+\includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung}
+\caption{Typische Netzwerkdarstellung eines Zuordnungsproblems.}
+\label{munkres:Vr2}
+\end{figure}
+\begin{figure}
+\centering
+\includegraphics[width=5cm]{papers/munkres/figures/Matrixdarstellung}
+\caption{Typische 4x4 Matrixdarstellung eines Zuordnungsproblems.}
+\label{munkres:Vr2}
+\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}
+\end{figure}
diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex
index 23536b9..a3b249e 100644
--- a/buch/papers/munkres/teil2.tex
+++ b/buch/papers/munkres/teil2.tex
@@ -3,38 +3,11 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Teil 2
+\section{Schwierigkeit der Lösung (Permutationen)
\label{munkres:section:teil2}}
-\rhead{Teil 2}
-Sed ut perspiciatis unde omnis iste natus error sit voluptatem
-accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
-quae ab illo inventore veritatis et quasi architecto beatae vitae
-dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit
-aspernatur aut odit aut fugit, sed quia consequuntur magni dolores
-eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam
-est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci
-velit, sed quia non numquam eius modi tempora incidunt ut labore
-et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima
-veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam,
-nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure
-reprehenderit qui in ea voluptate velit esse quam nihil molestiae
-consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla
-pariatur?
+\rhead{Schwierigkeit der Lösung (Permutationen)}
-\subsection{De finibus bonorum et malorum
-\label{munkres:subsection:bonorum}}
-At vero eos et accusamus et iusto odio dignissimos ducimus qui
-blanditiis praesentium voluptatum deleniti atque corrupti quos
-dolores et quas molestias excepturi sint occaecati cupiditate non
-provident, similique sunt in culpa qui officia deserunt mollitia
-animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis
-est et expedita distinctio. Nam libero tempore, cum soluta nobis
-est eligendi optio cumque nihil impedit quo minus id quod maxime
-placeat facere possimus, omnis voluptas assumenda est, omnis dolor
-repellendus. Temporibus autem quibusdam et aut officiis debitis aut
-rerum necessitatibus saepe eveniet ut et voluptates repudiandae
-sint et molestiae non recusandae. Itaque earum rerum hic tenetur a
-sapiente delectus, ut aut reiciendis voluptatibus maiores alias
-consequatur aut perferendis doloribus asperiores repellat.
+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ücksichtigender Permutationen.
diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index b67ad74..874baae 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -3,38 +3,116 @@
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Teil 3
+\section{Der Munkres-Algorithmus (Ungarische Methode)
\label{munkres:section:teil3}}
-\rhead{Teil 3}
-Sed ut perspiciatis unde omnis iste natus error sit voluptatem
-accusantium doloremque laudantium, totam rem aperiam, eaque ipsa
-quae ab illo inventore veritatis et quasi architecto beatae vitae
-dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit
-aspernatur aut odit aut fugit, sed quia consequuntur magni dolores
-eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam
-est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci
-velit, sed quia non numquam eius modi tempora incidunt ut labore
-et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima
-veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam,
-nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure
-reprehenderit qui in ea voluptate velit esse quam nihil molestiae
-consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla
-pariatur?
-
-\subsection{De finibus bonorum et malorum
+\rhead{Der Munkres-Algorithmus (Ungarische Methode)}
+
+Mit der ungarischen Methode können also Optimierungsprobleme gelöst
+werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen.
+Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so
+optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der
+Gesamtgewinn maximiert werden kann.
+
+\subsection{Geschichte
+\label{munkres:subsection:malorum}}
+Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht.
+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.
+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
+Munkres-Zuordnungsalgorithmus bekannt.
+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
+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.
+
+\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 eine 3 Mitarbeiter 4 Eignungstests abdsolvieren müssen. In diesem Fall wird in der Ungarischen Methode die Matrix künstlich mittels einer Dummy Position quadratisch ergänzt. Dummy-Positionen werden dann mit der größten vorhandenen Zahl aus der Matrix besetzt. Beispielsweise eine $4\times 3$ wird zu einer $4\times 4$ Matrix.
+
+\subsection{Beispiel eines händischen Verfahrens
\label{munkres:subsection:malorum}}
-At vero eos et accusamus et iusto odio dignissimos ducimus qui
-blanditiis praesentium voluptatum deleniti atque corrupti quos
-dolores et quas molestias excepturi sint occaecati cupiditate non
-provident, similique sunt in culpa qui officia deserunt mollitia
-animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis
-est et expedita distinctio. Nam libero tempore, cum soluta nobis
-est eligendi optio cumque nihil impedit quo minus id quod maxime
-placeat facere possimus, omnis voluptas assumenda est, omnis dolor
-repellendus. Temporibus autem quibusdam et aut officiis debitis aut
-rerum necessitatibus saepe eveniet ut et voluptates repudiandae
-sint et molestiae non recusandae. Itaque earum rerum hic tenetur a
-sapiente delectus, ut aut reiciendis voluptatibus maiores alias
-consequatur aut perferendis doloribus asperiores repellat.
+Die ungarische Methode kann in einem einfachen händischen Beispiel
+erläutert werden. Es gibt eine Ausgangsmatrix. Diese Matrix wird in mehreren Schritten immer
+weiter reduziert. Anschließend erfolgen mehrere Zuordnungen. Hierbei ist zu beachten, dass
+jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt.
+Die optimale Lösung ist erreicht, wenn genau $n$ Zuordnungen gefunden
+sind.
+
+\begin{enumerate}
+\item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei
+allen anderen Ziffern in der jeweiligen Zeile subtrahiert.
+
+\item Danach zieht man wiederum die kleinste Zahl in jeder Spalte von allen
+Zahlen in der Spalte ab.
+
+\item Es sollen möglichst viele Nullen markiert werden, welche freistehend sind.
+(Freistehend bedeutet, sowohl in der jeweiligen Zeile und Spalte nur
+eine markierte Null zu haben)
+
+\item Jeweilige Zeilen eruieren, bei welchen keine markierte Null vorhanden sind und kennzeichnen.
+
+\item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls
+kennzeichnen (*2)
+
+\item Im der selben Spalte die Markierte Null eruieren und die dazugehörige
+Zeile kennzeichnen (*3)
+
+\item Alle Zeilen durchstreichen, welche KEINE Kennzeichnungen (*) haben
+
+\item Alle Spalten durchstreichen, welche EINE Kennzeichnung besitzt! (hier, *2)
+
+\item Kleinste Ziffer auswählen, welche nicht schon durchgestrichen sind.
+(Im Beispiel ist es die Zahl 1. (Egal welche 1)
+
+\item Die eruierte kleinste Ziffer, wird von den nicht durchgestrichenen Ziffern
+subtrahiert. Danach muss die Matrix wieder komplettiert werden. (inkl. Unterstreichen)
+
+\item Jeweilige Zahlen eruieren, welche vorgängig doppelt durchgestrichen wurden.
+
+\item Kleinste eruierte Ziffer von vorhin auf die zwei markierten Ziffern addieren.
+
+\item Es sollen wiederum von neuem möglichst viele Nullen markiert werden,
+welche freistehend sind. In diesem Schritt werden nur die markierten Nullen betrachtet.
+
+\item Aus allen markierten Nullen in eine eins umwandeln.
+
+\item Die restlichen Ziffern, durch eine Null ersetzen.
+
+\item Zu guter letzt soll überall wo eine 1 steht, in der Ausgangsmatrix die
+dazugehörige Ziffer ausgewählt werden. Nach Einsetzen und Eruieren der Zahlen ergeben sich nach Summieren der Zahlen der minimalste Transportweg.
+\end{enumerate}
+
+\begin{figure}
+\centering
+\includegraphics[width=14cm]{papers/munkres/figures/Ungarische_Methode_Beispiel.png}
+\caption{Händisches Beispiel des Munkres Algorithmus, minimalster Transportweg.}
+\label{munkres:Vr2}
+\end{figure}
+
+\subsection{Zuordnung der Kräne
+\label{munkres:subsection:malorum}}
+
+\begin{itemize}
+\item Der Kran von Baustelle A1 soll zur Baustelle B2.
+\item Der Kran von Baustelle A2 soll zur Baustelle B3.
+\item Der Kran von Baustelle A3 soll zur Baustelle B4.
+\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}
diff --git a/buch/papers/munkres/teil4.tex b/buch/papers/munkres/teil4.tex
new file mode 100644
index 0000000..9a27227
--- /dev/null
+++ b/buch/papers/munkres/teil4.tex
@@ -0,0 +1,9 @@
+%
+% teil4.tex -- Beispiel-File für Teil 4
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{-
+\label{munkres:section:teil4}}
+\rhead{-}
+
diff --git a/buch/papers/munkres/teil5.tex b/buch/papers/munkres/teil5.tex
new file mode 100644
index 0000000..b938c50
--- /dev/null
+++ b/buch/papers/munkres/teil5.tex
@@ -0,0 +1,8 @@
+%
+% teil5.tex -- Beispiel-File für Teil 5
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{-
+\label{munkres:section:teil5}}
+\rhead{-}