Новый приближенный алгоритм для решения задачи положительного линейного программирования

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