Пошук академічних текстів

Інформація × Реєстраційний номер 2118U001191, Матеріали видань та локальних репозитаріїв Категорія Стаття, Опубліковано, Рецензована стаття Назва роботи ОПТИМІЗАЦІЯ ЛІНІЙНИХ ФУНКЦІЙ НА МНОЖИНІ ЦИКЛІЧНИХ ПЕРЕСТАНОВОК З ЛІНІЙНИМИ ОБМЕЖЕННЯМИ Автор Grebennik I.Chernaya O.Makarova E.Grebennik I.Chernaya O.Makarova E. Дата публікації 03-07-2018 Постачальник інформації Національний університет «Полтавська політехніка імені Юрія Кондратюка» Першоджерело https://journals.nupp.edu.ua/sunz/article/view/1135 Видання Національний університет «Полтавська політехніка імені Юрія Кондратюка» Опис Дана робота присвячена рішенню завдань лінійної і дискретної оптимізації на різних класах комбінаторних множинах. Зокрема в роботі описано рішення задачі оптимізації лінійної функції з лінійними обмеженнями на множині циклічних перестановок. Це стратегія рішення з використанням алгоритму на основі випадкового пошуку. Для рішення задачі оптимізації лінійної функції на множині циклічних перестановок використовано підхід, заснований на ідеології випадкового пошуку і аналітичному рішенні систем лінійних нерівностей, що описують обмеження задачі. У процесі рішення вихідної задачі виникає необхідність багаторазового рішення додаткової задачі лінійної оптимізації на множині циклічних перестановок без обмежень. У роботі наводиться два варіанти рішення додаткової задачі. Перший алгоритм на основі методу гілок і меж. Описано переваги такого підходу - можливість отримати точне рішення, різні варіації методу розгалуження дозволяють гнучко управляти витратами обчислювальних потужностей. Так само в роботі приведена альтернатива методу гілок і меж - евристичний метод на основі транспозицій особливого виду. Для цього було розглянуто клас транспозиція, що характеризується тим, що транспозиції з даного класу відповідають критерію суміжності в переставному багатограннику. Запропоновані стратегії реалізовані програмно і протестовані на завданнях різної розмірності з вихідними даними, що генеруються випадковим чином. Проведено обчислювальні експерименти для порівняння точності і часу рішення вихідної задачі двома варіантами методу випадкового пошуку. Експерименти показують перевагу рішення додаткової задачі методом гілок і меж на малих розмірностях. При цьому на завданнях великих розмірностей метод на основі транспозицій особливого виду істотно виграє в плані економії обчислювальних потужностей. Додано в НРАТ 2026-04-19 Закрити