Науковий інтерес до задач комбінаторної оптимізації та їх актуальність зумовили виокремлення задач на евклідових комбінаторних множинах. У роботах Ю.Г.Стояна, а також О.О.Ємця, С.В.Яковлєва та інших представників цієї школи досліджувалися властивості евклідових комбінаторних множин при їх зануренні в арифметичний евклідовий простір, екстремальні властивості цільових функцій на таких множинах, розроблено та обґрунтовано методи розв’язування евклідових задач комбінаторної оптимізації на множинах переставлень, сполучень, поліпереставлень та ін. Недостатньо розробленими та дослідженими є методи й алгоритми розв’язування евклідових задач комбінаторної оптимізації на загальній множині розміщень. У той же час цілий ряд практичних задач, окремі моделі яких побудовано в роботі, можуть бути адекватно формалізовані за допомогою евклідових задач комбінаторної оптимізації на розміщеннях. Проведений аналіз методів розв’язування задач як дискретної, так і евклідової комбінаторної оптимізації, окремих методів опуклого програмування показав, що зазначений клас задач вимагає розробки спеціальних методів їх розв’язування. Виходячи з певної подібності окремих властивостей допустимих множин задач дискретної оптимізації та оптимізації на розміщеннях у дисертаційній роботі розроблено методи та обґрунтовано алгоритми розв’язування евклідових задач комбінаторної оптимізації на розміщеннях, що спираються на ідейні підґрунтя як відсікання частини допустимої множини, що не містить оптимуму, так і напрямленого перебору. Методи дослідження задач оптимізації на розміщеннях, що використовуються у дисертації, ґрунтуються на розвинутих раніше теорії та методах евклідової комбінаторної оптимізації, а також на інших відомих методах дискретної оптимізації. Достовірність результатів дисертації випливає з логічності та строгості математичних доведень, лем, тверджень та теорем і підтверджена результатами числових експериментів. У дисертації: уперше введено в розгляд евклідові задачі лексикографічної комбінаторної оптимізації на розміщеннях, а також побудовано моделі практичних задач як задач такого типу; уперше розроблено методи відсікання для розв’язування евклідових задач комбінаторної оптимізації на розміщеннях, встановлено коефіцієнти нерівностей, що додаються на кожній ітерації, в алгоритмах розв’язування лінійних та опуклих задач оптимізації на розміщеннях, а також доведено, що нерівності із визначеними згідно із запропонованими формулами коефіцієнтами задають правильні відсікання; уперше здійснено розбиття многогранної множини за допомогою відношення лексикографічної еквівалентності відносно розміщень та впорядковано елементи одержаної фактор-множини, досліджено окремі характеристики класів еквівалентності; уперше здійснено алгоритмізацію напрямленого перебору класів еквівалентності на основі розв’язування послідовності задач лінійного програмування; уперше запропоновано метод розв’язування лінійних умовних задач лексикографічної оптимізації на розміщеннях, який використовує такий перебір; уперше обґрунтовано алгоритми методу комбінаторного відсікання для розв’язування лінійної умовної задачі оптимізації на розміщеннях та її частинного випадку, а також задачі опуклої оптимізації на розміщеннях та доведено їх скінченність; розроблено алгоритми методу побудови лексикографічної еквівалентності для розв’язування задач лексикографічної оптимізації на розміщеннях. Урахування комбінаторного характеру окремих обмежень дозволяє повною мірою відобразити змістовну сутність ряду практичних задач. У той же час для деяких задач важливою також є можливість вибору серед усіх екстремалей однієї, яка є кращою у певному розумінні. Уведення в розгляд евклідових задач лексикографічної оптимізації на розміщеннях надає можливість побудови адекватних математичних моделей практичних задач із зазначеними властивостями. Розробка методів розв’язування оптимізаційних задач на розміщеннях дозволяє знаходити оптимальні розв’язки таких моделей. Однією з великих груп методів, що використовуються, як у дискретній, так і в евклідовій комбінаторній оптимізації, є методи відсікання, у яких розв’язок задачі одержується в результаті розв’язування послідовності релаксованих задач, перехід між якими здійснюється за допомогою додавання до системи обмежень правильного відсікання — лінійної нерівності, яку справджують усі допустимі точки задачі і не задовольняє одержаний розв’язок релаксованої задачі. Встановлення коефіцієнтів таких додаткових обмежень у процесі розв’язування задач на розміщеннях дозволяє поширити ідеї методів відсікання на розв’язування задач оптимізації на розміщеннях. Побудова нерівностей-відсікань для різних релаксованих задач (задач лінійного, дискретного, цілочислового лінійного програмування) дозволяє повніше враховувати специфіку конкретної евклідової задачі комбінаторної оптимізації і обирати більш ефективний алгоритм для її розв’язання. Головне значення введеного в роботі відношення лексикографічної еквівалентності відносно розміщень, яке є відношенням еквівалентності, полягає у розбитті многогранної множини на класи еквівалентності (-класи), причому кожна точка, яка є розміщенням, утворює окремий (комбінаторний) -клас. Уведення відношення порядку на множині класів еквівалентності та розв’язування задачі пошуку комбінаторного -класу, найближчого до заданого класу у впорядкованій фактор-множині, може бути покладено в основу алгоритмів напрямленого перебору -класів. У свою чергу ці алгоритми можуть використовуватися при розв’язуванні задач оптимізації на розміщеннях. Формулювання та обґрунтування алгоритмів розроблених методів розв’язування задач на розміщеннях дозволяє автоматизувати процес пошуку розв’язків таких задач за рахунок використання ЕОМ. Практична ефективність запропонованих алгоритмів підтверджена числовими експериментами. | 