METHODS FOR SOLVING LINEAR PROGRAMMING PROBLEMS WITH ADDITIONAL RESTRICTIONS TO THE PARTICULAR VARIABLES

The paper describes the solution of the problem related to the specific admissible sets of variables in linear programming. We are discussing the feasible set which is the union of segments with multiplier parameter for some variable. The solution of this problem is performed in two stages: at the beginning the relaxed problem of linear optimization is solved (without additional restrictions to the variables), and then auxiliary nonlinear optimization problem is constructed on the basis of the obtained solution. Solution of the mentioned auxiliary problem is based on a specialized method of nonlinear optimization - Box method. The result is the algorithm proposed by the author for solving linear programming problems with additional restrictions to the variables with indication of the accuracy estimates. The solution of this problem has a high practical importance. Such restrictions to the variables in the linear programming problems occur often enough for production problems. Method application is shown on the example of an optimal plan finding for pattern cutting in the paper industry, when the task arises associated with the rounding of reels number for paper machines in terms of the found optimal paper cutting plan.

1. Urban A.R., Kuznetsov V.A. Matematicheskie modeli i metody ucheta srokov produktsii v zadache raskroya tamburov bumagodelatel'nykh mashin [Mathematical models and methods of output production timeline consideration in cutting reels of paper machine]. Uchenye Zapiski PetrGU. Seriya Estestvennye i Tekhnicheskie Nauki, 2014, no. 4 (141), pp. 112–115.

2. Kuznetsov V.A. Zadachi Raskroya v Tsellyulozno-Bumazhnoi Promyshlennosti [Cutting Problem in the Pulp and Paper Industry]. St. Petersburg, SPbFTU Publ., 2000, 132 p.

3. Voronov R.V. Matematicheskie Modeli i Metody Avtomatizirovannykh Sistem Planirovaniya Proizvodstva Bumagi: Avtoref. diss. … kand. tekhn. nauk [Mathematical Models and Methods of Automated Systems for

Planning of Paper Production. Thesis eng. sci. diss.]. Petrozavodsk, 2004, 22 p.

4. Westerlund T., Harjunkoski I., Isaksson J. Solving a production optimization problem in a paper-converting mill with MILP. Computers and Chemical Engineering, 1998, vol. 22, no. 4–5, pp. 563–570.

5. Voronin A.V., Kuznetsov V.A., Arkhipov I.V., Shabaev A.I. Software system for sawmill operation planning. Proc. 12th Conference of FRUCT Association. St. Petersburg, Russia, 2012, pp. 165–171.

6. Shabaev A.I., Arhipov I.V., Spirichev M.V., Urban A.R., Torozerov M.A. Development of planning system for plywood production using matrix designer. Proc. 14th Conference of FRUCT Association. St. Petersburg,

Russia, 2014, pp. 140–147.

7. Vasenin V.A., Vodomerov A.N. A formal model of a system for automated program parallelization. Programming and Computer Software, 2007, vol. 33, no. 4, pp. 181–194. doi: 10.1134/S0361768807040019

8. Ilyushin A.I., Olenin M.A., Vasil'ev S.A. Solution of parallel computation problem based on «Space-Time» concept. Programming and Computer Software, 2012, vol. 38, no. 4, pp. 189–200. doi:

10.1134/S0361768812040020

9. Bazara M.S., Shetty C.M. Nonlinear Programming. Theory and Algorithms. NY, Wiley, 1979.

10. Afanasyeva A.S., Buzdalov M.V. Vybor funktsii prisposoblennosti osobei geneticheskogo algoritma s pomoshch'yu obucheniya s podkrepleniem [Fitness function choosing for genetic algorithms with reinforcement learning]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 1 (77), pp. 77–81.

11. Eremeev A.V. Geneticheskii algoritm s turnirnoi selektsiei kak metod lokal'nogo poiska [Genetic algorithm with tournament selection as a local search method]. Journal of Applied and Industrial Mathematics, 2012,

vol. 6, no. 3, pp. 286–294. doi: 10.1134/S1990478912030039

12. Shtovba S.D. Ant algorithms: theory and applications. Programming and Computer Software, 2005, vol. 31, no. 4, pp. 167–178. doi: 10.1007/s11086-005-0029-1

13. Khapaev M.M., Tsygankov A.A. An algorithm for the constrained extremum problem. Computational Mathematics and Modeling, 1997, vol. 8, no. 4, pp. 322–325.

14. Trifonov A.G. Postanovka Zadachi Optimizatsii i Chislennye Metody ee Resheniya [Formulation of the Optimization Problem and Numerical Methods for its Solution]. Available at:

http://matlab.exponenta.ru/optimiz/book_2/index.php (accessed 25.01.2015)

15. Medynskii M.M., Antonii E.V. Chislennye Metody Nelineinoi Optimizatsii: Algoritmy i Programmy. Uchebnoe Posobie [Numerical Methods for Nonlinear Optimization: Algorithms and Programs. Textbook].

Moscow, MAI Publ., 2003, 192 p.

16. Gorodetskii S.Yu., Grishagin V.A. Nelineinoe Programmirovanie i Mnogoekstremal'naya Optimizatsiya [Nonlinear Programming and Optimization Multiextremal]. Nizhny Novgorod, UNN Publ., 2007, 489 p.

17. Kapitonova A.P., Smelyanskii R.L., Terekhov I.V. A support system for estimating computational complexity in programs. Computational Mathematics and Modeling, 1994, vol. 5, no. 4, pp. 279–287. doi:

10.1007/BF01130310

18. Cormen T.H., Leiserson C.E., Rivest R.L. Introduction to Algorithms. MIT Press, 2001, 984 p.

19. Gass S.I. Linear Programming. Methods and Applications. NY, McGraw-Hill Book Co., 1958.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License