Algorytm simpleks - Simplex algorithm

W optymalizacji matematycznej , Dantzig „s simplex algorytm (lub metoda simplex ) jest popularny algorytm dla programowania liniowego .

Nazwa algorytmu wywodzi się z pojęcia simpleksu i została zasugerowana przez TS Motzkina . W metodzie tak naprawdę nie stosuje się uproszczeń, ale jedną z jej interpretacji jest to, że operuje ona na stożkach simplicjalnych , które stają się właściwymi uproszczeniami z dodatkowym ograniczeniem. Stożki proste, o których mowa, to narożniki (tj. sąsiedztwo wierzchołków) obiektu geometrycznego zwanego polytope . Kształt tego politopu jest określony przez ograniczenia nałożone na funkcję celu.

Historia

George Dantzig pracował nad metodami planowania dla Sił Powietrznych Armii USA podczas II wojny światowej przy użyciu kalkulatora biurkowego. W 1946 jego kolega rzucił mu wyzwanie zmechanizowania procesu planowania, aby odwrócić jego uwagę od podjęcia innej pracy. Dantzig sformułował problem jako nierówności liniowe inspirowane pracą Wassily'ego Leontiefa , jednak w tym czasie nie uwzględniał celu jako części swojego sformułowania. Bez celu możliwa jest ogromna liczba rozwiązań, a zatem, aby znaleźć „najlepsze” wykonalne rozwiązanie, należy zastosować określone przez wojsko „podstawowe zasady”, które opisują, w jaki sposób cele mogą zostać osiągnięte, w przeciwieństwie do określania samego celu. Podstawowym spostrzeżeniem Dantziga było uświadomienie sobie, że większość takich podstawowych zasad można przełożyć na liniową funkcję celu, którą należy zmaksymalizować. Rozwój metody simplex był ewolucyjny i trwał około roku.

Po tym, jak w połowie 1947 r. Dantzig włączył funkcję celu jako część swojego sformułowania, problem stał się matematycznie łatwiejszy do rozwiązania. Dantzig zdał sobie sprawę, że jeden z nierozwiązanych problemów, które pomylił jako pracę domową na zajęciach profesora Jerzego Neymana (a właściwie później rozwiązany), dotyczył znalezienia algorytmu dla programów liniowych. Problem ten obejmował znalezienie mnożników Lagrange'a dla ogólnych programów liniowych w kontinuum zmiennych, z których każda jest ograniczona od zera do jednego, oraz spełniających ograniczenia liniowe wyrażone w postaci całek Lebesgue'a . Dantzig opublikował później swoją „pracę domową” jako pracę magisterską, aby zdobyć doktorat. Geometria kolumny użyta w tej pracy dała Dantzigowi wgląd, który kazał mu wierzyć, że metoda Simplex będzie bardzo wydajna.

Przegląd

Układ liniowych nierówności definiuje Polytope jako regionu wykonalne. Algorytm simpleks zaczyna się od wierzchołka początkowego i przesuwa się wzdłuż krawędzi wielokąta, aż osiągnie wierzchołek optymalnego rozwiązania.

Wielościan algorytmu simplex w 3D

Algorytm simpleks działa na programach liniowych w postaci kanonicznej

Wyolbrzymiać ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

podlega i${\ Displaystyle A \ mathbf {x} \ leq \ mathbf {b}}$${\ Displaystyle \ mathbf {x} \ geq 0}$

ze współczynnikami funkcji celu, jest macierzą transponowaną , i są zmiennymi problemu, jest macierzą p × n , oraz . Istnieje prosty proces konwersji dowolnego programu liniowego na program o standardowej formie, więc używanie tej formy programów liniowych nie powoduje utraty ogólności. ${\ Displaystyle \ mathbf {c} = (c_ {1}, \, \ kropki, \, c_ {n})}$${\ Displaystyle (\ cdot) ^ {\ operatorname {T}}}$${\ Displaystyle \ mathbf {x} = (x_ {1} \ \ kropki \ x_ {n})}$${\ Displaystyle A}$${\ Displaystyle \ mathbf {b} = (b_ {1}, \ \ kropki \ b_ {p})}$

W kategoriach geometrycznych wykonalny obszar zdefiniowany przez wszystkie wartości takie, że i jest (prawdopodobnie nieograniczonym) wypukłym polytopem . Skrajny punkt lub wierzchołek tego politopu jest znany jako podstawowe rozwiązanie dopuszczalne (BFS). ${\displaystyle \mathbf {x}}$${\textstyle A\mathbf {x} \leq \mathbf {b} }$${\ Displaystyle \ forall ja, x_ {i} \ geq 0}$

Można wykazać, że dla programu liniowego w postaci standardowej, jeśli funkcja celu ma maksymalną wartość w obszarze dopuszczalnym, to ma tę wartość na (co najmniej) jednym z punktów skrajnych. To samo w sobie sprowadza problem do skończonego obliczenia, ponieważ istnieje skończona liczba punktów ekstremalnych, ale liczba punktów ekstremalnych jest nie do opanowania dla wszystkich, z wyjątkiem najmniejszych programów liniowych.

Można również wykazać, że jeśli punkt skrajny nie jest punktem maksymalnym funkcji celu, to istnieje krawędź zawierająca ten punkt, tak że wartość funkcji celu ściśle rośnie wraz z krawędzią oddalającą się od tego punktu. Jeśli krawędź jest skończona, wówczas łączy się z innym skrajnym punktem, w którym funkcja celu ma większą wartość, w przeciwnym razie funkcja celu jest nieograniczona powyżej na krawędzi, a program liniowy nie ma rozwiązania. Algorytm simpleks stosuje to spostrzeżenie, przechodząc wzdłuż krawędzi politopu do skrajnych punktów o coraz większych wartościach obiektywnych. Trwa to do momentu osiągnięcia maksymalnej wartości lub odwiedzin nieograniczonej krawędzi (wnioskując, że problem nie ma rozwiązania). Algorytm zawsze się kończy, ponieważ liczba wierzchołków w polytope jest skończona; ponadto, ponieważ przeskakujemy między wierzchołkami zawsze w tym samym kierunku (w kierunku funkcji celu), mamy nadzieję, że liczba odwiedzonych wierzchołków będzie niewielka.

Rozwiązanie programu liniowego realizowane jest w dwóch krokach. W pierwszym kroku, znanym jako Faza I, znajduje się punkt początkowy. W zależności od charakteru programu może to być trywialne, ale ogólnie można to rozwiązać, stosując algorytm simpleks do zmodyfikowanej wersji oryginalnego programu. Możliwymi wynikami Fazy I są albo znalezienie podstawowego możliwego rozwiązania, albo to, że wykonalny obszar jest pusty. W tym drugim przypadku program liniowy nazywamy niewykonalnym . W drugim etapie, Fazie II, algorytm simpleks jest stosowany przy użyciu podstawowego możliwego rozwiązania znalezionego w Fazie I jako punktu wyjścia. Możliwe wyniki z fazy II są albo optymalnym podstawowym możliwym rozwiązaniem, albo nieskończoną krawędzią, na której funkcja celu jest nieograniczona powyżej.

Forma standardowa

Przekształcenie programu liniowego w program o standardowej formie można przeprowadzić w następujący sposób. Po pierwsze, dla każdej zmiennej z dolnym ograniczeniem innym niż 0 wprowadzana jest nowa zmienna reprezentująca różnicę między zmienną a ograniczeniem. Oryginalną zmienną można następnie wyeliminować przez podstawienie. Na przykład, biorąc pod uwagę ograniczenie

${\displaystyle x_{1}\geq 5}$

nowa zmienna, , jest wprowadzana z ${\displaystyle Y_{1}}$

${\ Displaystyle {\ zacząć {wyrównany} y_ {1} = x_ {1}-5 \ \ x_ {1} = y_ {1} + 5 \ koniec {wyrównany}}}$

Drugie równanie może być wykorzystane do wyeliminowania z programu liniowego. W ten sposób wszystkie ograniczenia dolnej granicy mogą zostać zmienione na ograniczenia nieujemne. ${\displaystyle x_{1}}$

Po drugie, dla każdego pozostałego ograniczenia nierówności wprowadzana jest nowa zmienna, nazywana zmienną luźną , aby zmienić ograniczenie na ograniczenie równości. Ta zmienna reprezentuje różnicę między dwiema stronami nierówności i zakłada się, że jest nieujemna. Na przykład nierówności

${\ Displaystyle {\ zacząć {wyrównany} x_ {2} + 2 x {3} i \ leq 3 \ \ - x {4} + 3 x_ {5} i \ geq 2 \ koniec {wyrównany}}}$

są zastępowane przez

${\ Displaystyle {\ zacząć {wyrównany} x_ {2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{ 1},\,s_{2}&\geq 0\end{aligned}}}$

W tej postaci znacznie łatwiej jest przeprowadzić algebraiczne manipulacje nierównościami. W nierównościach, w których pojawia się ≥ jak druga, niektórzy autorzy odnoszą się do zmiennej wprowadzonej jako azmienna nadwyżkowa .

Po trzecie, każda nieograniczona zmienna jest eliminowana z programu liniowego. Można to zrobić na dwa sposoby, po pierwsze, rozwiązując zmienną w jednym z równań, w którym występuje, a następnie eliminując zmienną przez podstawienie. Drugim jest zastąpienie zmiennej różnicą dwóch zmiennych zastrzeżonych. Na przykład, jeśli jest nieograniczony, napisz ${\displaystyle z_{1}}$

${\ Displaystyle {\ zacząć {wyrównany} i z_ {1} = z_ {1} ^ {+}-z_ {1} ^ {-} \ \ i z_ {1} ^ {+} \, z_ {1} ^ { -}\geq 0\end{wyrównany}}}$

Równanie można wykorzystać do wyeliminowania z programu liniowego. ${\displaystyle z_{1}}$

Po zakończeniu tego procesu możliwy region będzie miał postać

${\ Displaystyle \ mathbf {A} \ mathbf {x} = \ mathbf {b}, \, \ forall i \ x_ {i} \ geq 0}$

Przydatne jest również założenie, że ranga jest liczbą wierszy. Nie powoduje to utraty ogólności, ponieważ w przeciwnym razie albo system ma nadmiarowe równania, które można pominąć, albo system jest niespójny i program liniowy nie ma rozwiązania. ${\ Displaystyle \ mathbf {A}}$${\ Displaystyle \ mathbf {A} \ mathbf {x} = \ mathbf {b}}$

Tabela simpleksowa

Program liniowy w postaci standardowej można przedstawić w postaci tableau postaci

${\ Displaystyle {\ zacząć {bmatrix} 1 i - \ mathbf {c} ^ {T} i 0 \ \ 0 i \ mathbf {A} i \ mathbf {b} \ koniec {bmatrix}}}$

Pierwszy wiersz definiuje funkcję celu, a pozostałe wiersze określają ograniczenia. Zero w pierwszej kolumnie reprezentuje wektor zerowy o tym samym wymiarze co wektor b (różni autorzy stosują różne konwencje co do dokładnego układu). Jeśli kolumny A można przestawić tak, aby zawierały macierz jednostkową rzędu p (liczbę wierszy w A), to mówi się, że tablica ma postać kanoniczną . Zmienne odpowiadające kolumnom macierzy jednostkowej nazywane są zmiennymi podstawowymi, podczas gdy pozostałe zmienne nazywane są zmiennymi niepodstawowymi lub wolnymi . Jeżeli wartości zmiennych niepodstawowych są ustawione na 0, to wartości zmiennych podstawowych można łatwo uzyskać jako wpisy w b i to rozwiązanie jest podstawowym rozwiązaniem możliwym do zrealizowania. Algebraiczną interpretacja jest to, że współczynniki równania liniowego przedstawione każdym rzędzie są albo , albo jakiś inny numer. Każdy wiersz będzie miał kolumnę z wartością , kolumny ze współczynnikami , a pozostałe kolumny z kilkoma innymi współczynnikami (te inne zmienne reprezentują nasze zmienne niepodstawowe). Ustawiając wartości zmiennych niepodstawowych na zero zapewniamy w każdym wierszu, że wartość zmiennej reprezentowanej przez a w jej kolumnie jest równa wartości w tym wierszu. ${\ Displaystyle 0}$${\ Displaystyle 1}$${\ Displaystyle 1}$${\ Displaystyle 1}$${\displaystyle p-1}$${\ Displaystyle 0}$${\ Displaystyle 1}$${\displaystyle b}$

Odwrotnie, mając podstawowe możliwe rozwiązanie, kolumny odpowiadające zmiennym niezerowym można rozwinąć do macierzy nieosobliwej. Jeśli odpowiednia tablica jest pomnożona przez odwrotność tej macierzy, to wynikiem jest tablica w formie kanonicznej.

Pozwolić

${\ Displaystyle {\ zacząć {bmatrix} 1 i - \ mathbf {c} _ {B} ^ {T} i - \ mathbf {c} _ {D} ^ {T} i 0 \ \ 0 i ja i \ mathbf {D} i \ mathbf {b} \end{bmacierz}}}$

być tableau w formie kanonicznej. Dodatkowe przekształcenia dodawania wierszy można zastosować w celu usunięcia współczynników cT
B z funkcji celu. Ten proces nazywa się wyceną i skutkuje kanoniczną tabelą

${\ Displaystyle {\ zacząć {bmatrix} 1 i 0 i - {\ bar {\ mathbf {c}}} _ {D} ^ {T} i z_ {B} \ \ 0 i ja i \ mathbf {D} i \ mathbf {b} \ koniec {bmatryca}}}$

gdzie z _B jest wartością funkcji celu przy odpowiednim podstawowym rozwiązaniu dopuszczalnym. Zaktualizowane współczynniki, zwane również względnymi współczynnikami kosztu , są szybkościami zmian funkcji celu względem zmiennych niepodstawowych.

Operacje obrotowe

Operacja geometryczna przejścia od podstawowego rozwiązania wykonalnego do sąsiedniego podstawowego rozwiązania wykonalnego jest realizowana jako operacja obrotowa . Najpierw w niepodstawowej kolumnie wybierany jest niezerowy element obrotu . Wiersz zawierający ten element jest mnożony przez jego odwrotność, aby zmienić ten element na 1, a następnie wielokrotności wiersza są dodawane do innych wierszy, aby zmienić inne wpisy w kolumnie na 0. Wynik jest taki, że jeśli element przestawny jest w wierszu r , to kolumna staje się r-tą kolumną macierzy jednostkowej. Zmienna dla tej kolumny jest teraz zmienną podstawową, zastępującą zmienną, która przed operacją odpowiadała r -tej kolumnie macierzy jednostkowej. W efekcie zmienna odpowiadająca kolumnie przestawnej wchodzi do zestawu zmiennych podstawowych i jest nazywana zmienną wchodzącą , a zastępowana zmienna opuszcza zestaw zmiennych podstawowych i jest nazywana zmienną wychodzącą . Tableau jest nadal w formie kanonicznej, ale ze zbiorem podstawowych zmiennych zmienionych o jeden element.

Algorytm

Niech program liniowy będzie dany przez tablicę kanoniczną. Algorytm simpleks wykonuje kolejne operacje obrotu, z których każda daje ulepszone podstawowe możliwe rozwiązanie; wybór elementu obrotowego na każdym etapie jest w dużej mierze zdeterminowany przez wymaganie, aby ten element obrotowy poprawiał rozwiązanie.

Wprowadzanie wyboru zmiennej

Ponieważ zmienna wchodząca na ogół wzrośnie od 0 do liczby dodatniej, wartość funkcji celu zmniejszy się, jeśli pochodna funkcji celu względem tej zmiennej będzie ujemna. Równoważnie wartość funkcji celu jest zwiększana, jeśli kolumna przestawna jest wybrana tak, że odpowiedni wpis w wierszu celu tabeli jest dodatni.

Jeśli istnieje więcej niż jedna kolumna, tak że wpis w wierszu celu jest pozytywny, to wybór, którą z nich dodać do zestawu podstawowych zmiennych, jest nieco arbitralny i opracowano kilka reguł wyboru zmiennych wprowadzania, takich jak algorytm Devex .

Jeżeli wszystkie wpisy w wierszu celu są mniejsze lub równe 0, to nie można dokonać wyboru wpisywania zmiennej i rozwiązanie jest w rzeczywistości optymalne. Łatwo zauważyć, że jest optymalny, ponieważ wiersz celu odpowiada teraz równaniu postaci

${\displaystyle z(\mathbf {x} )=z_{B}+{\text{warunki nieujemne odpowiadające zmiennym niepodstawowym}}}$

Zmieniając regułę wyboru wprowadzanych zmiennych tak, aby wybierała kolumnę, w której wpis w wierszu celu jest ujemny, algorytm jest zmieniany tak, że znajduje maksimum funkcji celu, a nie minimum.

Pozostawienie wyboru zmiennej

Po wybraniu kolumny przestawnej wybór rzędu przestawnego jest w dużej mierze zdeterminowany przez wymóg, aby powstałe rozwiązanie było wykonalne. Po pierwsze, tylko dodatnie wpisy w kolumnie przestawnej są brane pod uwagę, ponieważ gwarantuje to, że wartość wprowadzanej zmiennej będzie nieujemna. Jeśli w kolumnie przestawnej nie ma wpisów dodatnich, zmienna wprowadzająca może przyjąć dowolną wartość nieujemną, przy czym rozwiązanie pozostanie wykonalne. W tym przypadku poniżej funkcja celu jest nieograniczona i nie ma minimum.

Następnie należy wybrać wiersz przestawny, aby wszystkie pozostałe zmienne podstawowe pozostały dodatnie. Obliczenia pokazują, że dzieje się tak, gdy wynikowa wartość wprowadzanej zmiennej jest minimalna. Innymi słowy, jeśli kolumna przestawna to c , wiersz przestawny r jest tak wybrany, że

${\displaystyle b_{r}/a_{rc}\,}$

jest minimalna nad wszystkimi R tak, że _rc > 0. To się nazywa badanie stosunek minimum . Jeśli istnieje więcej niż jeden wiersz, dla którego osiągnięto minimum, do ustalenia można zastosować regułę upuszczania zmiennej wyboru .

Przykład

Rozważmy program liniowy

Zminimalizować

${\ Displaystyle Z = -2x-3y-4z\,}$

Z zastrzeżeniem

${\ Displaystyle {\ zacząć {wyrównane} 3 x + 2y + z i \ równoważnik 10 \ \ 2 x + 5 y + 3 z \ równoważnik 15 \ \ x \, y \, z i \ geq 0 \ koniec {wyrównany}}}$

Po dodaniu luźnych zmiennych s i t jest to reprezentowane przez tabelę kanoniczną

${\ Displaystyle {\ zacząć {bmatrix} 1 i 2 i 3 i 4 i 0 i 0 i 0 \\ 0 i 3 i 2 i 1 i 1 i 0 i 10 \\ 0 i 2 i 5 i 3 i 0 i 1 i 15 \ koniec {bmatrix}}}$

gdzie kolumny 5 i 6 reprezentują podstawowe zmienne s i t, a odpowiadające im podstawowe rozwiązanie dopuszczalne to

${\displaystyle x=y=z=0,\s=10\t=15.}$

Kolumny 2, 3 i 4 można wybrać jako kolumny przestawne, w tym przykładzie wybrano kolumnę 4. Wartości z wynikające z wyboru rzędów 2 i 3 jako rzędów przestawnych wynoszą odpowiednio 10/1 = 10 i 15/3 = 5. Spośród nich minimum to 5, więc rząd 3 musi być rzędem obrotowym. Wykonanie obrotu daje

${\ Displaystyle {\ zacznij {bmatrix} 3 i 2 i 11 i 0 i 0 i 4 i -60 \ \ 0 i 7 i 1 i 0 i 3 i 1 i 15 \ \ 0 i 2 i 5 i 3 i 0 i 1 i 15 \ koniec {bmatrix}}}$

Teraz kolumny 4 i 5 reprezentują podstawowe zmienne z i s, a odpowiadające im podstawowe dopuszczalne rozwiązanie to

${\displaystyle x=y=t=0,\z=5\s=5.}$

W następnym kroku nie ma pozytywnych wpisów w wierszu celów i w rzeczywistości

${\ Displaystyle Z = {\ Frac {-60 + 2 x + 11 y + 4 t} {3}} = -20 + {\ Frac {2 x + 11 y + 4 t} {3}}}$

więc minimalna wartość Z wynosi -20.

Znalezienie początkowej tabeli kanonicznej

Ogólnie rzecz biorąc, program liniowy nie zostanie podany w postaci kanonicznej i przed uruchomieniem algorytmu simpleks należy znaleźć równoważną tablicę kanoniczną. Można to osiągnąć poprzez wprowadzenie sztucznych zmiennych . Kolumny macierzy tożsamości są dodawane jako wektory kolumn dla tych zmiennych. Jeśli wartość b równania ograniczenia jest ujemna, równanie jest negowane przed dodaniem kolumn macierzy tożsamości. Nie zmienia to zbioru rozwiązań dopuszczalnych ani rozwiązania optymalnego i zapewnia, że ​​zmienne wolne będą stanowić wstępne rozwiązanie dopuszczalne. Nowe tableau jest w formie kanonicznej, ale nie jest tożsame z pierwotnym problemem. Wprowadza się więc nową funkcję celu, równą sumie zmiennych sztucznych, i stosuje się algorytm simpleks do znalezienia minimum; zmodyfikowany program liniowy nazywa się problemem fazy I.

Algorytm simpleks zastosowany do zagadnienia fazy I musi kończyć się wartością minimalną dla nowej funkcji celu, ponieważ będąc sumą zmiennych nieujemnych, jej wartość jest ograniczona poniżej przez 0. Jeżeli minimum wynosi 0, to zmienne sztuczne można wyeliminować z powstałe kanoniczne tableau tworzące kanoniczne tableau równoważne z pierwotnym problemem. W celu znalezienia rozwiązania można zastosować algorytm simpleks; ten etap nazywa się Fazą II . Jeśli minimum jest dodatnie, to nie ma wykonalnego rozwiązania problemu fazy I, w którym wszystkie sztuczne zmienne są równe zeru. Oznacza to, że dopuszczalny obszar pierwotnego problemu jest pusty, a zatem pierwotny problem nie ma rozwiązania.

Przykład

Rozważmy program liniowy

Zminimalizować

${\ Displaystyle Z = -2x-3y-4z\,}$

Z zastrzeżeniem

${\ Displaystyle {\ zacząć {wyrównane} 3x + 2y + z i = 10 \ \ 2x + 5y + 3z i = 15 \ \ x, \, y, \, z i \ geq 0 \ koniec {wyrównane}}}$

Jest to reprezentowane przez (niekanoniczne) tableau

${\ Displaystyle {\ zacząć {bmatrix} 1 i 2, 3 i 4 i 0 \ \ 0 i 3 i 2 i 1 i 10 \ \ 0 i 2 i 5 i 3 i 15 \ koniec {bmatrix}}}$

Wprowadź sztuczne zmienne u i v oraz funkcję celu W  =  u  +  v , dając nową tablicę

${\ Displaystyle {\ zacząć {bmatrix} 1 i 0 i 0 i 0 i 1 i 1 i 1 i 0 \\ 0 i 1 i 2 i 3 i 4 i 0 i 0 \\ 0 i 0 i 3 i 2 i 1 i 1 i 0 i 10 \\ 0 i 0 i 2 i 5 i 3 i 0 i 1 i 15 \ koniec {bmatrix}}}$

Równanie określające pierwotną funkcję celu jest zachowane w oczekiwaniu na fazę II.

Z konstrukcji u i v są zmiennymi podstawowymi, ponieważ są częścią początkowej macierzy tożsamości. Jednak funkcja celu W obecnie zakłada, że u i v są równe 0. Aby dostosować funkcję celu, aby była poprawną wartością, gdzie u  = 10 i v  = 15, dodaj trzeci i czwarty wiersz do pierwszego wiersza, dając

${\ Displaystyle {\ zacznij {bmatrix} 1 i 0, 5, 7, 4, 0, 0, 25, 0, 2, 3, 4, 0, 0, 0, 0, 3, 2, 1, 0, 10, 0, 0, 2, 5, 3, 0, 1 i 15, koniec {bmatrix}}}$

Wybierz kolumnę 5 jako kolumnę przestawną, więc wiersz przestawny musi być wierszem 4, a zaktualizowana tabela to

${\ Displaystyle {\ zacząć {bmatrix} 3 i 0 i 7 i 1 i 0 i 0 i 4 i 15 \\ 0 i 3 i 2 i 11 i 0 i 0 i 4 i 60 \\ 0 i 0 i 7 i 1 i 0 i 3 i 1 i 15 \\ 0 i 0 i 2 i 5 i 3 i 0 i 1 i 15 \ koniec {bmatrix}}}$

Teraz wybierz kolumnę 3 jako kolumnę przestawną, dla której wiersz 3 musi być wierszem przestawnym, aby uzyskać

${\ Displaystyle {\ zacząć {bmatrix} 7 i 0 i 0 i 0 i 7 i 7 i 7 i 0 \\ 0 i 7 i 0 i 25 i 0 i 2 i 10 i 130 \\ 0 i 0 i 7 i 1 i 0 i 3 i 1 i 15 \\ 0 i 0 i 0 i 11 i 7 i 2 i 3 i 25 \ koniec {bmatrix}}}$

Sztuczne zmienne mają teraz wartość 0 i mogą zostać usunięte, dając kanoniczną tablicę równoważną oryginalnemu problemowi:

${\ Displaystyle {\ zacząć {bmatrix} 7 i 0 i 25 i 0 i 130 \ \ 0 i 7 i 1 i 0 i 15 \ \ 0 i 0 i 11 i 7 i 25 \ koniec {bmatrix}}}$

Jest to na szczęście już optymalne, a optymalna wartość dla oryginalnego programu liniowego wynosi -130/7.

Zaawansowane tematy

Realizacja

Forma tableau użyta powyżej do opisania algorytmu nadaje się do natychmiastowej implementacji, w której tablica jest utrzymywana jako tablica prostokątna ( m  +1)-by-( m  +  n  +1). Łatwo jest uniknąć przechowywania m jawnych kolumn macierzy jednostkowej, które pojawią się w tablicy, ponieważ B jest podzbiorem kolumn [ A ,  I ]. Ta implementacja jest określana jako „ standardowy algorytm simpleks”. Obciążenie pamięcią i obliczeniami jest takie, że standardowa metoda simpleks jest nadmiernie kosztownym podejściem do rozwiązywania dużych problemów programowania liniowego.

W każdej iteracji simpleksowej jedyne wymagane dane to pierwszy wiersz tabeli, kolumna (przestawna) tabeli odpowiadająca zmiennej wejściowej oraz prawa strona. Ta ostatnia może być aktualizowana za pomocą kolumny głównej, a pierwszy wiersz tabeli może być aktualizowany za pomocą (głównego) wiersza odpowiadającego zmiennej opuszczającej. Zarówno kolumna osiowa, jak i wiersz osiowy mogą być obliczane bezpośrednio przy użyciu rozwiązań liniowych układów równań obejmujących macierz B i iloczyn macierzy-wektorów za pomocą A . Te obserwacje uzasadniają „ zrewidowany algorytm simpleks ”, dla którego implementacje wyróżniają się odwracalną reprezentacją  B .

W dużych problemach programowania liniowego A jest zwykle macierzą rzadką, a gdy wynikowa rzadkość B jest wykorzystywana przy zachowaniu jego odwracalnej reprezentacji, poprawiony algorytm simpleks jest znacznie bardziej wydajny niż standardowa metoda simpleks. Komercyjne solwery simpleksowe są oparte na poprawionym algorytmie simpleksowym.

Degeneracja: przeciąganie i jazda na rowerze

Jeśli wartości wszystkich podstawowych zmiennych są ściśle dodatnie, to zwrot musi skutkować poprawą wartości obiektywnej. Kiedy tak jest zawsze, żaden zestaw podstawowych zmiennych nie występuje dwa razy i algorytm simpleks musi zakończyć się po skończonej liczbie kroków. Podstawowe możliwe rozwiązania, w których co najmniej jedna z podstawowych zmiennych wynosi zero, nazywane są degenerowanymi i mogą skutkować powstaniem zwrotów, dla których nie ma poprawy wartości obiektywnej. W tym przypadku nie dochodzi do faktycznej zmiany rozwiązania, a jedynie do zmiany zestawu zmiennych podstawowych. Kiedy kilka takich zwrotów pojawia się kolejno, nie ma poprawy; w dużych zastosowaniach przemysłowych degeneracja jest powszechna i takie „ przeciąganie ” jest godne uwagi. Gorsze od przeciągania jest możliwość, że ten sam zestaw podstawowych zmiennych wystąpi dwukrotnie, w którym to przypadku deterministyczne reguły obrotu algorytmu simpleks wytworzą nieskończoną pętlę lub „cykl”. Podczas gdy degeneracja jest zasadą w praktyce i przeciąganie jest powszechne, jazda na rowerze jest rzadkością w praktyce. W Padberg ma miejsce dyskusja na temat przykładu praktycznej jazdy na rowerze . Reguła Blanda zapobiega cykliczności, a tym samym gwarantuje, że algorytm simpleks zawsze się kończy. Inny algorytm obrotowy, algorytm krzyżowy, nigdy nie działa w programach liniowych.

Zasady obrotu na podstawie historii, takie jak reguły Zadeh za i reguły Cunninghama także spróbować obejść problem zwłokę i rowerowej poprzez śledzenie poszczególnych zmiennych, jak często są używane, a następnie faworyzować takie zmienne, które zostały najrzadziej używanych.

Efektywność

Metoda simpleks jest niezwykle skuteczna w praktyce i stanowiła znaczne ulepszenie w stosunku do wcześniejszych metod, takich jak eliminacja Fouriera-Motzkina . Jednak w 1972 Klee i Minty podali przykład, sześcian Klee–Minty'ego , pokazując, że najgorszą złożonością metody simplex sformułowanej przez Dantziga jest czas wykładniczy . Od tego czasu dla prawie każdego wariantu metody wykazano, że istnieje rodzina programów liniowych, w przypadku których sprawdza się ona źle. Pytaniem otwartym jest, czy istnieje zmienność z czasem wielomianowym , chociaż znane są sub-wykładnicze reguły przestawne.

W 2014 roku udowodniono, że określony wariant metody simpleks jest NP-mighty , tzn. może być użyty do rozwiązania, z narzutem wielomianowym, dowolnego problemu w NP niejawnie podczas wykonywania algorytmu. Co więcej, decydowanie, czy dana zmienna kiedykolwiek wejdzie w bazę podczas wykonywania algorytmu na danym wejściu, oraz określenie liczby iteracji potrzebnych do rozwiązania danego problemu, są problemami NP-trudnymi . Mniej więcej w tym samym czasie wykazano, że istnieje sztuczna reguła przechyłu, dla której obliczanie jego wyjścia jest zgodne z PSPACE . W 2015 r. zostało to wzmocnione, aby pokazać, że obliczanie wyniku reguły przestawnej Dantziga jest zgodne z PSPACE .

Analiza i kwantyfikacja obserwacji, że algorytm simpleks jest skuteczny w praktyce pomimo swojej wykładniczej złożoności najgorszego przypadku, doprowadziła do opracowania innych miar złożoności. Algorytm simpleks charakteryzuje się wielomianową złożonością przypadków przeciętnych dla różnych rozkładów prawdopodobieństwa , przy czym dokładna wydajność algorytmu simpleks dla przypadków średnich zależy od wyboru rozkładu prawdopodobieństwa dla macierzy losowych . Inne podejście do badania „ typowych zjawisk ” wykorzystuje teorię kategorii Baire'a z ogólnej topologii i pokazuje, że (topologicznie) „większość” macierzy można rozwiązać algorytmem simpleks w wielomianowej liczbie kroków. Inna metoda analizy wydajności algorytmu simpleks polega na badaniu zachowania najgorszych scenariuszy przy niewielkich perturbacjach – czy najgorsze scenariusze są stabilne przy niewielkiej zmianie (w sensie stabilności strukturalnej ), czy też stają się wykonalne? Ten obszar badań, zwany analizą wygładzoną , został wprowadzony specjalnie do badania metody simplex. Rzeczywiście, czas działania metody simpleks na wejściu z szumem jest wielomianem liczby zmiennych i wielkości perturbacji.

Inne algorytmy

Inne algorytmy rozwiązywania problemów programowania liniowego są opisane w artykule o programowaniu liniowym . Innym algorytmem przestawnym wymiany bazy jest algorytm krzyżowy . Wielomian są algorytmy czasu do programowania liniowego, które wykorzystują metody punkt wnętrza: są to Khachiyan jest elipsoidalny algorytmu , Karmarkar jest algorytm rzutowe , oraz algorytmy odtwarzania trajektorii .

Programowanie liniowo-ułamkowe

Programowanie liniowo-ułamkowe (LFP) jest uogólnieniem programowania liniowego (LP). W LP funkcja celu jest funkcją liniową , natomiast funkcja celu programu liniowo-ułamkowego jest stosunkiem dwóch funkcji liniowych. Innymi słowy, program liniowy to program ułamkowo-liniowy, w którym mianownikiem jest stała funkcja mająca wszędzie wartość jeden. Program liniowo-ułamkowy można rozwiązać wariantem algorytmu simpleks lub algorytmem krzyżowym .

Zobacz też

Uwagi

Bibliografia

• Murty, Katta G. (1983). Programowanie liniowe . Nowy Jork: John Wiley & Sons, Inc. s. xix+482. Numer ISBN 978-0-471-09725-9. MR  0720547 .

Dalsza lektura

Te wstępy są napisane dla studentów informatyki i badań operacyjnych :

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN  0-262-03293-7 . Sekcja 29.3: Algorytm simpleks, s. 790-804.
• Frederick S. Hillier i Gerald J. Lieberman: Wprowadzenie do badań operacyjnych , wydanie ósme. McGraw-Hill. ISBN  0-07-123828-X
• Rardina, Ronalda L. (1997). Optymalizacja w badaniach operacyjnych . Sala Prezydencka. P. 919. ISBN 978-0-02-398415-0.

Zewnętrzne linki

• Wprowadzenie do programowania liniowego i algorytmu Simplex autorstwa Spyrosa Reveliotisa z Georgia Institute of Technology.
• Greenberg, Harvey J., Klee-Minty Polytope pokazuje wykładniczą złożoność czasową metody Simplex, University of Colorado w Denver (1997) PDF do pobrania
• Simplex Method Samouczek metody Simplex z przykładami (również dwufazowa i metoda M).
• Mathstools Simplex Kalkulator z www.mathstools.com
• Przykład procedury simpleksowej dla standardowego problemu programowania liniowego autorstwa Thomasa McFarlanda z University of Wisconsin-Whitewater.
• PHPSimplex: narzędzie online do rozwiązywania problemów programowania liniowego autorstwa Daniela Izquierdo i Juana José Ruiza z Uniwersytetu w Maladze (UMA, Hiszpania)
• simplex-m Online Simplex Solver