Stabilność numeryczna metody Simplex

Algorytm simpleksowy jest często traktowany albo w ramach rzeczywistej arytmetyki, albo w świecie dyskretnym z dokładnymi obliczeniami. Wydaje się jednak, że jest najczęściej wdrażany za pomocą arytmetyki zmiennoprzecinkowej.

Prowadzi to do pytania, czy algorytm simpleks należy traktować jako algorytm numeryczny, w szczególności w jaki sposób błędy zaokrąglenia wpływają na obliczenia. Nie interesują mnie praktyczne wdrożenia, ale podstawy teoretyczne.

Czy znasz jakieś badania na ten temat?

— shuhalo
źródło

Jeśli jesteś zainteresowany implementacją algorytmu simplex, sugerowałbym, aby zadać pytanie w serwisie or-exchange.com

— Snowie

@Sowie: To pytanie dotyczy mniej praktycznego wdrożenia, ale raczej aspektów teoretycznych. Przeprowadzono prace nad teoretycznymi podstawami analizy numerycznej i zastanawiam się, czy wpłynęło to na teorię algorytmu simpleks. W każdym razie dzięki jeszcze za link.

— shuhalo

Zredagowałem to pytanie, aby moje zainteresowanie było wyraźniejsze.

— shuhalo

Czy spojrzałeś na płynną analizę ? Ta praca dotyczy nie tylko średniego czasu trwania przypadku, ale także stabilności tego przypadku.

— Peter Shor,

Tak, są badania nad tym zagadnieniem.

Metoda simpleksowa nie zawsze jest dobrze zachowana , Włodzimierz Ogryczak

retroLP, Implementacja standardowej metody Simplex , Gavriel Yarmish i Richard Van Slyke

Numerycznie stabilna forma algorytmu simpleksowego , Philip E. Gill i Walter Murray

Być może zainteresuje Cię również zmieniona metoda simpleks . Ta metoda może wykorzystywać rzadkość macierzy; nie zachowuje reprezentacji całej macierzy. Ta teza była dla mnie bardzo interesująca: Porównanie algorytmów metody Simplex .

— jnm2
źródło