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

Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
Hauptverfasser:	Колечкина, Л.Н., Нагорная, А.М.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2020
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы оптимизации и оптимальное управление
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/208710
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Условная оптимизация задачи с квадратичной функцией цели на множестве размещений / Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. — 2020. — № 2. — С. 46-61. — Бібліогр.: 31 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208710
record_format	dspace
spelling	irk-123456789-2087102025-11-05T01:06:58Z Условная оптимизация задачи с квадратичной функцией цели на множестве размещений Умовна оптимізація задачі з квадратичною функцією цілі на множині розміщень Conditional optimization of a problem with objective quadratic function on a set of permutations Колечкина, Л.Н. Нагорная, А.М. Методы оптимизации и оптимальное управление Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості 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. 2020 Article Условная оптимизация задачи с квадратичной функцией цели на множестве размещений / Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. — 2020. — № 2. — С. 46-61. — Бібліогр.: 31 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208710 519.85 10.1615/JAutomatInfScien.v52.i4.50 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление
spellingShingle	Методы оптимизации и оптимальное управление Методы оптимизации и оптимальное управление Колечкина, Л.Н. Нагорная, А.М. Условная оптимизация задачи с квадратичной функцией цели на множестве размещений Проблемы управления и информатики
description	Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кроків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості 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 точок. Використовуючи даний метод, за скінчене число кроків можна отримати оптимальний розв’язок.
format	Article
author	Колечкина, Л.Н. Нагорная, А.М.
author_facet	Колечкина, Л.Н. Нагорная, А.М.
author_sort	Колечкина, Л.Н.
title	Условная оптимизация задачи с квадратичной функцией цели на множестве размещений
title_short	Условная оптимизация задачи с квадратичной функцией цели на множестве размещений
title_full	Условная оптимизация задачи с квадратичной функцией цели на множестве размещений
title_fullStr	Условная оптимизация задачи с квадратичной функцией цели на множестве размещений
title_full_unstemmed	Условная оптимизация задачи с квадратичной функцией цели на множестве размещений
title_sort	условная оптимизация задачи с квадратичной функцией цели на множестве размещений
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2020
topic_facet	Методы оптимизации и оптимальное управление
url	https://nasplib.isofts.kiev.ua/handle/123456789/208710
citation_txt	Условная оптимизация задачи с квадратичной функцией цели на множестве размещений / Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. — 2020. — № 2. — С. 46-61. — Бібліогр.: 31 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT kolečkinaln uslovnaâoptimizaciâzadačiskvadratičnojfunkciejcelinamnožestverazmeŝenij AT nagornaâam uslovnaâoptimizaciâzadačiskvadratičnojfunkciejcelinamnožestverazmeŝenij AT kolečkinaln umovnaoptimízacíâzadačízkvadratičnoûfunkcíêûcílínamnožinírozmíŝenʹ AT nagornaâam umovnaoptimízacíâzadačízkvadratičnoûfunkcíêûcílínamnožinírozmíŝenʹ AT kolečkinaln conditionaloptimizationofaproblemwithobjectivequadraticfunctiononasetofpermutations AT nagornaâam conditionaloptimizationofaproblemwithobjectivequadraticfunctiononasetofpermutations
first_indexed	2025-11-05T02:12:49Z
last_indexed	2025-11-06T02:07:39Z
_version_	1848004951991648256
fulltext	© Л.Н. КОЛЕЧКИНА, А.Н. НАГОРНАЯ, 2020 46 ISSN 0572-2691 УДК 519.85 Л.Н. Колечкина, А.Н. Нагорная УСЛОВНАЯ ОПТИМИЗАЦИЯ ЗАДАЧИ С КВАДРАТИЧНОЙ ФУНКЦИЕЙ ЦЕЛИ НА МНОЖЕСТВЕ РАЗМЕЩЕНИЙ Ключевые слова: оптимизация, математическая модель, квадратичная функ- ция, множество размещений, опорное решение, оптимальное решение. Введение Исследование задач комбинаторной оптимизации базируется на довольно широком спектре математических моделей, связанных с необходимостью решения различных важных практических проблем оптимального планирования, управления и проектирования [1–7]. В связи с этим в последнее время появи- лось много работ, посвященных исследованию задач комбинаторной оптими- зации на различных комбинаторных множествах и разработке новых подходов к их решению [8–15]. Интересной особенностью комбинаторных задач являются погружения в ев- клидово комбинаторное пространство. Исследованию комбинаторных задач в nR пространстве и разработке методов их решения, основанных на свойствах комбинаторных множеств, погруженных в евклидово пространство, посвящены работы [4, 5, 7, 10, 13]. Задачи комбинаторной оптимизации рассматриваются на разных комбина- торных множествах и с различными целевыми функциями [16–27]. Следует отме- тить, что класс задач нелинейного программирования значительно шире линейно- го и большое количество задач прикладного характера решается при моделирова- нии определенных процессов нелинейными функциями. Значительного внимания заслуживает квадратичная функция, которая является частным случаем нелиней- ной, представленной в виде суммы линейной и квадратичной функций. В [4] опи- саны некоторые приложения теории оптимизации квадратичных функций на ев- клидовых комбинаторных множествах. Ряд практических задач технико-экономического содержания моделируется задачами с квадратичными целевыми функциями, и значительное количество мо- делей разработаны как вспомогательные или промежуточные [4]. В связи с этим возникает необходимость оценить существующие методы решения и создать но- вые подходы и алгоритмы для решения задач комбинаторной оптимизации с не- линейными целевыми функциями [28–30]. В статье представлена условная оптимизационная задача с квадратичной функцией цели на множестве размещений. Здесь сформулирована постановка за- дачи и ее свойства, а также предлагается метод решения комбинаторной задачи с квадратичной функцией цели на множестве размещений и пример ее решения. При реализации метода находится первый опорный план и осуществляется проверка возможного его улучшения за счет сформулированных неравенств, налагаемых на элементы множества размещений. 1. Постановка задачи Пусть }...,,{ 1 n= — конечное множество различных элементов произ- вольной природы. Рассмотрим комбинаторное множество ,P порожденное  . Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 47 Определение 1 [4]. Множество P назовем евклидовым комбинаторным, если его элементами являются упорядоченные наборы элементов множества  . Обозначим }....,,2,1{ mIm = Тогда каждый элемент Pn = }...,,{ 1 пред- ставляет собой упорядоченный набор ....,,1,,},...,,{ 1 njJji mji n == (1) Примерами евклидовых комбинаторных множеств являются множества nP перестановок из n символов без повторений, множество nkP перестановок из n сим- волов, из которых k различных, множество n kP k размещений без повторений, множество n kP k размещений с повторениями и т.д. Отобразим множество P в арифметическое евклидово пространство [4]. Пусть }...,,{ 1 mM = — множество k различных действительных чисел. Установим взаимно-однозначное соответствие f между элементами множества  и M : ....,,2,1),(),( 1 miff iiii === − Осуществим биекцию множества P на подмножество .: EE f  Каждому элементу }...,,{ 1 n= вида (1) поставим в соответствие вектор n n Rxxx = )...,,( 1 по следующему правилу: ....,,2,1),(1 nifx i == (2) Перенумеруем элементы множества  . Поставим в соответствие множест- ву  множество номеров его элементов, т.е. положим }....,,1{ mJM m == Пусть P и имеет вид (2). Тогда ....,,1, njix jj == Рассмотрим случай, когда элементами множества  являются действитель- ные числа ....,,1 m Тогда элементу Ex вида (1) можно поставить в соответ- ствие вектор )...,,( 1 nxxx с координатами ....,,1,, njJix mjij j == В дальнейшем представим комбинаторные множества, порожденные дей- ствительными числами. Пусть n kP — множество n размещений без повторений, индуцируемое nk  различными символами из множества }....,,{ 1 k= Образ множества n kP при отображении в nR обозначим .n kE Всякая точка n kEx об- ладает тем свойством, что ее координаты принимают различные значения из множества действительных чисел },...,,{ 1 kM = т.е. ),...,,( 1 nxxx = где .,,, jiJjixxMx kjii  Соответственно, выполняется равенство .nnn n k EEE == Рассмотрим множество n kP n размещений с повторениями, индуцируемое k сим- волами из множества  . Образ множества n kP в nR обозначим .n kE Всякая точка n kEx обладает тем свойством, что ее координаты могут принимать любые зна- чения из множества действительных чисел },...,,{ 1 kM = т.е. ),...,,( 1 nxxx = где ....,,1, niMxi = Рассмотрим задачу оптимизации функционала на евклидовом комбинатор- ном множестве. Пусть на евклидовом комбинаторном множестве P задан функ- 48 ISSN 0572-2691 ционал ).(k Требуется найти точку ,* R такую, что ).(extr)( * =  P k При отображении множества P в евклидово пространство nR можно сформулировать задачу оптимизации некоторой функции )(x на множестве ,E причем каждой точке P будет соответствовать точка ,Ex такая, что ).()( = kx В резуль- тате имеем задачу математического программирования: требуется найти точку ,* Ex  такую, что ).(extr)( * xx Ex =  Далее задачу запишем в виде }\|)({extr:),( n k n k PDXaFPFZ  (3) при дополнительных условиях },)(\|{ bGxRPxD nn k = (4) где )()( xFa = при ,n kPa ,n kPx .)( 1 11 2  = == += n i n j jiij n j jj xxaxcxF (5) Таким образом, рассматривается условная оптимизация задачи с квадратич- ной функцией цели на множестве размещений. Согласно [27, 31] выпуклой оболочкой точек комбинаторного множества размещений является многогранник размещений ).( n kPM Многогранник разме- щений при )( kn  комбинаторно эквивалентен перестановочному многограннику размерности n ).( nPM Тогда X — непустое множество в ,nR которое обозна- чим следующим образом: ),(vert n kPMX = .conv nPM = Эквивалентность многогранников позволяет рассчитать количество транспози- ций элементов множества размещений в многограннике размещений [7]: . 2 )1(2 p nn Cn = − = (6) На основании изложенных выше свойств и утверждений предложен метод решения оптимизационной задачи с квадратичной функцией цели на множестве размещений. 2. Метод решения комбинаторной задачи с квадратичной функцией цели на множестве размещений Метод решения состоит из трех шагов. На первом шаге строится граф реше- ний, на втором — находится множество опорных решений с учетом выполнения ограничений задачи (3)–(5), на третьем — из множества опорных решений выби- рается оптимальное, при котором квадратичная целевая функция (5) достигает своего экстремального значения. Далее рассмотрим более подробно изложенный метод для предложенной задачи. Шаг 1. Построение графа поиска решений задачи. Задача (3)–(5) рассматри- вается на множестве размещений ,n kP естественно полагать, что допустимым Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 49 множеством решений является множество размещений. Граф G поиска решений представляет собой подмножества размещений, где отображаются точки множе- ства размещений, которые формируются при рассмотрении транспозиции элемен- тов множества. Из этого следует, что граф G является лишь частью многогран- ника размещений ).( n kPM Назовем данное подмножество множеством транспози- ций ,trS представленным в виде графа G (рис. 1). ).()( APSPMG n k trn k  (7) Рис. 1 С помощью формулы (6) вычисляем количество транспозиций элементов множества размещений. При рассмотрении каждой транспозиции элементов мно- жества размещений квадратичную функцию цели (5) необходимо представить в виде произведения двух сомножителей: ),...)(( kkjijiijjiij xaxaxaxxF +++−= (8) где ,...,,2,1 ki = ....,,2 kj = . Таким образом, на данном шаге составляются все возможные транспозиции в количестве ,p которые определяют дальнейшее представление множества точек размещений в виде перестановки соответствующих элементов (рис. 2). Данные точки представляют собой подграфы графа G и составляют подмножества мно- жества транспозиций trS (рис. 2). Рис. 2 Тогда множество транспозиций trS будет иметь вид ],...,,2,1[,...21 pqSSSS tr q trtrtr ==  (9) где tr qS — множество точек, представляющее собой подграфы графа .G Количество точек, которые формируют подграфы графа ,G т.е. принадле- жащих одной транспозиции, определяется выполнением условий сформирован- ных задач ,p которые рассматриваются на следующем шаге. Шаг 2. Нахождение опорного множества решений задачи. На данном шаге осуществляется нахождение множества опорных решений, которое состоит из не- рассмотренных на первом шаге точек множества размещений n kP и оптимального решения, которое принадлежит .trS Шаг 2.1. Составление задач, определяющих транспозиции элементов множе- ства размещений. Для каждой функции (8) с учетом ее экстремальности необхо- димо сформировать дополнительные ограничения. Таким образом, составляем p задач. x1 ↔ x2 x1 ↔ x3 x1 ↔ xk … … x2 ↔ x3 x3 ↔ xk xk–1 ↔xk (x1, x2,…, xk) xi ↔ xj ),...,,( 21 kxxx  … ),...,,( 21 kxxx  50 ISSN 0572-2691 Задача 1. :)...,,2(,1 kixx i = :21 xx  ),...)((extr 22121122112 kk xaxaxaxxF +++−=                  − kk k xx xx xx xx xx )( ... ,)( ,)( ... ,)( ,)( 1 32 1 31 21 … … … . Задача 2. ),...,,3(,2 kixx k = );...)((extr 2221122 kkkkkk xaxaxaxxF +++−= (10)                  − kk k xx xx xx xx xx )( ... ,)( ,)( ... ,)( ,)( 1 32 1 31 21 … … … . Задача p. ,1 kk xx − )....)((extr 11121211111 kkkkkkkkkkkk xaxaxaxaxxF −−−−−−− +++−=                  − .)( ... ,)( ,)( ... ,)( ,)( 1 32 1 31 21 kk k xx xx xx xx xx Шаг 2.2. Нахождение множества опорных решений задачи. При решении каждой задачи (10) на множестве размещений n kP с учетом дополнительных ограничений формируются соответствующие определенным подграфам (рис. 2) подмножества транспозиций вида tr qS ,cl q con q op q tr q SSSS = ],...,,2,1[ pq = (11) где op qS — подмножество точек подграфа графа ,G которые удовлетворяют ограничениям; con qS — подмножество точек подграфа графа ,G которые не удо- Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 51 влетворяют ограничениям; cl qS — подмножество отсеченных точек подграфа графа ,G не принадлежащих двум предыдущим подмножествам. Тогда множество транспозиций ,trS представленное в виде графа ,G будет иметь вид ,clconoptr SSSS = (12) где ,...21 op p opopop SSSS = ];...,,2,1[ pq = ;...21 con p conconcon SSSS = =clS ....21 cl p clcl SSS = Возможен вариант ,0=opS когда нет точек множества допустимых решений, ко- торые удовлетворяли бы (4) и (8) одновременно. На каждом подграфе графа G осуществляется проверка дополнительных ограничений (4) задачи (3)–(5). Следует учесть, что при проверке первой точки подграфов графа G необходимо сформировать ограничения вида       = = − − .)(),...,,,( ......,........................................ ,)(),...,,,( 121 11 11 1 1 2 1 11 ii i n i n ii i nn bbxxxxg bbxxxxg (13) Если рассматриваемая точка удовлетворяет всем ограничениям (4), то составляем необходимые условия для приростов ограничений:      −= −= .,)( .....,.............................. ,,)( 1111111 bbbbg bbbbg iiiiii (14) Для всех последующих точек расчета прирост ограничений находится по формуле: =−= 12 ggg ).()( 1212 g i g ji g j g ij xxcxxc −+− (15) Для нахождения прироста f целевой функции (5) нужно использовать необ- ходимую форму целевой функции в зависимости от транспозиции элементов в рассматриваемой точке подграфов графа G (8). Если ограничения не выполняются, но приросты целевой функции возрас- тают (при максимизации (5)) или убывают (при минимизации (5)), то проверка продолжается, в противном случае необходимо перейти к следующей задаче вида (10), т.е. на следующий подграф графа G cогласно транспозиции элементов. Следует также отметить, что если ограничения выполняются, но целевая функция убывает (при максимизации) или возрастает (при минимизации), то дальнейшая проверка точек множества также продолжается. Поиск опорного решения прекращается только в случае невыполнения огра- ничений (4) и неудовлетворения экстремальности функции цели (5). Согласно (7) можно утверждать, что существуют нерассмотренные точки множества ,n kP которые не принадлежат .trS Они будут образовывать подмно- жество допустимых решений: .\)( trn k as SAPS = (16) Множество acS является подмножеством n kP соответственно .astrn k SSP = (17) 52 ISSN 0572-2691 Из множества opS выбирается точка экстремума ,extrx при которой ).(extr extrxF Тогда множество опорных решений supS будет иметь вид .extr sup xSS as = (18) Следовательно, для нахождения множества опорных решений необходимо найти наилучшую точку множества opS и рассмотреть все точки множества ,n kP которые не принадлежат графу .G Шаг 3. Нахождение оптимального решения. Для нахождения оптимального решения необходимо взять точку extrx и поочередно рассмотреть все точки мно- жества ,acS которые находятся левее или правее данной точки, в зависимости от экстремума функции (5). Согласно определению множество размещений учиты- вает порядок следования элементов, поэтому нет необходимости в упорядочении точек множества .acS Следует отметить, что при рассмотрении точек множества acS значение це- левой функции и ограничений вычисляется только для первой точки, для всех по- следующих необходимо использовать формулы (8),(15), т.е. необходимо выпол- нение шага 2.2. Далее рассмотрим примеры, для решения которых будет использован изло- женный метод. Пример. Необходимо найти максимальное значение квадратичной функции вида 424314341321 2 4 2 3 2 2 2 1 7,02,05235,0357)( xxxxxxxxxxxxxxxxxF +++−++−−= на мно- жестве размещений ,4 5P которое образовано с помощью чисел )5,4,3,2,1(=A с учетом следующих линейных ограничений:        ++−= +++−= +++−= +++−= .7112425 ,566543 ,40724 ,25532 43214 43213 43212 43211 xxxxg xxxxg xxxxg xxxxg Решение. Согласно (6), .6=p Соответственно, необходимо рассмотреть транспозиции элементов ,21xx ,31xx ,41xx ,32xx ,42xx .43xx Граф G поиска решений будет иметь вид, представленный на рис. 3. Рис. 3 Для первой транспозиции 21xx составляем квадратичную функцию ).2,07,21212)(( 434212112 xxxxxxxF +−+−= С учетом максимизации функции цели формируем условия дальнейшего по- иска максимального значения:       →  . min, , 43 4 21 xx x xx x1 ↔ x2 x1 ↔ x3 x1 ↔ x4 x2 ↔ x3 x2 ↔ x4 x3 ↔x4 (x1, x2, x3, x4, x5) Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 53 Тогда подграф 12G графа G будет иметь вид, как на рис. 4. Рис. 4 С учетом рис. 4 необходимо рассмотреть точки множества размещений (табл. 1). Таблица 1 № ),,,( 4213 xxxx ),,,( 4231 xxxx ),,,( 4231 xxxx 1 )2,5,3,4( )2,4,3,5( )2,3,4,5( 2 )1,5,3,4( )1,4,3,5( )1,3,4,5( 3 )1,5,2,4( )1,4,2,5( )1,2,4,5( 4 )1,5,2,3( )1,3,2,5( )1,2,3,5( 5 )1,4,2,3( )1,3,2,4( )1,2,3,4( Осуществим проверку точек вида ).,,,( 4213 xxxx Точка :)2,5,3,4( первое условие 2520)2,5,3,4(1 =g не выполняется, функ- ция цели .20,220)2,5,3,4( =f Тогда .51 g Рассмотрим следующую точку :)1,5,3,4( первое условие = )1,5,3,4(1g 55−= не выполняется, а функция цели убывает, поскольку прирост = )1,5,3,4(f 06,24 −= . Следовательно, нет необходимости рассматривать точки, меньше точки ),1,5,3,4( т.е. ниже данной на подграфе ,12G согласно табл. 1, они будут входить во множество отсеченных точек при транспозиции .21xx Аналогично проверим точки вида ).,,,( 4231 xxxx Точка :)2,4,3,5( первое условие 2515)2,4,3,5(1 =g не выполняется, ,101 g функция цели .20,296)2,4,3,5( =f Точка :)1,4,3,5( первое условие 105)1,4,3,5(1 −=g не выполняется, функ- ция цели убывает .06,17)1,4,3,5( −= f Следовательно, точки, меньше точки ),1,4,3,5( т.е. ниже данной на подграфе ,12G согласно табл. 1, будут входить во множество отсеченных точек при транс- позиции .21xx Для точек вида ),,,( 4231 xxxx имеем следующее. Точка )2,3,4,5( : первое условие 2513)2,3,4,5(1 =g не выполняется, ,121 g а функция цели равна .60,271)2,3,4,5( =f Точка :)1,3,4,5( 125)1,3,4,5(1 −=g не выполняется, а функция цели убывает .03,12)1,3,4,5( −= f Точки, меньше точки )1,3,4,5( , т.е. ниже данной на подграфе ,12G согласно табл. 1, будут входить в подмножество отсеченных точек при транспозиции .21xx Подмножество отсеченных точек при транспозиции 21xx будет иметь такой вид: =clS12 ),1,5,2,4(( ),1,5,2,3( ),1,4,2,3( ),1,4,2,5( ),1,3,2,5( ),1,3,2,4( ),1,2,4,5( ),1,2,3,5( )).1,2,3,4( x1 ↔ x2 ),,,( 4213 xxxx ),,,( 4231 xxxx ),,,( 4321 xxxx 54 ISSN 0572-2691 Подмножество оптимальных точек .012 = op S Подмножество точек, не удовлетворяющих ограничениям, — =conS12 ),2,5,3,4(( ),1,5,3,4( ),2,4,3,5( ),1,4,3,5( ),2,3,4,5( )).1,3,4,5( Для второй транспозиции 31xx составляем квадратичную функцию ).71010)(( 4313113 xxxxxF −+−= Формируем условия дальнейшего поиска максимального значения:     →  .min , 4 31 x xx Согласно изложенному выше условию необходимо рассмотреть точки под- графа 13G (рис. 5). Рис. 5 Точки ),,,,( 4213 xxxx ),,,( 4231 xxxx рассмотрены при транспозиции 21xx в подграфе ,12G поэтому необходимо рассмотреть только точки вида :),,,( 4312 xxxx ),2,3,5,4( ),1,3,5,4( ),1,2,5,4( ),1,2,5,3( ).1,2,4,3( Осуществим проверку точек ).,,,( 4312 xxxx Точка :)2,3,5,4( первое условие 2511)2,3,5,4(1 =g не выполняется,  1g ,14 функция цели .8,167)2,3,5,4( =f Рассмотрим следующую точку множества. Точка :)1,3,5,4( 145)1,3,5,4(1 =g не выполняется, а функция цели убы- вает .04,14)1,3,5,4( −= f Точки, меньше точки ),1,3,5,4( т.е. ниже данной на подграфе ,13G нет необ- ходимости рассматривать, они будут входить во множество отсеченных точек при транспозиции элементов .31xx Подмножество отсеченных точек при транспозиции элементов 31xx будет иметь вид: =clS13 ),1,2,5,4(( ),1,2,5,3( )).1,2,4,3( Тогда ,013 = op S =conS13 ),2,3,5,4(( )).1,3,5,4( Для транспозиции 41xx квадратичная функция имеет вид: −= )( 4114 xxF ).357,05,65,6( 323241 xxxxxx +−−+ Формируем условия дальнейшего поиска максимального значения         → →  . min, max, , 42 3 1 41 xx x x xx x1 ↔ x3 ),,,( 4321 xxxx ),,,( 4231 xxxx ),,,( 4312 xxxx Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 55 Необходимо рассмотреть точки подграфа 14G (рис. 6). Рис. 6 Тогда :),,,( 3241 xxxx ),4,2,3,5( ),4,1,3,5( ),4,1,2,5( ),3,1,2,5( ).3,1,2,4( Точка :)4,2,3,5( первое условие 2519)4,2,3,5(1 =g не выполняется, ,61 g функция цели .4,232)4,2,3,5( =f Точка :)4,1,3,5( 63)4,1,3,5(1 −=g не выполняется, а функция цели убы- вает .04,60)1,3,5,4( −= f Точки, меньше точки ),4,1,3,5( т.е. ниже данной на подграфе ,14G нет необходимости рассматривать, они будут входить в подмножество отсеченных точек при транспозиции :41xx =clS14 ),4,1,2,5(( ),3,1,2,5( )).3,1,2,4( Тогда ,014 = op S =conS14 ),4,2,3,5(( )).4,1,3,5( Для транспозиции 32xx составляем квадратичную функцию =23F ).3,42,022)(( 4413123 xxxxxxx +++−= Формируем условия дальнейшего поиска максимального значения:    →  .max , 4 23 x xx Подграф 23G для данной транспозиции будет иметь вид, представленный на рис. 7. Рис. 7 С учетом составленного условия необходимо рассмотреть точки подграфа 23G (табл. 2). Таблица 2 № ),,,( 1234 xxxx ),,,( 2134 xxxx ),,,( 2314 xxxx 1 )5,4,3,2( )5,4,2,3( )5,3,2,4( 2 )5,4,3,1( )5,4,1,3( )5,3,1,4( 3 )5,4,2,1( )5,4,1,2( )5,2,1,4( 4 )5,3,2,1( )5,3,1,2( )5,2,1,3( 5 )4,3,2,1( )4,3,1,2( )4,2,1,3( Проверим точки ).,,,( 1234 xxxx Точка :)5,4,3,2( ,2536)5,4,3,2(1 =g ,4038)5,4,3,2(2 =g =)5,4,3,2(3g ,5656 = 7180)5,4,3,2(4 =g выполняются, функция цели .118)5,4,3,2( =f Тогда ,111 −g ,22 g ,03 g .94 −g Точка :)5,4,3,1( 112)5,4,3,1(1 −=g выполняется, 24)5,4,3,1(2 =g не выполняется, а функция цели убывает, поскольку прирост .51)5,4,3,1( −= f x1 ↔ x4 ),,,( 3241 xxxx x2 ↔ x3 ),,,( 1234 xxxx ),,,( 2134 xxxx ),,,( 2314 xxxx 56 ISSN 0572-2691 Следовательно, нет необходимости рассматривать точки, меньше точки ),5,4,3,1( т.е. ниже данной на подграфе ,23G согласно табл. 2, они будут форми- ровать множество отсеченных точек при данной транспозиции. Проверим точки вида ).,,,( 2134 xxxx Точка :)5,4,2,3( ,2533)5,4,2,3(1 =g ,4033)5,4,2,3(2 =g =)5,4,2,3(3g ,5649 = 7187)5,4,2,3(4 =g выполняются, функция цели .5,168)5,4,2,3( =f Тогда ,111 −g ,72 g ,73 g .164 −g Точка :)5,4,1,3( ,1111 −−=g ,712 −=g ,743 =g 1624 −=g вы- полняются, функция цели .5,24)5,4,1,3( −= f Поскольку прирост функции убы- вает, а все ограничения выполняются, следует продолжить поиск решения. Необ- ходимо учесть, что ,101 −g ,82 g ,33 g .184 −g Точка :)5,4,1,2( ,1021 −=g ,842 =g ,333 =g 1854 −−=g выполняются, функция цели .41)5,4,1,2( −= f Поскольку прирост функции убывает, а все ограничения выполняются, следует продолжить поиск решения. Необходимо учесть, что ,121 −g ,42 g ,03 g .134 −g Точка :)5,3,1,2( ,1231 −−=g ,422 −=g ,053 −=g 1344 −−=g выполняются, функция цели .12)5,3,1,2( −= f Поскольку прирост функции убывает, а все ограничения выполняются, следует продолжить поиск решения. Необходимо учесть, что ,91 −g ,22 g ,53 g .94 −g Точка :)4,3,1,2( ,951 −−=g ,272 −=g 563 −=g выполняются, 9124 −−=g не выполняется, функция цели .4,17)4,3,1,2( −= f Данная точ- ка не является оптимальной. Подмножество отсеченных точек при транспозиции :, 32 xx =clS23 ),5,4,2,1(( ),5,3,2,1( ),4,3,2,1( ),5,2,1,3( )).4,2,1,3( = op S23 ),5,4,3,2(( ),5,4,2,3( ),5,4,1,3( ),5,4,1,2( ),5,3,1,2( ),5,3,2,4( )).5,3,1,4( =conS23 ),5,4,3,1(( ),4,3,1,2( )).5,2,1,4( Для транспозиции 42, xx составляем квадратичную функцию ).8,2525,55,5)(( 3131422424 xxxxxxxxF −+−+−= Условия дальнейшего поиска максимального значения имеют вид      → →  .min max, , 1 4 24 x x xx Согласно изложенным выше условиям необходимо рассмотреть точки под- графа :24G ),,,,( 1324 xxxx ),,,,( 1234 xxxx ),,,( 3124 xxxx (рис. 8). Рис. 8 x2 ↔ x4 ),,,( 1324 xxxx ),,,( 1234 xxxx ),,,( 3124 xxxx Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 57 Точки ),,,( 1234 xxxx рассмотрены при транспозиции элементов ,32xx по- этому рассмотрим точки согласно табл. 3. Таблица 3 № ),,,( 1324 xxxx ),,,( 3124 xxxx 1 )5,3,4,2( )5,2,4,3( 2 )5,3,4,1( )5,1,4,3( 3 )5,2,4,1( )5,1,4,2( 4 )5,2,3,1( )5,1,3,2( 5 )4,2,3,1( )4,1,3,2( Проверим точки вида ).,,,( 1324 xxxx Точка :)5,3,4,2( ,2534)5,3,4,2(1 =g ,4037)5,3,4,2(2 =g =)5,3,4,2(3g ,5655 = 7174)5,3,4,2(4 =g выполняются, функция цели .5,80)5,3,4,2( =f Тогда ,91 −g ,32 g ,13 g .34 −g Точка :)5,3,4,1( 921 −=g выполняется, 342 =g не выполняется, а функция цели убывает, поскольку прирост .50)5,3,4,1( −= f Поэтому нет необ- ходимости рассматривать точки, меньше данной, они будут формировать множе- ство отсеченных точек при данной транспозиции. Осуществим проверку точек вида ).,,,( 3124 xxxx Точка :)5,2,4,3( ,2529)5,2,4,3(1 =g ,4031)5,2,4,3(2 =g =)5,2,4,3(3g ,5647 = 7175)5,2,4,3(4 =g выполняются, функция цели .5,95)5,2,4,3( =f Тогда ,41 −g ,92 g ,93 g .44 −g Точка :)5,1,4,3( ,431 −−=g ,922 −=g ,953 −=g 444 −−=g выполняются, прирост .55)5,1,4,3( −= f Тогда ,11 −g ,112 g ,143 g .04 g Поскольку все ограничения выполняются, необходимо рассмотреть сле- дующую точку множества. Точка :)5,1,4,2( ,121 −=g ,1142 =g 1433 =g выполняются, = 4g 05 −= не выполняется, прирост убывает ,38)5,1,4,2( −= f поэтому нет смысла в рассмотрении точек, меньше данной. Соответственно, =clS24 ),5,2,4,1(( ),5,2,3,1( ),4,2,3,1( ),5,1,3,2( )),4,1,3,2( = op S24 ),5,3,4,2(( ),5,2,4,3( )),5,1,4,3( =conS24 ),5,3,4,1(( )).5,1,4,2( Для транспозиции 43, xx составляем квадратичную функцию ).7,0235,35,3)(( 2121434334 xxxxxxxxF −++−−−= . Формируем условия дальнейшего поиска максимального значения:     →  .max , 1 43 x xx Согласно изложенному выше условию необходимо рассмотреть точки мно- жества подграфа :34G ),,,,( 2431 xxxx ),,,,( 4231 xxxx ),,,( 4321 xxxx (рис. 9). Рис. 9 x3 ↔ x4 ),,,( 2431 xxxx ),,,( 4231 xxxx ),,,( 4321 xxxx 58 ISSN 0572-2691 Точки ),,,,( 4231 xxxx ),,,( 4321 xxxx рассмотрены при транспозиции .21xx Поэтому рассматриваются только точки вида :),,,( 2431 xxxx ),3,4,2,5( ),3,4,1,5( ),2,4,1,5( ),2,3,1,5( ).2,3,1,4( Точка :)3,4,2,5( первое условие 2519)3,4,2,5(1 =g не выполняется, ,61 g функция цели .7,277)3,4,2,5( =f Точка :)3,4,1,5( 61)3,4,1,5(1 −=g не выполняется, а функция цели убы- вает .01,47)3,4,1,5( −= f Точки, которые расположены ниже точки )3,4,1,5( в подграфе ,34G нет необходимости рассматривать, они будут входить в подмножество отсеченных точек при транспозиции :, 43 xx =clS34 ),2,4,1,5(( ),2,3,1,5( )).2,3,1,4( Получено ,034 = op S =conS34 ),3,4,2,5(( )).3,4,1,5( Рассмотрим подмножество ).( 342423141312 opopopopopopop ZZZZZZZ = В данном множестве максимальное значение целевая функция принимает в точке ),5,3,2,4( .5,203max =F Данная точка является оптимальной на множестве транспозиций элементов, поэтому необходимо проверить, нет ли точек на множе- стве вида ,acS которые могли давать большее значение целевой функции. Необходимо рассмотреть точку ),2,1,3,4( которая принадлежит общему множеству acS и находится правее точки ).5,3,2,4( Точка :)5,3,2,4( 25241 =g не выполняется, а функция возрастает ,70,208)5,3,2,4( =f поэтому необходимо рассмотреть следующую точку мно- жества .acS Точка :)2,1,3,4( 0161 −=g не выполняется, ;9,106)2,1,3,4( −= f нет необходимости в дальнейшем рассмотрении следующих точек. Ответ: Оптимальным решением является точка ),5,3,2,4( при которой целе- вая функция принимает максимальное значение .5,203max =F Заключение В статье рассмотрена оптимизационная задача на множестве размещений с квадратичной целевой функцией и предложен метод ее решения. Представленный метод состоит из трех шагов. На первом осуществляется по- строение дерева решений, ветки ветвления которого представляют собой транспо- зиции соответствующих элементов множества размещений .n kP Таким образом, на данном шаге составляются все возможные транспозиции в количестве ,p ко- торые определяют дальнейшее представление множества точек размещений в ви- де перестановки соответствующих элементов. Данные точки представляют собой подграфы графа G и составляют подмножества множества транспозиций .trS На втором шаге составляются задачи, целевые функции которых являются квадратичными и представляются с учетом рассматриваемых транспозиций. При решении каждой задачи рассматриваются op qS — подмножество точек подграфа графа ,G которые удовлетворяют ограничениям; con qS — подмножество точек подграфа графа ,G которые не удовлетворяют ограничениям; cl qS — подмножество Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 59 отсеченных точек подграфа графа ,G не принадлежащих к двум предыдущим. Данные подмножества в совокупности составляют множества транспозиций .trS На каждом подграфе графа G проверяются дополнительные ограничения (4) зада- чи (3)–(5). При этом вычисляются лишь приросты ограничений и целевой функ- ции с помощью необходимых формул. Множество опорных решений будет состо- ять из точки экстремума ,extrx при которой )(extr extrxF , и множества точек раз- мещения, которые не были рассмотрены при транспозиции элементов .acS На третьем шаге осуществляется поиск оптимального решения задачи путем сравнения приростов целевой функции точки extrx и точек множества .acS В статье предложен числовой пример реализации данного метода. Из 120 то- чек множества размещений найдено оптимальное решение при рассмотрении 27 и отсечении 28 точек за 18 шагов. Дальнейшие исследования будут направлены на адаптацию данного метода на других комбинаторных множествах с дробно-линейной функцией цели. ABSTRACTS Л.М. Колєчкіна, А.М. Нагірна УМОВНА ОПТИМІЗАЦІЯ ЗАДАЧІ З КВАДРАТИЧНОЮ ФУНКЦІЄЮ ЦІЛІ НА МНОЖИНІ РОЗМІЩЕНЬ Сформульовано постановку задачі оптимізації з квадратичною функцією цілі на комбінаторній множині розміщень і запропоновано метод її розв’язування з урахуванням виконання умов задач, сформованих при розгляді транспозицій елементів множини розміщень. Представлений метод складається з трьох кро- ків. На першому здійснюється побудова дерева рішень, гілки розгалуження якого є транспозиції відповідних елементів множини розміщень. На даному етапі складаються всі можливі транспозиції в кількості ,p які визначають по- дальше представлення множини точок розміщень у вигляді перестановки від- повідних елементів. З даних точок здійснюється побудова підграфів графа G і складаються підмножини множини транспозицій. Необхідно відзначити, що граф G є лише частиною багатогранника розміщень ).( n kPM На другому кроці складаються задачі, цільові функції яких є квадратичними і представляються з урахуванням розглянутих транспозицій. При розв’язуванні кожної задачі фор- мується множина транспозицій елементів, яка складається з op qS (підмножина точок підграфа графа G , які задовольняють обмеженням); con qS (підмножина точок підграфа графа G , які не задовольняють обмеженням); cl qS (підмножина відсічених точок підграфа графа G , що не належать до двох попередніх підм- ножин). На кожному підграфі графа G здійснюється перевірка додаткових об- межень (4) задачі (3)–(5). При цьому обчислюються лише прирости обмежень і цільової функції за допомогою необхідних формул. Множина опорних розв’язків буде складатися з точки ,extrx при якій )(extr extrxF , і множини точок розміщення acS , які не були розглянуті при транспозиції елементів, але нале- жать багатограннику розміщень ).( n kPM На третьому кроці здійснюється по- шук оптимального розв’язку задачі шляхом порівняння приростів квадратичної цільової функції точки extrx і точок множини acS . Запропоновано числовий приклад реалізації даного методу. З 120 точок множини розміщень знайдено оптимальний розв’язок за 18 кроків при розгляді 27 і відсіканні 28 точок. Використовуючи даний метод, за скінчене число кроків можна отримати оптимальний розв’язок. 60 ISSN 0572-2691 Ключові слова: оптимізація, математична модель, квадратична функція, множина розміщень, опорний розв’язок, оптимальне рішення. L.N. Koliechkina, A.N. Nahirna CONDITIONAL OPTIMIZATION OF A PROBLEM WITH OBJECTIVE QUADRATIC FUNCTION ON A SET OF PERMUTATIONS 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 op- timization 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 corre- sponding 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. Sub- graphs 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 ).( n kPM At the second step, tasks are compiled whose objective functions are quadratic and are presented taking into account the transposi- tions under consideration. When solving each problem, a set of transpositions of ele- ments is formed, which consists of op qS — subset of points in the graph G subgraph that satisfy the constraints; con qS — subset of points in a subgraph of a graph G that do not satisfy the constraint; cl qS — subset of the cut-off points of a graph G sub- graph 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 extrx at which )(extr extrxF and the set of partial permutation points acS , which were not considered during the transposition of elements, but belong to the polyhedron of permutations ).( n kPM At the third step, the search for the optimal solution to the problem is carried out by comparing the increments of the quadratic objective func- tion of the point extrx and the points of the set acS . The article offers a numerical example of the implementation of this method. From 120 points of the set of permu- tations, 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. Keywords: optimization, mathematical model, quadratic function, partial permuta- tion, reference solution, optimal solution. REFERENCES 1. Sergienko I.V., Shilo V.P. Modern approaches to solving complex discrete optimization prob- lems. Journal of Automation and Information Sciences. 2016. 48, N 1. P. 15–24. 2. Згуровский М.З., Павлов А.А. Труднорешаемые задачи комбинаторной оптимизации в планировании и принятии решений. К. : Наук. думка, 2016. 715 с. 3. Colbourn C.J., Dinitz J.H. Handbook of combinatorial designs, second edition. London; New York : CRC Press, 2010. 784 p. 4. Яковлев С.В., Гиль Н.И., Комяк В.М., Аристов И.В. Элементы теории геометрического проектирования. Под ред. В.Л. Рвачева. К. : Наук. думка, 1995. 241 с. 5. Korte B., Vygen J. Combinatorial optimization: theory and algorithms. Heidelberg; New York : Springer, 2018. 698 p. 6. Pardalos P.M., Du D-Z., Graham R.L. Handbook of combinatorial optimization. New York : Springer, 2013. 3409 p. 7. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: algorithms and complexity. Mineo- la : Dover Publications, 2013. 528 p. Международный научно-технический журнал «Проблемы управления и информатики», 2020, № 2 61 8. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization prob- lems. Optimization Methods and Applications. Butenko S. et al.(eds.). New York : Springer, 2017. P. 239–250. 9. Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних множинах: методи дослідження та розв’язання. К. : Наук. думка, 2009. 266 с. 10. Semenova N.V., Kolechkina L.N., Nagornaya A.N. Solution and investigation of vector problems of combinatorial optimization on a set of permutations. Journal of Automation and Information Sciences. 2008. 40, N 12. P. 67–80. 11. Kolechkina L.N., Dvirna O.A., Nagornaya A.N. Modified coordinate method to solve multicrite- ria optimization problems on combinatorial configurations. Cybernetics and Systems Analysis. 2014. 59, N 4. P. 620–626. 12. Pichugina O.S., Yakovlev S.V. Continuous representations and functional extensions in combina- torial optimization. Cybernetics and Systems Analysis. 2016. 52, N 6. P. 921–930. 13. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in . n R Cybernetics and Systems Analysis. 1991. 27, N 4. P. 562–567. 14. Koliechkina L., Pichugina O. A horizontal method of localizing values of a linear function in permuta- tion-based optimization. In Le Thi H.A., Le H.M., Pham Dinh T. (eds.) Optimization of Complex Sys- tems: theory, models, algorithms and applications. London : Springer, 2020. P. 355–364. 15. Yakovlev S.V., Pichugina O.S. Properties of combinatorial optimization problems over polyhe- dral-spherical sets. Cybernetics and Systems Analysis. 2018. 54, N 1. P. 99–109. 16. Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: theory and applications. In 2017 IEEE First Ukrainian Conference on Electrical and Computer Engeneering (UKRCON 2017). Proceedings. Kyiv. 2017. P. 1167–1175. 17. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distrib- uted masses. Energomashinostroyenie. 1982. N 2. P. 4–5. 18. Yakovlev S.V., Grebennik I.V. Localization of solutions of some problems of nonlinear integer optimization. Cybernetics and Systems Analysis. 1993. 29, N 5. P. 419–426. 19. Semenova N.V., Kolechkina L.N., Nagirna A.N. An approach to solving discrete vector optimiza- tion problems over a combinatorial set of permutations. Cybernetics and Systems Analysis. 2008. 44, N 3. P. 441–451. 20. Semenova N.V., Kolechkina L.N., Nagornaya A.N. Solution and investigation of vector problems of combinatorial optimization on a set of polypermutations. Journal of Automation and Infor- mation Sciences. 2008. 40, N 12. P. 27–42. 21. Semenova N.V., Kolechkina L.N. A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements. Cybernetics and Systems Analysis. 2009. 45, N 3. P. 438–445. 22. Semenova N.V., Kolechkina L.N., Nagornaya A.N. On approach to solving vector problems with fractionally linear functions of the criteria on the combinatorial set of arrangements. Journal of Automation and Information Sciences. 2010. 42, N 2. P. 67–80. 23. Kolechkina L.N., Dvirna O.A. Solving extremum problems with linear fractional objective func- tions on the combinatorial configuration of permutations under multicriteriality. Cybernetics and Systems Analysis. 2017. 53, N 4. P. 590–599. 24. Колєчкіна Л.М., Нагірна А.М. Комбінаторна математична модель багатокритеріальної оп- тимізації при побудові комп’ютерних мереж. Математичні машини і системи. 2016. № 6. С. 26–41. 25. Донець Г.П., Колєчкіна Л.М. Екстремальні задачі на комбінаторних конфігураціях. Полта- ва : РВВ ПУЕТ, 2011. 309 с. 26. Колечкина Л.Н., Нагорная А.Н., Семенов В.В. Метод решения задачи условной опти- мизации на комбинаторном множестве размещений. Международный научно-технический журнал «Проблемы управления и информатики». 2019. № 4. С. 62–72. 27. Стоян Ю.Г., Яковлев C.В., Пичугина О.С. Евклидовы комбинаторные конфигурации: мо- нография. Харьков : Константа, 2017. 404 с. 28. Yakovlev S.V. On some classes of spatial configurations of geometric objects and their formali- zation. Journal of Automation and Information Sciences. 2018. 50, N 9. P. 38–50. 29. Yakovlev S.V. Formalization of spatial configuration optimization problems with a special func- tion class. Cybernetics and Systems Analysis. 2019. 55, N 4. P. 512–523. 30. Yakovlev S., Pichugina O., Yarovaya O. Polyhedral spherical configuration in discrete optimiza- tion. Journal of Automation and Information Sciences. 2019. 51, N 1. P. 38–50. 31. Yemelichev V.A., Kovalev V.A., Kravtsov M.K. Polytopes, graphs and optimisation. Cambrid- ge : Cambridge University Press, 1984. 432 p. Получено 25.10.2019 https://link.springer.com/search?facet-creator=%22N.+V.+Semenova%22 https://link.springer.com/search?facet-creator=%22L.+N.+Kolechkina%22 https://link.springer.com/search?facet-creator=%22A.+N.+Nagirna%22 https://link.springer.com/article/10.1007/s10559-008-9016-x https://link.springer.com/article/10.1007/s10559-008-9016-x https://link.springer.com/search?facet-creator=%22N.+V.+Semenova%22 https://link.springer.com/search?facet-creator=%22L.+N.+Kolechkina%22 https://link.springer.com/article/10.1007/s10559-009-9110-8 https://link.springer.com/article/10.1007/s10559-009-9110-8

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

Institution

Ähnliche Einträge