Math
Simpleks na płaszczyźnie
Obszar dopuszczalny leży na stole, a nad nim wisi płyta na wysokości celu. Cel jest liniowy, więc płyta jest płaska i pochylona, a najlepszy punkt to dosłownie jej najwyższy róg.
Co się dzieje
Dwie zmienne i kilka ograniczeń: każde to ściana na stole, a to, co zostaje w środku, jest obszarem dopuszczalnym. Nad nim wisi płyta, której wysokość w każdym punkcie równa się celowi p·x + q·y. Ponieważ cel jest liniowy, płyta jest płaską pochyłą płaszczyzną - nie ma wzgórza pośrodku - i najlepszy punkt to jej najwyższy róg. Stąd wszystko: odpowiedź zawsze leży w wierzchołku, a 60 000 prób we wnętrzu obszaru nigdy go nie pobiło. Simpleks wchodzi po tych schodach: od początku układu do sąsiedniego rogu, który stoi wyżej, krok po kroku, i staje tam, gdzie żaden sąsiad nie jest wyższy. Jego odpowiedź porównano z przeglądem wszystkich wierzchołków, który o tabeli nie wie nic. Odsuń ścianę o jeden, a optimum urośnie dokładnie o jej cenę dualną - chyba że w górnym rogu spotykają się trzy ściany, i wtedy jednego tempa wzrostu nie ma.
Równania modułu
Równania zmaksymalizuj p·x + q·y przy ograniczeniach a·x + b·y ≤ c dla każdego wiersza oraz x ≥ 0, y ≥ 0 obszar dopuszczalny jest przecięciem półpłaszczyzn; funkcja celu jest liniowa, więc jej wykres nad obszarem jest płaską, pochyloną płaszczyzną dlatego maksimum leży w WIERZCHOŁKU - punkcie, w którym przecinają się dwie z prostych (osie też się liczą) i nadal spełnione są wszystkie ograniczenia simpleks: zacznij w początku układu (każde c ≥ 0, więc jest dopuszczalny), idź do sąsiedniego wierzchołka, który zwiększa funkcję celu, zatrzymaj się, gdy żaden tego nie robi reguła Blanda - wchodzi zmienna o najmniejszym dopuszczalnym indeksie, wychodzi ta o najmniejszym indeksie bazowym wśród równych ilorazów - uniemożliwia zapętlenie cena cieniowa wiersza jest zmienną dualną: przesuń jego c o h, a optimum wzrośnie o h·y, chyba że górny wierzchołek jest ZDEGENEROWANY wierzchołek zdegenerowany: więcej niż dwie proste przechodzą przez ten sam punkt - pochodna tam nie istnieje, więc cena cieniowa nie jest określona
