Algorytm simplex i skrajne punkty
W przypadku tego pytania moją krótką ręką jest LP = program liniowy, BFS = podstawowe możliwe rozwiązanie, SEF = standardowa forma równości.
Ponieważ algorytm Simplex iteruje od skrajnego punktu do skrajnego punktu (co odpowiada faktowi, że Simplex iteruje od BFS do BFS, gdy LP jest w SEF), w jaki sposób algorytm Simplex działa geometrycznie, gdy wykonalny region jest wielościanem, którego nie można zrealizować w SEF (np. Pół spacji)? Załóżmy, że mamy LP, dla którego możliwy region nie ma skrajnych punktów. Następnie możemy napisać „równoważny” LP, który jest w SEF i zamiast tego uruchomić na nim algorytm Simplex. Ale dla tego nowego wielościanu istnieją skrajne punkty, podczas gdy w oryginale nie ma z założenia. Początkowo myślałem, że skrajne punkty jednego LP bijektywnie odpowiadają skrajnym punktom drugiego, ale najwyraźniej tak nie jest.
Więc kiedy dokładnie skrajne punkty wersji SEF LP odpowiadają bijektywnie skrajnym punktom oryginału? I dalej, jeśli taki bijekcja nie zachodzi, jak mamy geometrycznie zinterpretować, co robi algorytm Simplex w odniesieniu do oryginalnego LP?
Odpowiedzi
algorytm Simplex iteruje od skrajnego punktu do skrajnego punktu
Technicznie nie. Algorytm simplex iteruje od podstawy do podstawy . Po prostu zdarza się, że wykonalne podstawowe rozwiązania odpowiadają skrajnym punktom. (na przykład dual simplex iteruje przez podwójne wykonalne rozwiązania podstawowe, które nie są skrajnymi punktami pierwotnie wykonalnego regionu).
Rozważmy LP w standardowej formie, w której pisze \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}Ten możliwy obszar LP jest zawsze wielościenny. Jeśli nie ma skrajnych punktów, to jest albo pusta (i nie ma podstawowych wykonalnych rozwiązań), albo afiniczna podprzestrzeń$\mathbb{R}^{n}$. Teraz ten drugi przypadek nie może się zdarzyć, ponieważ żadna podprzestrzeń afiniczna nie może być podzbiorem$\mathbb{R}_{+}^{n}$.
A teraz wracając do (jak myślę) twojego pierwotnego pytania: biorąc pod uwagę oryginalny wielościan i jego reprezentację SEF, czy ta reprezentacja ma punkty skrajne i czy odpowiadają one skrajnym punktom oryginalnego polyhderonu? Odpowiedź brzmi: tak, SEF będzie miał skrajne punkty i nie, nie zawsze mogą one odpowiadać skrajnym punktom twojego oryginalnego wielościanu.
Oto prosty przykład: weź $\mathcal{P} = \{x \in \mathbb{R}\}$, który jest jednowymiarowym wielościanem. Jego sformułowanie ma jedną swobodną zmienną i żadnych ograniczeń.
Aby zbudować reprezentację SEF, zamień $x$ przez $x^{+} - x^{-}$ z $x^{\pm} \geq 0$. Teraz,$(0, 0)$ jest skrajnym punktem tej funkcji SEF, której odpowiada $x=0$, co nie jest skrajnym punktem $\mathcal{P}$.
Nie jestem pewien, czy w pełni rozumiem twoje pytanie, ale wydaje mi się, że twoje zamieszanie wynika z założenia, że podstawowe rozwiązanie to „skrajny punkt”. Podstawowym (niekoniecznie pierwotnym lub podwójnym wykonalnym) rozwiązaniem jest po prostu przecięcie ograniczeń liczby wierszy (z których niektóre mogą być granicami). Jest możliwe, że problem nie ma pierwotnego lub podwójnego wykonalnego rozwiązania, w wyniku czego jest niewykonalny lub nieograniczony. Podręcznikowe algorytmy simplex czasami pomijają fakt, że jakaś forma podejścia fazy 1 jest potrzebna do ustanowienia BFS, aby faktycznie uruchomić algorytm. Jest możliwe, że pierwotna faza 1 uzna problem pierwotny za niewykonalny, a także możliwe, że w fazie podwójnej 1 problem będzie nieograniczony.
Aktualizacja: Odpowiedź mtanneau prawdopodobnie mówi wszystko, co można powiedzieć, dla pojedynczego ograniczenia ze zmiennymi wolnymi to samo dotyczy. Chcę tylko dodać, że implementacje simplex działają bezpośrednio z wolnymi zmiennymi i nie konwertują ich na dwie zmienne ograniczone przez 0. Ale to samo jest takie samo, algorytm iteruje po podstawowych rozwiązaniach i jest przyjęta konwencja, że zmienne inne niż podstawowe mają wartość 0. Należy również zauważyć, że w przypadku ograniczonych wielościanów podstawowe rozwiązania odpowiadają skrajnym punktom.