УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ

• Дата: 2020
• Автори: Koliechkina, L.N., Nahirna, A.N.
• Формат: Стаття
• Мова: English
• Опубліковано: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
• Теми: оптимізація; математична модель; квадратична функція; множина розміщень; опорний розв’язок; оптимальне рішення
• Онлайн доступ: https://jais.net.ua/index.php/files/article/view/457
• Назва журналу: Problems of Control and Informatics

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 (Pn ). 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 op — subset of points in the graph G subgraph that satisfy the constraints; Scon — subset of points in a subgraph of a graph G that do not satisfy the constraint; S cl 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 ) 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 (Pn ). 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.