Наближений метод розв'язування задачі булевого програмування. Ознака оптимальності наближеного розв'язку

Автор(и)

DOI:

https://doi.org/10.24144/2616-7700.2026.49(2).292-299

Ключові слова:

булеве програмування, математична модель, алгоритм наближеного методу, достатня умова оптимальності

Анотація

У статті розглядається математична модель задачі булевого програмування для випадків, коли всі коефіцієнти цільової функції та обмежень є додатними величинами. Оскільки точні класичні алгоритми вимагають значного обсягу роботи, для розв'язання задачі пропонується ітеративний наближений метод. Алгоритм поетапно формує часткові рішення з одночасною оцінкою цільової функції та відсіканням безперспективних варіантів, що дає змогу зменшити кількість необхідних обчислень. Наближений розв'язок не завжди є оптимальним, тому в статті наводиться достатня умова, при виконанні якої його можна оптимізувати.

Спонсор дослідження

  • Дослiдження здiйснено в рамках кафедральної науково-дослiдної роботи «Моделi i методи системного аналiзу в мiждисциплiнарних дослiдженнях» (державний облiковий номер 0125U003246).

Біографії авторів

Г. Г. Цегелик, Львівський національний університет імені Івана Франка

Професор кафедри математичного моделювання соціально-економічних процесів. Доктор фiзико-математичних наук

М. І. Глебена, ДВНЗ «Ужгородський нацiональний унiверситет»

Завiдувач кафедри cистемного аналiзу та теорiї оптимiзацiї. Кандидат фiзико-математичних наук, доцент

М. Г. Цегелик, ПП «Бінар»

Директор

Посилання

  1. Hnatenko, I. M., Liashenko, V. I., & Manhasarian, A. V. (2013). Boolean programming: theory and practice. KNEU [in Ukrainian].
  2. Zaichenko, Yu. P. (2005). Operations research. Vydavnychyi tsentr “Akademiia” [in Ukrainian].
  3. Katrenko, A. V. (2004). Operations research. Mahnoliia Plius [in Ukrainian].
  4. Balas, E. (1965). An additive algorithm for solving linear programs with zero-one variables. Operations Research, 13(4), 517–546.
  5. Tsehelyk, H. H., Seno, P. S., Hlebena, M. I., & Tsehelyk, M. H. (2026). An approach to solving boolean programming problems based on structural interpretation. Scientific Bulletin of Uzhhorod University. Series of Mathematics and Informatics, 48(1), 232–242. https://doi.org/10.24144/2616-7700.2026.48(1).232-242 [in Ukrainian].
  6. Tsehelyk, H. H., & Tsehelyk, M. H. (2026). Approximate method for solving boolean programming problems. In International Scientific and Practical Conference "Current problems of science, education and technologies: from theoretical foundations to practical solutions of the XXI century". (pp. 120–124). [in Ukrainian].

##submission.downloads##

Опубліковано

2026-04-30

Як цитувати

Цегелик, Г. Г., Глебена, М. І., & Цегелик, М. Г. (2026). Наближений метод розв’язування задачі булевого програмування. Ознака оптимальності наближеного розв’язку. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 49(2), 292–299. https://doi.org/10.24144/2616-7700.2026.49(2).292-299

Номер

Том 49 № 2 (2026)

Розділ

Iнформатика, комп’ютернi науки та прикладна математика

Ліцензія

Авторське право (c) 2026 Г. Г. Цегелик, М. І. Глебена, М. Г. Цегелик

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.