Параллельные реализации симплекс-метода для безошибочного решения задач линейного программирования

В работе рассмотрены подходы к решению задачи линейного программирования с абсолютной точностью, достигаемой применением в алгоритмах симплекс-метода дробно-рациональных вычислений без округления. Если при этом $m$ - минимальная из размерностей задачи, $l$ - число бит, необходимых под один численный элемент исходных данных, то пространственная сложность алгоритма не превосходит $4lm^4+o(m^3)$, при этом вычислительная сложность одной итерации симплекс-метода не превосходит $O(lm^4)$, а эффективность распараллеливания (т.е. отношение ускорения к числу процессоров) в предложенной реализации параллельного алгоритма составляет в асимптотике 100

Ключевые слова

линейое ограммирование, симплекс-метод, распределенные вычисления, параллельные вычисления, символические вычисления, оптимизация, интервальная арифметика.

Литература

1. Гаранжа, В.А. Параллельная реализация метода Ньютона для решения больших задач линейного программирования / В.А. Гаранжа, А.И. Голиков, Ю.Г. Евтушенко // Журн. вычисл. мат. и мат. физики. - 2009. - Т. 49, № 8. - C. 1369 - 1384.
2. Hall, Ju. Towards a practical parallelization of the simplex method / Ju. Hall // J. Computational Management Science. - 2010. - V. 7, № 2. - P. 139 - 170.
3. Panyukov, A.V. Exact and Guaranteed Accuracy Solutions of Linear Programming Problems by Distributed Computer Systems with MPI / A. V. Panyukov, V. V. Gorbik // Tambov University REPORTS: A Theoretical and Applied Scientific Journal. Series: Natural and Technical Sciences. - 2010. - V. 15, Issue 4. - P. 1392 - 1404. http://vestnik.tsutmb.ru/old/index.php?module=subjects&func=viewpage&pageid=165
4. Панюков, А.В. Библиотека классов 'Exact Computational', / А.В. Панюков, М.И. Германенко, В.В. Горбик // Программы для ЭВМ, базы данных, топологии интегральных микросхем: официальный бюллетень Рос. агентства по патентам и товарным знакам № 3. - 2009. - С. 251.
5. Панюков, А.В. Параллельные алгоритмы решения систем линейных алгебраических уравнений с применением вычислений без округления / А.В. Панюков, М.И. Германенко, В.В. Горбик // Параллельные вычислительные технологии (ПАВТ-2007): тр. междунар. науч. конф. (Челябинск, 29 января - 2 февраля 2007 г.). - Челябинск: Изд-во ЮУрГУ, 2007. - Т. 2. - С. 238 - 249.
6. Панюков, А.В. Приложение для безошибочного нахождения обобщенной обратной матрицы методом Мура-Пенроуза и безошибочное решение систем линейных алгебраических уравнений / А.В. Панюков, М.И. Германенко // Информационные технологии моделирования и управления. - 2009. - № 1 (53). - С. 78 - 87.
7. Васильев, Ф.П. Линейное программирование / Ф.П. Васильев, А.Ю. Иваницкий - М.: Изд-во Факториал Пресс. - 2003. - 352 с.