aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/munkres
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-08-04 16:27:05 +0200
committerGitHub <noreply@github.com>2021-08-04 16:27:05 +0200
commit7e6a5d89c257dc47292a08a0a00b23a755d8c759 (patch)
treeea6f1d98891db0c2b15c546d0b36a81a8afe9a5d /buch/papers/munkres
parentMerge pull request #64 from Kuehnee/master (diff)
parentneue version (diff)
downloadSeminarMatrizen-7e6a5d89c257dc47292a08a0a00b23a755d8c759.tar.gz
SeminarMatrizen-7e6a5d89c257dc47292a08a0a00b23a755d8c759.zip
Merge pull request #66 from Kuehnee/master
Munkres-MarcKuehne-request-20210804
Diffstat (limited to '')
-rw-r--r--buch/papers/munkres/teil1.tex29
-rw-r--r--buch/papers/munkres/teil3.tex4
2 files changed, 24 insertions, 9 deletions
diff --git a/buch/papers/munkres/teil1.tex b/buch/papers/munkres/teil1.tex
index 363dc06..07489e3 100644
--- a/buch/papers/munkres/teil1.tex
+++ b/buch/papers/munkres/teil1.tex
@@ -35,30 +35,45 @@ In einem Zuordnungsproblem sind alle Angebots- und Bedarfsmengen gleich 1
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.
+In der Zelle dieser Matrix sind $a_{i,j}$ Zahlen dargestellt, welche den Weg in z.B. Kilometer beschreiben.
+Sie entstehen, wenn man z.B. einem Kran $i$ den Einsatzort $j$ zuordnet.
\begin{figure}
-\centering
-\includegraphics[width=5cm]{papers/munkres/figures/MatrixA.png}
+\[
+A
+=
+\begin{pmatrix}
+a_{11}&a_{12}&\dots &a_{1m}\\
+a_{21}&a_{22}&\dots &a_{2m}\\
+\vdots&\vdots&\ddots&\vdots\\
+a_{n1}&a_{n2}&\dots &a_{nm}
+\end{pmatrix}
+\]
\caption{Darstellung einer Matrix $A$}
-\label{munkres:Vr2}
\end{figure}
-
+Eine Matrix, wie hier in Abbildung 21.2 ersichtlich, ist ein rechteckiges Schema, dessen Elemente üblicherweise Zahlen, aber auch andere mathematische Elemente wie Variablen oder Funktionen sein können. Sie besteht aus $n$ Zeilen und $m$ Spalten. D.h. die Elemente einer Matrix vom Typ $(n,m)$ mit Namen $A$ sind $a_{ij}$ wobei $i$ = 1,..., $m$ ist und $j$ = 1,...,$n$. $a_{ij}$ ist der Eintrag in der $i$-ten Zeile und $j$-ten Spalte der Matrix . Zum Beispiel ist a21 das Element der 2. Zeile und 1. Spalte. $i$ wird auch der Zeilenindex, $j$ der Spaltenindex genannt.
\subsection{Alternative Darstellungen des Zuordnungsproblems
\label{munkres:subsection:bonorum}}
\begin{equation}
Netzwerk
\end{equation}
+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.3 dargestellt sind in den eckigen Klammern links die externen Flüsse $[1]$ für jeden Arbeiter und in den eckigen Klammern rechts eine $[-1]$ für jede Tätigkeit. Die Kosten sind entlang der Kanten als Zahlen in Klammern dargestellt.
\begin{equation}
Matrix
\end{equation}
+Im Bild 21.4 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.
\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.
+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.
+\begin{itemize}
+\item 3 = Anzahl der Knoten aus Menge A.
+\item 3 = Anzahl der Knoten aus Menge B.
+\end{itemize}
+
+
\begin{figure}
\centering
\includegraphics[width=5cm]{papers/munkres/figures/Netzwerkdarstellung}
diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex
index 0d2c86e..d2e8174 100644
--- a/buch/papers/munkres/teil3.tex
+++ b/buch/papers/munkres/teil3.tex
@@ -45,9 +45,9 @@ Die ungarische Methode kann in einem einfachen händischen Beispiel erläutert w
\begin{enumerate}
\item Pro Zeile eruiert man die kleinste Zahl. Diese kleinste Zahl wird bei
-allen anderen Ziffern in der jeweiligen Zeile subtrahiert. Mit dieser Subtraktion zieht man die unvermeidbaren Kosten ab.
+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.
-\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 Auch in diesem Schritt werden die unvermeidbaren Weg-Kosten abgezogen. Man zieht die kleinste Zahl in jeder Spalte von allen Zahlen in der Spalte ab.
\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