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

  Повний текст PDF - 294.742 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"