Одержано 04.06.2020; Виправлено 14.06.2020; Прийнято 30.06.2020

Надруковано 24.07.2020; Вперше Online 27.07.2020

https://doi.org/10.34229/2707-451X.20.2.2

Попередня  |  Повний текст  |  Наступна

 

УДК 519.8

Про задачу локалізації лінійної функції на перестановках

Г.П. Донець ,   В.І. Білецький

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

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

Дана робота присвячена описанню методу розв’язання задачі локалізації лінійної цільової функції на множині перестановок. Суть задачі полягає у наступному. На множині перестановок знайти такі локально-допустимі перестановки, на яких лінійна функція приймає задане значення. Така задача в загальному випадку може не мати розв’язку. 

В роботі приводиться новий розроблений метод, який дає можливість отримати  розв’язок задачі (у випадку, якщо такий розв’язок існує) шляхом цілеспрямованого пошуку локально-допустимих перестановок з найменшим числом перебору варіантів, набагато меншим числа всіх варіантів.

Пошук розв’язку зводиться до генерації варіантів перестановок і їх оцінки. Оцінка кожної перестановки складається з двох частин. Перша частина стосується зменшення значення функції за рахунок транспозиції чисел у перші n – 3 позиції, а друга частина – з оцінки  перестановок для інших трьох чисел. Потім, аналізуючи співвідношення, яке назване балансом, приходимо до висновку, чи є  розв’язком перестановка, що розглядується, чи ні.

В роботі метод локалізації розглядується на прикладі розв’язання задачі для n = 5. 

 

Ключові слова: локалізація, лінійна функція, перестановка, транспозиція, баланс, позиція.

 

Цитувати так: Донец Г.А., Билецкий В.И. О задаче локализации линейной функции на перестановках. Cybernetics and Computer Technologies. 2020. 2. С. 14–18. https://doi.org/10.34229/2707-451X.20.2.2

 

Список літератури

           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. Cybern Syst Anal. 2009. 45 (2). P. 204–213. https://doi.org/10.1007/s10559-009-9092-6

           3.     Донец Г.А., Колечкина Л.Н. Об одной задачи оптимизации дробно-линейной функции цели на перестановках. Проблемы управления и информации. 2010, 2. С. 31–41. https://doi.org/10.1615/JAutomatInfScien.v42.i4.10

           4.     Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок. Кибернетика и системный анализ. 2008. 44 (3). С. 158–172. https://doi.org/10.1007/s10559-008-9016-x

           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. Cybern Syst Anal. 2014. 50 (4). 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. Cybern Syst Anal. 2014. 50 (4). P. 620–626. https://doi.org/10.1007/s10559-014-9650-4

           7.     Ємець О.О., Колечкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функціями. К.: Наукова думка, 2005. 117 с.

           8.     Емец О.А., Барболина Т.Н. Комбинаторная оптимизация на размещениях. К.: Наукова думка, 2008. 159 с.

           9.     Емец О.А., Черненко О.А. Оптимизация дробно-линейных функций на размещениях. К.: Наукова думка, 2011. 139 с.

       10.     Сергиенко И.В., Емец О.А., Черненко О.А. Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ. Кибернетика и системный анализ. 2012. № 6. С. 30 – 35. https://doi.org/10.1007/s10559-012-9462-3

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна