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

Для одновременного решения прямой и двойственной задач линейного программирования (ЛП) предлагается использовать новую вспомогательную функцию, близкую к модифицированной функции Лагранжа, и применить обобщенный метод Ньютона для безусловной максимизации этой функции. Предлагаемый подход применим для решения задач ЛП с большим числом (несколько миллионов) неотрицательных переменных и средним числом (несколько тысяч) ограничений типа равенств. Приводятся результаты тестовых расчетов на компьютере P-IV, которые показали, что задачи указанных размерностей решаются за время от нескольких десятков до нескольких тысяч секунд. Библ. 15. Табл. 1.