aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
authorAdrian Kummerlaender2018-06-26 12:48:20 +0200
committerAdrian Kummerlaender2018-06-26 12:48:37 +0200
commitd1d733138d22ce7cfcb396eeca5cab5f13c48dc0 (patch)
treed369907d19381e2a786297c82089b016f60761ac /content
parent971ad42a2b27547255b97e4252b8b195b62c419c (diff)
downloadmath_reference_sheets-d1d733138d22ce7cfcb396eeca5cab5f13c48dc0.tar
math_reference_sheets-d1d733138d22ce7cfcb396eeca5cab5f13c48dc0.tar.gz
math_reference_sheets-d1d733138d22ce7cfcb396eeca5cab5f13c48dc0.tar.bz2
math_reference_sheets-d1d733138d22ce7cfcb396eeca5cab5f13c48dc0.tar.lz
math_reference_sheets-d1d733138d22ce7cfcb396eeca5cab5f13c48dc0.tar.xz
math_reference_sheets-d1d733138d22ce7cfcb396eeca5cab5f13c48dc0.tar.zst
math_reference_sheets-d1d733138d22ce7cfcb396eeca5cab5f13c48dc0.zip
Expand Simplex section in optitheo digest
Diffstat (limited to 'content')
-rw-r--r--content/optimierungstheorie.tex42
1 files changed, 41 insertions, 1 deletions
diff --git a/content/optimierungstheorie.tex b/content/optimierungstheorie.tex
index 84f8746..f107598 100644
--- a/content/optimierungstheorie.tex
+++ b/content/optimierungstheorie.tex
@@ -93,7 +93,7 @@ Dann gilt entweder \(\inf (P_N) = -\infty\) oder \((P_N)\) ist mit einer Ecke vo
\subsection*{Basislösung}
-\(x \in \R^n\) ist Basislösung zu \(A_N x = b_N\), wenn es \(m\)-elementige Indexmenge \(J_x\) gibt mit linear unabhg. \(\{a_{*j} | j \in J_x\}\) und \(\forall j \notin J_x : x_j = 0\).
+\(x \in \R^n\) ist Basislösung zu \(A_N x = b_N\), wenn es \(m\)-elementige Indexmenge \(J_x\) gibt mit linear unabhg. \(\{a_{*j} | j \in J_x\}\) und \(\forall j \notin J_x : x_j = 0\).
\spacing
@@ -146,3 +146,43 @@ Sei \((P)\) mit \(A,b,c\) und Basislsg. \(z \in M\) aus Phase I und \((\tilde P)
\item \((\tilde P)\) mit Baislösung \(\tilde z\) erfüllt (E1)-(E4)
\end{enumerate}
+\subsubsection*{Entartete Basislösungen}
+
+Basislösung \(z \in M\) ist \emph{nicht entartet}, wenn \(z_j > 0\) für \(j \in J_z\) gilt.
+
+Im Simplex-Tableau ist \(z\) nicht entartet gdw. \(b_i > 0\) für \(i=1,\dots,m\) gilt.
+
+Für entartete \(z \in M\) ist das Simplex-Verfahren i.A. nicht zyklenfrei.
+
+\subsubsection*{Regel von Bland}
+
+Sei \(s := \min \{ j \in \{1,\dots,n\} | c_j < 0 \}\) die Pivotspalte und \(r\) die Pivotzeile s.d. gilt:
+
+\(\frac{b_r}{a_{rs}} = \min \left\{ \frac{b_i}{a_{is}} \middle| a_{is} > 0, \ i=1,\dots,m \right\}\).
+
+Wird das Minimum für mehrere Zeilen angenommen, so wähle die Pivotzeile \(r\) s.d. \(j_r < j_k\) gilt. d.h. der \(r\)-te Einheitsvektor steht am weitestens links.
+
+\spacing
+
+Phase II mit Regel von Bland stoppt immer im Optimum zu \((P)\) insofern ein solches existiert.
+
+\subsubsection*{Bestimmung von Basislösung in Phase I}
+
+Definiere Hilfsproblem \((H) \ \min e^\top (b-Ax)\) auf \(M_H = \{ x \in \R_{\geq 0}^n | A_N x \leq b_N \}\) wobei \(e = 1 \in \R^n\).
+
+Für das Hilfsproblem \((H)\) gelten:
+
+\begin{enumerate}[label=(\alph*)]
+ \item wg. \(b_N \geq 0 \implies 0 \in M_H\) ist \((H)\) zulässig
+ \item \(x \in M_H \implies e^\top (b_N - A_N x) \geq 0\) \\ d.h. \((H)\) hat immer Lösung, \(\inf \ (H) > -\infty\)
+ \item Mit Schlupfvariablen lässt sich Phase II auf \((H)\) direkt anwenden
+\end{enumerate}
+
+Ist \(\hat z \in M_H\) optimale Basislösung zu \((H)\) so gelten:
+
+\begin{enumerate}[label=(\alph*)]
+ \item \(e^\top (b_N - A_N \hat z) = 0 \implies \hat z\) ist zulässig zu \((P_N)\)
+ \item \(e^\top (b_N - A_N x) \geq e^\top (b_N - A_N \hat z) > 0 \\ \implies M_N \neq \emptyset\) und \((P_N)\) ist nicht zulässig
+\end{enumerate}
+
+\section*{Dualitätstheorie}