Next: Bereiche Approximieren
Up: Lösen von linearen Ungleichungssystemen
Previous: Vorgehen:
Contents
Index
Für die optimierte Lösung werden alle Randhyperebenen außer Punkten, Geraden und Hyperebenen der Dimensionalität weggelassen. Der hier gegebene Algorithmus ist für mindestens drei Parameter (). Wenn die Lösung nur zwei oder ein Parameter hat, kann ein anderer Algorithmus verwendet werden, bzw. der nachfolgende Algorthmus angepasst werden.
- 0 Initialisiere die Hyperebenen ( und ) mit dem Hyperkörper der maximalen Lösungsmenge (eventuell unter Zuhilfenahme von )
- 1 Prüfe :
- 1.1 Fall 1: Wenn größer , setze auf und gehe zu "8. Lösung ermitteln"
- 1.2 Sonst: Nehme nächste Ungleichung
- 1.2.1 Erstelle eine orientierte Hyperfläche für aktuelle Ungleichung als Normalgleichung, mit dem Normalenvektor in Richtung der zulässigen Lösungen. Aus der Ungleichung in der Form
wird die Normalengleichung
mit
und
- 2. Prüfe für alle Punkte auf welcher Seite der Hyperflache sie liegen
- 2.1 Fall 1: alle Eckpunkte liegen in Richtung des Normalenvektors oder auf der Hyperebene -> erhöhe Zähler und gehe zu 1. (die Hyperfläche schränkt die Lösungsmenge nicht weiter ein, d. h. ist nicht relevant)
- 2.2 Fall 2: alle Eckpunkte liegen nicht in Richtung des Normalenvektors -> erniedrige Zähler und gehe zu "8. Lösung ermitteln" (durch die Hinzunahme der Ungleichung gäbe es keine Lösungen mehr, bzw. die Ungleichung macht das bisherige Gleichungsystem unlösbar)
- 2.3 Sonst: einige Eckpunkte liegen in Richtung des Normalenvektors , andere nicht -> gehe zu Schritt 3., bzw. integriere die Hyperfläche in den konvexer Hyperkörper der möglichen Lösungen
- 3 ermittle alle (Rand-) Linien/Geraden des Hyperkörpers zwischen den Eckpunkten nicht in Richtung des Normalenvektors und Eckpunkten in dessen Richtung (ignoriere Eckpunkte auf )
- 3.1 für jede dieser Geraden : ermittle Schnittpunkte mit der Hyperfläche und füge sie zum Hyperkörper hinzu
- 3.2 finde Geraden zwischen den Schnittpunkten auf , welche einen konvexen Körper bilden: für jeden Schnittpunkt auf (
) ermittle alle Schnittpunkt auf die gemeinsam auf mindestens anderen Hyperflächen () liegen. (Diese Hyperflächen sollten zusammen mit der Hyperfläche als Schnittfläche eine Gerade haben. Da die Dimensionalität hat und der Schnitt mit jeder weiteren ( dimensionalen) Hyperflächen die Dimensionalität der Schnittfläche um eins verringert.)
- 3.2.1 ermittle Geraden zwischen und die gemeinsam auf gemeinsammen anderen Hyperfläche liegen
- 3.2.2 füge Geraden zu und als auf liegend hinzu
- 3.2.3 füge und als auf liegend hinzu
- 4. entferne alle Eckpunkte die nicht in Richtung des Normalenvektors von liegen
- 5. entferne alle Gerade die nur noch einen Eckpunkt besitzen
- 6. entferne alle Hyperflächen auf denen keine Geraden mehr liegen
- 7. wenn : erhöhe Zähler und gehe zu 1. (sonst 8.)
- 8. Lösung ermitteln:
- 8.1. Alternative 1:
- 8.1.1. Gebe als Eckpunkte der (konvexen) Lösungsmenge und als Anzahl der erfüllten Ungleichungen zurück (eine Lösung kann dann aus dem Bereich ermittelt werden)
- 8.1. Alternative 2:
- 8.1.1. Nehme den Mittelpunkt /Schwerpunkt aller Eckpunkte :
- 8.1.2. Gebe als Lösung und als Anzahl der erfüllten Ungleichungen zurück
Next: Bereiche Approximieren
Up: Lösen von linearen Ungleichungssystemen
Previous: Vorgehen:
Contents
Index
Betti Österholz
2013-02-13