RUS  ENG
Полная версия
ЖУРНАЛЫ // Челябинский физико-математический журнал // Архив

Челяб. физ.-матем. журн., 2016, том 1, выпуск 2, страницы 68–77 (Mi chfmj20)

Математика

Алгоритм нахождения неотрицательного решения системы линейных уравнений

Е. Н. Севостьяновa, М. Г. Лепчинскийb

a ЗАО "Диджитал Айрон Пайп", Челябинск, Россия
b Челябинский государственный университет, Челябинск, Россия

Аннотация: В статье рассматривается новый алгоритм для отыскания точного решения задачи линейного программирования. Метод основан на сведении задачи линейного программирования к задаче решения системы линейных уравнений неполного ранга в неотрицательных числах, которая решается через последовательные приближения в специально построенных подпространствах. Доказана сходимость метода за конечное число шагов. Приводятся результаты тестирования алгоритма на данных задачи Кли–Минти и на группе случайных тестов.

Ключевые слова: алгоритм линейного программирования, неотрицательное решение системы линейных уравнений, линейное неравенство.

УДК: 519.85

Поступила в редакцию: 08.04.2016
Исправленный вариант: 21.05.2016



Реферативные базы данных:


© МИАН, 2024