Search academic texts

Information × Registration Number 2118U001191, Article popup.category Стаття, Опубліковано, Рецензована стаття Title OPTIMIZATION OF LINEAR FUNCTIONS ON A SET OF CYCLIC PERMUTATIONS WITH LINEAR CONSTRAINTS popup.author Grebennik I.Chernaya O.Makarova E.Grebennik I.Chernaya O.Makarova E. popup.publication 03-07-2018 popup.source_user Національний університет «Полтавська політехніка імені Юрія Кондратюка» popup.source https://journals.nupp.edu.ua/sunz/article/view/1135 popup.publisher Національний університет «Полтавська політехніка імені Юрія Кондратюка» Description Дана робота присвячена рішенню завдань лінійної і дискретної оптимізації на різних класах комбінаторних множинах. Зокрема в роботі описано рішення задачі оптимізації лінійної функції з лінійними обмеженнями на множині циклічних перестановок. Це стратегія рішення з використанням алгоритму на основі випадкового пошуку. Для рішення задачі оптимізації лінійної функції на множині циклічних перестановок використовано підхід, заснований на ідеології випадкового пошуку і аналітичному рішенні систем лінійних нерівностей, що описують обмеження задачі. У процесі рішення вихідної задачі виникає необхідність багаторазового рішення додаткової задачі лінійної оптимізації на множині циклічних перестановок без обмежень. У роботі наводиться два варіанти рішення додаткової задачі. Перший алгоритм на основі методу гілок і меж. Описано переваги такого підходу - можливість отримати точне рішення, різні варіації методу розгалуження дозволяють гнучко управляти витратами обчислювальних потужностей. Так само в роботі приведена альтернатива методу гілок і меж - евристичний метод на основі транспозицій особливого виду. Для цього було розглянуто клас транспозиція, що характеризується тим, що транспозиції з даного класу відповідають критерію суміжності в переставному багатограннику. Запропоновані стратегії реалізовані програмно і протестовані на завданнях різної розмірності з вихідними даними, що генеруються випадковим чином. Проведено обчислювальні експерименти для порівняння точності і часу рішення вихідної задачі двома варіантами методу випадкового пошуку. Експерименти показують перевагу рішення додаткової задачі методом гілок і меж на малих розмірностях. При цьому на завданнях великих розмірностей метод на основі транспозицій особливого виду істотно виграє в плані економії обчислювальних потужностей. popup.nrat_date 2026-04-19 Close