Том 8, серия 2, номер 2, 2001 г., Стр. 52-72

УДК 519.852
С. А. Фомин
Новый приближённый алгоритм для решения задачи положительного   линейного программирования

Аннотация:
Предлагается новый алгоритм нахождения $\varepsilon$-оптимального решения задачи положительного линейного программирования: найти $\max\{cx|Ax\leqslant b,x\geqslant 0\}$; где все исходные данные неотрицательны. Алгоритм не уступает лучшим из известных алгоритмов для этой задачи по верхним оценкам времени выполнения, в частности для него доказана верхняя оценка вычислительной сложности $O(\frac{mn}{\varepsilon^2}\log^2\frac{mn}{\varepsilon^2})$, и имеет простые последовательные и параллельные реализации. Проведенные вычислительные эксперименты показывают преимущество нового алгоритма над алгоритмами, разработанными в последние годы [3, 4].
Табл. 9, библиогр. 10.

Фомин С. А. ¹
1. Институт системного программирования,
ул. Б. Коммунистическая, 25, 109004 Москва, Россия
е-mail: fomin@ispras.ru

Статья поступила 13 января 2000 г.