Modelirovanie i Analiz Informatsionnykh Sistem
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Modelirovanie i Analiz Informatsionnykh Sistem, 2021, Volume 28, Number 4, Pages 434–451
DOI: https://doi.org/10.18255/1818-1015-2021-4-434-451
(Mi mais761)
 

Algorithms

Solving linear programming problems by reducing to the form with an obvious answer

G. D. Stepanov

Voronezh State Pedagogical University, 86 Lenin str, Voronezh 394043, Russia
References:
Abstract: 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.
Keywords: linear programming, Gauss method, simplex method, LPP matrix, resolving element, choice rule, Farkas lemma, systems of linear equations, non-negative solution.
Received: 11.07.2021
Revised: 01.12.2021
Accepted: 08.12.2021
Document Type: Article
UDC: 519.852
MSC: 90C05
Language: Russian
Citation: G. D. Stepanov, “Solving linear programming problems by reducing to the form with an obvious answer”, Model. Anal. Inform. Sist., 28:4 (2021), 434–451
Citation in format AMSBIB
\Bibitem{Ste21}
\by G.~D.~Stepanov
\paper Solving linear programming problems by reducing to the form with an obvious answer
\jour Model. Anal. Inform. Sist.
\yr 2021
\vol 28
\issue 4
\pages 434--451
\mathnet{http://mi.mathnet.ru/mais761}
\crossref{https://doi.org/10.18255/1818-1015-2021-4-434-451}
Linking options:
  • https://www.mathnet.ru/eng/mais761
  • https://www.mathnet.ru/eng/mais/v28/i4/p434
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
    Statistics & downloads:
    Abstract page:163
    Full-text PDF :60
    References:36
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024