Условная оптимизация задачи с квадратичной функцией цели на множестве размещений - Колечкина, Л.Н.; Нагорная, А.М. (Проблемы управления и информатики, 2020)
Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості 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 точок. Використовуючи даний метод, за скінчене число кроків можна отримати оптимальний розв’язок. The statement of the optimization problem with the quadratic objective function on the combinatorial set of permutations is formulated. A new method of solving the optimization problem, taking into account the fulfillment of the conditions of the tasks formed when considering transpositions of elements of the set of permutations is proposed. The presented method consists of three steps. At the first step, a decision tree is constructed, the branch branches of which are transpositions of the corresponding elements of the set of permutations. At this step, all possible transpositions are compiled in the quantity p that determine the further representation of the set of permutation points in the form of a permutation of the corresponding elements. Subgraphs of the graph G are constructed from these points and subsets of the set of transpositions are compiled. It should be noted that the graph G is only part of the polyhedron of permutations M(Pkn ). At the second step, tasks are compiled whose objective functions are quadratic and are presented taking into account the transpositions under consideration. When solving each problem, a set of transpositions of elements is formed, which consists of Sqop — subset of points in the graph G subgraph that satisfy the constraints; Sqcon — subset of points in a subgraph of a graph G that do not satisfy the constraint; Sqcl — subset of the cut-off points of a graph G subgraph that do not belong to the two previous subsets. On each of the subgraphs of the graph G , additional constraints (4) of the problem (3)–(5) are checked. In this case, only the increments of the constraints and the objective function are calculated using the necessary formulas. The set of supporting solutions will consist of a point xextr at which extr F(xextr) x and the set of partial permutation points Sac , which were not considered during the transposition of elements, but belong to the polyhedron of permutations M(Pkn ). k At the third step, the search for the optimal solution to the problem is carried out by comparing the increments of the quadratic objective function of the point xextr and the points of the set Sac . The article offers a numerical example of the implementation of this method. From 120 points of the set of permutations, the optimal solution was found in 18 steps when considering 27 points and cut off 28 points. Using this method, you can get the optimal solution in a finite number of steps.