Симплексный алгоритм часто трактуется либо в реальной арифметике, либо в дискретном мире с точными вычислениями. Однако, это, кажется, чаще всего реализуется с помощью арифметики с плавающей точкой.
Это приводит к вопросу, следует ли рассматривать симплексный алгоритм как числовой алгоритм, в частности, как ошибки округления влияют на вычисления. Меня не интересуют практические реализации, а скорее теоретические основы.
Вам известно о каких-либо исследованиях по этому вопросу?
Ответы:
Да, есть исследования по этому вопросу.
Симплексный метод не всегда хорошо себя ведет , Влодзимеж Огричак
retroLP, реализация стандартного симплекс-метода , Гавриил Ярмиш и Ричард Ван Слайк
Численно устойчивая форма симплекс-алгоритма , Филип Э. Джилл и Уолтер Мюррей
Вас также может заинтересовать пересмотренный симплекс-метод . Этот метод может использовать преимущества разреженности матриц; он не хранит представление всей матрицы. Этот тезис представлял для меня большой интерес: сравнение алгоритмов симплекс-метода .
источник