2022, випуск 1, c. 5-10
Одержано 25.05.2022; Виправлено 31.05.2022; Прийнято 28.06.2022
Надруковано 30.06.2022; Вперше Online 03.08.2022
https://doi.org/10.34229/2707-451X.22.1.1
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Про деякі оптимізаційні задачі на перестановках
Г.П. Донець 
, В.І. Білецький
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Дослідженню задач комбінаторної оптимізації та методів їх розв’язування присвячено багато робіт, оскільки багато практичних задач описуються за допомогою комбінаторних оптимізаційних моделей. Чільне місце серед них займають задачі оптимізації функцій на комбінаторних конфігураціях. У багатьох таких роботах розглядаються підходи та описані методи розв’язування комбінаторних задач оптимізації лінійних, дробово-лінійних функцій на комбінаторних множинах таких як перестановки, розміщення.
Дана робота присвячена опису нових підходів та методів розв’язування деяких задач максимізації лінійної, дробово-лінійної та квадратичної функцій на множині перестановок. Наводяться схеми алгоритмів розв'язання цих задач.
Для лінійної функції наведено досить простий метод знаходження перестановки, де функція приймає максимальне значення.
Описується загальна схема алгоритму знаходження максимуму дробово-лінійної функції. Розглядаються випадки, коли змінні чисельника та знаменника не перетинаються, коли функції у чисельнику та знаменнику мають одну загальну змінну. Описується також випадок, коли функції у чисельнику та знаменнику в сумі мають неповний список змінних, тобто коли кількість змінних у сумі менше кількості чисел у множині для перестановок.
Відносно розв’язання задачі знаходження максимуму квадратичної функції на перестановках виявляться, що не існує універсального алгоритму розв’язання цієї задачі для будь-якої квадратичної функції. В роботі описується метод знаходження максимуму квадратичної функції на перестановках, що складається з двох доданків.
Наводяться приклади розв'язання розглянутих оптимізаційних задач.
Ключові слова: функція, перестановка, множина, транспозиція, коефіцієнти.
Цитувати так: Донець Г.П., Білецький В.І. Про деякі оптимізаційні задачі на перестановках. Cybernetics and Computer Technologies. 2022. 1. С. 5–10. https://doi.org/10.34229/2707-451X.22.1.1
Список літератури
1. Донець Г.П., Колечкіна Л.М. Екстремальні задачі на комбінаторних конфігураціях. Полтава: РВВ ПУЕТ, 2011. 309 с. http://dspace.uccu.org.ua/handle/123456789/560
2. Donets G.A., Kolechkina L.N. Method of ordering the values of a linear function on a set of permutations. Cybernetics and Systems Analysis. 2009. 45. P. 204–213. https://doi.org/10.1007/s10559-009-9092-6
3. Донец Г.А., Колечкина Л.Н. Об одной задачи оптимизации дробно-линейной функции цели на перестановках. Проблемы управления и информации. 2010. № 2. С. 31–41.
4. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок. Кибернетика и системный анализ. 2008. № 3. С. 158–172.
5. Yemets O.O., Yemets E.M., Olhovskiy D.M. The Method of Cutting the Vertices of Permutation Polyhedron Graph to Solve Linear Conditional Optimization Problems on Permutations. Cybernetics and Systems Analysis. 2014. 50. P. 613–619. https://doi.org/10.1007/s10559-014-9649-x
6. Koliechkina L.N., Dvernaya O.A., Nagornaya A.N. Modified Coordinate Method to Solve Multicriteria Optimization Problems on Combinatorial Configurations. Cybernetics and Systems Analysis. 2014. 50. P. 620–626. https://doi.org/10.1007/s10559-014-9650-4
7. Ємець О.О., Колечкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функціями. Київ: Наук. думка, 2005. 117 с.
8. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1967. 575 с.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна