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

Loading...
Thumbnail Image
Date
2020
Authors
Колечкина, Людмила
Нагорная, Алла
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
В статье представлена условная оптимизационная задача с квадратичной функцией цели на множестве размещений. Здесь сформулирована постановка задачи и ее свойства, а также предлагается метод решения комбинаторной задачи с квадратичной функцией цели на множестве размещений и пример ее решения. При реализации метода находится первый опорный план и осуществляется проверка возможного его улучшения за счет сформулированных неравенств, налагаемых на элементы множества размещений.
Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості р, які визначають подальше представлення множини точок розміщень у вигляді перестановки відповідних елементів. З даних точок здійснюється побудова підграфів графа Є і складаються підмножини множини транспозицій. Необхідно відзначити, що граф Є є лише частиною багатогранника розміщень М(Р^). На другому кроці складаються задачі, цільові функції яких є квадратичними і представляються з урахуванням розглянутих транспозицій. При розв’язуванні кожної задачі формується множина транспозицій елементів, яка складається з (гіідмножина точок підграфа графа б , які задовольняють обмеженням); і ’“ " (підмножина точок підграфа графа й , які не задовольняють обмеженням); 5 ^ (підмножина відсічених точок підграфа графа й , що не належать до двох попередніх підмножин). На кожному підграфі графа О здійснюється перевірка додаткових обмежень (4) задачі (3)~(5). При цьому обчислюються лише прирости обмежень і цільової функції за допомогою необхідних формул. Множина опорних розв’язків буде складатися з точки дгех(г, при якій ехїг Р(хепт) , і множини точок розміщення 5 ас, які не були розглянуті при транспозиції елементів, але належать багатограннику розміщень М(Р£). На третьому кроці здійснюється пошук оптимального розв’язку задачі шляхом порівняння приростів квадратичної цільової функції точки тех(г і точок множини 5 ас. Запропоновано числовий приклад реалізації даного методу. З 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 o f the corresponding elements. Subgraphs of the graph G are constructed from these points and subsets of the set o f transpositions are compiled. It should be noted that the graph G is only part of the polyhedron of permutations M(Pj?). 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 S"p — subset of points in the graph G subgraph that satisfy the constraints; S c'm — subset o f points in a subgraph of a graph G that do not satisfy the constraint; S„ — subset o f the cut-off points of a graph G subgraph that do not belong to the two previous subsets. On each o f the subgraphs of the graph G , additional constraints (4) o f 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 o f supporting solutions will consist of a point *extr at which extr F(xaat) and the set of partial permutation points Sac, which were not considered during the transposition o f elements, but belong to the polyhedron of permutations M(P£). 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 jtextr and the points of the set Sac. The article offers a numerical example of the implementation o f this method. From 120 points o f 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.
Description
Keywords
оптимизация, математическая модель, квадратичная функция, множество размещений, опорное решение, оптимальное решение, статья, оптимізація, математична модель, квадратична функція, множина розміщень, опорний розв’язок, оптимальне рішення, optimization, mathematical model, quadratic function, partial permutation, reference solution, optimal solution
Citation
Колечкина Л. Н. Условная оптимизация задачи с квадратичной функцией цели на множестве размещений / Л. Н. Колечкина, А. Н. Нагорная // Проблемы управления и информатики. - 2020. - № 2. - С. 46-61.