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

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

Рассмотрена постановка задачи оптимизации на комбинаторном множестве размещений и предложен метод ее решения с учетом выполнения условий, налагаемых на приросты ограничений и целевой функции. Метод состоит из трех шагов, где на начальном этапе строятся матрицы нормализации и соответствия, которые об...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Проблемы управления и информатики
Datum:2019
Hauptverfasser: Колечкина, Л.Н., Нагорная, А.Н., Семенов, В.В.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schlagworte:
Методы оптимизации и оптимальное управление
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/180820
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:Метод решения задачи условной оптимизации на комбинаторном множестве размещений / Л.Н. Колечкина, А.Н. Нагорная, В.В. Семенов // Проблемы управления и информатики. — 2019. — № 4. — С. 62-72. — Бібліогр.: 38 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-180820
record_format dspace
spelling Колечкина, Л.Н.
Нагорная, А.Н.
Семенов, В.В.
2021-10-20T11:59:55Z
2021-10-20T11:59:55Z
2019
Метод решения задачи условной оптимизации на комбинаторном множестве размещений / Л.Н. Колечкина, А.Н. Нагорная, В.В. Семенов // Проблемы управления и информатики. — 2019. — № 4. — С. 62-72. — Бібліогр.: 38 назв. — рос.
0572-2691
https://nasplib.isofts.kiev.ua/handle/123456789/180820
519.85
Рассмотрена постановка задачи оптимизации на комбинаторном множестве размещений и предложен метод ее решения с учетом выполнения условий, налагаемых на приросты ограничений и целевой функции. Метод состоит из трех шагов, где на начальном этапе строятся матрицы нормализации и соответствия, которые обеспечивают преобразование элементов множества размещений в необходимую форму для целевой функции и заданных ограничений. Второй шаг заключается в нахождении первого опорного развязку с учетом свойства множества размещений. Третий шаг метода обеспечивает нахождение оптимальных решений при непосредственном улучшении найденного опорного решения.
Розглянуто постановку задачі оптимізації на комбінаторій множині розміщень і запропоновано метод її розв’язання з урахуванням виконання умов, що накладаються на прирости обмежень і цільової функції. Метод складається з трьох кроків, де на початковому етапі будуються матриці нормалізації та відповідності, які забезпечують перетворення елементів множини розміщень в необхідну форму для цільової функції і заданих обмежень. Другий крок полягає в знаходженні першого опорного розв'язку з урахуванням властивості множини розміщень. Третій крок методу забезпечує знаходження оптимального розв’язку за безпосереднього покращення знайденого опорного розв’язку.
Defining a problem of optimization on a combinatorial set of arrangements is considered and presenting the method of its solution, taking into account satisfaction of the conditions imposed on gains of restrictions and objective function is proposed. The method consists of three steps where at the initial stage matrixes of normalization and compliance are built, which provide elements arrangement set transformation to a necessary form for criterion function and the defined restrictions. The second step consists in finding the first basic solution, taking into account property of arrangement set. It should be noted that for finding the first basic solution it is enough to calculate gains of restrictions. The third step of a method provides finding of an optimal solution at direct improvement of the found basic solution.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Проблемы управления и информатики
Методы оптимизации и оптимальное управление
Метод решения задачи условной оптимизации на комбинаторном множестве размещений
Метод вирішення задачі умовної оптимізації на комбінаторній множині розміщень
Method of solving the problem of conditional optimization on a combinatorial set of arrangements
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Метод решения задачи условной оптимизации на комбинаторном множестве размещений
spellingShingle Метод решения задачи условной оптимизации на комбинаторном множестве размещений
Колечкина, Л.Н.
Нагорная, А.Н.
Семенов, В.В.
Методы оптимизации и оптимальное управление
title_short Метод решения задачи условной оптимизации на комбинаторном множестве размещений
title_full Метод решения задачи условной оптимизации на комбинаторном множестве размещений
title_fullStr Метод решения задачи условной оптимизации на комбинаторном множестве размещений
title_full_unstemmed Метод решения задачи условной оптимизации на комбинаторном множестве размещений
title_sort метод решения задачи условной оптимизации на комбинаторном множестве размещений
author Колечкина, Л.Н.
Нагорная, А.Н.
Семенов, В.В.
author_facet Колечкина, Л.Н.
Нагорная, А.Н.
Семенов, В.В.
topic Методы оптимизации и оптимальное управление
topic_facet Методы оптимизации и оптимальное управление
publishDate 2019
language Russian
container_title Проблемы управления и информатики
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Метод вирішення задачі умовної оптимізації на комбінаторній множині розміщень
Method of solving the problem of conditional optimization on a combinatorial set of arrangements
description Рассмотрена постановка задачи оптимизации на комбинаторном множестве размещений и предложен метод ее решения с учетом выполнения условий, налагаемых на приросты ограничений и целевой функции. Метод состоит из трех шагов, где на начальном этапе строятся матрицы нормализации и соответствия, которые обеспечивают преобразование элементов множества размещений в необходимую форму для целевой функции и заданных ограничений. Второй шаг заключается в нахождении первого опорного развязку с учетом свойства множества размещений. Третий шаг метода обеспечивает нахождение оптимальных решений при непосредственном улучшении найденного опорного решения. Розглянуто постановку задачі оптимізації на комбінаторій множині розміщень і запропоновано метод її розв’язання з урахуванням виконання умов, що накладаються на прирости обмежень і цільової функції. Метод складається з трьох кроків, де на початковому етапі будуються матриці нормалізації та відповідності, які забезпечують перетворення елементів множини розміщень в необхідну форму для цільової функції і заданих обмежень. Другий крок полягає в знаходженні першого опорного розв'язку з урахуванням властивості множини розміщень. Третій крок методу забезпечує знаходження оптимального розв’язку за безпосереднього покращення знайденого опорного розв’язку. Defining a problem of optimization on a combinatorial set of arrangements is considered and presenting the method of its solution, taking into account satisfaction of the conditions imposed on gains of restrictions and objective function is proposed. The method consists of three steps where at the initial stage matrixes of normalization and compliance are built, which provide elements arrangement set transformation to a necessary form for criterion function and the defined restrictions. The second step consists in finding the first basic solution, taking into account property of arrangement set. It should be noted that for finding the first basic solution it is enough to calculate gains of restrictions. The third step of a method provides finding of an optimal solution at direct improvement of the found basic solution.
issn 0572-2691
url https://nasplib.isofts.kiev.ua/handle/123456789/180820
citation_txt Метод решения задачи условной оптимизации на комбинаторном множестве размещений / Л.Н. Колечкина, А.Н. Нагорная, В.В. Семенов // Проблемы управления и информатики. — 2019. — № 4. — С. 62-72. — Бібліогр.: 38 назв. — рос.
work_keys_str_mv AT kolečkinaln metodrešeniâzadačiuslovnoioptimizaciinakombinatornommnožestverazmeŝenii
AT nagornaâan metodrešeniâzadačiuslovnoioptimizaciinakombinatornommnožestverazmeŝenii
AT semenovvv metodrešeniâzadačiuslovnoioptimizaciinakombinatornommnožestverazmeŝenii
AT kolečkinaln metodviríšennâzadačíumovnoíoptimízacíínakombínatorníimnožinírozmíŝenʹ
AT nagornaâan metodviríšennâzadačíumovnoíoptimízacíínakombínatorníimnožinírozmíŝenʹ
AT semenovvv metodviríšennâzadačíumovnoíoptimízacíínakombínatorníimnožinírozmíŝenʹ
AT kolečkinaln methodofsolvingtheproblemofconditionaloptimizationonacombinatorialsetofarrangements
AT nagornaâan methodofsolvingtheproblemofconditionaloptimizationonacombinatorialsetofarrangements
AT semenovvv methodofsolvingtheproblemofconditionaloptimizationonacombinatorialsetofarrangements
first_indexed 2025-11-24T21:02:44Z
last_indexed 2025-11-24T21:02:44Z
_version_ 1850496518967001088
fulltext © Л.Н. КОЛЕЧКИНА, А.Н. НАГОРНАЯ, В.В. СЕМЕНОВ, 2019 62 ISSN 0572-2691 УДК 519.85 Л.Н. Колечкина, А.Н. Нагорная, В.В. Семенов МЕТОД РЕШЕНИЯ ЗАДАЧИ УСЛОВНОЙ ОПТИМИЗАЦИИ НА КОМБИНАТОРНОМ МНОЖЕСТВЕ РАЗМЕЩЕНИЙ Ключевые слова: задача условной оптимизации, комбинаторное множество размещений, экстремум функции, матрица нормализации. Введение Исследования задач комбинаторной оптимизации составляют довольно широкий спектр математических моделей, связанных с необходимостью решения различных важных практических проблем оптимального планирования, управления и проек- тирования [1–4]. Многие модели прикладних задач являются задачами комбина- торной оптимизации, свойства которых широко освещаются в работах как зару- бежных, так и отечественных авторов [1–10]. Под задачами комбинаторной опти- мизации понимается оптимизация некоторой заданной функции на комбинаторном множестве. В случае несколько целевых функций имеем многок- ритериальные задачи, различные классы которых достаточно подробно исследо- ваны в [10–12]. Примерами комбинаторных множеств являються множества пере- становок, размещений, сочетаний и т.д. Следует отметить, что комбинаторные оптимизационные задачи — одни из самых сложных с вычислительной точки зрения. Универсальный метод решения таких задач — полный перебор вариантов, который может применяться для задач малой размерности, но не дает желаемого результата на больших размерностях. Безусловно, существуют и другие методы решения таких задач, но, как правилo, каждый из них имеет свои преимущества и недостатки. Поэтому возникает необ- ходимость в разработке новых методов, как точных, так и приближенных, ко- торые учитывали бы специфику целевой функции и ограничений задачи оптими- зации на комбинаторных множествах. Особый интерес представляют свойства комбинаторных множеств при их отображении в арифметическое евклидово пространство. Такие множества названы евклидовыми комбинаторными [4, 13]. Важным классом евклидовых комбинатор- ных множеств являются вершинно-расположенные множества пространства nR , обладающие тем свойством, что они совпадают с вершинами своей выпуклой оболочки [14, 15]. Заметим, что любое конечное множество nE R можно раз- ложить на его вершинно-расположенные подможества. Методы оптимизации ли- нейных, квадратичных и выпуклых функций для различных классов вершинно- расположенных множеств рассмотрены в работах [16–25], а в многокритериаль- ной постановке — в [26–31]. Современные исследования комбинаторных множеств, связанные с понятием комбинаторной конфигурации, рассмотрены в [9, 31]. Модели и методы оптими- зации для различных классов комбинаторных конфигураций и их приложения рассмотрены, в частности, в [32–38]. В данной статье формулируется постановка задачи оптимизации на комбина- торном множестве размещений и предложен метод ее решения с учетом выполне- ния условий, налагаемых на приросты ограничений и целевой функции. Новый Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 63 метод обеспечивает нахождение оптимального решения оптимизационной задачи на множестве размещений с учетом дополнительных ограничений за определен- ное количество шагов. Для демонстрации работы метода представлены численные эксперименты, характеризующие его конечность и результативность, а также приведен анализ их результатов. Постановка задачи Пусть задано некоторое конечное множество A из k различных элементов. Из числа k элементов выбраны различные n (n ≤ k). Упорядоченный набор из n различных элементов некоторого множества k различных элементов называется размещением из k элементов по n и обозначается n kA . Рассмотрим оптимизационную задачу вида }|)({extr:),( n k n k AAaaAZ  , (1) где A — некоторое подмножество комбинаторного множества размещений n kA , определяемое заданной системой ограничений. Осуществим биективное отображение множества n kA в пространство nR , по- ставив каждому элементу n kAa в соответствие вектор nx R . Образ множества n kA обозначим n n kЕ R . В результате имеем задачу комбинаторной оптимизации в евклидовой постановке (задачу евклидовой комбинаторной оптимизации) }|)({extr:),( n k n k ÅDxxFÅFZ  , (2) })(|{ bGxRÅxD nn k  , где G — m n -матрица, mRb , причем )()( xFa  при n kAa , n kx Е . В данной статье рассмотрим класс линейных целевых функций, положив 1 ( ) n j j j F x c x   . Дополнительные линейные ограничения образуют многогранное множе- ство nRD . Рассмотрим метод решения задачи (1), который использует построение мат- рицы нормализации. Метод решения комбинаторной задачи условной оптимизации Шаг 1. Построение матрицы нормализации. Согласно порядку неубыва- ния коэффициентов целевой функции осуществляется перестановка коэффициен- тов заданных ограничений, по результатам которой составляется матрица норма- лизации (рис. 1). Она формируется на основе переобозначения порядка следова- ния коэффициентов дополнительных ограничений в формулировке задачи (2). Коэффициенты дополнительных ограничений преобразовываются в новые коэффициенты путем транcпозиции элементов с учетом условия упорядочения их по неубыванию: naaa 11211 ...  , naaa 22221 ...  , …, mnmm aaa  ...21 . При такой сортировке изменится местоположение коэффициента. Таким образом в матрицу записывается новое местоположение коэффициентов. 64 ISSN 0572-2691 fn 1u 2u … 1nu nu 1gn 11u 12u … 11 nu nu1 2gn 21u 22u … 12  nu nu2 … … … … … … mgn 1mu 2mu … 1mnu mnu Рис. 1 В соответствии с [32] fn , 1gn , 2gn , …, mgn — номер места соответствующего элемента множества размещений; для целевой функции — fn , для ограничений — 1gn , 2gn , …, , mgn где           )(...)2()1( ... :: 111 11 2 1 1 11 muuu xxx uCNu m . Следует отметить, что независимо от поиска максимума или минимума дан- ная матрица обеспечивает преобразование полученного решения в необходимую форму для функции цели или ограничений. Для удобства расчетов можно составить матрицу соответствия каждого эле- мента решения определенной позиции в зависимости от рассматриваемого огра- ничения (рис. 2). 1 fn 1u 2u … 1nu nu 2 f f x1 f x2 … f nx 1 f nx 3 1gn 11u 12u … 11 nu nu1 4 1g 1 1 g x  1 2 g x  … 1 1 g nx   1g nx  5 2gn 21u 22u … 12  nu nu2 6 2g 2 1 g x  2 2 g x  … 2 1 g nx   2g nx  … … … … … … … m–1 mgn 1mu 2mu … 1mnu mnu m mg mg x  1 mg x  2 … mg nx  1 mg nx  Рис. 2 В данной матрице 1g , 2g , …, mg определяют элементы точки множества размещений для целевой функции f и дополнительных ограничений; ( f x1 , ,2 f x …, …, f nx ) — опорное решение задачи. Шаг 2. Нахождение первого опорного решения. Согласно определению множество размещений учитывает порядок следования элементов. Упорядочим координаты точки x таким образом: для максимума по возрастанию )...( 121 nn xxxx   , соответственно, для минимума по убыванию )...( 121 nn xxxx   , поэтому при нахождении максимума (минимума) функции начальной выбирается «максимальная» («минимальная») точка множества разме- щений ),...,,,( 121 nn xxxx  . Затем производится расчет: Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 65 ),...,,,( 121 max(min) 1 nn xxxxf  , 11 11 1 1 2 1 11 )(),...,,,( bbxxxxg nn   , 22 22 1 2 2 2 12 )(),...,,,( bbxxxxg nn   , (3) ………………………………., ii i n i n ii i bbxxxxg )(),...,,,( 121   . Для дальнейшего поиска экстремума функции составляются необходимые условия для приростов ограничений: 1111111 ,)( bbbbg  , 2222222 ,)( bbbbg  , (4) ………………….., iiiiiii bbbbg  ,)( . Если данная начальная точка множества размещений удовлетворяет всем ограничениям, то найдено первое опорное решение. Далее необходимо сформи- ровать исходные данные для дальнейшего его улучшения: ...,,, icic 21 gg  icic 1,..., fgi и перейти к шагу 3. Для нахождения значений приростов функции f и ограничений ig необ- ходимо использовать следующие формулы [32]:  12 fff )**()**( 1122 i f ij f ji f jj f i cxcxcxcx  , (5)  12 ggg )**()**( 1122 i g ij g ji g jj g i cxcxcxcx  . (6) Если же ограничения не выполняются, то в данном случае необходимо вы- брать следующую точку из множества размещений и перейти к проверке условий (4). Шаг 3. Улучшение опорного решения. Улучшение опорного решения про- исходит за счет выбора следующей точки из множества размещений по убыванию (возрастанию) целевой функции, согласно главному условию проверки: )0(0 minmax  ff . (7) Если данное условие не выполняется, то полученное опорное решение нельзя улучшить, а следовательно, найдено оптимальное решение. В противном случае выбирается точка из множества размещений по убыва- нию (возрастанию) целевой функции и осуществляется проверка ограничений по формулам (4) шага 2. Необходимо отметить, что условия (4) являются достаточными для поиска оптимального решения, а выполнение неравенства (7) необходимо для поиска оп- тимального решения. Далее рассмотрим примеры, для решения которых будет использован изло- женный метод. Пример 1. Необходимо найти максимальное значение функции )(xf 4321 12425 xxxx  на множестве размещений 4 5A чисел )5,4,3,2,1( с учетом следующих линейных ограничений: 66 ISSN 0572-2691          .304635 ,18427 ,6532 43213 43212 43211 xxxxg xxxxg xxxxg Решение. Осуществляем нормализацию линейных ограничений:          .306543 ,18724 ,6532 31423 12432 43121 xxxxg xxxxg xxxxg          .306543 ,18724 ,6532 43213 43212 43211 xxxxg xxxxg xxxxg Соответственно матрица нормализации будет иметь следующий вид: fn 1 2 3 4 1gn 2 1 3 4 2gn 3 4 2 1 3gn 2 4 1 3. Найдем максимальное значение функции, выбрав точку (2, 3, 4, 5) из множе- ства размещений, в которой достигается наибольшее значение целевой функ- ции, тогда 60)5,4,3,2(max 1 f . Проверяем выполнение дополнительных ограничений, предварительно переведя данную точку в необходимую форму: 633)5,4,2,3(1 g , 189)2,3,5,4(2 g . Поскольку 3045)4,2,5,3(3 g , неравенство не выполняется, поэтому дан- ная точка не является допустимым решением. Для дальнейшего поиска поочередно должны выполняться следующие усло- вия: 271 g , 92 g , 153 g . Следующая точка выбирается из множества размещений по убыванию значе- ния целевой функции. Аналогично предыдущим вычислениям проверяем выпол- нение дополнительных ограничений в точке )5,4,3,1( , вычисляя только прирос- ты дополнительных ограничений ).3,2,1(  igi Тогда 2711 g , 972 g , но 1553 g . Последнее неравенство не выполняется, следо- вательно, рассматривается следующая точка из множества размещений и осу- ществляются аналогичные вычисления. Для точки )5,4,2,1( : 1)5,4,1,2(1 g , 9)1,2,5,4(2 g ,  )4,1,5,2(3g 152  . Для точки )5,3,4,1( : 6)5,3,1,4(1 g , 1)1,4,5,3(2 g ,  )3,1,5,4(3g 1514  . Точка )5,3,2,1( : 2)5,3,1,2(1 g , 5)1,2,5,3(2 g ,  )3,1,5,2(3g 158  . Для точки )5,2,3,1( : 7)5,2,1,3(1 g , 1)1,3,5,2(2 g ,  )2,1,5,3(3g 1517  . Соответственно 626733)5,2,1,3()5,4,2,3()5,2,1,3( 111  ggg , 181019)1,3,5,2()2,3,5,4()1,3,5,2( 222  ggg , .30281745)2,1,5,3()4,2,5,3()2,1,5,3( 333  ggg Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 67 Итак, все неравенства выполняются, поэтому найдено первое опорное решение: .57360)5,4,3,2()5,2,3,1( 1 max 11ic  fff Для дальнейшего поиска оптимальных решений данные значения следует считать начальными: 26)5,2,1,3( ic1 g , 10)1,3,5,2( ic2 g , 28)2,1,5,3( ic3 g , 57)5,2,3,1( ic1 f . Поскольку необходимо найти максимум целевой функции, а выбор точек из множества размещений осуществляется в порядке убывания, необходимо соблю- дать условие .0f Рассмотрим следующую точку )1425( : 023*24*21 f , значит, значение целевой функции уменьшится на две единицы, поэтому следует прекра- тить поиск решения. Поскольку значение целевой функции в следующей точке меньше, чем в предыдущей, точка )5,2,3,1( является оптимальным решением .57)5,2,3,1(max f Пример 2. Найти минимальное значение функции 321 1142)( xxxxf  на множестве размещений 3 5A из чисел )5,4,3,2,1( с учетом следующих линейных ограничений:          .2857 ,17296 ,1034 3213 3212 3211 xxxg xxxg xxxg Решение. Нормализуем дополнительные ограничения согласно коэффициен- там целевой функции:          .2875 ,17926 ,1043 3213 3212 3211 xxxg xxxg xxxg Запишем матрицу нормализации: fn 1 2 3 1gn 3 2 1 2gn 1 3 2 3gn 3 1 2 Для нахождения минимума целевой функции выбираем наименьшую точку множества размещений )1,2,3( , соответственно .13)1,2,3(min 1 f Пользуясь матрицей нормализации, проверяем выполнение ограничений: 1011)3,2,1(1 g ,  )2,1,3(2g 172  , 2828)2,3,1(3 g . Поскольку выпол- няется только последнее неравенство, следовательно, данная точка не является допустимым решением. Соответственно, имеют место условия: 11 g , 192 g , 03 g . Следующая точка выбирается по возрастанию точки )1,2,4( . Находим при- росты функций-ограничений. Для 041 g , что противоречит условию 11 g , поэтому проверка ограничений не осуществляется. Для точки )521( : 18)5,2,1(1 g , следовательно, не рассматривается. Для точки )231( : 93 g , 1915)3,1,2(2 g , не рассматривается. 68 ISSN 0572-2691 Точка )431( : 15)4,3,1(1 g , не рассматривается. Для точки )531( : 19)5,3,1(1 g , не рассматривается. Для точки )241( : 12)2,4,1(1 g , 1924)4,1,2(2 g , 09)4,2,1(3 g . Соответственно 109211)2,4,1()3,2,1()2,4,1( 111  ggg , 1722242)4,1,2()2,1,3()4,1,2( 222  ggg , .2837928)4,2,1()2,3,1()4,2,1( 333  ggg Поскольку все неравенства выполняются, найдено первое опорное решение: .231013)1,2,3()1,4,2( 1 min 11ic  fff Итак, исходными данными для дальнейшего поиска оптимального решения будут: 9)2,4,1( ic1 g , 22)4,1,2( ic2 g , 37)4,2,1( ic3 g , 23)1,4,2( ic1 f . Соответственно имеют место условия: 11 g , 52 g , 93 g . Поскольку необходимо найти минимальное значение функции цели, а выбор точек из множества размещений осуществляется в порядке возрастания, необхо- димо соблюдать следующее условие: 0f . Рассмотрим точку )1,4,2( : 022*23*21 f , поэтому необходимо осуществить проверку ограничений по приростам функций: 14)3,4,1(1 g , неравенство не выполняется. Точка )1,4,5( : 062 f , 112)5,4,1(1 g . Неравенство не выполняется. Точка )1,5,2( : 043 f , поскольку функция возрастает и координаты точки увеличиваются, выполнение шагов метода прекращается. Итак, точка )1,4,2( является оптимальным решением, .23)1,4,2(min f Для решения примера 2 по предложенному методу с помощью программы на языке программирования С++ был проведен вычислительный эксперимент, с учетем возрастания количества элементов выборки множества размещений при фиксированном 3n . Результа- ты вычислительных экспериментов представлены в таблице, где k — количество элементов, из которых строиться множество размещений; 3 kA — количество элементов мно- жества размещений; r — количест- во точек, которые перебираються в процессе отыскания оптимального решения; s — количество шагов нахождения оптимального решения. Анализируя результаты вычис- лительного эксперимента, следует отметить, что при возрастании ко- личества элементов выборки мно- жества размещений возрастает ко- личество точек, которые перебира- ються ( r ), и количество шагов отыскания оптимального решения ( s ), что очевидно. При этом значительное воз- Таблица № k 3 kA r s ( r / 3 kA ), % 1 4 24 7 9 29,17 2 5 60 11 13 18,33 3 6 120 13 15 10,83 4 7 210 17 19 8,10 5 8 336 20 22 5,95 6 9 504 23 25 4,56 7 10 720 26 28 3,61 8 11 990 29 31 2,93 9 12 1320 32 34 2,42 10 13 1716 35 37 2,04 11 14 2184 38 40 1,74 12 15 2730 41 43 1,50 13 16 3360 44 46 1,31 14 17 4080 47 49 1,15 15 18 4896 50 51 1,02 Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 69 растание колличества элементов множества 3 kA не приводит к стремительному росту показателей r и s . Как показано в таблице, процентное соотношение количества точек, которые перебираються в процессе поиска оптимального решения, и количества элементов множества размещений, значительно уменьшается, что подтверждает эффектив- ное использование предложенного метода. Например, при 9 < k < 18 использует- ся всего лишь от 1 % до 5 % элементов множества размещений, в то же время, при k = 4, 5, 6, от 11 % до 29 %. Необходимо отметить, что предложенный метод позволяет за считанные ша- ги ( s = 9, 13, 15, ..., 51) найти экстремум функции на множестве размещений. Это говорит о том, что количество шагов метода — конечное число, которое ограни- чивается невыполнением условия (7). Если данное условие не выполняется, то данное опорное решение нельзя улучшить, а следовательно, найдено оптимальное решение и дальнейшее выполнение шагов метода приостанавливается. Заключение В статье предложен новый метод решения комбинаторной задачи условной оптимизации на множестве размещений. Его суть заключается в нахождении пер- вого опорного решения, на базе которого осуществляется поиск оптимального, за счет улучшения предыдущего. Предложеный метод состоит из трех шагов, где на начальном этапе строятся матрицы нормализации и соответствия, которые обеспечивают преобразование элементов множества размещений в необходимую форму для целевой функции и заданных ограничений. Следует отметить, что для нахождения первого опорного решения не нужно делать проверку всех ограничений, достаточно рассчитать приросты ограничений ig (5). Если допустимое решение удовлетворяет данным неравенствам, то фиксируются начальные данные, которые будут условиями про- верки для следующего улучшенного решения. Улучшение опорного плана про- исходит согласно условию (7). Значение функции цели находится за счет нахо- ждения приростов f (6), без необходимости вычисления всей предыдущей фун- кции. Случай невыполнения условия (7) обеспечивает нахождение оптимального решения. Рассмотрены числовые примеры поиска экстремумов функций на множестве размещений, а также представлен числовой эксперимент для случая 3 kA , при воз- растании количества элементов выборки множества размещений ( k ). Также следует отметить, что количество шагов нахождения оптимального решения не увиличивается значительно, при резком возрастании количества элементов мно- жества размещений. Например, для 3 10A = 720 оптимальное решение было най- дено за 28 шагов метода, при рассмотрении 26 элементов множества размещений, для 3 18A = 4896 поиск оптимального решения осуществлен за 51 шаг при рассмо- трении 50 элементов множества размещений. Анализируя показатель процентного соотношения количества рассмот- ренных точек при нахождении оптимального решения и количества элементов множества размещений, следует отметить его значительное уменьшение, что сви- детельствует об эффективности предлагаемого метода. 70 ISSN 0572-2691 Данный метод позволяет значительно упростить процедуру поиска оптима- льного решения, поскольку неравенства приростов ограничений позволяют сразу определить, будет ли точка множества размещений опорным решением. Не нужно делать сложные расчеты всех ограничений и целевой функции, достаточно найти прирост ограничения и функции в случае улучшения решения. Итак, пользуясь данным методом, за конечное число шагов можно найти экстремум функции на множестве размещений. Дальнейшие исследования будут направлены на адаптацию метода для других комбинаторных множеств и модели- рования процессов и явлений с использованием метода. Л.М. Колєчкіна, А.М. Нагірна, В.В. Семенов МЕТОД ВИРІШЕННЯ ЗАДАЧІ УМОВНОЇ ОПТИМІЗАЦІЇ НА КОМБІНАТОРНІЙ МНОЖИНІ РОЗМІЩЕНЬ Розглянуто постановку задачі оптимізації на комбінаторій множині розміщень і запропоновано метод її розв’язання з урахуванням виконання умов, що накла- даються на прирости обмежень і цільової функції. Метод складається з трьох кроків, де на початковому етапі будуються матриці нормалізації та відповідно- сті, які забезпечують перетворення елементів множини розміщень в необхідну форму для цільової функції і заданих обмежень. Другий крок полягає в знахо- дженні першого опорного розв’язку з урахуванням властивості множини роз- міщень. Слід зазначити, що для знаходження першого опорного розв’язку до- статньо розрахувати прирости обмежень. Якщо допустимий розв’язок задово- льняє даним нерівностям, то фіксуються початкові дані, які будуть умовами перевірки для наступного покращеного розв’язку. Значення функції цілі знахо- диться розрахунком приростів цільової функції без необхідності обчислення всієї попередньої функції. Третій крок методу забезпечує знаходження оптима- льного розв’язку за безпосереднього покращення знайденого опорного розв’язку. На даному етапі сформульовано достатні і необхідні умови для по- шуку оптимального розв’язку. Розглянуто числові приклади пошуку екстрему- мів функцій на множині розміщень, а також представлено числовий експери- мент для випадку 3 kA , при зростанні кількості елементів вибірки множини ро- зміщень ( k ). Також слід зазначити, що кількість кроків знаходження оптимального розв’язку істотно не збільшується за різкого зростання кількості елементів множини розміщень. Аналізуючи показник процентного співвідно- шення кількості розглянутих точок при знаходженні оптимального розв’язку до кількості елементів множини розміщень, слід зазначити його значне зменшен- ня, що свідчить про ефективність запропонованого методу. Отже, користую- чись даним методом, можна за скінчене число кроків знайти екстремум функції на множині розміщень. Ключові слова: задача умовної оптимізації, комбінаторна множина розміщень, екстремум функції, матриця нормалізації. L.N. Kolechkina, A.N. Nagornaya, V.V. Semenov METHOD OF SOLVING THE PROBLEM OF CONDITIONAL OPTIMIZATION ON A COMBINATORIAL SET OF ARRANGEMENTS Defining a problem of optimization on a combinatorial set of arrangements is consid- ered and presenting the method of its solution, taking into account satisfaction of the conditions imposed on gains of restrictions and objective function is proposed. The method consists of three steps where at the initial stage matrixes of normalization and Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 71 compliance are built, which provide elements arrangement set transformation to a necessary form for criterion function and the defined restrictions. The second step consists in finding the first basic solution, taking into account property of arrange- ment set. It should be noted that for finding the first basic solution it is enough to calculate gains of restrictions. If the allowable solution satisfies presented inequalities, then initial data is fixed, which will be the verification conditions for the following improved solution. The value of the goal function is determined at the expense of calculating the increments of the target function, without the need to calculate the entire previous function. The third step of a method provides finding of an optimal solution at direct improvement of the found basic solution. On this step sufficient and necessary conditions for search of an optimal solution are formulated. Numerical examples of search functions's extrems on a set of arrange- ments are considered and also the numerical experiment for the case 3 kA is presented, at increase of sample units quantity of an arrangements set ( k ). Also it should be noted that the finding steps quantity of an optimal solution considerably does not increase, at sharp increase of elements quantity in a set of arrangements. Analyzing an indicator of percentage correlation of the considered points quantity when finding an optimal solution to quantity of elements on an arrangements set, it should be noted its considerable reduction that gives evidence about efficiency of the offered method. So, this method allows to find a function extremum on a set of ar- rangements during a finite number of steps. Keywords: conditional optimization problem, combinatorial set of allocations, func- tion extremum, normalization matrix. 1. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. Київ : Наук. думка, 2003. 261с. 2. Згуровский М.З., Павлов А.А. Труднорешаемые задачи комбинаторной оптимизации в планировании и принятии решений. Київ : Наук. думка, 2016. 715 с. 3. Colbourn C.J., Dinitz J.H. Handbook of combinatorial designs, second edition. CRC Press, 2010. 784 p. 4. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри- ческого проектирования. Киев: Наук.думка, 1986. 268 с. 5. Korte B., Vygen J. Combinatorial optimization: theory and algorithms. Heidelberg; New York : Springer, 2018. 698 p. 6. Pardalos P.M., D-Z. Du, Graham R.L. Handbook of combinatorial optimization. New York : Springer, 2013. 3409 p. 7. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: algorithms and complexity. Mineola : Dover Publications, 2013. 528 p. 8. Sergienko I.V., Shilo V.P. Modern approaches to solving complex discrete optimization problems. Journal of Automation and Information Sciences. 2016, 48, N 1. P. 15–24. 9. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization prob- lems. Optimization Methods and Applications, S. Butenko et al.(eds.). New York : Springer, 2017. P. 239–250. 10. Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних множинах: методи дослідження та розв'язання. Київ: Наук. думка, 2009. 266 с. 11. 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. 12. Koliechkina L. N., Dvirna O. A., Nagornaya A. N. Modified coordinate method to solve mul- ticriteria optimization problems on combinatorial configurations. Cybernetics and Systems Analy- sis. 2014. 59, N 4. P. 620–626. 13. Стоян Ю. Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. Київ: Ін-т системн. дослідж. освіти, 1993. 188 с. 14. Yakovlev S. V. The theory of convex continuations of functions on vertices of convex polygons. Computational Mathematics and Mathematical Physics. 1994. 34, N 7. P. 959–965. 15. Yakovlev S. Convex extensions in combinatorial optimization and their applications. Springer Optimization Methods and Applications. 2017. 130. P. 567–584. 72 ISSN 0572-2691 16. Yakovlev S.V., Valuiskaya O.A. Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints. Ukrainian Mathematical Journal. 2001. 53, N 9. P. 1535–1545. 17. 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. 18. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in nR . Cybernetics and Systems Analysis. 1991. 27, N 4. P. 562–567. 19. Емец О. А., Емец О. А., Емец Е. М. Модификация метода комбинаторного отсечения в за- дачах оптимизации на вершинно расположенных множествах. Кибернетика и системный анализ. 2009. 45, № 5. С. 129–136. 20. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функціями. Київ: Наук. думка, 2005. 117 с. 21. Ємець О.О., Колєчкіна Л.М. Задача оптимізації на переставленнях з дробово-лінійною цільовою функцією: властивості множини допустимих розв’язків. Український матема- тичний журнал. 2000. 52, № 12. С. 1630–1640. 22. S. V. Yakovlev, Pichugina O. S. Properties of combinatorial optimization problems over polyhe- dral-spherical sets. Cybernetics and Systems Analysis. 2018. 54, N 1. P. 99–109. 23. Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: Theory and applications. In 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (UKRCON 2017). Proceedings, Kyiv, 2017. P. 1167–1175. 24. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distrib- uted masses. Energomashinostroenie. 1982. N 2. P. 4–5. 25. 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. 26. 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. 27. 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. 28. 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. 29. 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. 30. Koliechkina L. N., Dvirna O.A. Solving extremum problems with linear fractional objective functions on the combinatorial configuration of permutations under multicriteriality. Cybernetics and Systems Analysis. 2017. 53, N 4. P. 590–599. 31. Колєчкіна Л.М., Нагірна А.М. Комбінаторна математична модель багатокритеріальної оптимі- зації при побудові комп’ютерних мереж. Математичні машини і системи. 2016. № 6. С. 26–41. 32. Донець Г.П., Колєчкіна Л.М. Екстремальні задачі на комбінаторних конфігураціях. Полта- ва: РВВ ПУЕТ, 2011. 309 с. 33. Стоян Ю. Г., Яковлев C.В., Пичугина О.С. Евклидовы комбинаторные конфигурации: мо- нография. Харьков : Константа, 2017. 404 с. 34. 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. 35. 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. 36. Yakovlev, S., Pichugina, O., Yarovaya, O. On optimization problems on the polyhedral-spherical configurations with their properties. In 2018 IEEE First International Conference on System Analysis Intelligent Computing (SAIC 2018). Proceedings, Kyiv. 2018. P. 94–100. 37. Yakovlev, S., Pichugina, O., Yarovaya, O. Polyhedral spherical configuration in discrete optimi- zation. Journal of Autom. and Information Sci. 2019. 51, N 1. P. 38–50. 38. Нагірна А.М., Семенов В.В. Оптимізація вибору програмного забезпечення на основі бага- токритеріальних моделей на нечітко заданій комбінаторній множині. Вісник Київського на- ціонального університету імені Тараса Шевченка. Серія фізико-математичні науки. 2012. № 2. С. 188–193. Получено 10.09.2018 После доработки 30.05.2019 http://dspace.puet.edu.ua/handle/123456789/474 http://dspace.puet.edu.ua/handle/123456789/474 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

Ähnliche Einträge