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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
|
\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}
\section*{Lineare Programme}
\((P) \ \min_{x \in M} f(x)\) ist linear, wenn:
\(f: \R^n \to \R\) affin linear ist mit \(f(x)=c^\top 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)^\top \in \R^{(m+p) \times n}, b = (b_g \ b_u)^\top \in \R^{m+p}\)
\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
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\).
\subsection*{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 \)
\subsection*{Existenz von linearen Programmen}
Sei \( (P_N) \ \min c^\top x \) auf \( M_N = \{ x \in \R_{\geq 0}^n | Ax = b \} \neq \emptyset\).
Dann gilt entweder \(\inf (P_N) = -\infty\) oder \((P_N)\) ist mit einer Ecke von \(M_N\) lösbar.
\section*{Simplex-Algorithmus}
\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\).
\spacing
\(x \in M_N\) Basislösung \(\iff x\) ist Ecke von \(M_N\)
\subsection*{Phase I}
Bestimme Basislösung \(z \in M_N\) und äquivalente Darstellung \((P)\) zu \((P_N)\):
\vspace*{-2mm}
\[ (P) \ \min c^\top x \text{ auf } M = \{ x \in \R_{\geq 0}^n | Ax=b \} \]
Mit Bedingungen:
\begin{enumerate}[label=(E\arabic*)]
\item \(a_{*j} = e_{\ell_j}\) für \(j \in J_z\)
\item \(c_j = 0\) für \(j \in J_z\)
\item \(b \geq 0\)
\item \(c^\top x = c_N^\top x - c_N^\top z\) d.h. \(c^\top z = 0\)
\end{enumerate}
\subsection*{Phase II}
Seien \(z, A, b, c\) aus Phase I gegeben.
Iterativ werden nun neue Basislösungen \(\tilde z\) und Darstellungen \(\tilde A x = \tilde b\) mit Bedingungen (E1)-(E4) bestimmt s.d.: \(c^\top \tilde z \leq c^\top z = 0\)
Diese Iteration bricht ab, wenn \(\tilde z\) Lösung zu \((P_N)\) ist oder \(\inf (P_N) = -\infty\) gilt.
\subsubsection*{Algorithmus zu Phase II}
\begin{enumerate}[label=(\arabic*)]
\item \(c \geq 0? \rightsquigarrow\) Abbruch denn \(z\) ist Lösung zu \((P)\) mit \(c^\top z = \eta - c_N^\top z = 0\)
\item Wähle Pivotindex \(s \in \{1,\dots,n\}\) mit \(c_s < 0\)
\item \(a_{*s} \leq 0? \rightsquigarrow\) Abbruch mit \(\inf (P) = -\infty\)
\item Wähle \(r \in \{1,\dots,m\}\) s.d. Pivotelement \(a_{rs}\) mit \(\frac{b_r}{a_{rs}} = \min \left\{ \frac{b_i}{a_{is}} \middle| i \in \{1,\dots,n\} \text{ mit } a_{is} > 0 \right\}\) die Bedingung \(a_{rs} > 0\) erfüllt
\item Gauß-Transformation zu \(\tilde A x = \tilde b\) s.d. \(r\)-ter Einheitsvektor in \(\tilde A\) in der \(s\)-ten Spalte steht
\item Ersetze \((P)\) mit \((\tilde P)\) und wiederhole ab (1)
\end{enumerate}
\subsection*{Durchführbarkeit des Simplex-Verfahren}
Sei \((P)\) mit \(A,b,c\) und Basislsg. \(z \in M\) aus Phase I und \((\tilde P)\) durch Phase II Schritt erzeugt. Dann:
\begin{enumerate}[label=(\alph*)]
\item \(c \geq 0 \implies z\) ist optimal
\item \(c_s < 0 \land a_{*s} \leq 0 \implies \inf (P) = -\infty\)
\item \((P)\) und \((\tilde P)\) sind äquiv. mit \(\tilde c^\top x = c^\top x - c^\top \tilde z\) für \(x \in M\)
\item \(c^\top \tilde z \leq c^\top z = 0\)
\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\).
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}
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\).
Dann gilt für Lösung \(\hat x \in M\) von \((P_N)\):
\[\exists \hat y \in N = \{ y \in \R^m | A^\top y \leq c \} \text{ mit } b^\top \hat y = c^\top \hat x\]
\subsection*{Duales Optimierungsproblem}
Zu \emph{primalem} LP in Normalform \((P_N)\) ist das duale Optimierungsproblem \((D)\) gegeben durch:
\[(D) \ \max_{y \in N} b^\top y \text{ auf } N = \{y \in \R^m | A^\top y \leq c\}\]
\subsection*{Schwacher Dualitätssatz}
Für zulässige \((P_N)\) und \((D)\) gelten:
\begin{enumerate}[label=(\alph*)]
\item \(\forall x \in M, y \in N : b^\top y \leq c^\top x\)
\item \((P_N)\) und \((D)\) sind lösbar
\item \(\hat x \in M \land \hat y \in N \land b^\top \hat y = c^\top \hat x \\ \implies \hat x\) löst \((P_N)\) und \(\hat y\) löst \((D)\)
\end{enumerate}
\subsection*{Satz von Kuhn-Tucker}
\[\hat
|
