Benutzer:Xorx77/Baustelle

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

beziehungsweise in Vektor-Matrix-Schreibweise

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

[Bearbeiten | Quelltext bearbeiten]

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 so nach einer der Variablen 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 neue Ungleichungen, wobei 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 oder redundante Ungleichungen, wie z.B. wenn bereits gilt, enstehen. Diese können entfernt werden.

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

[Bearbeiten | Quelltext bearbeiten]

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

Berechnung der Ecken eines konvexen Polyeders

[Bearbeiten | Quelltext bearbeiten]

Die Lösungsmenge des linearen Ungleichungssystems mit kann als ein konvexes Polyeder im 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

[Bearbeiten | Quelltext bearbeiten]

Betrachte das Ungleichungssystem in den Unbekannten und .

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

also in Matrixschreibweise

Es sollen nun alle Ecken des konvexen Polyeders gefunden werden und, falls vorhanden, auch die Kanten von , die unbeschränkt sind.

1. Eliminierung von

Rückwärtssubstitution liefert bzw. . Es wurde also die Ecken und und die unbeschränkte Kante nach von gefunden.

2. Eliminierung von

Rückwärtssubstitution von liefert und von liefert . Es wurden also die Ecken und und die unbeschränkte Kante nach von gefunden.

Beispiel im Dreidimensionalen

[Bearbeiten | Quelltext bearbeiten]
Das hellblaue Polyeder P mit dunkelblauen Kanten und roten Ecken. Zur besseren Orientierung sind die Projektionslinien zweier Kanten gestrichelt eingezeichnet

Sei das Ungleichungssystem

gegeben und 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

1.1 Eliminierung von

lineare Optimierungsaufgabe

[Bearbeiten | Quelltext bearbeiten]

Nachteile des Verfahrens

[Bearbeiten | Quelltext bearbeiten]

Der Hauptnachteil des Verfahrens wird bereits in der Beschreibung 2. Schritt genannt: Aus Ungleichung vor dem Kombinationsschritt werden maximal viele danach. Insgesamt müssen also --- bei einem Ausgangssystem von Ungleichung --- maximal

Ungleichungen betrachtet werden. Diese obere Schranke wird auch angenommen, z.B. durch das Ungleichungssystem, das durch die Koeffizientenmatrix mit Zweierpotenz und beliebiger rechter Seite , gegeben ist.