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

Simple item page
dc.contributor.authorКолечкина, Людмила
dc.contributor.authorНагорная, Алла
dc.date.accessioned2021-02-02T19:04:14Z
dc.date.available2021-02-02T19:04:14Z
dc.date.issued2020
dc.description.abstractВ статье представлена условная оптимизационная задача с квадратичной функцией цели на множестве размещений. Здесь сформулирована постановка задачи и ее свойства, а также предлагается метод решения комбинаторной задачи с квадратичной функцией цели на множестве размещений и пример ее решения. При реализации метода находится первый опорный план и осуществляется проверка возможного его улучшения за счет сформулированных неравенств, налагаемых на элементы множества размещений.ru_RU
dc.description.abstractСформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості р, які визначають подальше представлення множини точок розміщень у вигляді перестановки відповідних елементів. З даних точок здійснюється побудова підграфів графа Є і складаються підмножини множини транспозицій. Необхідно відзначити, що граф Є є лише частиною багатогранника розміщень М(Р^). На другому кроці складаються задачі, цільові функції яких є квадратичними і представляються з урахуванням розглянутих транспозицій. При розв’язуванні кожної задачі формується множина транспозицій елементів, яка складається з (гіідмножина точок підграфа графа б , які задовольняють обмеженням); і ’“ " (підмножина точок підграфа графа й , які не задовольняють обмеженням); 5 ^ (підмножина відсічених точок підграфа графа й , що не належать до двох попередніх підмножин). На кожному підграфі графа О здійснюється перевірка додаткових обмежень (4) задачі (3)~(5). При цьому обчислюються лише прирости обмежень і цільової функції за допомогою необхідних формул. Множина опорних розв’язків буде складатися з точки дгех(г, при якій ехїг Р(хепт) , і множини точок розміщення 5 ас, які не були розглянуті при транспозиції елементів, але належать багатограннику розміщень М(Р£). На третьому кроці здійснюється пошук оптимального розв’язку задачі шляхом порівняння приростів квадратичної цільової функції точки тех(г і точок множини 5 ас. Запропоновано числовий приклад реалізації даного методу. З 120 точок множини розміщень знайдено оптимальний розв’язок за 18 кроків при розгляді 27 і відсіканні 28 точок. Використовуючи даний метод, за скінчене число кроків можна отримати оптимальний розв’язок.uk_UA
dc.description.abstractThe 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.en_US
dc.identifier.citationКолечкина Л. Н. Условная оптимизация задачи с квадратичной функцией цели на множестве размещений / Л. Н. Колечкина, А. Н. Нагорная // Проблемы управления и информатики. - 2020. - № 2. - С. 46-61.ru_RU
dc.identifier.issn0572-2691
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/19380
dc.language.isoruuk_UA
dc.relation.sourceПроблемы управления и информатики.ru_RU
dc.statusfirst publisheduk_UA
dc.subjectоптимизацияru_RU
dc.subjectматематическая модельru_RU
dc.subjectквадратичная функцияru_RU
dc.subjectмножество размещенийru_RU
dc.subjectопорное решениеru_RU
dc.subjectоптимальное решениеru_RU
dc.subjectстатьяru_RU
dc.subjectоптимізаціяuk_UA
dc.subjectматематична модельuk_UA
dc.subjectквадратична функціяuk_UA
dc.subjectмножина розміщеньuk_UA
dc.subjectопорний розв’язокuk_UA
dc.subjectоптимальне рішенняuk_UA
dc.subjectoptimizationen_US
dc.subjectmathematical modelen_US
dc.subjectquadratic functionen_US
dc.subjectpartial permutationen_US
dc.subjectreference solutionen_US
dc.subjectoptimal solutionen_US
dc.titleУсловная оптимизация задачи с квадратичной функцией цели на множестве размещенийru_RU
dc.title.alternativeУмовна оптимізація задачі з квадратичною функцією цілі на множині розміщеньuk_UA
dc.title.alternativeConditional Optimization of a Problem with Objective Quadratic Function on a Set of Permutationsen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Kolechkina_Uslovnaya_optimizatsiya_zadachi.pdf
Size:
688.39 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Кафедра інформатики