Simplex-Algorithmus und Extrempunkte
Für diese Frage ist meine Abkürzung LP = lineares Programm, BFS = realisierbare Grundlösung, SEF = Standardgleichheitsform.
Da der Simplex-Algorithmus von Extrempunkt zu Extrempunkt iteriert (entsprechend der Tatsache, dass Simplex von BFS zu BFS iteriert, wenn sich die LP in SEF befindet), wie funktioniert der Simplex-Algorithmus geometrisch, wenn der realisierbare Bereich ein Polyeder ist, in dem nicht realisiert werden kann SEF (zB ein halber Raum)? Angenommen, wir haben eine LP, für die die realisierbare Region keine Extrempunkte hat. Dann können wir eine 'äquivalente' LP schreiben, die sich in SEF befindet, und stattdessen den Simplex-Algorithmus darauf ausführen. Aber es gibt extreme Punkte für dieses neue Polyeder, während es unter der Annahme keine für das Original gibt. Ich dachte ursprünglich, dass die Extrempunkte einer LP bijektiv den Extrempunkten der anderen entsprechen, aber dies ist offensichtlich nicht der Fall.
Wann genau entsprechen die Extrempunkte der SEF-Version einer LP bijektiv den Extrempunkten des Originals? Und wenn eine solche Bijektion nicht zutrifft, wie sollen wir dann geometrisch interpretieren, was der Simplex-Algorithmus in Bezug auf die Original-LP tut?
Antworten
Der Simplex-Algorithmus iteriert von Extrempunkt zu Extrempunkt
Technisch gesehen nein. Der Simplex-Algorithmus iteriert von Basis zu Basis . Es kommt einfach vor, dass realisierbare Grundlösungen Extrempunkten entsprechen. (Zum Beispiel iteriert der Dual-Simplex durch dual-realisierbare Grundlösungen, die keine Extrempunkte des primär realisierbaren Bereichs sind).
Betrachten Sie eine LP in Standardform, die schreibt \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}Die realisierbare Region dieser LP ist immer polyedrisch. Wenn es keine Extrempunkte hat, ist es entweder leer (und es gibt keine realisierbaren Grundlösungen) oder ein affiner Unterraum von$\mathbb{R}^{n}$. Der letztere Fall kann nun nicht eintreten, da kein affiner Unterraum eine Teilmenge von sein kann$\mathbb{R}_{+}^{n}$.
Kommen wir nun zu Ihrer ursprünglichen Frage zurück (was ich denke): Hat diese Darstellung angesichts eines ursprünglichen Polyeders und einer SEF-Darstellung extreme Punkte und entsprechen sie extremen Punkten des ursprünglichen Polyhderons? Die Antwort lautet: Ja, der SEF hat Extrempunkte, und nein, sie entsprechen möglicherweise nicht immer den Extrempunkten Ihres ursprünglichen Polyeders.
Hier ist ein einfaches Beispiel: nehmen $\mathcal{P} = \{x \in \mathbb{R}\}$Dies ist ein eindimensionales Polyeder. Seine Formulierung hat eine freie Variable und keine Einschränkungen.
Ersetzen Sie, um eine SEF-Darstellung zu erstellen $x$ durch $x^{+} - x^{-}$ mit $x^{\pm} \geq 0$. Jetzt,$(0, 0)$ ist ein extremer Punkt dieses SEF, der entspricht $x=0$, was kein extremer Punkt von ist $\mathcal{P}$.
Ich bin mir nicht sicher, ob ich Ihre Frage vollständig verstehe, aber ich denke, Ihre Verwirrung beruht auf der Annahme, dass eine grundlegende Lösung ein "extremer Punkt" ist. Eine grundlegende (nicht unbedingt ursprüngliche oder doppelte realisierbare) Lösung ist nur der Schnittpunkt der Anzahl der Zeilenbeschränkungen (von denen einige Grenzen sein können). Es ist möglich, dass ein Problem keine ursprüngliche oder doppelte realisierbare Lösung hat, da es entweder nicht realisierbar oder unbegrenzt ist. Lehrbuch-Simplex-Algorithmen überspringen manchmal die Tatsache, dass irgendeine Form von Phase-1-Ansatz erforderlich ist, um ein BFS einzurichten, um den Algorithmus tatsächlich zu starten. Es ist möglich, dass eine ursprüngliche Phase 1 das Problem als nicht realisierbar ansieht, und es ist auch möglich, dass eine doppelte Phase 1 das Problem unbegrenzt findet.
Update: Die Antwort von mtanneau sagt wahrscheinlich alles, was es zu sagen gibt, für eine einzelne Einschränkung mit freien Variablen gilt das Gleiche. Ich möchte nur hinzufügen, dass Simplex-Implementierungen direkt mit freien Variablen arbeiten und diese nicht in zwei durch 0 begrenzte Variablen konvertieren. Gleiches gilt jedoch, der Algorithmus iteriert über grundlegende Lösungen und es wird die Konvention aufgestellt, dass nicht grundlegende freie Variablen den Wert annehmen 0. Beachten Sie auch, dass für begrenzte Polyeder grundlegende Lösungen Extrempunkten entsprechen.