Параллельные реализации симплекс-метода для безошибочного решения задач линейного программирования
Автор: Панюков Анатолий Васильевич, Горбик Василий Владимирович
Рубрика: Программирование
Статья в выпуске: 25 (242), 2011 года.
Бесплатный доступ
В работе рассмотрены подходы к решению задачи линейного программирования с абсолютной точностью, достигаемой применением в алгоритмах симплекс-метода дробно-рациональных вычислений без округления. Если при этом m - минимальная из размерностей задачи, 1 - число бит, необходимых под один численный элемент исходных данных, то пространственная сложность алгоритма не превосходит 41m4 + o(m3), при этом вычислительная сложность одной итерации симплекс-метода не превосходит O(lm4), а эффективность распараллеливания (т.е. отношение ускорения к числу процессоров) в предложенной реализации параллельного алгоритма составляет в асимптотике 100%.
Линейое ограммирование, симплекс-метод, распределенные вычисления, параллельные вычисления, символические вычисления, оптимизация, интервальная арифметика
Короткий адрес: https://sciup.org/147159094
IDR: 147159094
Список литературы Параллельные реализации симплекс-метода для безошибочного решения задач линейного программирования
- Гаранжа, В.А. Параллельная реализация метода Ньютона для решения больших задач линейного программирования/В.А. Гаранжа, А.И. Голиков, Ю.Г. Евтушенко//Журн. вычисл. мат. и мат. физики. -2009. -Т. 49, № 8. -C. 1369 -1384.
- Hall, Ju. Towards a practical parallelization of the simplex method/Ju. Hall//J. Computational Management Science. -2010. -V. 7, № 2. -P. 139 -170.
- 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>
- Панюков, А.В. Библиотека классов «Exact Computational»/А.В. Панюков, М.И. Германенко, В.В. Горбик//Программы для ЭВМ, базы данных, топологии интегральных микросхем: официальный бюллетень Рос. агентства по патентам и товарным знакам № 3. -2009. -С. 251.
- Панюков, А.В. Параллельные алгоритмы решения систем линейных алгебраических уравнений с применением вычислений без округления/А.В. Панюков, М.И. Германенко, В.В. Горбик//Параллельные вычислительные технологии (ПАВТ-2007): тр. междунар. науч. конф. (Челябинск, 29 января -2 февраля 2007 г.). -Челябинск: Изд-во ЮУрГУ, 2007. -Т. 2. -С. 238 -249.
- Панюков, А.В. Приложение для безошибочного нахождения обобщенной обратной матрицы методом Мура-Пенроуза и безошибочное решение систем линейных алгебраических уравнений/А.В. Панюков, М.И. Германенко//Информационные технологии моделирования и управления. -2009. -№ 1 (53). -С. 78 -87.
- Васильев, Ф.П. Линейное программирование/Ф.П. Васильев, А.Ю. Иваницкий -М.: Изд-во Факториал Пресс. -2003. -352 с.
