diff options
author | Andreas Müller <andreas.mueller@ost.ch> | 2021-07-27 12:33:10 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-07-27 12:33:10 +0200 |
commit | 34a89cce6f8e8abc7fe71cc89bbb2492a475a5db (patch) | |
tree | 4e90618011fddccf8725b4c22a7d3b0fb50d1c1e /buch/papers/munkres/teil4.tex | |
parent | Merge branch 'master' of github.com:AndreasFMueller/SeminarMatrizen (diff) | |
parent | neue version (diff) | |
download | SeminarMatrizen-34a89cce6f8e8abc7fe71cc89bbb2492a475a5db.tar.gz SeminarMatrizen-34a89cce6f8e8abc7fe71cc89bbb2492a475a5db.zip |
Merge pull request #48 from Kuehnee/master
neue version
Diffstat (limited to '')
-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. |