Lineares Programm
Einfache Sprache
Ein Optimierungsproblem ist ein lineares Problem, wenn $f$ (ggf. auch $g,h$) linear sind. Wird auch primal genannt (im Gegensatz zum dual Lineares Programm)
Lineares Programm
Das Lineare Programm gibt eine Matrix $\mathfrak A\in\mathbb R^{m\times n}$ und zwei Vektoren $\mathfrak b\in \mathbb R^m$ und $\mathfrak c\in \mathbb R^n$ vor. Eine zulässige Lösung ist ein Vektor $\mathfrak x\in\mathbb R^n$ (nicht der Null-Vektor), der die linear Bedingungen
$$\begin{align}a_{11}x_1 &+\ldots &+a_{1n}x_n &\leq b_1\\a_{21}x_1 &+\ldots &+a_{2n}x_n &\leq b_2\\\vdots & &&\vdots\\a_{m1}x_1 &+\ldots &+a_{mn}x_n &\leq b_m\end{align}$$Ziel ist es unter allen zulässigen Lösungen den Vektor zu finden, für den
$$\mathfrak c^T\mathfrak x = c_1x_1+\ldots+c_nx_n$$maximiert wird.
Die Standardform für ein LP ist wie folgt:
$$\begin{align}\max\; &\mathfrak c^T\mathfrak x\\ & \mathfrak{Ax\leq b}\\&\mathfrak x\in\mathbb R^n\end{align}$$was äquivalent zu der folgender Schreibweise ist
$$\min\{\mathfrak c^T\mathfrak x\mid \mathfrak{Ax= b}, \mathfrak x\in\mathbb R^n_{\geq 0}\}$$
Lineares Programm Problem
Gegeben eine Matrix $\mathfrak A\in\mathbb R^{m\times n}$ und Vektoren $\mathfrak b\in \mathbb R^m$ und $\mathfrak c\in \mathbb R^n$. Entweder
- finde ein Vektor $\mathfrak x\in\mathbb R^n$ so, dass $\mathfrak{Ax\leq b}$ und $\mathfrak c^T \mathfrak x$ das Maximum ist oder
- entscheide das $\{x\in\mathbb R^n\mid \mathfrak{ Ax\leq b}\} = \emptyset$ oder
- entscheide das für alle $\alpha\in\mathbb R$ ein $x\in\mathbb R^n$ existiert so ,dass $\mathfrak{Ax\leq b}$ und $\mathfrak c^T\mathfrak{x>\alpha}$.
Hier heißt $\leq$ das die Relation für jede Zeile gilt.
Geometrische Interpretation
Die einzelnen Bedingungen $\mathfrak a_i\mathfrak x\leq b_i$ teilen den Raum in zwei Halbräume, also mit der [[Hyper. Zulässige Lösungen sind damit nur die Punkte auf einer Seiter dieser