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?
ds.algorithms
reference-request
optimization
linear-programming
na.numerical-analysis
shuhalo
źródło
źródło
Odpowiedzi:
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 .
źródło