Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer
The article considers a method for solving a linear programming problem (LPP), which requires finding the minimum or maximum of a linear functional on a set of non-negative solutions of a system of linear algebraic equations with the same unknowns. The method is obtained by improving the classical s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2021-12-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1569 |
| _version_ | 1797877790505172992 |
|---|---|
| author | Gleb D. Stepanov |
| author_facet | Gleb D. Stepanov |
| author_sort | Gleb D. Stepanov |
| collection | DOAJ |
| description | The article considers a method for solving a linear programming problem (LPP), which requires finding the minimum or maximum of a linear functional on a set of non-negative solutions of a system of linear algebraic equations with the same unknowns. The method is obtained by improving the classical simplex method, which when involving geometric considerations, in fact, generalizes the Gauss complete exclusion method for solving systems of equations. The proposed method, as well as the method of complete exceptions, proceeds from purely algebraic considerations. It consists of converting the entire LPP, including the objective function, into an equivalent problem with an obvious answer. For the convenience of converting the target functional, the equations are written as linear functionals on the left side and zeros on the right one. From the coefficients of the mentioned functionals, a matrix is formed, which is called the LPP matrix. The zero row of the matrix is the coefficients of the target functional, $a_{00}$ is its free member. The algorithms are described and justified in terms of the transformation of this matrix. In calculations the matrix is a calculation table. The method under consideration by analogy with the simplex method consists of three stages. At the first stage the LPP matrix is reduced to a special 1-canonical form. With such matrices one of the basic solutions of the system is obvious, and the target functional on it is $ a_{00}$, which is very convenient. At the second stage the resulting matrix is transformed into a similar matrix with non-positive elements of the zero column (except $a_{00}$), which entails the non-negativity of the basic solution. At the third stage the matrix is transformed into a matrix that provides non-negativity and optimality of the basic solution. For the second stage the analog of which in the simplex method uses an artificial basis and is the most time-consuming, two variants without artificial variables are given. When describing the first of them, along the way, a very easy-to-understand and remember analogue of the famous Farkas lemma is obtained. The other option is quite simple to use, but its full justification is difficult and will be separately published. |
| first_indexed | 2024-04-10T02:23:55Z |
| format | Article |
| id | doaj.art-33d25d0670ea4e72a599fcaced14dd5a |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:23:55Z |
| publishDate | 2021-12-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-33d25d0670ea4e72a599fcaced14dd5a2023-03-13T08:07:35ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172021-12-0128443445110.18255/1818-1015-2021-4-434-4511200Solving Linear Programming Problems by Reducing to the Form with an Obvious AnswerGleb D. Stepanov0Воронежский государственный педагогический университетThe article considers a method for solving a linear programming problem (LPP), which requires finding the minimum or maximum of a linear functional on a set of non-negative solutions of a system of linear algebraic equations with the same unknowns. The method is obtained by improving the classical simplex method, which when involving geometric considerations, in fact, generalizes the Gauss complete exclusion method for solving systems of equations. The proposed method, as well as the method of complete exceptions, proceeds from purely algebraic considerations. It consists of converting the entire LPP, including the objective function, into an equivalent problem with an obvious answer. For the convenience of converting the target functional, the equations are written as linear functionals on the left side and zeros on the right one. From the coefficients of the mentioned functionals, a matrix is formed, which is called the LPP matrix. The zero row of the matrix is the coefficients of the target functional, $a_{00}$ is its free member. The algorithms are described and justified in terms of the transformation of this matrix. In calculations the matrix is a calculation table. The method under consideration by analogy with the simplex method consists of three stages. At the first stage the LPP matrix is reduced to a special 1-canonical form. With such matrices one of the basic solutions of the system is obvious, and the target functional on it is $ a_{00}$, which is very convenient. At the second stage the resulting matrix is transformed into a similar matrix with non-positive elements of the zero column (except $a_{00}$), which entails the non-negativity of the basic solution. At the third stage the matrix is transformed into a matrix that provides non-negativity and optimality of the basic solution. For the second stage the analog of which in the simplex method uses an artificial basis and is the most time-consuming, two variants without artificial variables are given. When describing the first of them, along the way, a very easy-to-understand and remember analogue of the famous Farkas lemma is obtained. The other option is quite simple to use, but its full justification is difficult and will be separately published.https://www.mais-journal.ru/jour/article/view/1569линейное программированиеметод гауссасимплекс-методматрица злпразрешающий элементправило выборалемма фаркашасистемы линейных уравненийнеотрицательное решение |
| spellingShingle | Gleb D. Stepanov Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer Моделирование и анализ информационных систем линейное программирование метод гаусса симплекс-метод матрица злп разрешающий элемент правило выбора лемма фаркаша системы линейных уравнений неотрицательное решение |
| title | Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer |
| title_full | Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer |
| title_fullStr | Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer |
| title_full_unstemmed | Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer |
| title_short | Solving Linear Programming Problems by Reducing to the Form with an Obvious Answer |
| title_sort | solving linear programming problems by reducing to the form with an obvious answer |
| topic | линейное программирование метод гаусса симплекс-метод матрица злп разрешающий элемент правило выбора лемма фаркаша системы линейных уравнений неотрицательное решение |
| url | https://www.mais-journal.ru/jour/article/view/1569 |
| work_keys_str_mv | AT glebdstepanov solvinglinearprogrammingproblemsbyreducingtotheformwithanobviousanswer |