Development of a formal algorithm for the formulation of a dual linear optimization problem

Authors

DOI:

https://doi.org/10.15587/1729-4061.2019.175105

Keywords:

linear optimization, primal problem, dual problem, duality, objective function, constraint system, pairs of conjugate problems

Abstract

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.

Author Biographies

Lyudmila Chernova, Admiral Makarov National University of Shipbuilding Heroiv Ukrainy ave., 9, Mykolayiv, Ukraine, 54025

PhD, Associate Professor

Department of Information Control Systems and Technologies

Sergiy Titov, Admiral Makarov National University of Shipbuilding Heroiv Ukrainy ave., 9, Mykolayiv, Ukraine, 54025

PhD, Associate Professor

Department of Higher Mathematics

Sergii Chernov, Admiral Makarov National University of Shipbuilding Heroiv Ukrainy ave., 9, Mykolayiv, Ukraine, 54025

Doctor of Technical Sciences, Professor

Department of Project Management

Kateryna Kolesnikova, Taras Shevchenko National University of Kiyv Volodymyrska str., 60, Kyiv, Ukraine, 01033

Doctor of Technical Sciences, Professor

Department of Technology Management

Liubava Chernova, Admiral Makarov National University of Shipbuilding Heroiv Ukrainy ave., 9, Mykolayiv, Ukraine, 54025

PhD, Associate Professor

Department of Computer-aided Systems Software Support

Viktor Gogunskii, Odessa National Polytechnic University Shevchenka ave., 1, Odessa, Ukraine, 65044

Doctor of Technical Sciences, Professor

Department of Systems Management Life Safety

References

  1. 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
  2. Sigal, I. H., Ivanova, A. P. (2003). Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitel'nye algoritmy. Moscow, 240.
  3. Hetmantsev, V. D. (2001). Liniyna alhebra i liniyne prohramuvannia. Kyiv: Lybid, 250.
  4. 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
  5. 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
  6. Tytov, S. D., Chernova, L. S. (2017). Vyshcha ta prykladna matematyka. Ch. 1. Kharkiv: Fakt, 336.
  7. Nozicka, F., Guddat, J., Hollatz, H. (1972). Theorie der Linearen Optimierung. Berlin, 378.
  8. Lau, D. (2011). Algebra und Diskrete Mathematik 1. Springer. doi: https://doi.org/10.1007/978-3-642-19443-6
  9. 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
  10. 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
  11. Unger, N., Dempe, S. (2010). Lineare Optimierung. Springer. doi: https://doi.org/10.1007/978-3-8348-9659-9
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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

2019-08-07

How to Cite

Chernova, L., Titov, S., Chernov, S., Kolesnikova, K., Chernova, L., & Gogunskii, V. (2019). Development of a formal algorithm for the formulation of a dual linear optimization problem. Eastern-European Journal of Enterprise Technologies, 4(4 (100), 28–36. https://doi.org/10.15587/1729-4061.2019.175105

Issue

Section

Mathematics and Cybernetics - applied aspects