Die Fourier-Motzkin-Elimination ist ein Verfahren, um einen durch ein lineares Ungleichungssystem gegebenen konvexen Polyeder
auf eine Hyperebene der Form
zu projizieren. Dabei ist
eine Matrix und
eine passende rechte Seite.
Das Verfahren wurde von Joseph Fourier im Jahr 1827 erstmals beschrieben,[1] geriet jedoch in Vergessenheit und wurde schließlich 1936 in der Doktorarbeit von Theodore Motzkin
erneut entdeckt.[2]
Beschreibung des Verfahrens
Der Algorithmus kombiniert die Zeilen
der Matrix
und die Einträge der rechten Seite
konisch zu neuen Ungleichungen. Dies geschieht in einer Weise, die
sicherstellt, dass die resultierenden neuen Ungleichungen die Variable
nicht länger beinhalten.
Der Algorithmus wird durch folgenden Pseudocode beschrieben:
function FourierMotzkin(A, b, j) is
Eingabe: eine Matrix
der Dimension
, ein Vektor
der Dimension
und ein Index j
Ausgabe: eine Matrix
der Dimension
, sodass
für alle
und ein Vektor
mit
Einträgen
eine Indizierung der Elemente in
, also eine Bijektion
for
to
do
if
then
else if
then
endif
endfor
return
Der resultierende Polyeder
beschreibt anschließend die gewünschte Projektion[A. 1].
Beispiel für die Fourier-Motzkin-Elimination
Als Beispiel wählen wir den Polyeder
, der durch das folgende Ungleichungssystem gegeben ist:
![{\displaystyle P(A,b)=\{(x,y)\in \mathbb {R} ^{2}\ |\ x\geq 1,\ 2x+4y\leq 14,\ x-2y\leq -1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63f8f4af1c374c7162bb0592abe235b20fedc688)
Die entsprechende Matrix und rechte Seite sind folglich
![{\displaystyle A=\left({\begin{array}{rr}-1&0\\2&4\\1&-2\\\end{array}}\right),\ b=\left({\begin{array}{r}-1\\14\\-1\\\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/412237b579e928fad2afbd8669ce0799f5ecefe2)
Für die Projektion auf die Hyperebene
, also für
, erhalten wir die folgenden Mengen:
,
und
.
Damit ist
und
. Wir setzen
.
Für
kombinieren wir die erste und zweite Ungleichung:
![{\displaystyle 2\cdot (-x)-(-1)\cdot (2x+4y)\leq 2\cdot (-1)-(-1)\cdot (14)\;\Longrightarrow \;4y\leq 12}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de9888c8bdfd54818d99bc264a717f53fcb58e60)
Für
erhalten wir durch die Kombination der ersten und dritten Ungleichung die folgende neue Ungleichung:
![{\displaystyle 1\cdot (-x)-(-1)\cdot (x-2y)\leq 1\cdot (-1)-(-1)\cdot (-1)\;\Longrightarrow \;-2y\leq -2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7243d1d6616158998bc65423a10bc52b8179a627)
Das Bild der Projektion ist also gegeben durch
,
während die resultierende Matrix
bzw.
die rechte Seite
die folgende Gestalt haben:
![{\displaystyle D=\left({\begin{array}{rr}0&4\\0&-2\\\end{array}}\right),\ d=\left({\begin{array}{r}12\\-2\\\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/500d6de6dac936a394c33918a28873242414daf7)
Die Fourier-Motzkin-Elimination aus Sicht der linearen Algebra
Die im Algorithmus angewandten Zeilenoperationen lassen sich durch die Multiplikation der Matrix
bzw. der
rechten Seite
mit einer Matrix
darstellen, deren
-te Zeile gegeben ist durch
![{\displaystyle U_{i\cdot }={\begin{cases}e_{k}&{\text{falls }}p(i)=k\in Z\\a_{tj}e_{s}-a_{sj}e_{t}&{\text{falls }}p(i)=(s,t)\in N\times P\\\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74a1d2ac6e60147272bdd0753fafd7d16fccd176)
Da die Matrix
eine konische Kombination der Zeilen von
beschreibt, sind alle Einträge
von
nicht negativ.
Im obigen Beispiel ist
![{\displaystyle U=\left({\begin{array}{rrr}2&1&0\\1&0&1\\\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4c8d8f1311373508f9b293fd19403c71f799404)
Anwendungen
Zulässigkeitsprobleme
Die Fourier-Motzkin-Elimination hat als Projektionsverfahren die Eigenschaft, dass das
System
eine Lösung besitzt genau dann wenn dies auch auf das
System
zutrifft.
Während es im Allgemeinen schwierig ist, zu entscheiden, ob ein konvexer Polyeder eine zulässige
Lösung besitzt, lässt sich dies in einigen Spezialfällen recht leicht bewerkstelligen:
- Verbleibt keine Variable in dem resultierenden System
, ist also
die Nullmatrix, so ist das System dann und nur dann lösbar, wenn die rechte Seite
nicht negativ ist
- Enthält nur eine einzige zu einer Variable
gehörige Spalte der Matrix
von Null verschiedene Einträge, so entspricht die Projektion einem Intervall
. Ist dieses nicht leer, so ist auch das System
lösbar. Weiterhin sind die möglichen Werte der Variablen
in dem Polyeder
gerade durch das Intervall
gegeben
Diese Erkenntnis lässt sich nutzen, um zu überprüfen, ob ein beliebiges Polyeder
eine zulässige Lösung hat oder nicht: Zunächst werden sämtliche Variablen nacheinander herausprojiziert:
![{\displaystyle P(A,b)\ {\xrightarrow {{\text{FourierMotzkin}}(A,b,1)}}\ P(D^{(1)},d^{(1)})\ {\xrightarrow {{\text{FourierMotzkin}}(D^{(1)},d^{(1)},2)}}\ P(D^{(2)},d^{(2)})\ \cdots \ P(D^{(n-1)},d^{(n-1)})\ {\xrightarrow {{\text{FourierMotzkin}}(D^{(n-1)},d^{(n-1)},n)}}\ P(D^{(n)},d^{(n)})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49d417d3fd0ae19b4be18bcba4c6e726dd641cca)
Die resultierende Matrix
ist dann die Nullmatrix und man kann entscheiden, ob
, denn
gdw.
.
Insbesondere gilt
gdw.
.
Da sich der
-te Projektionsschritt durch eine Multiplikation mit einer nichtnegativen Matrix
ausführen lässt, gilt außerdem:
.
Wenn der
-te Eintrag von
negativ ist,
so ist
und
, wobei
. Diese Aussage entspricht dem Farkas' Lemma. Da sich die Matrizen
während der Ausführung des Algorithmus aufstellen lassen, bietet die Fourier-Motzkin-Elimination damit die Möglichkeit, das Zertifikat für
explizit zu berechnen.
Zusätzlich impliziert die Fourier-Motzkin-Elimination, dass die Projektion eines Polyeders wieder ein Polyeder ist.
Dieses Resultat kann benutzt werden, um die Äquivalenz der
- und
-Darstellung von Polyedern zu zeigen.
Beispiel zur Entscheidung der Zulässigkeit
Wir wollen entscheiden, ob der folgende konvexe Polyeder eine zulässige Lösung hat:
![{\displaystyle P(A,b)=\{x\in \mathbb {R} ^{2}\ |\ x_{1}+x_{2}\geq 4,\ x_{1}\leq 1,\ x_{2}\leq 1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11153e7022405d798c8cc796a785c896691b4e7d)
Dies entspricht in der Form
dem System
![{\displaystyle \left[{\begin{array}{rrr}-x_{1}&-x_{2}&\leq -4\\x_{1}&&\leq 1\\&x_{2}&\leq 1\\\end{array}}\right]\;\;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6dfa74bec84df18da8b9ef93010db157761c042f)
Nach den einzelnen Projektionsschritten ergeben sich folgenden Systeme:
![{\displaystyle \left[{\begin{array}{rr}-x_{2}&\leq -3\\x_{2}&\leq 1\\\end{array}}\right]\;\;\left[{\begin{aligned}0&\leq -2\\\end{aligned}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d4cdd020904b43c782d192d318f0f8f6845aa43)
Es offenbart sich also ein Widerspruch, der Polyeder
entspricht der leeren Menge.
Die resultierenden Matrizen sind gegeben durch
![{\displaystyle U^{(1)}=\left({\begin{array}{rrr}1&1&0\\0&0&1\\\end{array}}\right),\;\;U^{(2)}=\left({\begin{array}{rr}1&1\\\end{array}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b8b3a4c0dcdc472f329ced38c27e1b9c5c8b8b8)
Ein Zertifikat für die Nichtzulässigkeit ist also der Vektor
.
Durch Ausnutzen der Dualität der linearen Optimierung lässt sich
jedes lineare Programm auf ein Zulässigkeitsproblem reduzieren, welches sich dann durch die Anwendung
der Fourier-Motzkin-Elimination lösen lässt. In diesem Fall benötigt man jedoch recht viele neue
Variablen und Ungleichungen, was die Anwendung des Verfahrens verlangsamt.
Alternativ kann man den folgenden Ansatz wählen: Um das Problem
zu lösen, führt man eine zusätzliche Variable
ein, und fordert zusätzlich, dass
. Der Wert der Variablen
ist also
durch die Optimallösung des Problems beschränkt. Man erhält dadurch einen Polyeder
mit
![{\displaystyle {\tilde {A}}=\left({\begin{array}{rr}A&0\\-c^{T}&1\\\end{array}}\right)\in \mathbb {R} ^{m+1\times n+1},\ {\tilde {b}}=\left({\begin{array}{r}b\\0\\\end{array}}\right)\in \mathbb {R} ^{m+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a1851673141c4857a7e3ce496b9c7d2e701070e)
Man projiziert anschließend die ersten
Einträge heraus, sodass man schließlich ein System der Form
![{\displaystyle {\begin{aligned}D_{1,n+1}^{(n)}y&\leq d_{1}^{(n)}\\\vdots &\\D_{l,n+1}^{(n)}y&\leq d_{l}^{(n)}\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b89c655c84fac0c917a291e9f6ce44a22e4e832)
erhält. Das resultierende Intervall
beschreibt die Menge der möglichen Werte
für die Variable
. Es treten folgende Fälle auf:
- Das Intervall ist leer. In diesem Fall besitzt das Optimierungsproblem keine zulässige Lösung.
- Das Intervall ist nicht nach oben beschränkt. Damit ist auch das Optimierungsproblem unbeschränkt.
- Das Intervall ist nicht leer und besitzt ein maximales Element
. Damit ist der Zielfunktionswert der Optimallösung des Problems genau
.
Um eine Lösung
mit einem gegebenen Zielfunktionswert
zu erhalten,
geht man wie folgt vor:
Zunächst betrachtet man das System nach der
-ten Iteration: Es treten nur noch die Variablen
und
auf, wobei der Wert von
schon auf
festgelegt ist:
![{\displaystyle {\begin{aligned}D_{1,n}^{n-1}x_{n}+D_{1,n+1}^{n-1}y&\leq d_{1}^{n-1}\\\vdots &\\D_{l,n}^{n-1}x_{n}+D_{l,n+1}^{n-1}y&\leq d_{l}^{n-1}\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09c8360eda1f618abfd5168e8ac3092e5b6eb02c)
Man erhält somit ein (nicht leeres) Intervall von möglichen Lösungen für
, von denen man eine beliebige auswählt. Diesen Prozess iteriert man für
[A. 2].
Beispiel zur Lösung eines linearen Programms
Zur Illustration des Verfahrens wählen wir das Programm
![{\displaystyle {\begin{aligned}\max ~&x_{1}\\{\text{so dass }}&x_{1}+x_{2}\leq 4\\&x_{1}\geq 0\\&x_{2}\geq 0\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfdbf3dc7d4213502726168290df3776a8b52adc)
Um das Problem zu lösen, fügen wir die Variable
zusammen mit der Ungleichung
zu dem Problem hinzu. Die folgenden Systeme zeigen den Polyeder
, sowie
die veränderten Systeme nach der Projektion auf
und
:
![{\displaystyle \left[{\begin{array}{rrrr}x_{1}&+x_{2}&&\leq 4\\-x_{1}&&&\leq 0\\&-x_{2}&&\leq 0\\-x_{1}&&+y&\leq 0\\\end{array}}\right]\;\;\left[{\begin{array}{rr}-x_{2}&\leq 0\\x_{2}&\leq 4\\x_{2}+y&\leq 4\\\end{array}}\right]\;\;\left[{\begin{aligned}0&\leq 4\\y&\leq 4\\\end{aligned}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02989982f68ef77cc27bf4287311d0d9c8daf793)
Damit steht fest, dass die Optimallösung des Problems den Zielfunktionswert 4 hat. Um eine entsprechende Lösung
zu erhalten, setzen wir
und kehren zum vorletzten Schritt zurück. Es ergibt sich das System
![{\displaystyle {\begin{aligned}-x_{2}&\leq 0\\x_{2}&\leq 4\\x_{2}&\leq 0\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ba1f0161708f1c486ece9f946e58c39076912fa)
Es bleibt also nichts anderes übrig, als
zu setzen. Der Wert von
ergibt
sich schlussendlich aus dem System
![{\displaystyle {\begin{aligned}x_{1}&\leq 4\\-x_{1}&\leq 0\\-x_{1}&\leq -4\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12b863c90ddf74690367c7d3a844bf5730b698d8)
Damit ist die Optimallösung
. Diese hat natürlich auch den erwarteten
Zielfunktionswert von
.
Laufzeit
Obwohl die Fourier-Motzkin-Elimination zur Lösung von linearen Programmen verwendet werden kann, gibt man in der
Praxis anderen Algorithmen den Vorzug. Das Problem der Fourier-Motzkin-Elimination ist, dass im ungünstigsten Fall
die Anzahl der Ungleichungen bzw. die Größe der Matrizen
in jeden Projektionsschritt
von vorher
auf
anwächst.
In diesem Fall ist die Laufzeit des Algorithmus nicht mehr polynomiell.
Im Allgemeinen sind außerdem die meisten der erzeugten Ungleichungen redundant.
Da dies in der Regel allerdings nicht effizient erkannt werden kann,
wird für die Fourier-Motzkin-Elimination weit mehr Speicher
gebraucht als nötig wäre, um die Polyeder
zu beschreiben.
Anmerkungen
- ↑
Da die Menge
im Allgemeinen sehr groß werden kann, ist es ratsam, die Ungleichungen zunächst so zu skalieren, dass
für alle
. Zur Bestimmung
von
und
müssen die Spalten dann nur noch voneinander subtrahiert werden.
- ↑
Das hier vorgestellte Verfahren des Rückwärtseinsetzens lässt sich stets anwenden, um eine zulässige Lösung
des Polyeders zu erhalten.
Einzelnachweise
- ↑ J.B.J. Fourier aus dem Journal: Analyse des travaux de l'Académie Royale des Sciences pendant l'année 1824, Partie mathématique, 1827.
- ↑ T.S. Motzkin: Beiträge zur Theorie der Linearen Ungleichungen.
Literatur
- Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6, S. 155–156.
- H. P. Williams: Fourier's Method of Linear Programming and its Dual. In: American Mathematical Monthly. 93, 1986, S. 681–695.
- Unger, Thomas; Dempe, Stefan: Lineare Optimierung, S. 19–23, Vieweg+Teubner 2010, ISBN 978-3-8351-0139-5
Weblinks