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/teil4.tex | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 buch/papers/munkres/teil4.tex

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

diff --git a/buch/papers/munkres/teil4.tex b/buch/papers/munkres/teil4.tex
new file mode 100644
index 0000000..3d76743
--- /dev/null
+++ b/buch/papers/munkres/teil4.tex
@@ -0,0 +1,36 @@
+%
+% teil4.tex -- Beispiel-File für Teil 4
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Matrix-Interpretation
+\label{munkres:section:teil4}}
+\rhead{Matrix-Interpretation}
+Gegeben ist die quadratische Matrix $C=(c_{ij})$ der Grösse $n\times n$.
+Ohne Beschränkung der Allgemeinheit werden eine Zuordnung $j
+\rightarrow  s_j$, $j = 1, \dots, n$ mit minimaler Gesamtsumme
+$\sum_{j=1}^{n}c_{s_j,j}$ gesucht, wobei die $s_j$ eine Permutation
+von $\{1,\ldots ,n\}$ sind.
+Soll die Summe maximiert werden, dann kann $C$ durch $-C$ ersetzt werden.
+Die Grundlage dieses Verfahrens ist, dass sich die optimale Zuordnung
+unter bestimmten Änderungen der Matrix nicht ändert, sondern nur
+der Optimalwert.
+Diese Änderungen sind durch Knotenpotentiale bzw.~duale Variablen 
+\begin{equation}
+u_1 u_2,{\dots}, u_n
+\end{equation}
+
+für die Zeilen und 
+
+\begin{equation}v_1,v_2,\dots,v_n \end{equation} fuer die Spalten angegeben.
+Die modifizierte Matrix hat dann die Komponenten $\tilde{c}_{i,j}
+= c_{ij} - u_j - v_j$.
+
+In der Summe über jede kantenmaximale Zuordnung kommt jedes
+Knotenpotential genau einmal vor, so dass die Änderung der Zielfunktion
+eine Konstante ist.
+Sind die Einträge von $C$ nichtnegativ, und sind alle Knotenpotentiale
+ebenfalls nichtnegativ, so nennt man die modifizierte Matrix \~{C}
+auch eine Reduktion.
+Ziel ist, in der reduzierten Matrix möglichst viele Komponenten auf
+den Wert Null zu bringen und unter diesen die Zuordnung zu konstruieren.
-- 
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/teil4.tex | 31 ++-----------------------------
 1 file changed, 2 insertions(+), 29 deletions(-)

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

diff --git a/buch/papers/munkres/teil4.tex b/buch/papers/munkres/teil4.tex
index 3d76743..9a27227 100644
--- a/buch/papers/munkres/teil4.tex
+++ b/buch/papers/munkres/teil4.tex
@@ -3,34 +3,7 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Matrix-Interpretation
+\section{-
 \label{munkres:section:teil4}}
-\rhead{Matrix-Interpretation}
-Gegeben ist die quadratische Matrix $C=(c_{ij})$ der Grösse $n\times n$.
-Ohne Beschränkung der Allgemeinheit werden eine Zuordnung $j
-\rightarrow  s_j$, $j = 1, \dots, n$ mit minimaler Gesamtsumme
-$\sum_{j=1}^{n}c_{s_j,j}$ gesucht, wobei die $s_j$ eine Permutation
-von $\{1,\ldots ,n\}$ sind.
-Soll die Summe maximiert werden, dann kann $C$ durch $-C$ ersetzt werden.
-Die Grundlage dieses Verfahrens ist, dass sich die optimale Zuordnung
-unter bestimmten Änderungen der Matrix nicht ändert, sondern nur
-der Optimalwert.
-Diese Änderungen sind durch Knotenpotentiale bzw.~duale Variablen 
-\begin{equation}
-u_1 u_2,{\dots}, u_n
-\end{equation}
+\rhead{-}
 
-für die Zeilen und 
-
-\begin{equation}v_1,v_2,\dots,v_n \end{equation} fuer die Spalten angegeben.
-Die modifizierte Matrix hat dann die Komponenten $\tilde{c}_{i,j}
-= c_{ij} - u_j - v_j$.
-
-In der Summe über jede kantenmaximale Zuordnung kommt jedes
-Knotenpotential genau einmal vor, so dass die Änderung der Zielfunktion
-eine Konstante ist.
-Sind die Einträge von $C$ nichtnegativ, und sind alle Knotenpotentiale
-ebenfalls nichtnegativ, so nennt man die modifizierte Matrix \~{C}
-auch eine Reduktion.
-Ziel ist, in der reduzierten Matrix möglichst viele Komponenten auf
-den Wert Null zu bringen und unter diesen die Zuordnung zu konstruieren.
-- 
cgit v1.2.1

