Розробка формального алгоритму складання двоїстої задачі лінійної оптимізації
DOI:
https://doi.org/10.15587/1729-4061.2019.175105Ключові слова:
лінійне програмування, пряма задача, двоїста задача, двоїстість, цільова функція, система обмежень, пари спряжених задачАнотація
Запропоновано строгий формальний алгоритм побудови двоїстої задачі для різних випадків запису (загальна, основна, стандартна та канонічна) прямої задачі лінійного програмування.
На початку наведено означення пари двоїстих задач для стандартної форми запису прямої задачі лінійного програмування. Такий підхід обґрунтовується з тих позицій, що за часом така пара була означена першою, оскільки мала змістовну інтерпретацію.
Економічною інтерпретацією стандартної задачі є максимізація прибутку при виробництві та реалізації деяких видів продукції. Такий підхід змістовно вказує на існування прямої задачі (I) та строго відповідної до неї двоїстої (спряженої) (II). Супутня до прямої задачі є задача про мінімізацію витрат.
Базовим поняттям теорії двоїстості в задачах лінійного програмування є той факт, що пара задач є взаємно спряженими – отримання двоїстої від двоїстої призводить до прямої задачі.
Строгий підхід до отримання алгоритму складання двоїстої задачі ґрунтується на твердженні – двоїста задача від двоїстої є прямою (вихідною) задачею. Для різних пар двоїстих задач строго доводиться виконання такого твердження.
Існуючі схеми переходу від прямої задачі до двоїстої носять змістовний характер. З огляду на цей факт, запропоновано та строго доведено алгоритм загального підходу до складання пар спряжених задач.
Формалізація розробленої схеми дозволяє легко отримувати пари відомих двоїстих задач. Це дозволило вперше запропонувати та довести істинність алгоритму побудови двоїстої задачі для довільної форми представлення прямої задачі
Посилання
- 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
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2019 Lyudmila Chernova, Sergiy Titov, Sergii Chernov, Kateryna Kolesnikova, Liubava Chernova, Viktor Gogunskii
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
