В роботі досліджено моделі та методи комбінаторної оптимізації, щовикористовують властивості множини циклічних перестановок і їхзастосування для розв'язання наукових і прикладних задач, серед яких —задачі транспортної маршрутизації.Досліджено властивості циклічних перестановок при їх відображенні вевклідів простір. Використовуються поліедральні властивості перестановок іциклічних перестановок, що відповідають підмножині вершинперестановочного багатогранника. Набув подальшого розвитку кластранспозицій суміжності для перестановок різних елементів, представникиякого породжують перестановки, відповідні суміжним вершинамперестановочного многогранника. Описано властивості суміжності іособливості зміни циклічної структури перестановок при впливі транспозиційсуміжності. Проведено класифікацію циклічних перестановок в залежності відвпливу транспозицій суміжності на їх циклічну структуру. Доведеновідповідні твердження про властивості транспозицій суміжності.Набули подальшого розвитку методи розв'язання задач оптимізаціїлінійних функцій на множині циклічних перестановок, зокрема, з лінійнимиобмеженнями. Для розв'язання задачі без обмежень запропоновано підхід, 20заснований на комбінації методу гілок та меж і евристики. Запропонованометод пошуку наближеного розв'язку задачі без обмежень з використаннямвластивостей транспозицій суміжності. Для розв'язання задачі оптимізаціїлінійних функцій на множині циклічних перестановок з лінійнимиобмеженнями запропоновано метод на основі випадкового пошуку, звикористанням транспозицій суміжності для розв'язання допоміжної задачі.Набув подальшого розвитку метод комбінаторної оптимізації на основіциклічних трансферів в частині генерації циклічних трансферів від'ємноївартості. Метод застосовано для покращення розв'язків задач транспортноїмаршрутизації, зокрема, задачі вивозу і доставки (Pickup and DeliveryProblem), отриманих за допомогою евристики.Для розв'язання задач, досліджених в роботі, розроблено програмнезабезпечення, що реалізує запропоновані моделі та методи комбінаторноїоптимізації. Наведено результати обчислювальних експериментів, проведеноаналіз результатів, який підтверджує ефективність запропонованих підходів.Отримані результати можуть бути використані при комп'ютерномумоделюванні і розв'язанні задач в областях архівації даних і криптографії,квантових обчислень, біоінформатики.Ключові слова: комбінаторна оптимізація, циклічні перестановки,транспозиції, перестановочний багатогранник, транспозиції суміжності,лінійна функція, метод гілок та меж, евристика, задача вивозу і доставки.

Постачальник даних: УкрІНТЕІ (Український Інститут науково-технічної експертизи та Інформації)

  Завантажити автореферат