A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations
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....
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2021-10-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1524 |
| _version_ | 1797877800863006720 |
|---|---|
| author | Gleb D. Stepanov |
| author_facet | Gleb D. Stepanov |
| author_sort | Gleb D. Stepanov |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T02:24:02Z |
| format | Article |
| id | doaj.art-5735c1316fe44c0a98f5a9ef644e920b |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:24:02Z |
| publishDate | 2021-10-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-5735c1316fe44c0a98f5a9ef644e920b2023-03-13T08:07:35ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172021-10-0128323423710.18255/1818-1015-2021-3-234-2371159A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic EquationsGleb D. Stepanov0Воронежский государственный педагогический университет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.https://www.mais-journal.ru/jour/article/view/1524система линейных алгебраических уравненийнеотрицательное решениелинейное программированиеправило выбора разрешающего элемента |
| spellingShingle | Gleb D. Stepanov A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations Моделирование и анализ информационных систем система линейных алгебраических уравнений неотрицательное решение линейное программирование правило выбора разрешающего элемента |
| title | A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations |
| title_full | A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations |
| title_fullStr | A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations |
| title_full_unstemmed | A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations |
| title_short | A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations |
| title_sort | simple algorithm for finding a non negative basic solution of a system of linear algebraic equations |
| topic | система линейных алгебраических уравнений неотрицательное решение линейное программирование правило выбора разрешающего элемента |
| url | https://www.mais-journal.ru/jour/article/view/1524 |
| work_keys_str_mv | AT glebdstepanov asimplealgorithmforfindinganonnegativebasicsolutionofasystemoflinearalgebraicequations AT glebdstepanov simplealgorithmforfindinganonnegativebasicsolutionofasystemoflinearalgebraicequations |