From d1d733138d22ce7cfcb396eeca5cab5f13c48dc0 Mon Sep 17 00:00:00 2001
From: Adrian Kummerlaender
Date: Tue, 26 Jun 2018 12:48:20 +0200
Subject: Expand Simplex section in optitheo digest

---
 content/optimierungstheorie.tex | 42 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 41 insertions(+), 1 deletion(-)

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}
-- 
cgit v1.2.3