From cecdcdb230662af594ce68715c61f1263bff9ace Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= 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?= 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?= 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