Про один підхід до розв'язування задач булевого програмування на основі його структурної інтерпретації
DOI:
https://doi.org/10.24144/2616-7700.2026.48(1).232-242Ключові слова:
математична модель, булеве програмування, двійкове дерево рішень, структурна інтерпретація, наближений та оптимальний розв’язки задачіАнотація
У роботi розглянуто актуальну проблему розв’язування задач дискретної оптимiзацiї, зокрема задач булевого лiнiйного програмування. Запропоновано графоаналiтичний пiдхiд до знаходження оптимального плану, що базується на структурнiй iнтерпретацiї простору розв’язкiв через побудову впорядкованого двiйкового дерева. Описано методику формування рiвнiв дерева, де кожна гiлка вiдповiдає вибору значення змiнної (0 або 1), а вершини впорядкованi згiдно з обраною стратегiєю iндексацiї. Розроблено комплексний алгоритм, який складається з двох етапiв: швидкого знаходження початкового допустимого розв’язку (рекорду) та iтерацiйного пошуку глобального оптимуму. Особливiстю методу є використання правил вiдсiкання безперспективних гiлок та виявлення «прямих» (безальтернативних) шляхiв, що дозволяє суттєво зменшити обчислювальну складнiсть порiвняно з повним перебором. Ефективнiсть запропонованого пiдходу проiлюстровано на прикладах.
Спонсор дослідження
- Дослiдження здiйснено в рамках кафедральної науково-дослiдної роботи «Моделi i методи системного аналiзу в мiждисциплiнарних дослiдженнях» (державний облiковий номер 0125U003246)
Посилання
- Balas, E. (1965). An additive algorithm for solving linear programs with zero-one variables. Operations Research, 13(4), 517–546.
- Burkard, R. E., Dell’Amico, M., & Martello, S. (2009). Assignment problems. SIAM.
- Hnatenko, I. M., Liashenko, V. I., & Manhasarian, A. V. (2013). Boolean programming: theory and practice. KNEU.
- Hooker, J. N. (2000). Logic-based methods for optimization: combining optimization and constraint satisfaction. Wiley.
- Katrenko, A. V. (2004). Operations research. Mahnoliia Plius.
- Katrenko, A. V., & Pasternak, O. V. (2014). System aspects of investment in information technology. Visnyk Natsionalnoho universytetu “Lvivska politekhnika”, 805, 402–411.
- Katrenko, A. V., & Pasternak, O. V. (2017). Mathematical models of investment in information technology. Visnyk Natsionalnoho universytetu “Lvivska politekhnika”. Seriia: Informatsiini systemy ta merezhi.
- Lavrov, Ye. A., Perkhun, L. P., & Shendryk, V. V. (2017). Mathematical methods of operations research. Sumskyi derzhavnyi universytet.
- Tsehelyk, H. H., & Tsehelyk, M. H. (2025, December 15–17). A new approach to solving Boolean programming problems. In Proceedings of the XII International Scientific and Practical Conference “Global trends in science and education”, 517–523. Kyiv, Ukraine.
- Tsehelyk, H. H., Tsehelyk, M. H., Dobuliak, L. P., & Piadko, O. Ya. (2025, September 11–13). Mathematical model of the problem of optimal financing of investment projects and an approximate method of its solution. In Proceedings of the I International Scientific and Practical Conference “Science, technology and global challenges”, 251–258. Tokyo, Japan.
- Zaichenko, Yu. P. (2005). Operations research. Vydavnychyi tsentr “Akademiia”.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2026 Г. Г. Цегелик, П. С. Сеньо, М. І. Глебена, М. Г. Цегелик
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
