Preview

Моделирование и анализ информационных систем

Расширенный поиск

Простой алгоритм отыскания неотрицательного базисного решения системы линейных алгебраических уравнений

https://doi.org/10.18255/1818-1015-2021-3-234-237

Полный текст:

Аннотация

В данной статье описывается алгоритм получения неотрицательного базисного решения системы линейных алгебраических уравнений. Эта задача, в частности, является наиболее трудоемким этапом знаменитого симплекс-метода решения задач линейного программирования, хотя бесспорно представляет и самостоятельный интерес. В отличии от метода искусственного базиса Ордена, применяемого в классическом симплекс-методе, предлагаемый алгоритм не использует искусственных переменных и экономно расходует вычислительные ресурсы.

Алгоритм состоит из двух этапов, основу каждого из которых составляют Гауссовы исключения. Первый этап совпадает с основной частью метода полных исключений Гаусса, в котором матрица системы приводится к виду с единичной подматрицей. Второй этап представляет из себя итерационный цикл, на каждой из итераций которого по некоторым правилам выбирается разрешающий элемент, а затем выполняется шаг исключения Гаусса, сохраняющий структуру матрицы, полученную на первом этапе. Цикл завершается, либо когда будет установлено отсутствие неотрицательных решений, либо когда будет найдено одно из них.

Приводятся два правила выбора разрешающего элемента. Более примитивное из них допускает неоднозначность выбора и не исключает зацикливания (но в очень редких случаях). Использование второго правила гарантирует отсутствие зацикливания.

Об авторе

Глеб Дмитриевич Степанов
Воронежский государственный педагогический университет
Россия

Кандидат физико-математических наук, доцент.

Ул. Ленина, д. 86, Воронеж, 394043



Список литературы

1. S. I. Gass, Linear Programming: Methods and Applications. McGraw-Hill: New York, 1958.

2. D. B. Yudin and E. G. Holstein, Linear Programming. Moscow: Nauka, 1963.

3. G. Dantzig, “Linear programming, its applications and generalizations”, Princeton University Press, 1963.

4. T. Hu, Integer programming and network flows. Addison-Wesley, 1969.

5. S. Ashmanov, Linear programming. Moscow: Nauka, 1981.

6. C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Prentice-Hall, 1982.

7. A. Schrijver, Theory of linear and integer programming. Moscow: Mir, 1991.

8. F. P. Vasiliev and A. Y. Ivanitsky, Linear Programming. MCCME, 2020.

9. V. Klee and G. J. Minty, “How good is the simplex algorithm?”, Inequalities, vol. 3, no. 3, pp. 159–175, 1972.


Рецензия

Для цитирования:


Степанов Г.Д. Простой алгоритм отыскания неотрицательного базисного решения системы линейных алгебраических уравнений. Моделирование и анализ информационных систем. 2021;28(3):234-237. https://doi.org/10.18255/1818-1015-2021-3-234-237

For citation:


Stepanov G.D. A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations. Modeling and Analysis of Information Systems. 2021;28(3):234-237. (In Russ.) https://doi.org/10.18255/1818-1015-2021-3-234-237

Просмотров: 273


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)