aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
authorAdrian Kummerlaender2018-06-28 15:33:52 +0200
committerAdrian Kummerlaender2018-06-28 15:33:52 +0200
commit43b133f18bb8b62dcc37542910b53a801c0e68ab (patch)
tree4d6e540c7c20133e81ed1cea4a38c455432e24dd /content
parent74b584b5a42d940eded337611f251369c75f94d5 (diff)
downloadmath_reference_sheets-43b133f18bb8b62dcc37542910b53a801c0e68ab.tar
math_reference_sheets-43b133f18bb8b62dcc37542910b53a801c0e68ab.tar.gz
math_reference_sheets-43b133f18bb8b62dcc37542910b53a801c0e68ab.tar.bz2
math_reference_sheets-43b133f18bb8b62dcc37542910b53a801c0e68ab.tar.lz
math_reference_sheets-43b133f18bb8b62dcc37542910b53a801c0e68ab.tar.xz
math_reference_sheets-43b133f18bb8b62dcc37542910b53a801c0e68ab.tar.zst
math_reference_sheets-43b133f18bb8b62dcc37542910b53a801c0e68ab.zip
Restructure optitheo digest
Diffstat (limited to 'content')
-rw-r--r--content/optimierungstheorie.tex67
1 files changed, 35 insertions, 32 deletions
diff --git a/content/optimierungstheorie.tex b/content/optimierungstheorie.tex
index 5898146..67fe414 100644
--- a/content/optimierungstheorie.tex
+++ b/content/optimierungstheorie.tex
@@ -1,13 +1,17 @@
\section*{Optimierungsprobleme}
Sei \(f: M \to \R\). Ein Optimierungsproblem ist:
+\[(P) \ \min_{x \in M} f(x)\]
-\((P) \ \min_{x \in M} f(x)\)
+\((P)\) ist \emph{zulässig}, wenn \(M \neq \emptyset\).
-\((P)\) ist zulässig, wenn \(M \neq \emptyset\).
+\(x \in M\) ist zulässiger Punkt.
\(\exists \hat x \in M \forall x \in M : f(\hat x) \leq f(x)\), so ist \((P)\) lösbar.
+Die Menge der Lösungen von \((P)\) ist:
+\[\text{argmin}_{x \in M} f = \{ \hat x \in M | \forall x \in M : f(\hat x) \leq f(x) \}\]
+
\subsection*{Klassifizierung}
\begin{enumerate}[label=(\alph*)]
@@ -28,16 +32,12 @@ Sei \(f: M \to \R\). Ein Optimierungsproblem ist:
\subsection*{Normalform}
Ein LP \((P_N)\) ist in Normalform gegeben, wenn \(A \in \R^{m \times n}, b \in \R^m\) und \(c \in \R^n\) ex. s.d. gilt:
-
-\((P_N) \ \min c^\top x\) mit \(M_N = \{ x \in \R_{\geq 0}^n | Ax=b \}\)
-
-\spacing
+\[(P_N) \ \min c^\top x \text{ mit } M_N = \{ x \in \R_{\geq 0}^n | Ax=b \}\]
Jedes LP \((P)\) besitzt Normalform \((P_N)\).
Dafür werden Ungleichungsbedingungen über \emph{Schlupfvariablen} umgeformt:
-
-\(A_u x \leq b_u \rightsquigarrow x_i^s = (b_u)_i - (A_u x)_i\) für \(i = 1,\dots,s\).
+\[ A_u x \leq b_u \rightsquigarrow x_i^s = (b_u)_i - (A_u x)_i \text{ für } i = 1,\dots,s \]
\subsection*{Konvexe Mengen}
@@ -80,8 +80,7 @@ Insgesamt existieren endlich viele Ecken.
Seien \( v^{(k)} \in M_N \) mit \(k=1,\dots,K\) Ecken von \(M_N\).
Dann \( \forall x \in M_N \exists \alpha_j \in [0,1], y \in \{ y \in \R_{\geq 0}^n | Ay = 0 \} :\)
-
-\( \sum_{j=1}^K \alpha_j = 1 \land x = \sum_{j=1}^K \alpha_j v^{(j)} + y \)
+\[ \textstyle\sum_{j=1}^K \alpha_j = 1 \land x = \sum_{j=1}^K \alpha_j v^{(j)} + y \]
\subsection*{Existenz von linearen Programmen}
@@ -146,26 +145,6 @@ Sei \((P)\) mit \(A,b,c\) und Basislsg. \(z \in M\) aus Phase I und \((\tilde P)
\item \((\tilde P)\) mit Basislö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\).
@@ -181,10 +160,34 @@ Für das Hilfsproblem \((H)\) gelten:
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 \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}
+\subsubsection*{Entartete Basislösungen}
+
+Sei \(z \in M\) eine Basislösung.
+
+\(z \in M\) ist \emph{nicht entartet}, wenn \(z_j > 0\) für \(j \in J_z\) gilt.
+
+\spacing
+
+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 \text{ für } 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.
+
+
\section*{Dualitätstheorie}
Sei \((P_N) \ \min_{x \in M} c^\top x\) auf \(M = \{ x \in \R_{\geq 0}^n | Ax=b \}\) mit \(A \in \R^{m \times n}, b \in \R^m\) und \(c \in \R^n\).
@@ -234,4 +237,4 @@ Seien \(A \in \R^{m \times n}\) und \(b \in \R^m\). Dann:
\begin{align*}
&\exists x \in \R_{\geq 0}^n &&: Ax=b \\
\iff &\not\exists y \in \R^m &&: A^\top y \leq 0 \land b^\top y > 0
-\end{align*} \ No newline at end of file
+\end{align*}