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