ОПТИМІЗАЦІЯ ЛІНІЙНИХ ФУНКЦІЙ НА МНОЖИНІ ЦИКЛІЧНИХ ПЕРЕСТАНОВОК З ЛІНІЙНИМИ ОБМЕЖЕННЯМИ
Ключові слова:
комбінаторна оптимізація, лінійна функція, перестановки, циклічні перестановки, випадковий пошук, транспозиції
Анотація
Дана робота присвячена рішенню завдань лінійної і дискретної оптимізації на різних класах комбінаторних множинах. Зокрема в роботі описано рішення задачі оптимізації лінійної функції з лінійними обмеженнями на множині циклічних перестановок. Це стратегія рішення з використанням алгоритму на основі випадкового пошуку. Для рішення задачі оптимізації лінійної функції на множині циклічних перестановок використовано підхід, заснований на ідеології випадкового пошуку і аналітичному рішенні систем лінійних нерівностей, що описують обмеження задачі. У процесі рішення вихідної задачі виникає необхідність багаторазового рішення додаткової задачі лінійної оптимізації на множині циклічних перестановок без обмежень. У роботі наводиться два варіанти рішення додаткової задачі. Перший алгоритм на основі методу гілок і меж. Описано переваги такого підходу - можливість отримати точне рішення, різні варіації методу розгалуження дозволяють гнучко управляти витратами обчислювальних потужностей. Так само в роботі приведена альтернатива методу гілок і меж - евристичний метод на основі транспозицій особливого виду. Для цього було розглянуто клас транспозиція, що характеризується тим, що транспозиції з даного класу відповідають критерію суміжності в переставному багатограннику. Запропоновані стратегії реалізовані програмно і протестовані на завданнях різної розмірності з вихідними даними, що генеруються випадковим чином. Проведено обчислювальні експерименти для порівняння точності і часу рішення вихідної задачі двома варіантами методу випадкового пошуку. Експерименти показують перевагу рішення додаткової задачі методом гілок і меж на малих розмірностях. При цьому на завданнях великих розмірностей метод на основі транспозицій особливого виду істотно виграє в плані економії обчислювальних потужностей.Завантаження
Дані про завантаження поки що недоступні.
Посилання
1. Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации / И. В. Сергиенко – К.: Наук. думка, 1988. – 472 с.
2. Емец О. А. Комбинаторная оптимизация на размещениях / О. А. Емец, Т. Н. Барболина. – К.: Наук. думка, 2008. – 159 с.
3. Стоян Ю. Г. Теорія і методи евклідової комбінаторної оптимізації / Ю. Г. Стоян, О. О. Ємець – К.: Інститут системних досліджень освіти, 1993. –188 с.
4. Стоян Ю. Г. Математические модели и оптимизационные методы геометрического проектирования / Ю. Г. Стоян, С. В. Яковлев – К.: Наук. думка, 1986. – 268 с.
5. Гребенник И. В. Упорядочение перестановок при решении задач комбинаторной оптимизации с линейной целевой функцией / И. В. Гребенник, Л. Ю. Юрченко // Системи обробки інформації.– Х.: ХУПС, 2007. – Вип. 8 (66).– С. 139-142.
6. Гребенник И. В. Решение некоторых задач условной оптимизации линейных функций на перестановочном многограннике. / И. В. Гребенник // Радиоэлектроника и информатика.– 1999.– № 1.– С. 55-59.
7. Емеличев В. А. Многогранники, графы, оптимизация. / В. А. Емеличев, М. М. Ковалев, М. К. Кравцов. – М.: Наука, 1981. – 344 с.
8. Стенли Р. Перечислительная комбинаторика / Р. Стенли; пер. с англ. А. И. Барвинка. – М.: Мир, 1990. – 440 с.
9. Гребенник И. В. Оптимизация линейной функции на множестве циклических перестановок / И. В. Гребенник, А. С.Литвиненко, О. С. Титова. – Бионика Интеллекта. – 2012. – № 2 (79). – С. 8-12.
10. Емец О. А. Решение линейных задач оптимизации на размещениях методом отсечения / О. А. Емец, Т. Н. Барболина // Кибернетика и системный анализ. – 2003. – Т. 37, № 6.
11. Гребенник И. В. Специальные транспозиции элементов перестановок и свойства композиции / И. В. Гребенник, О. С. Черная // Кибернетика и системный анализ.– 2017.– Т. 53, № 1. – С. 79-90.
12. Реклейтис Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел; пер. с англ. В. Я. Алтаева. – М.: Мир, 1986. – 348 с.
13. Bona M. Combinatorics of permutations / M. Bona. – Chapman & Hall/CRC, 2004. – 337 c.
14. Гребенник И. В. Оптимизация линейных функций с линейными ограничениями на комбинаторных множествах на основе случайного поиска / И. В. Гребенник, А. В. Баранов // Искусств. интеллект. – 2007. – № 1.– С. 132-137.
2. Емец О. А. Комбинаторная оптимизация на размещениях / О. А. Емец, Т. Н. Барболина. – К.: Наук. думка, 2008. – 159 с.
3. Стоян Ю. Г. Теорія і методи евклідової комбінаторної оптимізації / Ю. Г. Стоян, О. О. Ємець – К.: Інститут системних досліджень освіти, 1993. –188 с.
4. Стоян Ю. Г. Математические модели и оптимизационные методы геометрического проектирования / Ю. Г. Стоян, С. В. Яковлев – К.: Наук. думка, 1986. – 268 с.
5. Гребенник И. В. Упорядочение перестановок при решении задач комбинаторной оптимизации с линейной целевой функцией / И. В. Гребенник, Л. Ю. Юрченко // Системи обробки інформації.– Х.: ХУПС, 2007. – Вип. 8 (66).– С. 139-142.
6. Гребенник И. В. Решение некоторых задач условной оптимизации линейных функций на перестановочном многограннике. / И. В. Гребенник // Радиоэлектроника и информатика.– 1999.– № 1.– С. 55-59.
7. Емеличев В. А. Многогранники, графы, оптимизация. / В. А. Емеличев, М. М. Ковалев, М. К. Кравцов. – М.: Наука, 1981. – 344 с.
8. Стенли Р. Перечислительная комбинаторика / Р. Стенли; пер. с англ. А. И. Барвинка. – М.: Мир, 1990. – 440 с.
9. Гребенник И. В. Оптимизация линейной функции на множестве циклических перестановок / И. В. Гребенник, А. С.Литвиненко, О. С. Титова. – Бионика Интеллекта. – 2012. – № 2 (79). – С. 8-12.
10. Емец О. А. Решение линейных задач оптимизации на размещениях методом отсечения / О. А. Емец, Т. Н. Барболина // Кибернетика и системный анализ. – 2003. – Т. 37, № 6.
11. Гребенник И. В. Специальные транспозиции элементов перестановок и свойства композиции / И. В. Гребенник, О. С. Черная // Кибернетика и системный анализ.– 2017.– Т. 53, № 1. – С. 79-90.
12. Реклейтис Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел; пер. с англ. В. Я. Алтаева. – М.: Мир, 1986. – 348 с.
13. Bona M. Combinatorics of permutations / M. Bona. – Chapman & Hall/CRC, 2004. – 337 c.
14. Гребенник И. В. Оптимизация линейных функций с линейными ограничениями на комбинаторных множествах на основе случайного поиска / И. В. Гребенник, А. В. Баранов // Искусств. интеллект. – 2007. – № 1.– С. 132-137.
Опубліковано
2018-07-03
Як цитувати
Grebennik I. Оптимізація лінійних функцій на множині циклічних перестановок з лінійними обмеженнями / I. Grebennik, O. Chernaya, E. Makarova // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2018. – Т. 3 (49). – С. 67-72. – doi:https://doi.org/10.26906/SUNZ.2018.3.067.
Розділ
Математичні моделі та методи
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
