The method of design and increments in solving linear programming problems

Currently, the issue of choosing the optimal solution is one of the most important and urgent in industry, economy, agriculture, and the military sector. Methods and approaches of linear programming theory are used to solve many applied optimization tasks. The simplex method, which is the principal method of linear programming, is characterized by a large amount of computational actions and procedures. Owing to this, modifications of the main method with higher algorithmic efficiency are employed to address this problem. In this article, a new method for solving linear programming problems has been developed. The algorithmic complexity, which is less than that of the simplex method, is provided by considering a class of problems with completely limited areas of acceptable solutions. The new method is justified by the results announced in the proven statements. The implementation of the method is described by two algorithms: 1) search for a quasi-optimal solution by analyzing the coordinates of projections on hyper planes (design algorithm); 2) search for an optimal solution by setting increments to constraints (increment algorithm). To explain the functioning of the algorithms, specific numerical examples are analyzed. Algorithmic complexity estimates of the developed method are carried out by counting the number of arithmetic operations undertaken. Formula expressions for estimating the complexity of calculations are obtained.

1. Zhevnerov V.A. Modification of the simplex method based on the evolution principle. Problemy upravleniya = Control Sciences. 2004;1:28–31. (In Russ.).

2. Bazilevskij M.P. Selection of Informative Regressors Taking into Account Multicollinearity Between Them in Regression Models as a Problem of Partial-Boolean Linear Programming. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modeling, optimization and information technology. 2018;2(22):104–118. (In Russ.).

3. Bazilevskij M.P. Reduction of the problem of selecting informative regressors in estimating a linear regression model by the least squares method to a problem of partially Boolean linear programming. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modeling, optimization and information technology. 2018;1(20):108–117. (In Russ.).

4. Sumin V.I., Kuznecova L.D., Lukin M.A. Determination of the coefficients of the mathematical model of education quality control by the method of linear programming. Modeling, optimization and information technology. 2018;3(22):214–222. (In Russ.).

5. Shapovalov A.V., Preobrazhenskij A.P., Choporov O.N. Possibilities of using optimization methods in project portfolio management. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modeling, optimization and information technology. 2020;8(1). (In Russ.).

6. Zhilina A.A., Kostrova V.N., Preobrazhenskij Ju.P. Development of a methodology for setting the problem of choosing a management decision based on an optimization approach. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modeling, optimization and information technology. 2018;6(1):243–253. (In Russ.).

7. Ganicheva A.V., Ganichev A.V. Mathematical programming. SPb.: Lan'; 2020. 88 p. (In Russ.).

8. Hasanov A.S. On the Features of Algorithms for Solving Linear Programming Problems with Unlimited Domains of Admissible Solutions. Bulletin of Moscow Region State University. Series: Physics and Mathematics. 2017;1:113–123. (In Russ.).

9. Ganicheva A.V., Ganichev A.V. A method for solving some classes of optimization problems. Modelirovaniye, optimizatsiya i informatsionnyye tekhnologii = Modeling, optimization and information technology. 2019;7(2):43–54. (In Russ.).

10. Bereznev B.A. On the polynomial complexity of a modification of the simplex method. Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki = Computational Mathematics and Mathematical Physics. 2004;44(7):1244–1260. (In Russ.).