Розв’язування оптимізаційної комбінаторної задачі мінімізації
У роботі представлено математичну модель оптимізаційної задачі мінімізації на комбінаторній множині перестановок, яка може бути моделлю багатьох прикладних задач. Математична модель на комбінаторній множині перестановок, згідно з методом їх генерування, розглядається на графі, вершини якого відпові...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2018 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/150647 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Розв’язування оптимізаційної комбінаторної задачі мінімізації / Л.М. Колєчкіна, А.М. Нагірна // Математичні машини і системи. — 2018. — № 3. — С. 117-124. — Бібліогр.: 19 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860003418461962240 |
|---|---|
| author | Колєчкіна, Л.М. Нагірна, А.М. |
| author_facet | Колєчкіна, Л.М. Нагірна, А.М. |
| citation_txt | Розв’язування оптимізаційної комбінаторної задачі мінімізації / Л.М. Колєчкіна, А.М. Нагірна // Математичні машини і системи. — 2018. — № 3. — С. 117-124. — Бібліогр.: 19 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | У роботі представлено математичну модель оптимізаційної задачі мінімізації на комбінаторній множині перестановок, яка може бути моделлю багатьох прикладних задач. Математична модель на комбінаторній множині перестановок, згідно з методом їх генерування, розглядається на графі, вершини якого відповідають точкам множини перестановок.
В работе представлена математическая модель оптимизационной задачи минимизации на комбинаторном множестве перестановок, которая может быть моделью многих прикладных задач. Математическая модель на комбинаторном множестве перестановок по методу их генерирования рассматривается на графе, вершины которого соответствуют точкам множества перестановок.
The paper presents a mathematical model of optimization minimization problem on a combinatorial set of permutations, which can be a model of many applied problems. A mathematical model on a combinatorial set of permutations by the method of generating them is considered on a graph the vertices of which correspond to the points of the set of permutations.
|
| first_indexed | 2025-12-07T16:37:57Z |
| format | Article |
| fulltext |
© Колєчкіна Л.М., Нагірна А.М., 2018 117
ISSN 1028-9763. Математичні машини і системи, 2018, № 3
УДК 519.8
Л.М. КОЛЄЧКІНА
*
, А.М. НАГІРНА
**
РОЗВ’ЯЗУВАННЯ ОПТИМІЗАЦІЙНОЇ КОМБІНАТОРНОЇ ЗАДАЧІ МІНІМІЗАЦІЇ
*
Полтавський університет економіки і торгівлі, м. Полтава, Україна
**
Інститут кібернетики імені В.М. Глушкова НАН України, м. Київ, Україна
Анотація. У роботі представлено математичну модель оптимізаційної задачі мінімізації на ком-
бінаторній множині перестановок, яка може бути моделлю багатьох прикладних задач. Мате-
матична модель на комбінаторній множині перестановок, згідно з методом їх генерування, розг-
лядається на графі, вершини якого відповідають точкам множини перестановок. Описаний алго-
ритм складається з п’яти послідовних кроків і забезпечує знаходження єдиного оптимального
розв’язку оптимізаційної задачі мінімізації з урахуванням комбінаторних властивостей множини
перестановок. На першому кроці здійснюється нормалізація додаткових обмежень згідно з поряд-
ком зростання коефіцієнтів цільової функції: матриця нормалізації, що забезпечує перетворення
отриманих розв’язків у необхідну форму для обмежень чи цільової функції. На другому кроці зна-
ходиться опорний розв’язок, який задовольняє всі обмеження задачі. Причому пошук здійснюється
серед граничних точок графа обмежень. Третій крок полягає у побудові приростів цільової функції
у порядку зростання та вибору мінімального. Шляхом транспозицій відповідних елементів опорно-
го розв’язку визначаються всі інші можливі оптимальні розв’язки, причому розраховуються лише
прирости цільової функції. Мінімальний приріст дозволяє знайти найкращий оптимальний
розв’язок серед них. На четвертому кроці алгоритму здійснюється перевірка виконання обмежень
і визначається оптимальний розв’язок. На п’ятому кроці обчислюється мінімальне значення цільо-
вої функції. У статті представлено числовий приклад, який демонструє роботу алгоритму. За
рахунок використання транспозиції елементів у перестановці відбувається скорочення кроків
розв’язання задачі мінімізації, що й показано у наведеному числовому прикладі. Розв’язок знайдено
за шість кроків, при покращенні опорного розв’язку було розглянуто п’ять транспозицій, у той же
час при повному переборі необхідно було б проводити розрахунок по 24 перестановках з урахуван-
ням обмежень. Тому запропонований алгоритм забезпечує найкоротший шлях знаходження опти-
мального розв’язку, при якому досягається мінімальне значення цільової функції на множині пере-
становок.
Ключові слова: модель, комбінаторна оптимізація, комбінаторна задача, загальна множина пе-
рестановок,транспозиція, опорний розв’язок, оптимальний розв’язок, алгоритм розв’язування за-
дачі.
Аннотация. В работе представлена математическая модель оптимизационной задачи миними-
зации на комбинаторном множестве перестановок, которая может быть моделью многих прик-
ладных задач. Математическая модель на комбинаторном множестве перестановок по методу
их генерирования рассматривается на графе, вершины которого соответствуют точкам мно-
жества перестановок. Описанный алгоритм состоит из пяти последовательных шагов и обеспе-
чивает нахождение единого оптимального решения оптимизационной задачи минимизации с уче-
том комбинаторных свойств множества перестановок. На первом этапе осуществляется нор-
мализация дополнительных ограничений согласно порядку возрастания коэффициентов целевой
функции: матрица нормализации, что обеспечивает преобразование полученных решений в необ-
ходимую форму для ограничений или целевой функции. На втором шаге находится опорное реше-
ние, которое удовлетворяет все ограничения задачи. Причем, поиск осуществляется среди грани-
чных точек графа ограничений. Третий шаг заключается в построении приростов целевой функ-
ции в порядке возрастания и выбора минимального. Путем транспозиций соответствующих эле-
ментов опорного решения определяются все другие возможные оптимальные решения, но рассчи-
тываются только приросты целевой функции. Минимальный прирост позволяет найти лучшее
оптимальное решение среди них. На четвертом шаге алгоритма осуществляется проверка выпо-
лнения ограничений и определяется оптимальное решение. На пятом шаге вычисляется минима-
льное значение целевой функции. В статье представлен числовой пример, демонстрирующий ра-
боту алгоритма. За счет использования транспозиции элементов в перестановке происходит сок-
118 ISSN 1028-9763. Математичні машини і системи, 2018, № 3
ращение шагов решения задачи минимизации, что показано в приведенном числовом примере. Ре-
шение найдено за шесть шагов, при улучшении опорного решения было рассмотрено пять транс-
позиций, в то же время при полном переборе необходимо было бы проводить расчет по 24 перес-
тановкам с учетом ограничений. Поэтому предложенный алгоритм обеспечивает кратчайший
путь нахождения оптимального решения, при котором достигается минимальное значение целе-
вой функции на множестве перестановок.
Ключевые слова: модель, комбинаторная оптимизация, комбинаторная задача, общее множест-
во перестановок, транспозиция, опорное решение, оптимальное решение, алгоритм решения зада-
чи.
Abstract. The paper presents a mathematical model of optimization minimization problem on a combina-
torial set of permutations, which can be a model of many applied problems. A mathematical model on a
combinatorial set of permutations by the method of generating them is considered on a graph the vertices
of which correspond to the points of the set of permutations. The described algorithm consists of five con-
secutive steps and provides finding a single optimal solution of the optimization minimization problem,
taking into account the combinatorial properties of the set of permutations. In the first step, the normaliza-
tion of additional constraints is carried out according to the order of growth of the coefficients of the ob-
jective function: the matrix of normalization, which ensures the transformation of the resulting solutions
into the required form for restrictions or the objective function. The second step is the reference solution,
which satisfies all the limitations of the task. In addition, the search is carried out among the boundary
points of the graph of constraints. The third step is to build incremental target function in order of growth
and a minimum choice. Through the transpositions of the corresponding elements of the reference solu-
tion, all other possible optimal solutions are determined, and at the same time, only the increments of the
target function are calculated. The minimum gain allows you to find the best optimal solution among
them. The fourth step of the algorithm is to verify the implementation of the restrictions and determine the
optimal solution. In the fifth step, the minimum value of the target function is calculated. The article pre-
sents a numerical example that demonstrates the work of the algorithm. Due to the use of transposition of
elements in the permutation, there is a reduction in the steps of solving the minimization problem, which is
shown in the given numerical example. The solution was found in six steps, with the improvement of the
reference solution, five transpositions were considered, at the same time, at full interrogation, it would be
necessary to calculate the 24 permutations, taking into account the limitations. Therefore, the proposed
algorithm provides the shortest path for finding an optimal solution, which achieves the minimum value of
the objective function on the set of permutations.
Keywords: model, combinatorial optimization, combinatorial problem, the general permutation set, trans-
position, support solution, optimal solution, algorithm for solving the problem.
1. Вступ
Проблема дослідження задач комбінаторної оптимізації на сьогодні є досить актуальною,
про що свідчить велика кількість праць, присвячених методам розв’язування екстремаль-
них задач на комбінаторних множинах [1–17], в яких пропонуються нові підходи та удо-
сконалюються існуючі методи, досліджується їх ефективність. Даний факт пов’язаний з
тим, що екстремальні задачі дискретної оптимізації є моделями різних прикладних задач
проектування, планування, розміщення, класифікації і управління [11–13, 18, 19]. Слід за-
значити, що в науковій літературі широко вживається термін «задача комбінаторної опти-
мізації» (ЗКО), під якою розуміють проблему пошуку екстремумів заданої цільової функції
на комбінаторному просторі.
Оптимізаційні комбінаторні задачі знайшли своє широке застосування в різних сфе-
рах діяльності, наприклад, у програмуванні, медицині, в банківській сфері, у промисловос-
ті, молекулярній біології і т.п.
На особливу увагу заслуговують комбінаторні моделі, якими моделюються певні
класи практичних задач з урахуванням комбінаторних властивостей множини допустимих
розв’язків, які зручно представляти графічно, у вигляді графа [1, 2, 5, 6].
ISSN 1028-9763. Математичні машини і системи, 2018, № 3 119
Основна увага в комбінаторній оптимізації приділяється визначенню обчислюваль-
ної складності цих задач, розробці методів і алгоритмів їх розв’язання на основі властивос-
тей комбінаторних множин. Існує безліч різноманітних методів розв’язування екстремаль-
них задач як точних, так і наближених. Системне вивчення властивостей комбінаторних
множин та їх дослідження описані в багатьох роботах [1, 9, 11, 13]. Підвищений інтерес до
таких задач обумовлений дослідженнями останніх років в області комп’ютерних техноло-
гій при створенні сучасних алгоритмів і програм для розв’язування оптимізаційних задач.
На даний момент неможливо програмувати більшість задач без знань комбінаторики та
теорії графів, оскільки це значно полегшує і спрощує роботу на комп’ютері [1].
У даній статті формулюється постановка задачі комбінаторної оптимізації та запро-
поновано новий підхід до розв’язання сформульованої задачі. Новий алгоритм розв’язання
забезпечує знаходження оптимального розв’язку оптимізаційної задачі на множині перес-
тановок, а, отже, мінімізацію цільової функції, з урахуванням додаткових обмежень за лі-
чені кроки. Даний алгоритм застосовує матрицю нормалізації та прирости функції цілі для
знаходження оптимального розв’язку. Для демонстрації роботи алгоритму представлено
числовий приклад.
2. Постановка математичної моделі задачі
Введемо необхідні позначення. Позначимо 0 0k
kN N , вимірність підпростору
: dimkL R L , опукла оболонка множини M – conv M .
Мультимножиною є множина елементів, які можуть повторюватися. Мультимно-
жинa A зaдaється основою ( )S A , тобто набором усіх її різних елементів, і кратністю еле-
ментів ( )Ak a (або ( )k a ) – числом повторення кожного елементa основи цієї мульти-
множини.
Мультимножина B з основою ( )S B називається підмультимножиною мультимно-
жини A з основою ( )S A , якщо ( ) ( )S B S A , і для кожного елемента ( )a S B виконується
нерівність ( ) ( )B Ak a k a .
Нехай задана мультимножина 1 2{ , ,... }qA a a a її основа 1 2( ) { , ,..., }kS A e e e , де
1
j ke R j N і кратність елементів 1 2( ) , , ...j j k kk e r j N r r r q .
Впорядкованою n -вибіркою з мультимножини A називається набір
1 2
( , , , ),
ni i ia a a a (1)
де
jia А j ni N , nj N , s ti i , якщо s t ,ns N nt N .
Означення 1. Множина ( )E A , елементами якої є n -вибірки вигляду (1) з мультим-
ножини A, називається евклідовою комбінаторною множиною, якщо для довільних її еле-
ментів 1 2( , ,..., )na a a a , 1 2( , ,..., )na a a a виконуються умови: ( ) ( : )j ja a j a a ,
тобто два елементи множини ( )E A відмінні один від одного, якщо вони незалежно від ін-
ших відмінностей розрізняються порядком розміщення елементів, що їх утворюють.
Множина перестановок з повтореннями з n дійсних чисел, серед яких k різних, на-
зивається загальною множиною перестановок і позначається ( )nkР A . Це множина упоряд-
кованих n -вибірок вигляду (1) з мультимножини А за умови n q k .
При n k q маємо множину перестановок без повторень. Позначимо її nP . Очеви-
дно, що ( ) ( )n nnP A P A . У тих випадках, коли конкретно не будемо вказувати вид множини
перестановок, будемо записувати ці множини як ( )P A .
120 ISSN 1028-9763. Математичні машини і системи, 2018, № 3
fn 1u 2u … 1nu nu
1gn '
11u '
12u … '
1 1nu '
1nu
2gn '
21u '
22u … '
2 1nu '
2nu
… … … … … …
mgn '
1mu '
2mu … '
1mnu '
mnu
Рисунок 1 – Матриця нормалізації
Розглянемо задачу комбінаторної оптимізації на множині перестановок ( )P A ви-
гляду
( , ( )) : min{ (a) | a P(A)}Z P A , (2)
де
1
min (a)
n
j j
j
c x ,
{ | }nD x R Gx b Gx b ,
де m nG R , mb R – опукла многогранна множина
nD R , утворена додатковими ліній-
ними обмеженнями.
Далі сформулюємо задачу (F,X)Z , де кожній точці ( )nka P A відповідає точка
x X , така, що F(x) ( )a :
(F,X) : min{F(x) | x }Z X , (3)
де
1
F(x)
n
j j
j
c x , X – не порожня множина в nR і ( )X vert A , ( )convP A .
Відповідно, додаткові лінійні обмеження:
1
n
ij j i
j
Gx g x b або
1
n
ij j i
j
Gx g x b ,
mi N , nj N .
Послідовність перестановок, згідно з методом їх генерування, інтерпретується як
граф nG , вершини якого відповідають точкам множини перестановок ( )nP A [2, 11].
3. Алгоритм розв’язування комбінаторної
задачі мінімізації на множині перестано-
вок
1 крок. Побудова матриці нормалізації. На
першому кроці здійснюємо нормалізацію до-
даткових обмежень згідно з порядком зрос-
тання коефіцієнтів цільової функції:
1 2 1... n nc c c c , ' ' '
11 12 1... na a a ,
' ' '
21 22 2... na a a , …, ' ' '
1 2 ...m m mna a a [2].
Складаємо матрицю нормалізації (рис. 1), що забезпечує перетворення отриманих
розв’язків у необхідну форму для обмежень чи цільової функції.
1 fn 1u 2u … 1nu nu
2 f
1
f
x 2
f
x
1
f
nx
f
nx
3
1gn '
11u '
12u … '
1 1nu '
1nu
4 1g 1
1
g
x 1
2
g
x 1
1
g
nx 1g
nx
5
2gn '
21u '
22u … '
2 1nu '
2nu
6 2g 2
1
g
x 2
2
g
x 2
1
g
nx 2g
nx
… … … … … … …
7
mgn '
1mu '
2mu … '
1mnu '
mnu
8 mg
1
mg
x 2
mg
x …
1
mg
nx mg
nx
Рисунок 2 – Матриця відповідностей
ISSN 1028-9763. Математичні машини і системи, 2018, № 3 121
Для зручності розрахунків приростів функції f і обмежень ig складаємо матри-
цю відповідностей (рис. 2).
У даних матрицях
fn ,
1gn ,
2gn ,…,
mgn – номери місця відповідної цифри в перестановці,
де
1 1 1
1 2
1 1 1 1 1
...
: :
(1) (2) ... ( )
mx x x
u N C u
u u u m
[3];
f , 1g , 2g ,…, mg – точка (розв’язок, перестановка) у відповідній формі;
1
f
x , 2
f
x …, f
nx – опорний розв’язок 1(
f
x > 2
f
x >… > )f
nx .
2 крок. Знаходження опорного розв’язку. Першочергово визначається перший допустимий
розв’язок довільного обмеження згідно з алгоритмом [4]. У даному випадку – це гранична
точка, що задовольняє дане обмеження. Далі відбувається перевірка виконання всіх інших
обмежень. Знайдена точка буде опорним розв’язком, якщо нерівності справджуються, а
числові значення обмежень та цільової функції будуть початковими даними (
почig , почf ). У
випадку невиконання нерівностей задача не має розв’язку на множині перестановок.
Значення приростів функції f і обмежень ig знаходяться за такими формулами
[4]:
2 1f f f * * * *
f f f f
i j j i j j i ix c x c x c x c , (4)
2 1g g g * * * *
g g g g
i j j i j j i ix c x c x c x c . (5)
3 крок. Покращення опорного розв’язку. За рахунок транспозицій у перестановці першого
опорного розв’язку знаходимо прирости цільової функції f і впорядковуємо їх за спа-
данням:
1 2 1... n nf f f f . (6)
Мінімальний приріст цільової функції min nf f визначає покращений опорний
розв’язок.
4 крок. Знаходження оптимального розв’язку. Знаходимо ig для розв’язку, який отрима-
ний при знаходження nf , і перевіряємо виконання обмежень
i jg b ,
де
поч оптi i ig g g (7)
Якщо всі обмеження виконуються, то знайдено оптимальний розв’язок задачі, в ін-
шому випадку, розглядається розв’язок, що отриманий при знаходженні 1nf , і повторює-
мо аналогічні обчислення.
У випадку невиконання обмежень неможливо знайти мінімум функції при заданих
обмеженнях на множині перестановок.
5 крок. Знаходження мінімального розв’язку задачі. Після виконання кроку 4 знаходимо
мінімальне значення цільової функції:
min поч оптf f f . (8)
4. Приклад застосування алгоритму
Знайти мінімальне значення функції 1 2 3 4( ) 2 7 12f x x x x x на множині перестановок
(1, 2, 3, 4) з наступними додатковими обмеженнями:
122 ISSN 1028-9763. Математичні машини і системи, 2018, № 3
fn 1 2 3 4
1gn 2 3 4 1
2gn 1 3 2 4
3gn 4 3 1 2
Рисунок 3 – Матриця нормалізації
1 1 2 3 4
2 1 2 3 4
3 1 2 3 4
5 7 8,
4 3 9 12,
3 6 2 23.
g x x x x
g x x x x
g x x x x
Нормалізуємо додаткові обмеження згідно з цільовою функцією:
1 1 2 3 4
2 1 2 3 4
3 1 2 3 4
7 5 8,
4 3 9 12,
2 3 6 23.
g x x x x
g x x x x
g x x x x
Тоді матриця нормалізації буде мати ви-
гляд (рис. 3).
Точка (4321) – перша гранична точка, що
задовольняє обмеження 1g : 1(4321) 24 8g .
Користуючись матрицею нормалізації, знахо-
димо значення другого обмеження:
2 (1342) 9 12g . Тому дану точку не можна
вважати опорним розв’язком.
Беремо граничну точку (1234) для обмеження 2 (1234) 29 12g . З урахуванням ма-
триці нормалізації здійснюємо перевірку таких двох обмежень: 1(3241) 14 8g ,
3(4213) 15 23g .
Отже, т. (1324) буде першим опорним розв’язком, при якому мінімальне значення
цільової функції 1(1324) 57f . Тоді початковими значеннями варто вважати:
1 (3241) 14
поч
g , 2 (1234) 29
поч
g , 3 (4213) 15
поч
g , 1 (1324) 57
поч
f .
Здійснюємо покращення опорного розв’язку за рахунок таких транспозицій у пере-
становках:
1 4 : т. (4321) , 14 (( 2)*4 12*1) (( 2)*1 12*4) 42f ,
1 3 : т. (3124) , 13 (( 2)*3 ( 1)*1) (( 2)*1 ( 1)*3) 2f ,
1 2 : т. (2314) , 12 (( 2)*2 7*1) (( 2)*1 7*2) 9f ,
3 4 : т. (1423) , 34 (( 1)*4 12*3) (( 1)*3 12*4) 13f ,
2 4 : т. (1342) , 24 (7*4 12*2) (7*2 12*4) 10f .
Упорядкуємо прирости функцій f за спаданням:
13 2f , 12 9f , 24 10f , 34 13f , 14 42f ,
13f > 12f > 34f > 14f 14min (4321)nf f .
Знаходимо прирости обмежень та перевіряємо їх виконання:
2 1
11 11 11(3214) 21 9 12g g g , 11 11 1 12 14 2g g g , 11 8g ,
2 1
21 21 21(4231) 52 13 39g g g , 21 21 2 39 29 10g g g , 11 12g .
Отже, обмеження не виконується.
Беремо такий 1 34min (1423) 13nf f .
ISSN 1028-9763. Математичні машини і системи, 2018, № 3 123
Проводимо аналогічні обчислення:
2 1
12 12 12(4231) 25 17 8g g g , 12 12 1 8 14 22g g g , 12 8g ,
2 1
22 22 22(1243) 31 39 8g g g , 21 21 2 29 8 21g g g , 22 12g ,
2 1
31 31 31(3214) 18 10 8g g g , 21 21 2 8 15 23g g g , 22 12g .
Отже, всі нерівності справджуються, тому т. (1423) є оптимальним розв’язком. Тоб-
то, 34 (1423)оптf f , 34 (1423)оптf f відповідно до (8), min 1 34(1423) 57 13f f f ,
min 44f .
5. Висновки
У роботі розглянуто постановку оптимізаційної задачі мінімізації на комбінаторній мно-
жині перестановок, запропоновано та описано алгоритм знаходження оптимального
розв’язку.
Алгоритм розв’язання складається із п’яти кроків, які забезпечують знаходження
оптимального розв’язку, при якому цільова функція набуває мінімального значення.
На першому кроці знаходиться опорний розв’язок, який задовольняє всі обмеження
задачі. Шляхом транспозицій даного розв’язку визначаються всі інші можливі оптимальні
розв’язки. Мінімальний приріст цільової функції дозволяє знайти найкращий серед них,
після чого здійснюється перевірка обмежень.
Слід відмітити, що за рахунок використання транспозиції елементів у перестановці
значно скорочуються кроки розв’язання задачі. У наведеному числовому прикладі
розв’язок було знайдено за шість кроків при чому при покращенні опорного розв’язку бу-
ло розглянуто п’ять транспозицій, у той же час, при повному переборі, необхідно було б
проводити розрахунок по 24 перестановках, з урахуванням обмежень. Отже, даний алго-
ритм забезпечує найкоротший шлях знаходження оптимального розв’язку, при якому до-
сягається мінімальне значення цільової функції на множині перестановок.
Надалі наукові дослідження будуть спрямовані на адаптацію даного алгоритму для
розв’язування задач оптимізації з багатьма цільовими функціями на інших комбінаторних
множинах.
СПИСОК ДЖЕРЕЛ
1. Роберт С., Кевин У. Алгоритмы на java. М.: Питер, 2013. 848 с.
2. Донец Г.А. Колечкина Л.Н. Построение гамильтонова пути в графах перестановочных много-
гранников. Кибернетика и системный анализ. 2010. № 1. С. 10–16.
3. Донець Г.П., Нагірна А.М. Умовна оптимізація лінійної функції на перестановках. Теорія опти-
мальних рішень. 2014. С. 16–23.
4. Донець Г.П., Нагірна А.М. Метод оптимізації лінійної функції на перестановках. Теорія оптима-
льних рішень. 2018. С. 138–145.
5. Донец Г.А., Колечкина Л.Н. Алгоритм поиска значений линейной функции на лексикографичес-
ки упорядоченных перестановках. Теорія оптимальних рішень. 2009. № 8. С. 3–8.
6. Донец Г.А., Колечкина Л.Н. Об одном подходе к решению комбинаторной задачи оптимизации
на графах. Управляющие системы и машины. 2009. № 4. С. 36–42.
7. Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms. New York, 2012. 660 p.
8. Pardalos P.M., Du D. Handbook of combinatorial optimization / Eds. R.L. Graham. New York, 2013.
3409 p.
9. Pichuginа O., Yakovlev S. Convex extensions and continuous functional representations in
optimization, with their applications. J. Coupled Syst. Multiscale Dyn. 2016. Vol. 2, N 4. P. 129–152.
10. Pichuginа O., Yakovlev S. Continuous Approaches to the Unconstrained Binary Quadratic Problems.
Mathematical and Computational Approaches in Advancing Modern Science and Engineering / Ed.
124 ISSN 1028-9763. Математичні машини і системи, 2018, № 3
J. Bélair et al. Switzerland: Springer, 2016. P. 689–700.
11. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. К.: ІСДО, 1993.
188 с.
12. Semenova N.V., Kolechkina L.N., Nagornaya A.N. On an approach to the solution of vector problems
with linear-fractional criterion functions on a combinatorial set of arrangements. Upravlen. Inform. 2010.
N 1. P. 131–144.
13. Semenova N.V., Kolechkina L.N. Vector problems of discrete optimization on combinatorial sets:
methods of research and solution. Kyiv: Naukova Dumka, 2009. N 4. 266 p.
14. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Подход к решению векторных задач дискретной
оптимизации на комбинаторном множестве перестановок. Кибернетика и системный анализ. 2008.
№ 3. С. 158–172.
15. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Векторные задачи оптимизации с линейными
критериями на нечетко заданном комбинаторном множестве альтернатив. Кибернетика и
системный анализ. 2011. № 2. С. 88–99.
16. Koliechkina L.N., Dvirna O.A., Nagornaya A.N. Modified Coordinate Method to Solve Multicriteria
Optimization Problems on Combinatorial Configurations Multicriteriality. Cybernetics and Systems
Analysis. 2014. N 4. P. 154–161.
17. 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. Vol. 53, N 4. P. 590–599.
18. Pichugina O.S., Koliechkina L.N. Two criterial combination model of optimization telecommunication
networks. Mathematical Machines and Systems. 2017. Vol. 4. P. 126–144.
19. Колєчкіна Л.М., Нагірна А.М. Математична модель багатокритеріальної оптимізації на
множині сполучень при побудові комп’ютерних мереж. Математичні машини і системи. 2016.
№ 4. С. 68–73.
Стаття надійшла до редакції 25.08.2018
|
| id | nasplib_isofts_kiev_ua-123456789-150647 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:37:57Z |
| publishDate | 2018 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Колєчкіна, Л.М. Нагірна, А.М. 2019-04-11T16:38:00Z 2019-04-11T16:38:00Z 2018 Розв’язування оптимізаційної комбінаторної задачі мінімізації / Л.М. Колєчкіна, А.М. Нагірна // Математичні машини і системи. — 2018. — № 3. — С. 117-124. — Бібліогр.: 19 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/150647 519.8 У роботі представлено математичну модель оптимізаційної задачі мінімізації на комбінаторній множині перестановок, яка може бути моделлю багатьох прикладних задач. Математична модель на комбінаторній множині перестановок, згідно з методом їх генерування, розглядається на графі, вершини якого відповідають точкам множини перестановок. В работе представлена математическая модель оптимизационной задачи минимизации на комбинаторном множестве перестановок, которая может быть моделью многих прикладных задач. Математическая модель на комбинаторном множестве перестановок по методу их генерирования рассматривается на графе, вершины которого соответствуют точкам множества перестановок. The paper presents a mathematical model of optimization minimization problem on a combinatorial set of permutations, which can be a model of many applied problems. A mathematical model on a combinatorial set of permutations by the method of generating them is considered on a graph the vertices of which correspond to the points of the set of permutations. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління Розв’язування оптимізаційної комбінаторної задачі мінімізації Решение оптимизационной комбинаторной задачи минимизации Solution of optimization combinatorial minimization problem Article published earlier |
| spellingShingle | Розв’язування оптимізаційної комбінаторної задачі мінімізації Колєчкіна, Л.М. Нагірна, А.М. Моделювання і управління |
| title | Розв’язування оптимізаційної комбінаторної задачі мінімізації |
| title_alt | Решение оптимизационной комбинаторной задачи минимизации Solution of optimization combinatorial minimization problem |
| title_full | Розв’язування оптимізаційної комбінаторної задачі мінімізації |
| title_fullStr | Розв’язування оптимізаційної комбінаторної задачі мінімізації |
| title_full_unstemmed | Розв’язування оптимізаційної комбінаторної задачі мінімізації |
| title_short | Розв’язування оптимізаційної комбінаторної задачі мінімізації |
| title_sort | розв’язування оптимізаційної комбінаторної задачі мінімізації |
| topic | Моделювання і управління |
| topic_facet | Моделювання і управління |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/150647 |
| work_keys_str_mv | AT kolêčkínalm rozvâzuvannâoptimízacíinoíkombínatornoízadačímínímízacíí AT nagírnaam rozvâzuvannâoptimízacíinoíkombínatornoízadačímínímízacíí AT kolêčkínalm rešenieoptimizacionnoikombinatornoizadačiminimizacii AT nagírnaam rešenieoptimizacionnoikombinatornoizadačiminimizacii AT kolêčkínalm solutionofoptimizationcombinatorialminimizationproblem AT nagírnaam solutionofoptimizationcombinatorialminimizationproblem |