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
|
\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 Baislösung \(\tilde z\) erfüllt (E1)-(E4)
\end{enumerate}
|
