Условная оптимизация задачи с квадратичной функцией цели на множестве размещений

• Date: 2020
• Main Authors: Колечкина, Л.Н., Нагорная, А.М.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2020
• Series: Проблемы управления и информатики
• Subjects: Методы оптимизации и оптимальное управление
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/208710
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Условная оптимизация задачи с квадратичной функцией цели на множестве размещений / Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. — 2020. — № 2. — С. 46-61. — Бібліогр.: 31 назв. — рос.

Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості p, які визначають подальше представлення множини точок розміщень у вигляді перестановки відповідних елементів. З даних точок здійснюється побудова підграфів графа G і складаються підмножини множини транспозицій. Необхідно відзначити, що граф G є лише частиною багатогранника розміщень M(Pkn ). На другому кроці складаються задачі, цільові функції яких є квадратичними і представляються з урахуванням розглянутих транспозицій. При розв’язуванні кожної задачі формується множина транспозицій елементів, яка складається з Sqop (підмножина точок підграфа графа G , які задовольняють обмеженням); Sqcon (підмножина точок підграфа графа G , які не задовольняють обмеженням); Sqcl (підмножина відсічених точок підграфа графа G , що не належать до двох попередніх підмножин). На кожному підграфі графа G здійснюється перевірка додаткових обмежень (4) задачі (3)–(5). При цьому обчислюються лише прирости обмежень і цільової функції за допомогою необхідних формул. Множина опорних розв’язків буде складатися з точки , xextr при якій extr F(xextr), і множини точок розміщення Sac , які не були розглянуті при транспозиції елементів, але належать багатограннику розміщень M(Pkn ). На третьому кроці здійснюється пошук оптимального розв’язку задачі шляхом порівняння приростів квадратичної цільової функції точки xextr і точок множини Sac . Запропоновано числовий приклад реалізації даного методу. З 120 точок множини розміщень знайдено оптимальний розв’язок за 18 кроків при розгляді 27 і відсіканні 28 точок. Використовуючи даний метод, за скінчене число кроків можна отримати оптимальний розв’язок.