Prikladnaya Diskretnaya Matematika
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



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Prikl. Diskr. Mat., 2018, Number 41, Pages 110–125 (Mi pdm634)  

Computational Methods in Discrete Mathematics

Method for sequential activation of limitations in linear programming

V. S. Kolosov

Moscow, Russia

Abstract: In this paper, we present an algorithm for solving a problem in linear programming by means of procedure of sequential activation of limitations (inclusions in calculation are made one after another) with retention of the optimality status in the generated sequence of nested polyhedrons. Due to compression of the admissible solutions area, the objective function decreases on each step at the “max” criterion of an optimality (the movement to a maximum “from above”) contrary to its growth in other methods (“from below”). Geometrically, the motion to the maximum starts from the trivially determined starting point and continues along the broken line outside of the polytope of admissible solutions. In the theoretical justification of the algorithm, the signs for the incompatibility of the system of conditions in the problem, for the uniqueness and nonuniqueness of the solution, and for its unboundedness are formulated and proved. Computer experiments demonstrate the advantages of the program implementation of this algorithm in speed and completeness of the output information over the simplex-method option of the MATLAB's library linprog program.

Keywords: linear programming, activation of limitation, MATLAB, computer experiment.

DOI: https://doi.org/10.17223/20710410/41/11

Full text: PDF file (727 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.852

Citation: V. S. Kolosov, “Method for sequential activation of limitations in linear programming”, Prikl. Diskr. Mat., 2018, no. 41, 110–125

Citation in format AMSBIB
\Bibitem{Kol18}
\by V.~S.~Kolosov
\paper Method for sequential activation of limitations in~linear programming
\jour Prikl. Diskr. Mat.
\yr 2018
\issue 41
\pages 110--125
\mathnet{http://mi.mathnet.ru/pdm634}
\crossref{https://doi.org/10.17223/20710410/41/11}
\elib{https://elibrary.ru/item.asp?id=35688734}


Linking options:
  • http://mi.mathnet.ru/eng/pdm634
  • http://mi.mathnet.ru/eng/pdm/y2018/i3/p110

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:134
    Full text:99
    References:6

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021