1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
\section*{Optimierungsprobleme}
Sei \(f: M \to \R\). Ein Optimierungsproblem ist:
\((P) \ \min_{x \in M} f(x)\)
\((P)\) ist zulässig, wenn \(M \neq \emptyset\).
\(\exists \hat x \in M \forall x \in M : f(\hat x) \leq f(x)\), so ist \((P)\) lösbar.
\subsection*{Klassifizierung}
\begin{enumerate}[label=(\alph*)]
\item Endlich dim. Probleme mit \(M \subseteq \R^m\)
\item Lineare Probleme (vgl. LP)
\item Konvexe Probleme
\item Differenzierbare Probleme
\end{enumerate}
\subsection*{Lineare Programme}
\((P) \ \min_{x \in M} f(x)\) ist linear, wenn:
\(f: \R^n \to \R\) affin linear ist mit \(f(x)=c^T x + c_0\) für \(c \in \R^n, c_0 \in \R\) und \(M\) folgende Darstellung besitzt:
\(M = \{ x \in \R^n | A_g x = b_g, A_u x \leq b_u \}\) mit \\ \(A = (A_g \ A_n)^T \in \R^{(m+p) \times n}, b = (b_g \ b_u)^T \in \R^{m+p}\)
\subsubsection*{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^T x\) mit \(M_N = \{ x \in \R_{\geq 0}^n | Ax=b \}\)
\spacing
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\).
\subsubsection*{Konvexe Mengen}
\(U \subseteq \R^n\) ist \emph{konvex}, wenn für \(x, y \in U \land \lambda \in [0,1] : (1-\lambda)x + \lambda y \in U\) gilt.
\spacing
\( v = \sum_{j=1}^m \lambda_j v^{(j)} \) mit \( \lambda_j \in [0,1] \land \sum_{j=1}^m \lambda_j = 1\) heißt \emph{Konvexkombination} von \( v^{(1)}, \dots, v^{(m)} \).
\spacing
\((M_N)\) der Normalform ist konvex.
\spacing
Schnitte endlich vieler Halbräume in \(R^n\) heißen \emph{Polyeder}, beschränkte Polyeder heißen \emph{Polytope}.
\spacing
\(M_n\) ist Polytop gdw. \( \not\exists y \in \R_{\geq 0}^n \setminus \{0\} : Ay = 0 \).
\subsubsection*{Charakterisierung von Ecken in \(M_N\)}
\(x \in M\) ist Ecke, wenn aus \(x=(1-\lambda) u+\lambda v\) mit \(u, v \in M, \lambda \in (0,1)\) folgt: \( u = v = x \).
Ecke ist nicht als echte Konvexkomb. darstellbar.
\spacing
\( x \in M_N \) ist Ecke von \(M_N\) gdw. die Spalten \(\{a_{*j}\}_{j \in J_x}\) mit \(J_x = \{ j \in \{1,\dots,n\} | x_j > 0 \}\) linear unabhg. sind.
\subsubsection*{Satz zur Existenz endl. vieler Ecken in \(M_N\)}
\[ M_N \neq \emptyset \implies \exists x \in M_N : x \text{ ist Ecke} \]
Insgesamt existieren endlich viele Ecken.
\subsubsection*{Konvexkombination von 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 \)
|
