aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers
diff options
context:
space:
mode:
authorMarc Kühne <kuehnee@Marcs-MacBook-Pro.local>2021-08-02 21:06:43 +0200
committerMarc Kühne <kuehnee@Marcs-MacBook-Pro.local>2021-08-02 21:06:43 +0200
commit8e6efdb02d8e35d9a3749a377a80de679a8b3ba2 (patch)
treee7ef4f3700710175daa987bc76ee67e8550b6772 /buch/papers
parentfehlendes bild (diff)
downloadSeminarMatrizen-8e6efdb02d8e35d9a3749a377a80de679a8b3ba2.tar.gz
SeminarMatrizen-8e6efdb02d8e35d9a3749a377a80de679a8b3ba2.zip
neue version
Diffstat (limited to '')
-rw-r--r--buch/papers/munkres/teil1.tex16
-rw-r--r--buch/papers/munkres/teil3.tex18
2 files changed, 18 insertions, 16 deletions
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index d22b57f..388a448 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -15,13 +15,13 @@ Um dieses Problem in einer einfachen, händischen Art und Weise zu lösen wurde
\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.
+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 von A nach B oder gar kein Kran verschoben werden. Also 1 oder 0.
+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.
\begin{figure}
\centering
-\includegraphics[width=5cm]{papers/munkres/figures/ganzzahlige_punkte}
+\includegraphics[width=8cm]{papers/munkres/figures/ganzzahlige_punkte}
\caption{Problem der Ganzzahligkeit.}
\label{munkres:Vr2}
\end{figure}
@@ -37,6 +37,14 @@ a_{i}=b_{j}=1
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.
+\begin{figure}
+\centering
+\includegraphics[width=5cm]{papers/munkres/figures/MatrixA.png}
+\caption{Darstellung Matrix $A$}
+\label{munkres:Vr2}
+\end{figure}
+
+
\subsection{Alternative Darstellungen des Zuordnungsproblems
\label{munkres:subsection:bonorum}}
\begin{equation}
diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index 874baae..2a8f4a7 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -36,30 +36,24 @@ wie $n^2$, $n^3$, $n^4$, etc.~wächst und vernünftig skaliert. $n$ ist hierbei
\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.
+Es gibt Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt. Das ist z.B. dann der Fall, wenn 3 Mitarbeiter vier verschiedene Eignungstests absolvieren 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 wird eine $3\times 4$ zu einer $4\times 4$-Matrix.
\subsection{Beispiel eines händischen Verfahrens
\label{munkres:subsection:malorum}}
-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.
+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. Das Vorgehen wird in den nachfolgenden Schritten 1-16 beschrieben und auch in der Abbildung 21.5 dargestellt.
\begin{enumerate}
\item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei
-allen anderen Ziffern in der jeweiligen Zeile subtrahiert.
+allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab.
-\item Danach zieht man wiederum die kleinste Zahl in jeder Spalte von allen
-Zahlen in der Spalte ab.
+\item Auch in diesem Schritt werden die unvermeidbaren Kosten abgezogen. Man zieht 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.
+\item Bei den nachfolgenden Schritten bleiben dann nur noch die Kosten übrig, die man hat, wenn man eine andere Zuordnung wählt. Hierbei 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 Weiter werden die jeweiligen Zeilen eruiert, bei welchen keine markierte Null vorhanden sind. Diese kennzeichnet man.
\item In der vorherigen Zeile die 0 eruieren und die Spalte ebenfalls
kennzeichnen (*2)