nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Regularization and Matrix Correction of Improper Linear Programming Problems

verfasst von : Vladimir Erokhin, Sergey Sotnikov, Andrey Kadochnikov, Alexey Vaganov

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The results of the study of improper linear programming problems are presented, in which the duality theory is essentially used and the approaches of I.I. Eremin (correction of incompatible constraints) and A.N. Tikhonov (creation of compatible systems of constraints equivalent in accuracy to given incompatible constraints). The problem of a stable solution to an approximate (and, possibly, improper) pair of mutually dual linear programming problems with a coefficient matrix of size \(m\times n\) is reduced to a Mathematical Programming problem of dimension \(m + n + 2\). The necessary and sufficient conditions for the existence of a solution and constructive formulas for its calculation are obtained. Computational experiments were carried out on a model Linear Programming problem with an approximate matrix and vectors of the right-hand side and the objective function, demonstrating the convergence of the obtained solutions to the normal solutions to direct and dual problems with a decrease in the level of data error.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Analysis of Integer Programming Model of Academic Load Distribution

Nächstes Kapitel Discrete Time Lyapunov-Type Convergence Conditions for Recurrent Sequences in Optimization and Subgradient Method for Weakly Convex Functions

The author of the theorem is Alexander Krasnikov.

Eremin, I.I., Mazurov, V.D., Astaf’ev, N.N.: Improper Problems of Linear and Convex Programming. Nauka, Moscow (1983). (in Russian)

Vasil’ev, F.P., Ivanitskii, A.Yu.: Linear Programming. Faktorial Press, Moscow (2008). (in Russian)

Tikhonov, A.N.: Approximate systems of linear algebraic equations. USSR Comput. Math. Math. Phys. 20(6), 10–22 (1980). (in Russian)MathSciNetCrossRef

Tikhonov, A.N., Arsenin, V.Ja.: Methods for Solving ill-posed Problems, 3rd edn. Nauka, Moscow (1986). (in Russian)

Volkov, V.V., Erokhin, V.I.: Tikhonov solutions of approximately given systems of linear algebraic equations under finite perturbations of their matrices. Comput. Math. Math. Phys. 50(4), 589–605 (2010). https://doi.org/10.1134/S0965542510040032MathSciNetCrossRefMATH

Erokhin, V.I., Volkov, V.V.: On A. N. Tikhonov’s regularized least squares method. Vestn. St.-Peterburg Univ. Prikl. Mat. Inform. Protsessy Upr. 13(1), 4–16 (2017). (in Russian). https://doi.org/10.21638/11701/spbu10.2017.101

Erokhin, V.I.: Matrix correction of a dual pair of improper linear programming problems. Comput. Math. Math. Phys. 47(4), 564–578 (2007). https://doi.org/10.1134/S0965542507040033MathSciNetCrossRefMATH

Erokhin, V.I., Krasnikov, A.S., Khvostov, M.N.: Matrix corrections minimal with respect to the euclidean norm for linear programming problems. Autom. Remote Control 73(2), 219–231 (2012). https://doi.org/10.1134/S0005117912020026MathSciNetCrossRefMATH

Erokhin, V.I., Krasnikov, A.S., Khvostov, M.N.: On sufficient conditions for the solvability of linear programming problems under matrix correction of their constraints. Tr. Inst. Mat. Mekh. 19(2), 144–156 (2013). (in Russian)

10.

Erokhin, V.I.: On some sufficient conditions for the solvability and unsolvability of matrix correction problems of improper linear programming problems. Tr. Inst. Mat. Mekh. 21(3), 110–116 (2015). (in Russian)

11.

Erokhin, V.I., Krasnikov, A.S., Volkov, V.V., Khvostov, M.N.: Matrix correction minimal with respect to the euclidean norm of a pair of dual linear programming problems. In: CEUR Workshop Proceedings 9th, pp. 196–209 (2016)

12.

Erokhin, V.I.: A stable solution of linear programming problems with the approximate matrix of coefficients. In: 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), St. Petersburg, Russia, pp. 88–90. IEEE (2017). https://doi.org/10.1109/CNSA.2017.7973953

13.

Volkov, V.V., Erokhin, V.I., Krasnikov, A.S., et al.: Minimum-euclidean-norm matrix correction for a pair of dual linear programming problems. Comput. Math. Math. Phys. 57(11), 1757–1770 (2017). https://doi.org/10.1134/S0965542517110148MathSciNetCrossRefMATH

14.

Erokhin, V.I., Razumov, A.V., Krasnikov, A.S.: Tikhonov’s solution of approximate and improper LP problems. In: IX Moscow International Conference on Operations Research (ORM 2018), Proceedings, vol. I, pp. 131–136. MAKS Press, Moscow (2018). https://doi.org/10.29003/m211.ORM2018_v1

15.

Eremin, I.I., Makarova, D.A., Schultz, L.V.: Questions of stability and regularization of improper linear programming problems. In: Proceedings of the Ural State University, vol. 30, pp. 43–62 (2004)

16.

Gorelik, V., Zolotova, T.: Approximation of the improper linear programming problem with restriction on the norm of the correction matrix of the left-hand side of the constraints. In: 2018 IX International Conference on Optimization and Applications (OPTIMA 2018), pp. 14–24. DEStech Transactions on Computer Science and Engineering (2018). https://doi.org/10.12783/dtcse/optim2018/27918

17.

Shary, S.P.: Interval Regularization for Imprecise Linear Algebraic Equations. arXiv preprint arXiv:1810.01481 (2018)

18.

Artem’eva, L.A., Vasil’ev, F.P., Potapov, M.M.: Extragradient method for correction of inconsistent linear programming problems. Comput. Math. Math. Phys. 58(12), 1919–1925 (2018). https://doi.org/10.1134/S0965542518120163MathSciNetCrossRefMATH

19.

Popov, L.D.: Methods of interior points, adapted to improper linear programming problems. Tr. Inst. Mat. Mekh. 24(4), 208–216 (2018). (in Russian). https://doi.org/10.21538/0134-4889-2018-24-4-208-210

20.

Skarin, V.D.: Method of penalty functions and regularization in the analysis of improper problems of convex programming. Tr. Inst. Mat. Mekh. 24(3), 187–199 (2018). (in Russian). https://doi.org/10.21538/0134-4889-2018-24-3-187-199CrossRef

21.

Vatolin, A.A.: Approximation of improper linear programming problems using euclidean norm criterion. USSR Comput. Math. Math. Phys. Fiz. 24(12), 1907–1908 (1984). (in Russian)

22.

Gorelik, V.A.: Matrix correction of a linear programming problem with inconsistent constraints. Comput. Math. Math. Phys. 41(12), 1615–1622 (2001)MathSciNetMATH

23.

Amirkhanova, G.A., Golikov, A.I., Evtushenko, Yu. G.: On an inverse linear programming problem. Proc. Steklov Inst. Math. 295(1), 21–27 (2016)MathSciNetCrossRef

24.

Agayan, G.M., Ryutin, A.A., Tikhonov, A.N.: The problem of linear programming with approximate data. USSR Comput. Math. Math. Phys. 24(5), 14–19 (1984). (in Russian)CrossRef

Titel: Regularization and Matrix Correction of Improper Linear Programming Problems
verfasst von: Vladimir Erokhin
Sergey Sotnikov
Andrey Kadochnikov
Alexey Vaganov
Verlag: Springer International Publishing
Buch: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-33393-5

Electronic ISBN: 978-3-030-33394-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-33394-2_22

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"