Podręcznik

4. Algorytm lepszy niż Simplex?

Prawie, że od początku powstania algorytmu Simplex starano się wymyślać algorytmy lepsze, najczęściej rozumiejąc pod tym pojęciem szybsze. Uzasadnienie przeświadczenia, że można skonstruować algorytm szybszy jest oczywiste.

Algorytm Simplex „odwiedzając” kolejne wierzchołki idzie do celu długą drogą, co mu zajmuje wiele czasu. Najprostszy pomysł – to skrócenie drogi. Trzeba zarzucić przeglądanie wierzchołków i z dopuszczalnego punktu startowego poruszając się wewnątrz zbioru dopuszczalnego dotrzeć szybko do wierzchołka optymalnego jak na Rys. 2.5.

Poruszanie się wewnątrz zbioru dopuszczalnego dało nazwę algorytmom tej grupy – metody punktu wewnętrznego (interior point methods). Pierwszym efektywnym algorytmem tego typu był przedstawiony w 1984 r. przez N. Karmarkara algorytm, który teraz powszechnie nazywa się jego imieniem. Od tego czasu opublikowano wiele różnych algorytmów szukających rozwiązania zdania programowania liniowego wewnątrz zbioru dopuszczalnego. Najnowsze implementacje pozwalają rozwiązywać zadania prawie tak samo duże jak komercyjne pakiety oparte na metodzie Simplex, ale wciąż te metody cieszą się większym zaufaniem u naukowców niż menedżerów muszących rozwiązywać ogromne zadania optymalizacji. Wprowadzenie do problematyki związanej z metodami punktu wewnętrznego zainteresowany Czytelnik znajdzie we wspomnianym podręczniku A. Stachurskiego, podrozdział 4.8.