Кандидат физико-математических наук, доцент.
Ул. Ленина, д. 86, Воронеж, 394043
PhD, associate professor.
86 Lenin str, Voronezh 394043
В данной статье описывается алгоритм получения неотрицательного базисного решения системы линейных алгебраических уравнений. Эта задача, в частности, является наиболее трудоемким этапом знаменитого симплекс-метода решения задач линейного программирования, хотя бесспорно представляет и самостоятельный интерес. В отличии от метода искусственного базиса Ордена, применяемого в классическом симплекс-методе, предлагаемый алгоритм не использует искусственных переменных и экономно расходует вычислительные ресурсы.
Алгоритм состоит из двух этапов, основу каждого из которых составляют Гауссовы исключения. Первый этап совпадает с основной частью метода полных исключений Гаусса, в котором матрица системы приводится к виду с единичной подматрицей. Второй этап представляет из себя итерационный цикл, на каждой из итераций которого по некоторым правилам выбирается разрешающий элемент, а затем выполняется шаг исключения Гаусса, сохраняющий структуру матрицы, полученную на первом этапе. Цикл завершается, либо когда будет установлено отсутствие неотрицательных решений, либо когда будет найдено одно из них.
Приводятся два правила выбора разрешающего элемента. Более примитивное из них допускает неоднозначность выбора и не исключает зацикливания (но в очень редких случаях). Использование второго правила гарантирует отсутствие зацикливания.
This article describes an algorithm for obtaining a non-negative basic solution of a system of linear algebraic equations. This problem, which undoubtedly has an independent interest, in particular, is the most time-consuming part of the famous simplex method for solving linear programming problems.
Unlike the artificial basis Orden’s method used in the classical simplex method, the proposed algorithm does not attract artificial variables and economically consumes computational resources.
The algorithm consists of two stages, each of which is based on Gaussian exceptions. The first stage coincides with the main part of the Gaussian complete exclusion method, in which the matrix of the system is reduced to the form with an identity submatrix. The second stage is an iterative cycle, at each of the iterations of which, according to some rules, a resolving element is selected, and then a Gaussian elimination step is performed, preserving the matrix structure obtained at the first stage. The cycle ends either when the absence of non-negative solutions is established, or when one of them is found.
Two rules for choosing a resolving element are given. The more primitive of them allows for ambiguity of choice and does not exclude looping (but in very rare cases). Use of the second rule ensures that there is no looping.
The authors declare that there are no conflicts of interest present.