diff options
author | JODBaer <JODBaer@github.com> | 2021-07-27 13:20:19 +0200 |
---|---|---|
committer | JODBaer <JODBaer@github.com> | 2021-07-27 13:20:19 +0200 |
commit | 058ff7a7400c321861da6d2b5156bf957cb09fd3 (patch) | |
tree | 776ef99b73444e731609237e4982b45027a90b02 /buch/papers/munkres/teil4.tex | |
parent | save (diff) | |
parent | Merge pull request #49 from Kuehnee/master (diff) | |
download | SeminarMatrizen-058ff7a7400c321861da6d2b5156bf957cb09fd3.tar.gz SeminarMatrizen-058ff7a7400c321861da6d2b5156bf957cb09fd3.zip |
Merge remote-tracking branch 'upstream/master' into Baer
Diffstat (limited to 'buch/papers/munkres/teil4.tex')
-rw-r--r-- | buch/papers/munkres/teil4.tex | 31 |
1 files changed, 2 insertions, 29 deletions
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. |