Лінійне програмування – генерація та розв'язування прикладів

YURIY FEDKOVYCH CHERNIVTSI NATIONAL UNIVERSITY in cooperation with National Academy of Sciences of Ukraine Institute of Cybernetics NАS Ukraine Taras Shevchenko National University of Kyiv National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute» Proceedings of the Fourteenth International Conference on «INFORMATICS AND COMPUTER TECHNICS PROBLEMS» (PICT – 2025) 13 – 15 November, 2025, Chernivtsi, UKRAINE Інститут кібернетики імені В.М. Глушкова НАН України Київський національний університет імені Тараса Шевченка Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» Чернівецький національний університет імені Юрія Федьковича «ПРОБЛЕМИ ІНФОРМАТИКИ ТА КОМП’ЮТЕРНОЇ ТЕХНІКИ» (ПІКТ – 2025) Праці XIV Міжнародної науково-практичної конференції ЧЕРНІВЦІ 13 – 15 ЛИСТОПАДА, 2025 Чернівці 2025 Проблеми інформатики та комп’ютерної техніки: праці XIV Міжнародної науково-практичної конференції (ПІКТ – 2025), присвяченої 85-й річниці від дня народження проф. Кириченка М.Ф. м. Чернівці, 13–15 лист. 2025. Чернівці : Технодрук, 2025. 204 с. Програмний комітет: Організаційний комітет: Співголови Білоскурський Р.Р. проф. (Україна, Чернівці) Крак Ю.В., проф. (Україна, Київ) Члени комітету Азаров О.Д., проф. (Україна, Вінниця) Байєр Г., проф. (Німеччина, Цвікау) Бармак О.В., проф. (Україна, Хмельницький) Абабій В., проф. (Молдова, Кишинів) Граур А., проф., (Румунія, Сучава) Гребеннік І.В., проф. (Україна, Харків) Григорків В.С., проф. (Україна, Чернівці) Дейбук В.Г., проф. (Україна, Чернівці) Дивак М.П., проф. (Україна, Тернопіль) Добровольський Ю.Г., проф. (Україна, Чернівці) Крістіа Д., проф., (Румунія, Ясси) Кушнір Р.М., проф. (Україна, Львів) Куц Р. проф., (США, Ньюхевен) Мельник А.О., проф. (Україна, Львів) Наконечний О.Г., проф. (Україна, Київ) Пікієвич П., проф., (Польща, Д.-Гурнича) Ситніков В.С., проф. (Україна, Одеса) Станушек М., проф., (Польща, Краків) Тарасенко В.П., проф. (Україна, Київ) Ушенко Ю.О., проф. (Україна, Чернівці) Федасюк Д.В., проф. (Україна, Львів) Філіпова Л. PhD, (Словаччина, Братислава) Хаас В., проф., (Чехія, Прага) Хіміч О.М., проф. (Україна, Київ) Чикрій А.О., проф. (Україна, Київ) Шрайнер В., проф., (Австрія, Лінц) Ясній П.В., проф. (Україна, Тернопіль) Якоб Ф., проф., (Словаччина, Кошице) © Чернівецький нац. ун-т, 2025 © ПВКФ "Технодрук", 2025 Голова Остапов С.Е., проф. Заступники голови Баловсяк С.В., доц., Малик І.В., проф., Угрин Д.І., проф. Члени оргкомітету Руснак М.А. – вчений секретар, Антонюк С.В., Воробець Г.І., Газдюк К.П., Дрінь Я.М., Кириченко О.Л., Кириченко О.О., Коцур М.П., Лазорик В.В., Стецько Ю.П., Танасюк Ю.В., Тимофієва Є.М., Філіпчук О.І., Фратавчан В.Г., Яковлєва І.Д. ISBN 978-617-8034-69-6 ISBN 978-617-8034-69-6 УДК 004(082) П-78 П-78 5 СЕКЦІЯ 4 КОМП’ЮТЕРНІ СИСТЕМИ І КОМПОНЕНТИ .................................................................................................... 79 КРИВОРУЧКО О.В., ЧОРНОУС О.С. ІНТЕЛЕКТУАЛЬНЕ УПРАВЛІННЯ ТА МОНІТОРИНГ МАГІСТРАЛЬНИХ ОПТОВОЛОКОННИХ МЕРЕЖ ПРОВАЙДЕРІВ . 79 ЛЯШКЕВИЧ В.Я., ОЛАР О.Я., ЯРОШЕНКО О.І. ВИБІР РЕЛЕВАНТНИХ ОЗНАК АНОМАЛЬНИХ ПРОЯВІВ У КОМП’ЮТЕРНИХ МЕРЕЖАХ ДЛЯ ЇХ АВТОМАТИЗОВАНОГО ВИДОБУВАННЯ З МЕРЕЖНОГО ТРАФІКУ ..................................................................................................................................... 81 СЕКЦІЯ 5 УПРАВЛІННЯ ТА МОДЕЛЮВАННЯ В СОЦІАЛЬНИХ І ЕКОНОМІ-ЧНИХ СИСТЕМАХ ....................... 83 BOROZAN O., ABABII V. ANALYSIS OF EMOTIONS IN SPEECH TO IDENTIFY EXCEPTIONAL SITUATIONS ...................................................................... 83 MELNIC R., ABABII V. DECISION SUPPORT SYSTEM FOR THE MANAGEMENT OF EDUCATIONAL INSTITUTIONS .................................................... 86 RORARI A., BOROZAN O., DRUMEA N., CLIMA A., ABABII V. APPLYING VIRTUAL REALITY MODELS IN REAL-TIME PROCESS MONITORING AND CONTROL ............................................ 88 STRUNA V., LUNGU I., ROȘCA N., LASCO V., ABABII V. ADAPTIVE SERVICE-ORIENTED COMPUTING ARCHITECTURE ................................................................................................... 90 IVATO Y., BUN R. SPATIAL MODELING OF GREENHOUSE GAS EMISSION PROCESSES FROM OIL INDUSTRY IN UKRAINE ............................. 92 КАПТАР Д.Є., ФРАТАВЧАН В.Г. СИСТЕМА ОБРОБКИ РЕЗУЛЬТАТІВ СОЦІОЛОГІЧНИХ ОПИТУВАНЬ СТУДЕНТІВ ................................................................. 94 МАГДА К.М., РУСНАК М.А. БАГАТОКРИТЕРІАЛЬНИЙ ПОШУК ТА ВІЗУАЛІЗАЦІЯ ОПТИМАЛЬНИХ ШЛЯХІВ НА МЕРЕЖІ ........................................... 96 МОСЯНДЗ О.М., ФРАТАВЧАН В.Г. ВІЗУАЛЬНИЙ МОНІТОРИНГ ХРОНОЛОГІЇ ПРИКОРДОННИХ ПРАВОПОРУШЕНЬ ............................................................... 97 NIKOLENKO K., MOROZ V. INTEGRATION OF MULTI-SCALE ADAPTIVE ATTENTION MECHANISM FOR SEMANTIC SEGMENTATION IN AUTONOMOUS DRIVING ..................................................................................................................................................................... 99 POHORILETS D., BUN R. GEOSPATIAL ANALYSIS OF CONSEQUENCES OF WAR-INDUCED FOREST FIRES IN THE ZHYTOMYR, RIVNE, AND VOLYN REGIONS USING SATELLITE IMAGE PROCESSING AND A CLOUD PLATFORM ....................................................................... 101 PUTO A., BUN R. SPATIAL MODELING OF GREENHOUSE GAS EMISSIONS FROM ROAD TRANSPORT IN UKRAINE ........................................ 103 УРБАНОВИЧ А.М., МІНКОВ К.О., ФРАТАВЧАН В.Г. ПЕРСОНАЛЬНИЙ АСИСТЕНТ ОБЛІКУ ОСОБИСТИХ ФІНАНСОВИХ ВИТРАТ: МОДЕЛЬ, АЛГОРИТМИ ТА РЕАЛІЗАЦІЯ НА ПЛАТФОРМІ PYTHON ................................................................................................................................................................. 105 РУСНАК М.А., ФАРБАТЮК В.В. ЛІНІЙНЕ ПРОГРАМУВАННЯ – ГЕНЕРАЦІЯ ТА РОЗВ'ЯЗУВАННЯ ПРИКЛАДІВ .................................................................... 106 СЕКЦІЯ 6 ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ ТА ЇХ ЗАСТОСУВАННЯ ................................................ 109 БАНДУРА Б. В., АНТОНЮК С. В. SPOTWISE - ІНТЕЛЕКТУАЛЬНИЙ ТУРИСТИЧНИЙ АСИСТЕНТ ................................................................................................ 109 УГРИН Д.І., УШЕНКО Ю.О., БРЕСЛАВСЬКИЙ О.І. 106 text( ) ∏ ( ∣ ) Комбінування рішень через зважену лог-правдоподібність:  ( ( ∣ ) ( )∑ ( ∣ )) [ ] Коментар: внесок ознаки  ; для тексту - лог-частки ( ∣ ) ( ∣ ). Невизначеність: якщо ( ∣ ) , транзакція здійснюється за підтвердженням користувача. Бюджетування: для категорії та інтервалу [ )визначимо витрати ( ) ∑ ( ) ( ) рівень використання бюджету 𝑢 ( ) 𝑢 де — поріг попередження/перевищення. Прогноз до кінця періоду при середньоденному темпі ˉ : 󰆹 EOM ( ) ˉ ⋅ днів до Рекомендація перерозподілу мінімізує опуклий штраф перевищення: ∑ ( 𝛿 )s.t. ∑ 𝛿 де — дозволена сума витрат, — Huber. Виявлення аномалій: на рівні категорії/мерчанта застосовано робастні оцінки. Для вікна обчислюється 𝑧 ( ) ( ) ( ) ( ) аномалія якщо ∣𝑧 ( )∣ Висновок. «Фінансовий асистент» забезпечує систематичну реєстрацію витрат, їх автоматичну категоризацію з коментарями, контроль виконання бюджетів і вчасні сповіщення про ризики перевищення та атипові витрати. Модульність архітектури спрощує подальше розширення категорій, правил і джерел даних. ПЕРЕЛІК ЛІТЕРАТУРИ 1. Мобільні застосунки для планування бюджету та контролю витрат: які найбільш популярні. URL: https://epravda.com.ua/publications/2023/02/22/697326/ 2. Шаблони оформлення бюджету, на які можна покластися. URL: https://create.microsoft.com/uk-ua/templates/бюджети 3. Путівник мовою програмування Python. URL: http://pythonguide.rozh2sch.org.ua/ УДК 519.63.4 РУСНАК М.А., ФАРБАТЮК В.В. Чернівецький національний університет імені Юрія Федьковича (Україна) ЛІНІЙНЕ ПРОГРАМУВАННЯ – ГЕНЕРАЦІЯ ТА РОЗВ'ЯЗУВАННЯ ПРИКЛАДІВ Досліджується процес генерації та розв’язування задач лінійного програмування з метою удосконалення засвоєння теоретичних відомостей та закріпленню навичок їх використання на практиці . Лінійне програмування є одним із фундаментальних інструментів дослідження математичних моделей та розв’язування отимізаційних задач в області науки, відомій під узагальненою назвою «Дослідження операцій». Такі задачі виникають при плануванні виробництва, логістиці, фінансовому аналізі та деяких аспектах машинного навчання. Сьогодні важливо не лише розв’язувати такі задачі, а й генерувати приклади для тестування алгоритмів, 107 навчання моделей і створення навчальних матеріалів. Поєднання теорії розв’язування з автоматизованою генерацією відкриває нові можливості для навчання, досліджень та практичного використання алгоритмів оптимізації. Подальший аналіз базується на добре відомих [1] ключових положеннях теорії лінійного програмування, які й визначають методи розв’язування та можливості автоматизованої побудови прикладів. Серед відомих алгоритмів лінійного програмування є симплекс-метод (як варіант – двоїстий симплекс-метод), метод внутрішніх точок, еліпсоїдний метод Хачіяна, алгоритм прогнозування-коректор Мехротри та інші. Останні мають поліноміальний час роботи. Симплекс-метод забезпечує наочність і добре підходить для невеликих задач. Двоїстий симплекс-метод доцільний у випадках, коли потрібно швидко оновити розв’язок після зміни структури обмежень. Метод внутрішніх точок (алгоритм Кармаркара) ефективний при роботі з великими розмірностями задач, оскільки шукає оптимум усередині області допустимих розв’язків. Для простих навчальних прикладів також застосовують графічний метод, що дозволяє візуалізувати пошук оптимального рішення. Усі ці методи демонструють різні підходи до пошуку оптимальних рішень, однак ефективність їхнього застосування значною мірою залежить від структури самої задачі. Саме тому постає потреба у генерації різноманітних прикладів, які дозволяють перевіряти роботу алгоритмів, аналізувати їхню продуктивність та створювати навчальні матеріали для практичного опанування лінійного програмування [2]. Генерація прикладів у лінійному програмуванні полягає у створенні наборів задач, що мають задану структуру й контрольовані параметри. Мета цього процесу — дослідити поведінку алгоритмів за різних умов, оцінити стійкість отриманих результатів і сформувати репрезентативні приклади для навчальних або аналітичних цілей. Типова математична модель загальної задачі лінійного програмування має вигляд: (max) { Під час генерації прикладів, орієнтованих, наприклад, на дослідження роботи симплексметоду, особливу увагу приділяють геометричним властивостям допустимої множини. Оскільки цей метод здійснює пошук розв’язку шляхом послідовного переходу між вершинами багатогранника, необхідно, щоб побудована система обмежень утворювала опуклу багатогранну область із скінченою кількістю вершин. Для цього під час генерації необхідно підбирати такі коефіцієнти, за яких перетин гіперплощин утворює вершину ообласті. Для цього використовується наступне означення [1] – кутовою точкою або вершиною опуклого багатогранника D назвемо таку його точку x , для якої не існує інших точок 1 x , 2 x D , 21 xx  , таких, що 2 2 1 1xxx   при 0 1  , 0 2  , 1 21   . Крім того, важливо забезпечити правильне співвідношення між кількістю змінних і обмежень, оскільки надлишкова або недостатня кількість обмежень змінює форму багатогранника та впливає на кількість вершин (базисних векторів), які має обробити алгоритм. Для аналізу роботи симплекс-методу доцільно створювати приклади з різною кількістю обмежень, що дозволяє дослідити вплив структури допустимої області на швидкість збіжності до розвязку. Особливу роль відіграє контроль виродженості, коли кілька вершин мають однакові значення цільової функції. Такі ситуації можуть спричинити зациклення або повторні переходи між тими самими вершинами. Щоб цього уникнути, під час генерації задач до параметрів моделі вводяться незначні випадкові збурення, які не порушують загальної структури, але гарантують унікальність оптимального розв’язку [3]. Завдяки такому підходу згенеровані задачі відображають різні типи геометричних конфігурацій допустимої області і дозволяють досліджувати поведінку симплекс-методу за умов зміни її форми, складності системи обмежень та чутливості до варіацій у вихідних даних. 108 1. Руснак М.А., Коцур М.П. Математичне програмування : навч. посіб. / уклад.: М.А.Руснак, М.П. Коцур. Чернівці : Чернівец. нац. ун-т ім. Ю. Федьковича, 2025. 200 с. ISBN 978-966-423935-3. 2. Ладогубець Т.С. Лінійне програмування : навч.-метод. посібник. — Київ : КПІ ім. Ігоря Сікорського, 2019. URL: https://ela.kpi.ua/bitstreams/0dae7b19-940d-4b91-86088cd67911ad35/download 3. Ладієва Л.Р. Оптимізація систем керування: практикум. — Київ : КПІ ім. Ігоря Сікорського, 2021. URL: https://ela.kpi.ua/bitstreams/5c1969c0-3a4a-4e2a-a7780092586dbc82/download ПЕРЕЛІК ЛІТЕРАТУРИ «ПРОБЛЕМИ ІНФОРМАТИКИ ТА КОМП’ЮТЕРНОЇ ТЕХНІКИ» (ПІКТ – 2025) Праці XIV Міжнародної науково-практичної конференції ЧЕРНІВЦІ 13 – 15 ЛИСТОПАДА, 2025 Папір офсетний. Формат 60х84/8. Ум. друк. арк. 23,71. Вид. №25-15. Зам. № 37. Тираж 75 прим. Видавець та виготівник: ПВКФ «Технодрук» Свідоцтво суб’єкта видавничої справи ДК №1841 від 10.06.2004 р. 58000, м. Чернівці, вул. І. Франка, 20, оф.18, тел. (0372) 55-05-85 Видання містить праці учасників XIV Міжнародної науково-практичної конференції «Проблеми інформатики та комп’ютерної техніки» (ПІКТ–2025). Редакційна колегія: Остапов С.Е., Руснак М.А., Лазорик В.В. Комп’ютерний набір та верстка: Руснак О.В. Відповідальний за випуск: Остапов С.Е.