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

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

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 eleme...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2020
Hauptverfasser: Koliechkina, L.N., Nahirna, A.N.
Format: Artikel
Sprache:English
Veröffentlicht: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
Schlagworte:
оптимізація
математична модель
квадратична функція
множина розміщень
опорний розв’язок
оптимальне рішення
Online Zugang:https://jais.net.ua/index.php/files/article/view/457
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Problems of Control and Informatics

Institution

Problems of Control and Informatics
id oai:ojs2.jais.net.ua:article-457
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2025-03-14T15:38:27Z
collection OJS
language English
topic оптимізація
математична модель
квадратична функція
множина розміщень
опорний розв’язок
оптимальне рішення
spellingShingle оптимізація
математична модель
квадратична функція
множина розміщень
опорний розв’язок
оптимальне рішення
Koliechkina, L.N.
Nahirna, A.N.
УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ
topic_facet optimization
mathematical model
quadratic function
partial permutation
reference solution
optimal solution
оптимізація
математична модель
квадратична функція
множина розміщень
опорний розв’язок
оптимальне рішення
format Article
author Koliechkina, L.N.
Nahirna, A.N.
author_facet Koliechkina, L.N.
Nahirna, A.N.
author_sort Koliechkina, L.N.
title УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ
title_short УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ
title_full УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ
title_fullStr УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ
title_full_unstemmed УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ
title_sort умовна оптимізація задачі з квадратичною функцією цілі на множині розміщень
title_alt CONDITIONAL OPTIMIZATION OF A PROBLEM WITH OBJECTIVE QUADRATIC FUNCTION ON A SET OF PERMUTATIONS
description 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.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2020
url https://jais.net.ua/index.php/files/article/view/457
work_keys_str_mv AT koliechkinaln conditionaloptimizationofaproblemwithobjectivequadraticfunctiononasetofpermutations
AT nahirnaan conditionaloptimizationofaproblemwithobjectivequadraticfunctiononasetofpermutations
AT koliechkinaln umovnaoptimízacíâzadačízkvadratičnoûfunkcíêûcílínamnožinírozmíŝenʹ
AT nahirnaan umovnaoptimízacíâzadačízkvadratičnoûfunkcíêûcílínamnožinírozmíŝenʹ
first_indexed 2025-10-30T02:49:13Z
last_indexed 2025-10-30T02:49:13Z
_version_ 1847373388098568192
spelling oai:ojs2.jais.net.ua:article-4572025-03-14T15:38:27Z CONDITIONAL OPTIMIZATION OF A PROBLEM WITH OBJECTIVE QUADRATIC FUNCTION ON A SET OF PERMUTATIONS УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ Koliechkina, L.N. Nahirna, A.N. optimization mathematical model quadratic function partial permutation reference solution optimal solution оптимізація математична модель квадратична функція множина розміщень опорний розв’язок оптимальне рішення 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. Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості p, які визначають подальше представлення множини точок розміщень у вигляді перестановки відповідних елементів. З даних точок здійснюється побудова підграфів графа G і складаються підмножини множини транспозицій. Необхідно відзначити, що граф G є лише частиною багатогранника розміщень M (Pn ). На другому кроці складаються задачі, цільові функції яких є квадратичними і представляються з урахуванням розглянутих транспозицій. При розв’язуванні кожної задачі формується множина транспозицій елементів, яка складається з S op (підмножина точок підграфа графа G , які задовольняють обмеженням); Scon (підмножина точок підграфа графа G , які не задовольняють обмеженням); S cl (підмножина відсічених точок підграфа графа G , що не належать до двох попередніх підмножин). На кожному підграфі графа G здійснюється перевірка додаткових обмежень (4) задачі (3)–(5). При цьому обчислюються лише прирости обмежень і цільової функції за допомогою необхідних формул. Множина опорних розв’язків буде складатися з точки xextr , при якій extr F(xextr ) , і множини точок розміщення Sac , які не були розглянуті при транспозиції елементів, але належать багатограннику розміщень M (Pn ). На третьому кроці здійснюється пошук оптимального розв’язку задачі шляхом порівняння приростів квадратичної цільової функції точки xextr і точок множини Sac . Запропоновано числовий приклад реалізації даного методу. З 120 точок множини розміщень знайдено оптимальний розв’язок за 18 кроків при розгляді 27 і відсіканні 28 точок. Використовуючи даний метод, за скінчене число кроків можна отримати оптимальний розв’язок. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020-04-20 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/457 10.1615/JAutomatInfScien.v52.i4.50 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 65 № 2 (2020): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 46-61 International Scientific Technical Journal "Problems of Control and Informatics; Том 65 № 2 (2020): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 46-61 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 65 No. 2 (2020): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 46-61 2786-6505 2786-6491 en https://jais.net.ua/index.php/files/article/view/457/525 Copyright (c) 2020 L.N. Koliechkina, A.N. Nahirna https://creativecommons.org/licenses/by-nc-nd/4.0

Ähnliche Einträge