Development of a formal algorithm for the formulation of a dual linear optimization problem
DOI:
https://doi.org/10.15587/1729-4061.2019.175105Keywords:
linear optimization, primal problem, dual problem, duality, objective function, constraint system, pairs of conjugate problemsAbstract
The rigorous formal algorithm for formulating a dual problem for different forms (general, basic, standard, and canonical) of a primal linear programming problem is proposed. First, definitions of a pair of dual problems for standard form of primal linear programming are given. This approach is based on the fact that such a pair was noted first, since it had substantial interpretation.
The economic interpretation of the standard problem is profit maximization in the production and sale of some types of products. Such an approach substantially indicates the existence of the primal problem (I) and the strictly corresponding dual (conjugate) (II). The problem of cost minimization is accompanying to the primal problem.
The basic concept of the duality theory in linear programming problems is the fact that a pair of problems are mutually conjugate — obtaining dual of dual leads to a primal problem.
The rigorous approach to obtaining an algorithm for formulating a dual problem is based on the statement that the dual problem of dual is a primal (original) problem. This approach is used in the paper. For different pairs of dual problems, this statement is rigorously proved.
The existing schemes of primal to dual conversion are substantial. Given this, the algorithm of the general approach to formulating pairs of conjugate problems is proposed and rigorously proved.
Formalization of the developed scheme makes it easy to get pairs of known dual problems. This allowed for the first time to propose and validate the algorithm for constructing a dual problem for an arbitrary form of the primal problem.
References
- Drozd, J., Drozd, A. (2013). Models, methods and means as resources for solving challenges in co-design and testing of computer systems and their components. The International Conference on Digital Technologies 2013. doi: https://doi.org/10.1109/dt.2013.6566307
- Sigal, I. H., Ivanova, A. P. (2003). Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel'nye algoritmy. Moscow, 240.
- Hetmantsev, V. D. (2001). Liniyna alhebra i liniyne prohramuvannia. Kyiv: Lybid, 250.
- Teschl, G., Teschl, S. (2008). Mathematik für Informatiker. Band 1: Diskrete Mathematik und Lineare Algebra. Springer, 519. doi: https://doi.org/10.1007/978-3-540-77432-7
- Biloshchytskyi, A., Myronov, O., Reznik, R., Kuchansky, A., Andrashko, Y., Paliy, S., Biloshchytska, S. (2017). A method to evaluate the scientific activity quality of HEIs based on a scientometric subjects presentation model. Eastern-European Journal of Enterprise Technologies, 6 (2 (90)), 16–22. doi: https://doi.org/10.15587/1729-4061.2017.118377
- Tytov, S. D., Chernova, L. S. (2017). Vyshcha ta prykladna matematyka. Ch. 1. Kharkiv: Fakt, 336.
- Nozicka, F., Guddat, J., Hollatz, H. (1972). Theorie der Linearen Optimierung. Berlin, 378.
- Lau, D. (2011). Algebra und Diskrete Mathematik 1. Springer. doi: https://doi.org/10.1007/978-3-642-19443-6
- Biloshchytskyi, A., Kuchansky, A., Andrashko, Y., Biloshchytska, S., Kuzka, O., Shabala, Y., Lyashchenko, T. (2017). A method for the identification of scientists' research areas based on a cluster analysis of scientific publications. Eastern-European Journal of Enterprise Technologies, 5 (2 (89)), 4–11. doi: https://doi.org/10.15587/1729-4061.2017.112323
- Biloshchytskyi, A., Kuchansky, A., Biloshchytska, S., Dubnytska, A. (2017). Conceptual model of automatic system of near duplicates detection in electronic documents. 2017 14th International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). doi: https://doi.org/10.1109/cadsm.2017.7916155
- Unger, N., Dempe, S. (2010). Lineare Optimierung. Springer. doi: https://doi.org/10.1007/978-3-8348-9659-9
- Kolesnіkov, O., Gogunskii, V., Kolesnikova, K., Lukianov, D., Olekh, T. (2016). Development of the model of interaction among the project, team of project and project environment in project system. Eastern-European Journal of Enterprise Technologies, 5 (9 (83)), 20–26. doi: https://doi.org/10.15587/1729-4061.2016.80769
- Wu, C., Nikulshin, V. (2000). Method of thermoeconomical optimization of energy intensive systems with linear structure on graphs. International Journal of Energy Research, 24 (7), 615–623. doi: https://doi.org/10.1002/1099-114x(20000610)24:7<615::aid-er608>3.3.co;2-g
- Kuchansky, A., Biloshchytskyi, A., Andrashko, Y., Biloshchytska, S., Shabala, Y., Myronov, O. (2018). Development of adaptive combined models for predicting time series based on similarity identification. Eastern-European Journal of Enterprise Technologies, 1 (4 (91)), 32–42. doi: https://doi.org/10.15587/1729-4061.2018.121620
- Gogunskii, V., Kolesnikov, O., Kolesnikova, K., Lukianov, D. (2016). “Lifelong learning” is a new paradigm of personnel training in enterprises. Eastern-European Journal of Enterprise Technologies, 4 (2 (82)), 4–10. doi: https://doi.org/10.15587/1729-4061.2016.74905
- Demin, D. (2017). Improvement of approaches to the construction of the training process of sportsmen, considered within the framework of the realization of informal education processes. ScienceRise: Pedagogical Education, 9 (17), 28–46. doi: https://doi.org/10.15587/2519-4984.2017.111110
- Lax, P. D. (2013). Linear Algebra and Its Applications. Wiley, 392. Available at: https://www.wiley.com/en-us/Linear+Algebra+and+Its+Applications%2C+2nd+Edition-p-9781118626924
- Drozd, J., Drozd, A., Maevsky, D., Shapa, L. (2014). The levels of target resources development in computer systems. Proceedings of IEEE East-West Design & Test Symposium (EWDTS 2014). doi: https://doi.org/10.1109/ewdts.2014.7027104
- Chernov, S., Titov, S., Chernova, L., Gogunskii, V., Chernova, L., Kolesnikova, K. (2018). Algorithm for the simplification of solution to discrete optimization problems. Eastern-European Journal of Enterprise Technologies, 3 (4 (93)), 34–43. doi: https://doi.org/10.15587/1729-4061.2018.133405
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Lyudmila Chernova, Sergiy Titov, Sergii Chernov, Kateryna Kolesnikova, Liubava Chernova, Viktor Gogunskii
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
