Benutzer:Xorx77/Baustelle

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

${\displaystyle {\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}}}${\displaystyle {\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

${\displaystyle {\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}}}${\displaystyle {\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.

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 ${\displaystyle a_{i1}x_{1}+\ldots +a_{in}x_{n}\leq b_{i}}${\displaystyle a_{i1}x_{1}+\ldots +a_{in}x_{n}\leq b_{i}} so nach einer der Variablen ${\displaystyle x_{j}}${\displaystyle 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 ${\displaystyle (k/2)^{2}}${\displaystyle (k/2)^{2}} neue Ungleichungen, wobei ${\displaystyle k}${\displaystyle 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 ${\displaystyle 1\leq 2}${\displaystyle 1\leq 2} oder redundante Ungleichungen, wie z.B. ${\displaystyle x_{j}\leq 3}${\displaystyle x_{j}\leq 3} wenn bereits ${\displaystyle x_{j}\leq 2}${\displaystyle x_{j}\leq 2} gilt, enstehen. Diese können entfernt werden.

Entsteht bei irgendeinem der oberen Schritte ein Widerspruch, wie z.B. ${\displaystyle 2\leq 1}${\displaystyle 2\leq 1}, so ist das Ungleichungssystem nicht lösbar also unzulässig; anderfalls endet das Verfahren nach maximal ${\displaystyle n}${\displaystyle 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.

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

Die Lösungsmenge des linearen Ungleichungssystems ${\displaystyle \{x\in \mathbb {R} ^{n}:Ax\leq b\}}${\displaystyle \{x\in \mathbb {R} ^{n}:Ax\leq b\}} mit ${\displaystyle A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}}${\displaystyle A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m}} kann als ein konvexes Polyeder im ${\displaystyle \mathbb {R} ^{n}}${\displaystyle \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.

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

${\displaystyle {\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}}}${\displaystyle {\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

${\displaystyle \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}}${\displaystyle \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 ${\displaystyle P:=\{x\in \mathbb {R} ^{2}:Ax\leq b\}}${\displaystyle P:=\{x\in \mathbb {R} ^{2}:Ax\leq b\}} gefunden werden und, falls vorhanden, auch die Kanten von ${\displaystyle P}${\displaystyle P}, die unbeschränkt sind.

1. Eliminierung von ${\displaystyle x_{2}}${\displaystyle x_{2}}

${\displaystyle {\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}}}${\displaystyle {\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 ${\displaystyle x_{2}\geq 1}${\displaystyle x_{2}\geq 1} bzw. ${\displaystyle x_{2}\leq 2}${\displaystyle x_{2}\leq 2}. Es wurde also die Ecken ${\displaystyle (0,1)}${\displaystyle (0,1)} und ${\displaystyle (0,2)}${\displaystyle (0,2)} und die unbeschränkte Kante ${\displaystyle (0,2)}${\displaystyle (0,2)} nach ${\displaystyle (\infty ,2)}${\displaystyle (\infty ,2)} von ${\displaystyle P}${\displaystyle P} gefunden.

2. Eliminierung von ${\displaystyle x_{1}}${\displaystyle x_{1}}

${\displaystyle {\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}}}${\displaystyle {\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 ${\displaystyle 0\leq x_{2}}${\displaystyle 0\leq x_{2}} liefert ${\displaystyle x_{1}\geq 1}${\displaystyle x_{1}\geq 1} und von ${\displaystyle x_{2}\leq 2}${\displaystyle x_{2}\leq 2} liefert ${\displaystyle x_{1}\leq 0}${\displaystyle x_{1}\leq 0}. Es wurden also die Ecken ${\displaystyle (1,0)}${\displaystyle (1,0)} und ${\displaystyle (0,2)}${\displaystyle (0,2)} und die unbeschränkte Kante ${\displaystyle (1,0)}${\displaystyle (1,0)} nach ${\displaystyle (\infty ,0)}${\displaystyle (\infty ,0)} von ${\displaystyle P}${\displaystyle P} gefunden.

Sei das Ungleichungssystem

${\displaystyle {\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}}}${\displaystyle {\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 ${\displaystyle P}${\displaystyle 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 ${\displaystyle x_{3}}${\displaystyle x_{3}}

${\displaystyle {\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}}}${\displaystyle {\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 ${\displaystyle x_{2}}${\displaystyle x_{2}}

${\displaystyle {\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}}}${\displaystyle {\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}}}

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

${\displaystyle {\frac {n^{2n}}{2^{n(n+1)}}}}${\displaystyle {\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 ${\displaystyle ((-1)^{i+j}j^{i})_{1\leq i,j\leq n}}${\displaystyle ((-1)^{i+j}j^{i})_{1\leq i,j\leq n}} mit ${\displaystyle n}${\displaystyle n} Zweierpotenz und beliebiger rechter Seite ${\displaystyle b}${\displaystyle b}, gegeben ist.

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Benutzer:Xorx77/Baustelle&oldid=133489575"