Homepage von Boris Haase




Euklidische Geometrie • Gerechtes Verteilen • Lineare Optimierung • Mengenlehre • Nichtstandardanalysis • Ratschläge • Topologie • Transzendente Zahlen • Zahlentheorie • Zeitrechnung  (Vorherige | Nächste)



Lineare Optimierung

Lineare Optimierung

Im Folgenden lösen wir lineare Programme (LPs) mit dem exponentiellen Simplex- und dem polynomiellen Intexverfahren (Inter-/Extrapolation).

Durchmessersatz für Polytope: Ein durch m Restriktionen gegebenes n-dimensionales Polytop mit m, n ∈ ω≥2 hat einen Durchmesser von maximal 2(m + n - 3).

Beweis: Wir können maximal m - 1 Hyperebenen zu einem unvollständigen Zyklus (der Dimension 2) zusammenstellen und haben n - 2 Ausweichmöglichkeiten zur Seite (in den restlichen Dimensionen) zu berücksichtigen. Da wir jede Teilstrecke mit maximal zwei Kanten passieren können, ergibt sich der Faktor 2. Der Satz lässt sich auf Polyeder sinngemäß übertragen, wenn wir also nur die endliche Beschränkung fallen lassen.⃞

Definition: Sei ω der angestrebte Grenzwert aller Variablen in Landau-Notation und ϑ := ω ln ω. Ein Verfahren ist polynomiell (exponentiell), wenn seine Rechenzeit in Sekunden und (oder) sein Speicherbedarf in Bits OO(1)) (O(e|O(ω)|)) ist.

Satz: Das Simplexverfahren ist exponentiell.

Beweis und Algorithmus: Sei P := {x ∈ ωn : Ax ≤ b, b ∈ ωm, A ∈ ωm×n, m, n ∈ ωℕ*} der zulässige Bereich des LPs max {dTx : d ∈ ωn, x ∈ P}. Dualisieren wir es oder setzen x := x+ - x- mit x+, x- ≥ 0, erreichen wir x ≥ 0. Wir lösen zuerst max {-z : Ax - b ≤ (z, …, z)Tωm, z ≥ 0}, um ein zulässiges x zu erhalten, falls b ≥ 0 nicht gilt. Start- und Zielwert sind z := |min {b1, ..., bm}| bzw. z = 0. Wie im ersten Fall starten wir mit x := 0. Ein geeigneter Pivotschritt ergibt b ≥ 0.

Seien i, j, k ∈ ωℕ* und sei aiT der i-te Zeilenvektor von A. Gilt dj ≤ 0 für alle j, ist das LP gelöst. Gibt es ein dj > 0 (dj = 0) mit aij ≤ 0 für alle i, ist das LP positiv unbeschränkt (können wir dj und A.j wie die bi und ai mit aij < 0 vorerst entfernen). Unlösbar ist auch aijxj ≥ 0 > bi für alle j. Wir teilen eventuell alle aiTx ≤ bi durch ||ai|| und alle dj bzw. aij durch min |aij| für aij ≠ 0 für jedes j. Letzteres machen wir am Ende rückgängig. Wir wiederholen eventuell die Normierung mit ||ai||.

Überflüssige Restriktionen (mit ai ≤ 0) können wir stets entfernen. Wir wählen für jedes dj > 0 und Nichtbasisvariablen xj einen minimalen Quotienten bk/akj für aij > 0 aus. Die Variablen mit * seien die des jeweils nächsten Schritts. Dann ist durch xj* = xj + bk/akj die potentielle nächste zulässige Ecke x* gegeben. Bei Wahl der steilsten Kante ist das akj das Pivotelement zu dem xj darunter, das dTΔx/||Δx|| bzw. dj2/(1 + ||A.j||2) mit Δx := x* - x in der k-ten Restriktion maximiert.

Bei mehreren Maxima können wir die Pivotregel des Bestwerts maxk,j djbk/akj oder (weniger gut) des kleinsten Winkels min Σj dj*/||d*|| verwenden. Können wir die Zielfunktion nicht auf direktem Wege maximieren, behandeln wir die Restriktionen mit bi = 0 gleich, indem wir sie um einen identischen, aber minimalen Betrag abschwächen (perturbieren). Diesen brauchen wir im Tableau selbst nicht zu notieren: Wir setzen hier einfach bi = ||ai||.

Tritt erneut eine mehrfache Ecke auf, obwohl dies nicht sehr wahrscheinlich ist, erhöhen wir die bi von eben einfach um ||ai||. Der Aufwand eine mehrfache Ecke verlassen zu können, wonach wir die Abschwächungen zurücknehmen, entspricht einem LP mit d > 0 und b = 0. Die Zielfunktion wächst auf dem zurückgelegten Weg (quasi) streng monoton. Danach können wir dj*, aij* und bi* nach der Rechteckregel einfach berechnen (vgl. [775], S. 63).

Das Simplexverfahren ist im schlechtesten Fall trotz des Durchmessersatzes für Polytope unter allen Pivotregeln nicht polynomiell, da ein exponentielles "Driften" durch ein Polytop vom Klee-Minty- oder Jeroslow-Typ oder anders konstruiert werden kann, das durch Zwang zur Auswahl der jeweils ungünstigeren Kante vom kürzesten Pfad erheblich abweicht. Dies steht im Einklang mit existierenden Beweisen und es folgt die Behauptung.⃞

Satz: Das Intexverfahren löst jedes lösbare LP in O3).

Beweis und Algorithmus: Wir berechnen das LP min {h ∈ ω≥0 : bTy - dTx ≤ h, 0 ≤ x ∈ ωn, 0 ≤ y ∈ ωm, Ax - b ≤ (h, …, h)Tωm, d - ATy ≤ (h, …, h)Tωn} über das (duale) Programm min {bTy : 0 ≤ y ∈ ωm, ATy ≥ d} zu dem (primalen) Programm max {dTx : d ∈ ωn, x ∈ P≥0}. Sei v := (xT, yT)Tωm+n und das Ziel für die Höhe h sei 0. Wir normieren und skalieren bTy - dTx ≤ 0, Ax ≤ b und ATy ≥ d. Alle Skalarprodukte dTai, -dj, bTA.j und bi sortieren wir.

Wir berechnen x und analog y aus einigen Gleichungen aiTx = bi bzw. xj = 0 mit den größten zugehörigen dTai bzw. -dj. Der Startwert für h ist das für die Gültigkeit der Ungleichungen des LPs benötigte Minimum. Wir interpolieren nacheinander alle vk* := (max vk + min vk)/2 (wenige Male) und ermitteln die Richtung u ∈ ωm+n mit uk := Δvk Δhk/min Δhk nach Lösen aller LPs min hk in hk, vkω≥0. Wir lösen min h in h, s ∈ ω≥0 mit v* := v + su und festem v.

Das Bisektionsverfahren löst die zweidimensionalen LPs in O2). Nach erneuter Interpolation extrapolieren wir in O(ωϑ) (vT, h)T durch (v*T, h*)T in den Rand des Polytops. Wir berechnen (in der Nähe des Optimums) h als das Minimum aller bi - aiTx, A.jTy - dj und dTx - bTy. Per Bisektionsverfahren lösen wir das zweidimensionale LP min h in h, t ∈ ω≥0 mit v* := v + tr, rT ∈ {(0T, A.jT), (-aiT, 0T), (-aiT, A.jT), (dT, -bT)} und festem v ebenfalls in O2).

Auf die zweidimensionalen LPs können wir eventuell verzichten. Sind x und y optimal oder lässt sich h nicht weiter minimieren, stoppen wir das Verfahren. Können wir v nicht verlassen, schwächen wir alle Restriktionen außer v ≥ 0 ein wenig ab und machen dies am Ende eines Durchlaufs rückgängig. Da Δh bei jedem Durchlauf in O(ωϑ2) ungefähr die Hälfte von h ist, folgt aus dem starken Dualitätssatz ([775], S. 60 - 65) die Behauptung.⃞

Bemerkungen: Simplexverfahren und Face-Algorithmus ([916], S. 580 f.) lösen das LP für kleine m und n eventuell schneller. Wir können den aktuellen Bestand der Restriktionen bzw. Variablen einfach verändern, da das Intexverfahren ein nicht-transformierendes Verfahren und schneller als alle bekannten (Worst-Case-)LP-Algorithmen in O(ϑω3,5) ist. Wir haben lediglich ggf. h anzupassen, da wir zusätzliche Variable mit 0 initialisieren können.

Korollar: Jedes lösbare lineare Gleichungssystem (LGS) Ax = b mit x ∈ ωn lässt sich in O3) lösen, wenn wir es als LP min {h ∈ ω≥0 : ±(Ax - b) ≤ (h, …, h)Tωm} schreiben.⃞

Korollar: Jedes lösbare LP min {h ∈ ω≥0 : ±(Ax - λx) ≤ (h, …, h)Tωn} kann einen Eigenvektor x ∈ ωn \ {0} der Matrix A ∈ ωn×n zum Eigenwert λ ∈ ωℝ in O3) bestimmen.⃞

Korollar: Sei αj der j-te Spaltenvektor der Matrix A-1ωn×n und sei δij das Kronecker-Delta. Jedes LGS Aαj = (δ1j, ..., δnj)T zur Bestimmung der Inversen A-1 der regulären Matrix A lässt sich für j = 1, ..., n in O3) lösen. Ob A regulär ist, lässt sich ebenfalls in O3) bestimmen.⃞

Bemerkungen: Die drei Korollare lassen sich leicht ins Komplexe überführen. Das Intexverfahren ist numerisch sehr stabil, da wir die Ausgangsdaten nur wenig ändern, und lässt sich modifiziert durch verteiltes Rechnen in O(1) lösen. Es eignet sich für (gemischt-)ganzzahlige Probleme und Branch-and-Bound, insbesondere in der nicht-konvexen Optimierung. Es lässt sich leicht auf konvexe Programme (mit einer vektorwertigen Zielfunktion f1) übertragen:

Korollar: Jedes lösbare konvexe Programm min {f1(x) : x ∈ ωn, (f2(x), …, fm(x))T ≤ 0} mit konvexen Funktionen fiωℝ können die die fi abarbeitenden Intex- und zweidimensionalen Bisektions- oder Newtonverfahren in polynomieller Laufzeit lösen, wenn die Anzahl der Operanden xj der fi ≤ ωć-2 ist und ein x existiert mit fi(x) < 0 für alle i > 1 (s. [939], S. 589 ff.).⃞

Programmtext des Simplexverfahrens

© 2008-2018 by Boris Haase


Valid XHTML 1.0 • Haftungsausschluss • mail@boris-haase.de • PDF-Version • Literatur • Schlagwörter • Definitionen • Statistik • PHP-Code • RSS-Feed • Seitenbeginn