From cecdcdb230662af594ce68715c61f1263bff9ace Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Mon, 26 Jul 2021 07:57:58 +0200
Subject: add munkres files

---
 buch/papers/munkres/teil1.tex | 62 ++++++++++---------------------------------
 1 file changed, 14 insertions(+), 48 deletions(-)

(limited to 'buch/papers/munkres/teil1.tex')

diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index f4f5e39..7cbbbfd 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -3,53 +3,19 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Teil 1
+\section{Was ist die ungarische Methode?
 \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
-\begin{equation}
-\int_a^b x^2\, dx
-=
-\left[ \frac13 x^3 \right]_a^b
-=
-\frac{b^3-a^3}3.
-\label{munkres:equation1}
-\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.
-
-
+Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem
+in polynomieller Zeit löst.
+\begin{itemize}
+\item
+Polynom = vielgliedrig
+\end{itemize}
+Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms
+wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert.
+Mit der ungarischen Methode können also lineare 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. 
-- 
cgit v1.2.1


From 4f9cf26c7802a163da6b18cec9db62e75a9730cb Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Marc=20K=C3=BChne?= <kuehnee@marcs-macbook-pro.home>
Date: Tue, 27 Jul 2021 12:30:10 +0200
Subject: neue version

---
 buch/papers/munkres/teil1.tex | 65 +++++++++++++++++++++++++++++++++----------
 1 file changed, 51 insertions(+), 14 deletions(-)

(limited to 'buch/papers/munkres/teil1.tex')

diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index 7cbbbfd..c13732c 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -3,19 +3,56 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Was ist die ungarische Methode?
+\section{Beschrieb des Zuordnungsproblems
 \label{munkres:section:teil1}}
 \rhead{Problemstellung}
-Es ist ein kombinatorischer Optimierungsalgorithmus, der das Zuordnungsproblem
-in polynomieller Zeit löst.
-\begin{itemize}
-\item
-Polynom = vielgliedrig
-\end{itemize}
-Der Begriff polynomielle Laufzeit bedeutet, dass die Laufzeit des Programms
-wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert.
-Mit der ungarischen Methode können also lineare 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. 
+
+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-Materialien 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}}
+
+\subsection{Zuordnungsproblem abstrakt
+\label{munkres:subsection:bonorum}}
+
+Es sind alle Angebots- und Bedarfsmengen gleich 1 
+\begin{equation}
+a_{i}=b_{j}=1
+\end{equation}
+
+\subsection{alternative Darstellungen des Zuordnungsproblems
+\label{munkres:subsection:bonorum}}
+\begin{equation}
+Netzwerk
+\end{equation}
+\begin{equation}
+Matrix
+\end{equation}
+\begin{equation}
+Bitpartiter Graph
+\end{equation}
+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}
-- 
cgit v1.2.1


From 6c2ea74f867d898626e5ef25c61814cd2aa49bbd Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Marc=20K=C3=BChne?= <kuehnee@Marcs-MacBook-Pro.local>
Date: Sat, 31 Jul 2021 11:57:23 +0200
Subject: neue version

---
 buch/papers/munkres/teil1.tex | 17 +++++++++++++----
 1 file changed, 13 insertions(+), 4 deletions(-)

(limited to 'buch/papers/munkres/teil1.tex')

diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index c13732c..4532783 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -8,21 +8,30 @@
 \rhead{Problemstellung}
 
 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-Materialien auf bestimmte Orte, Stellen oder Aufgaben.
+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 der 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 gib 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.
+Doch das Problem bleibt, mit ganzzahligen Punkten kann kein Optimum erzielt werden und ist eine träge, langsame Angelegenheit.
 
 \subsection{Zuordnungsproblem abstrakt
 \label{munkres:subsection:bonorum}}
 
-Es sind alle Angebots- und Bedarfsmengen gleich 1 
+In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1 
 \begin{equation}
 a_{i}=b_{j}=1
 \end{equation}
 
-\subsection{alternative Darstellungen des Zuordnungsproblems
+Das Ziel ist es die Gesamtkosten zu minimieren. Mit Hilfe einer $n\times n$ Matrix $\mathbb{A}$ $\mathbb{\in}$ $\mathbb{R}^{n,n}$ kann dann auch der Faktor Kosten mit in die Rechnung eingebracht werden. 
+
+In der Zelle dieser Matrix sind $a_{i,j}$ die Kosten dargestellt, die entstehen, wenn man z.B. einem Arbeiter $i$ die Aufgabe $j$ zuordnet.
+
+\subsection{Alternative Darstellungen des Zuordnungsproblems
 \label{munkres:subsection:bonorum}}
 \begin{equation}
 Netzwerk
@@ -35,7 +44,7 @@ Bitpartiter Graph
 \end{equation}
 Ein bipartiter Graph ist ein mathematisches Modell für Beziehungen
 zwischen den Elementen zweier Mengen.
-Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen» 
+Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. 
 \begin{figure}
 \centering
 \includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung}
-- 
cgit v1.2.1

