ОПТИМИЗАЦИЯ ЛИНЕЙНЫХ ФУНКЦИЙ НА МНОЖЕСТВЕ ЦИКЛИЧЕСКИХ ПЕРЕСТАНОВОК С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ

ОПТИМІЗАЦІЯ ЛІНІЙНИХ ФУНКЦІЙ НА МНОЖИНІ ЦИКЛІЧНИХ ПЕРЕСТАНОВОК З ЛІНІЙНИМИ ОБМЕЖЕННЯМИ

Предметом статьи является процесс решения задач дискретной оптимизации на комбинаторных множествах различных классов. Целью является разработка методов решения задачи оптимизации линейной функции с линейными ограничениями на множестве циклических перестановок, погруженном в евклидово пространство. Задачи: найти точное или приближенное решение задачи оптимизации линейной функции с линейными ограничениями на множестве циклических перестановок, погруженном в евклидово пространство. Исследовать свойства задачи оптимизации, оценить приближенное решение. Основные результаты работы. Предложена стратегия решения с использованием алгоритма на основе случайного поиска. Для решения задачи оптимизации линейной функции на множестве циклических перестановок используется подход, основанный на идеологии случайного поиска и аналитическом решении систем линейных неравенств, описывающих ограничения задачи. В процессе решения исходной задачи необходимо многократное решение вспомогательной задачи оптимизации линейной функции на множестве циклических перестановок без ограничений. В работе приводится два подхода к решению вспомогательной задачи. Первый подход позволяет получить точное решение вспомогательной задачи методом ветвей и границ или приближенное решение при использовании дополнительных эвристик с оценкой полученного решения. Второй подход – эвристический метод на основе транспозиций специального вида. Для реализации подхода введен класс транспозиций, представители которого соответствуют критерию смежности в перестановочном многограннике. Предложенные стратегии реализованы программно и протестированы на задачах различной размерности с исходными данными, генерируемыми случайным образом. Проведены вычислительные эксперименты с целью сравнения точности и времени решения исходной задачи методом случайного поиска с использованием предложенных подходов к решению вспомогательной задачи. Выводы. Эксперименты показывают преимущество решения вспомогательной задачи методом ветвей и границ на малых размерностях. При этом на задачах больших размерностей метод на основе транспозиций существенно выигрывает в плане экономии вычислительных мощностей.

Дана робота присвячена рішенню завдань лінійної і дискретної оптимізації на різних класах комбінаторних множинах. Зокрема в роботі описано рішення задачі оптимізації лінійної функції з лінійними обмеженнями на множині циклічних перестановок. Це стратегія рішення з використанням алгоритму на основі випадкового пошуку. Для рішення задачі оптимізації лінійної функції на множині циклічних перестановок використовано підхід, заснований на ідеології випадкового пошуку і аналітичному рішенні систем лінійних нерівностей, що описують обмеження задачі. У процесі рішення вихідної задачі виникає необхідність багаторазового рішення додаткової задачі лінійної оптимізації на множині циклічних перестановок без обмежень. У роботі наводиться два варіанти рішення додаткової задачі. Перший алгоритм на основі методу гілок і меж. Описано переваги такого підходу - можливість отримати точне рішення, різні варіації методу розгалуження дозволяють гнучко управляти витратами обчислювальних потужностей. Так само в роботі приведена альтернатива методу гілок і меж - евристичний метод на основі транспозицій особливого виду. Для цього було розглянуто клас транспозиція, що характеризується тим, що транспозиції з даного класу відповідають критерію суміжності в переставному багатограннику. Запропоновані стратегії реалізовані програмно і протестовані на завданнях різної розмірності з вихідними даними, що генеруються випадковим чином. Проведено обчислювальні експерименти для порівняння точності і часу рішення вихідної задачі двома варіантами методу випадкового пошуку. Експерименти показують перевагу рішення додаткової задачі методом гілок і меж на малих розмірностях. При цьому на завданнях великих розмірностей метод на основі транспозицій особливого виду істотно виграє в плані економії обчислювальних потужностей.

Chernaya, O.

Makarova, E.

linear function

permutations

cyclic permutations

random search

transpositions

комбинаторная оптимизация

линейная функция

линейные ограничения

аналитическое решение системы линейных неравенств

циклические перестановки

случайный поиск

транспозиции

комбінаторна оптимізація

лінійна функція

перестановки

циклічні перестановки

випадковий пошук

транспозиції

info:eu-repo/semantics/publishedVersion

Рецензована Стаття

10.26906/SUNZ.2018.3.067

Системы управления, навигации и связи. Сборник научных трудов; Том 3 № 49 (2018): Системи управління, навігації та зв’язку; 67-72

Системи управління, навігації та зв’язку. Збірник наукових праць; Том 3 № 49 (2018): Системи управління, навігації та зв’язку; 67-72

2073-7394

10.26906/SUNZ.2018.3