Benutzer:Xorx77/Baustelle

Die Fourier-Motzkin Elimination ist eine dem Gauß-Verfahren ähnliche, einfache Methode um lineare Ungleichungssysteme der Form

${\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\ldots +a_{2n}x_{n}&\leq b_{2}\\\vdots &\\a_{m1}x_{1}+a_{m2}x_{2}+\ldots +a_{mn}x_{n}&\leq b_{m}\end{aligned}}$

beziehungsweise in Vektor-Matrix-Schreibweise

${\begin{pmatrix}a_{11}&\cdots &a_{1n}\\\vdots &&\vdots \\a_{m1}&\ldots &a_{mn}\end{pmatrix}}{\begin{pmatrix}x_{1}\\\vdots \\x_{n}\end{pmatrix}}\leq {\begin{pmatrix}b_{1}\\\vdots \\b_{m}\end{pmatrix}}$

auf Zulässigkeit zu prüfen und gegebenenfalls zu lösen. Sie wurde nach ihrem Entdecker Joseph Fourier und dem Mathematiker Theodore Motzkin benannt.

Beschreibung des Verfahrens

Das Verfahren besteht im Wesentlichen aus drei Schritten, die je nach Ungleichungssystem maximal so oft wiederholt werden müssen wie es verschiedene Variablen gibt:

1. Schritt: Auflösen nach einer der Variablen
   Löse jede Zeile $a_{i1}x_{1}+\ldots +a_{in}x_{n}\leq b_{i}$ so nach einer der Variablen $x_{j}$ auf, dass man die Gleichung nicht mit einer negativen Zahl durchmultipliziert. Dabei enstehen Zeilen, bei denen die aufgelöste Variable rechts von dem Kleiner-Gleich-Zeichen stehen und welche, bei denen sie links davon steht.
2. Schritt: Kombination der Zeilen und Elimination der aufgelösten Variable
   Kombiniere jede Zeile, in der die aufgelöste Variable links steht mit jeder Zeile, in der sie rechts steht. Es entstehen auf diese Art maximal $(k/2)^{2}$ neue Ungleichungen, wobei $k$ die Anzahl der noch übrigen Ungleichungen ist. Es wird so die aufgelöste Variable eliminiert.
3. Schritt: Streichen der offensichtlich redundanten Ungleichungen
   Durch die Kombination der Zeilen im 2.Schritt können triviale Ungleichungen der Art $1\leq 2$ oder redundante Ungleichungen, wie z.B. $x_{j}\leq 3$ wenn bereits $x_{j}\leq 2$ gilt, enstehen. Diese können entfernt werden.

Entsteht bei irgendeinem der oberen Schritte ein Widerspruch, wie z.B. $2\leq 1$, so ist das Ungleichungssystem nicht lösbar also unzulässig; anderfalls endet das Verfahren nach maximal $n$ Durchläufen der Schritte 1--3 und das Ungleichungssystem ist zulässig und durch Rückwärtssubstitution der Variablen kann ein Punkt der Lösungsmenge gefunden werden.

Anwendungen und Beispiele

Neben der offensichtlichen Anwendung des Lösens von Ungleichunssystemen gibt es weitere Anwendungsmöglichkeiten dieser Elimination.

Berechnung der Ecken eines konvexen Polyeders

Die Lösungsmenge des linearen Ungleichungssystems $\{x\in \mathbb {R} ^{n}:Ax\leq b\}$ mit $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}$ kann als ein konvexes Polyeder im $\mathbb {R} ^{n}$ aufgefasst werden.

Die Fourier-Motzkin Elimination kann dann für die Berechnung aller Ecken und unbeschränkten Kanten des Polyeders genutzt werden. Dies geschieht durch geschickte Rückwärtssubstitution der Variablen an ihren durch die Kombinations- und Eliminationsschritte gefundenen Grenzen sowie wiederholte Anwendung des Verfahrens (mit Auflösen nach einer anderen Variable).

Durch diese geometrische Interpretation des Verfahrens lässt sich auch die Funktionsweise besser nachvollziehen: Ein Kombinations- und Eliminationsschritt projeziert das Polyeder auf die eliminierte Variable; dies wird im dreidimensionalen Beispiel vorgeführt.

Beispiel im Zweidimensionalen

Betrachte das Ungleichungssystem in den Unbekannten $x_{1}$ und $x_{2}$.

Das unbeschränkte Polyeder P mit hellblauem Inneren, dunkelblauen Kanten und roten Ecken

${\begin{aligned}x_{1}+x_{2}&\geq 1\\x_{1}&\geq 0\\+x_{2}&\geq 0\\+x_{2}&\leq 2\end{aligned}}\qquad \Leftrightarrow \qquad {\begin{aligned}[rrl]-x_{1}-x_{2}&\leq -1\\-x_{1}&\leq 0\\-x_{2}&\leq 0\\+x_{2}&\leq 2\end{aligned}}$

also in Matrixschreibweise

$\underbrace {\begin{pmatrix}-1&-1\\-1&0\\0&-1\\0&1\end{pmatrix}} _{=:A}\underbrace {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}} _{=:x}\leq \underbrace {\begin{pmatrix}-1\\0\\0\\2\end{pmatrix}} _{=:b}$

Es sollen nun alle Ecken des konvexen Polyeders $P:=\{x\in \mathbb {R} ^{2}:Ax\leq b\}$ gefunden werden und, falls vorhanden, auch die Kanten von $P$, die unbeschränkt sind.

1. Eliminierung von $x_{2}$

${\begin{aligned}1-x_{1}&\leq x_{2}\\-x_{1}&\leq 0\\0&\leq x_{2}\\x_{2}&\leq 2\end{aligned}}\qquad {\begin{aligned}1-x_{1}&\leq 2\\-x_{1}&\leq 0\\0&\leq 2\end{aligned}}\qquad {\begin{aligned}-1&\leq x_{1}\\0&\leq x_{1}\end{aligned}}\qquad {\begin{aligned}0&\leq x_{1}\end{aligned}}$

Rückwärtssubstitution liefert $x_{2}\geq 1$ bzw. $x_{2}\leq 2$. Es wurde also die Ecken $(0,1)$ und $(0,2)$ und die unbeschränkte Kante $(0,2)$ nach $(\infty ,2)$ von $P$ gefunden.

2. Eliminierung von $x_{1}$

${\begin{aligned}1-x_{1}&\leq x_{2}\\-x_{1}&\leq 0\\0&\leq x_{2}\\x_{2}&\leq 2\end{aligned}}\qquad {\begin{aligned}1-x_{2}&\leq x_{1}\\0&\leq x_{1}\\-x_{2}&\leq 0\\x_{2}&\leq 2\end{aligned}}\qquad {\begin{aligned}0&\leq x_{2}\\x_{2}&\leq 2\end{aligned}}$

Rückwärtssubstitution von $0\leq x_{2}$ liefert $x_{1}\geq 1$ und von $x_{2}\leq 2$ liefert $x_{1}\leq 0$. Es wurden also die Ecken $(1,0)$ und $(0,2)$ und die unbeschränkte Kante $(1,0)$ nach $(\infty ,0)$ von $P$ gefunden.

Beispiel im Dreidimensionalen

Das hellblaue Polyeder P mit dunkelblauen Kanten und roten Ecken. Zur besseren Orientierung sind die Projektionslinien zweier Kanten gestrichelt eingezeichnet

Sei das Ungleichungssystem

${\begin{array}{rrrl}3x_{1}&&+x_{3}&\leq 3\\-3x_{1}&&+x_{3}&\leq 0\\&x_{2}&+x_{3}&\leq 1\\&2x_{2}&+x_{3}&\geq -1\\&&x_{3}&\geq 0\end{array}}$

gegeben und $P$ die Lösungsmenge des Systems, also ein konvexes Polyeder. Es werden wieder alle Ecken und unbeschränkten Kanten mit dem Fourier-Motzkin Verfahren berechnet. Hierbei ist zu beobachten, dass durch Elimination einer Unbekannten auch mehr Ungleichung als zuvor zu betrachten sein können.

1. Eliminierung von $x_{3}$

${\begin{aligned}3x_{1}&&+x_{3}&\leq 3\\-3x_{1}&&+x_{3}&\leq 0\\&x_{2}&+x_{3}&\leq 1\\&-2x_{2}&-x_{3}&\leq 1\\&&-x_{3}&\leq 0\end{aligned}}\qquad {\begin{aligned}+x_{3}\leq -3x_{1}+3\\+x_{3}\leq 3x_{1}\\+x_{3}\leq 1-x_{2}\\-2x_{2}-1\leq x_{3}\\0\leq x_{3}\end{aligned}}\qquad {\begin{aligned}-2x_{2}-1\leq -3x_{1}+3\\0\leq -3x_{1}+3\\-2x_{2}-1\leq 3x_{1}\\0\leq 3x_{1}\\-2x_{2}-1\leq 1-x_{2}\\0\leq 1-x_{2}\end{aligned}}$

1.1 Eliminierung von $x_{2}$

${\begin{aligned}-2+1,5x_{1}&\leq x_{2}\\-0,5-1,5x_{1}&\leq x_{2}\\-2&\leq x_{2}\\x_{2}&\leq 1\\0&\leq -3x_{1}+3\\0&\leq 3x_{1}\end{aligned}}\qquad {\begin{aligned}-2+1,5x_{1}&\leq 1\\-0,5-1,5x_{1}&\leq 1\\-2&\leq 1\\0&\leq -3x_{1}+3\\0&\leq 3x_{1}\end{aligned}}\qquad {\begin{aligned}x_{1}&\leq 2\\-1&\leq x_{1}\\x_{1}&\leq 1\\0&\leq x_{1}\end{aligned}}\qquad {\begin{aligned}x_{1}&\leq 1\\0&\leq x_{1}\end{aligned}}$

Nachteile des Verfahrens

Der Hauptnachteil des Verfahrens wird bereits in der Beschreibung 2. Schritt genannt: Aus $k$ Ungleichung vor dem Kombinationsschritt werden maximal $(k/2)^{2}$ viele danach. Insgesamt müssen also --- bei einem Ausgangssystem von $n$ Ungleichung --- maximal

${\frac {n^{2n}}{2^{n(n+1)}}}$

Ungleichungen betrachtet werden. Diese obere Schranke wird auch angenommen, z.B. durch das Ungleichungssystem, das durch die Koeffizientenmatrix $((-1)^{i+j}j^{i})_{1\leq i,j\leq n}$ mit $n$ Zweierpotenz und beliebiger rechter Seite $b$, gegeben ist.