Двокритеріальна комбінаторна модель оптимізації телекомунікаційних мереж
У роботі представлено математичну модель прикладної задачі визначення швидкості та якості передачі інформації по телекомунікаційній мережі як багатокритеріальної задачі евклідової комбінаторної оптимізації. Вона представляє собою двокритеріальну квадратичну умовну модель на композиційному образі заг...
Gespeichert in:
| Veröffentlicht in: | Математичні машини і системи |
|---|---|
| Datum: | 2017 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2017
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/131993 |
| 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: | Двокритеріальна комбінаторна модель оптимізації телекомунікаційних мереж / О.С. Пічугіна, Л.М. Колєчкіна // Математичні машини і системи. — 2017. — № 4. — С. 129-144. — Бібліогр.: 25 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-131993 |
|---|---|
| record_format |
dspace |
| spelling |
Пічугіна, О.С. Колєчкіна, Л.М. 2018-04-08T14:16:50Z 2018-04-08T14:16:50Z 2017 Двокритеріальна комбінаторна модель оптимізації телекомунікаційних мереж / О.С. Пічугіна, Л.М. Колєчкіна // Математичні машини і системи. — 2017. — № 4. — С. 129-144. — Бібліогр.: 25 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/131993 519.85 У роботі представлено математичну модель прикладної задачі визначення швидкості та якості передачі інформації по телекомунікаційній мережі як багатокритеріальної задачі евклідової комбінаторної оптимізації. Вона представляє собою двокритеріальну квадратичну умовну модель на композиційному образі загальної множини переставлень і булевої множини. Запропоновано підходи до її розв’язання, такі як метод гілок та меж, метод відсікань; графові методи, такі як метод направленого структурування та поліедрально-поверхневі методи. Метод опуклих продовжень застосовано до перетворення моделі на опуклу задачу евклідової комбінаторної оптимізації і таким чином обґрунтовано застосовність поліедрально-сферичних методів оптимізації до розв’язання поставленої задачі. В работе представлена математическая модель прикладной задачи определения скорости и качества передачи информации в телекоммуникационной сети в виде многокритериальной задачи евклидовой комбинаторной оптимизации. Она представляет собой двухкритериальную квадратичную условную модель на композиционном образе общего множества перестановок и булевого множества. Предложены подходы к ее решению, такие как метод ветвей и границ, метод отсечений; графовые методы, такие как метод направленного структурирования и полиэдрально-поверхностные методы. Метод выпуклых продолжений применен к переводу модели в выпуклую задачу евклидовой комбинаторной оптимизации и таким образом обоснована применимость полиэдрально-сферических методов оптимизации к решению поставленной задачи. A mathematical model of application problem of determining a speed and a quality of the information transmission through telecommunication networks is presented in the form of a multiobjective Euclidean combinatorial optimization problem. It is a two-objective quadratic constrained model over a compositional image of the general set of permutation and the Boolean set. Approaches to the problem solution such as the branch and bound method, cutting method, graph methods such as the directed structuring and the polyhedral-surface methods are suggested. The convex extensions method is applied to the transformation of the model into the convex Euclidean combinatorial optimization problem. Thus the applicability of polyhedral-spherical optimization methods to solving the problem is demonstraited. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління Двокритеріальна комбінаторна модель оптимізації телекомунікаційних мереж Двухкритериальная комбинаторная модель оптимизации телекоммуникационных сетей Two-criteria combinatorial model of optimization of telecommunication networks 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 |
2017 |
| language |
Ukrainian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Двухкритериальная комбинаторная модель оптимизации телекоммуникационных сетей Two-criteria combinatorial model of optimization of telecommunication networks |
| description |
У роботі представлено математичну модель прикладної задачі визначення швидкості та якості передачі інформації по телекомунікаційній мережі як багатокритеріальної задачі евклідової комбінаторної оптимізації. Вона представляє собою двокритеріальну квадратичну умовну модель на композиційному образі загальної множини переставлень і булевої множини. Запропоновано підходи до її розв’язання, такі як метод гілок та меж, метод відсікань; графові методи, такі як метод направленого структурування та поліедрально-поверхневі методи. Метод опуклих продовжень застосовано до перетворення моделі на опуклу задачу евклідової комбінаторної оптимізації і таким чином обґрунтовано застосовність поліедрально-сферичних методів оптимізації до розв’язання поставленої задачі.
В работе представлена математическая модель прикладной задачи определения скорости и качества передачи информации в телекоммуникационной сети в виде многокритериальной задачи евклидовой комбинаторной оптимизации. Она представляет собой двухкритериальную квадратичную условную модель на композиционном образе общего множества перестановок и булевого множества. Предложены подходы к ее решению, такие как метод ветвей и границ, метод отсечений; графовые методы, такие как метод направленного структурирования и полиэдрально-поверхностные методы. Метод выпуклых продолжений применен к переводу модели в выпуклую задачу евклидовой комбинаторной оптимизации и таким образом обоснована применимость полиэдрально-сферических методов оптимизации к решению поставленной задачи.
A mathematical model of application problem of determining a speed and a quality of the information transmission through telecommunication networks is presented in the form of a multiobjective Euclidean combinatorial optimization problem. It is a two-objective quadratic constrained model over a compositional image of the general set of permutation and the Boolean set. Approaches to the problem solution such as the branch and bound method, cutting method, graph methods such as the directed structuring and the polyhedral-surface methods are suggested. The convex extensions method is applied to the transformation of the model into the convex Euclidean combinatorial optimization problem. Thus the applicability of polyhedral-spherical optimization methods to solving the problem is demonstraited.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/131993 |
| citation_txt |
Двокритеріальна комбінаторна модель оптимізації телекомунікаційних мереж / О.С. Пічугіна, Л.М. Колєчкіна // Математичні машини і системи. — 2017. — № 4. — С. 129-144. — Бібліогр.: 25 назв. — укр. |
| work_keys_str_mv |
AT píčugínaos dvokriteríalʹnakombínatornamodelʹoptimízacíítelekomuníkacíinihmerež AT kolêčkínalm dvokriteríalʹnakombínatornamodelʹoptimízacíítelekomuníkacíinihmerež AT píčugínaos dvuhkriterialʹnaâkombinatornaâmodelʹoptimizaciitelekommunikacionnyhsetei AT kolêčkínalm dvuhkriterialʹnaâkombinatornaâmodelʹoptimizaciitelekommunikacionnyhsetei AT píčugínaos twocriteriacombinatorialmodelofoptimizationoftelecommunicationnetworks AT kolêčkínalm twocriteriacombinatorialmodelofoptimizationoftelecommunicationnetworks |
| first_indexed |
2025-11-25T21:07:32Z |
| last_indexed |
2025-11-25T21:07:32Z |
| _version_ |
1850551029986230272 |
| fulltext |
© Пічугіна О.С., Колєчкіна Л.М., 2017 129
ISSN 1028-9763. Математичні машини і системи, 2017, № 4
УДК 519.85
О.С. ПІЧУГІНА
*
, Л.М. КОЛЄЧКІНА
**
ДВОКРИТЕРІАЛЬНА КОМБІНАТОРНА МОДЕЛЬ ОПТИМІЗАЦІЇ
ТЕЛЕКОМУНІКАЦІЙНИХ МЕРЕЖ
*
Харківський національний університет радіоелектроніки, м. Харків, Україна
**
Полтавський університет економіки і торгівлі, м. Полтава, Україна
Анотація. У роботі представлено математичну модель прикладної задачі визначення швидкості
та якості передачі інформації по телекомунікаційній мережі як багатокритеріальної задачі евк-
лідової комбінаторної оптимізації. Вона представляє собою двокритеріальну квадратичну умовну
модель на композиційному образі загальної множини переставлень і булевої множини. Запропоно-
вано підходи до її розв’язання, такі як метод гілок та меж, метод відсікань; графові методи, та-
кі як метод направленого структурування та поліедрально-поверхневі методи. Метод опуклих
продовжень застосовано до перетворення моделі на опуклу задачу евклідової комбінаторної оп-
тимізації і таким чином обґрунтовано застосовність поліедрально-сферичних методів оптиміза-
ції до розв’язання поставленої задачі.
Ключові слова: телекомунікаційна мережа, передача інформації, багатокритеріальна оптиміза-
ція, евклідова комбінаторна оптимізація, суперкритерій, загальна множина переставлень, булева
множина, метод направленого структурування, опукле продовження функції, вершинно розташо-
вана множина, сферично розташована множина, поліедрально-сферичний метод.
Аннотация. В работе представлена математическая модель прикладной задачи определения ско-
рости и качества передачи информации в телекоммуникационной сети в виде многокритериаль-
ной задачи евклидовой комбинаторной оптимизации. Она представляет собой двухкритериальную
квадратичную условную модель на композиционном образе общего множества перестановок и
булевого множества. Предложены подходы к ее решению, такие как метод ветвей и границ, ме-
тод отсечений; графовые методы, такие как метод направленного структурирования и полиэд-
рально-поверхностные методы. Метод выпуклых продолжений применен к переводу модели в вы-
пуклую задачу евклидовой комбинаторной оптимизации и таким образом обоснована примени-
мость полиэдрально-сферических методов оптимизации к решению поставленной задачи.
Ключевые слова: телекоммуникационная сеть, передача информации, многокритериальная опти-
мизация, евклидова комбинаторная оптимизация, суперкритерий, общее множество перестано-
вок, булевое множество, метод направленного структурирования, выпуклое продолжение функ-
ции, вершинно расположенное множество, сферически расположенное множество, полиэдраль-
но-сферический метод.
Abstract. A mathematical model of application problem of determining a speed and a quality of the
information transmission through telecommunication networks is presented in the form of a multiobjective
Euclidean combinatorial optimization problem. It is a two-objective quadratic constrained model over a
compositional image of the general set of permutation and the Boolean set. Approaches to the problem
solution such as the branch and bound method, cutting method, graph methods such as the directed
structuring and the polyhedral-surface methods are suggested. The convex extensions method is applied to
the transformation of the model into the convex Euclidean combinatorial optimization problem. Thus the
applicability of polyhedral-spherical optimization methods to solving the problem is demonstraited.
Keywords: telecommunication network, information transmission, multiobjective optimization, Euclidean
combinatorial optimization, supercriterion, the general permutation set, boolean set, directional
structuring method, convex function, vertex-located set, spherically-located set, polyhedral-spherical
method.
1. Вступ
Створення ефективного інформаційного простору передбачає активне використання теле-
комунікаційних систем і мереж інформаційного обміну, широкомасштабну комп'ютериза-
130 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
цію процесів обробки інформації в усіх сферах діяльності. Інформаційна інфраструктура –
це комплекс програмно-технічних засобів, організаційних систем і нормативних баз, який
забезпечує організацію взаємодії інформаційних потоків, функціонування і розвиток засо-
бів інформаційної взаємодії та інформаційного простору світу, континенту, країни, регіону
чи організації [1–6].
Інформаційна інфраструктура включає в себе територіально розподілені державні та
корпоративні комп'ютерні і телекомунікаційні мережі, системи конфіденційного призна-
чення і загального користування, мережі та канали передачі даних, засоби комутації та
управління інформаційними потоками.
Поява мобільного зв'язку та бездротових мереж істотно вплинула на організацію
телекомунікаційних мереж, і на сьогоднішній день вони охоплюють величезні території з
великим числом користувачів [1]. Серед багатьох вимог, що висуваються до бездротових
мереж, основною є забезпечення високої продуктивності з гарантованою якістю обслуго-
вування запитів користувачів. Сфера телекомунікацій є одним із найбільших секторів сві-
тової економіки, що динамічно розвивається і формує передумови для подальшого розвит-
ку інформаційного суспільства. Світова телекомунікаційна сфера надає широкий спектр
сучасних телекомунікаційних та інформаційно-комунікаційних послуг, якісні характерис-
тики яких відповідають потребам найвимогливіших споживачів. У той же час, розвиток
сфери телекомунікацій, у свою чергу, значно впливає як на соціальний, так і на економіч-
ний розвиток багатьох країн. Отже, дослідження питань, пов'язаних з визначенням ступеня
і закономірностей впливу розвитку телекомунікацій на розвиток економіки в цілому, акту-
альні.
2. Постановка задачі
В організації будь-якої телекомунікаційної мережі можна виділити рівні, які відокремлені
територіально і взаємодіють між собою. У свою чергу, ці рівні системи можна розглядати
як накладені мережі різних технологій.
Абсолютна більшість інформаційних потоків, що передаються в сучасних телеко-
мунікаційних мережах, утворюють мультимедійний трафік. Він характеризується нерівно-
мірністю надходження запитів на передачу потоків мультимедійної інформації, що приз-
водить до виникнення як тимчасових перевантажень у мережі, так і інтервалів часу з недо-
статньою завантаженістю каналів [1]. Внаслідок цього, канали мережі використовуються
недостатньо ефективно. Відомі різні методики кількісної оцінки ефективності використан-
ня каналів телекомунікаційної мережі [5, 7]. Їх аналіз свідчить про те, що вони не дозво-
ляють точно визначити, наскільки раціонально використовується пропускна здатність ка-
налів мережі. Тому вважається за доцільне знайти такий спосіб обчислення завантаженості
каналу і якості передачі інформації, який відображав би реальну ефективність використан-
ня канальних ресурсів.
З цією метою розглянемо телекомунікаційну систему, що накопичує інформацію по
предметних областях (порталах) і здійснює передачу інформації на сервери, робочі станції,
термінали тощо. Необхідно скласти такий план розподілу деякого об'єму інформації по
предметних областях на порталах і її передачі, щоб мінімізувати сумарну швидкість її пе-
редачі на комп'ютери і максимізувати сумарний якісний коефіцієнт завантаження. При
цьому необхідно врахувати інтенсивність потоку запитів на передачу інформації по каналу
телекомунікаційної мережі; середню швидкість передачі потоку інформації; дискретність
обсягів інформації, що передається, тощо.
Зауважимо, що для вирішення даної проблематики в ряді робіт [8–10] пропонується
використовувати математичну модель мережі, що представляє собою набір графів, які мо-
жуть відрізнятися як кількістю ребер і вершин, так і топологією графів у цілому. Відзна-
чимо також, що в наведених роботах пропонується модель побудови телекомунікаційних
ISSN 1028-9763. Математичні машини і системи, 2017, № 4 131
мереж за умови, що місцезнаходження обладнання вузлів мережі, які забезпечують функ-
ціонування кожного з її рівнів, відоме.
Метою даної роботи є побудова математичної моделі даної задачі як багатокритері-
альної задачі евклідової комбінаторної оптимізації та пропонування підходів до її
розв’язання, що використовують властивості допустимої множини й особливості поведін-
ки функцій на цій множині.
3. Математична модель
Для побудови математичної моделі введемо необхідні позначення: визначимо m предмет-
них областей (порталів) і позначимо їх {1 }i mA , i J ,...,m . Нехай також k pI , k J визна-
чатиме набір видів інформації. Вважатимемо, що на кожному порталі iA накопичується
деяка невідома кількість k
ix одиниць інформації виду kI . Також відомо, що уся інформа-
ція розподіляється між n серверами (персональними комп'ютерами, терміналами), які поз-
начено j nB , j J .
Зауваження 1. В подальшому викладенні ми прив’яжемо використані вище індекси
i,k , j за номерами порталів, видами інформації та серверами. Будемо опускати границі
зміни цих індексів, маючи на увазі, що вони пробігають область зміни mi J , pk J ,
nj J . Таким чином,
{ } { } { }i i k k j jA , I , BA I B (1)
визначатиме множину усіх предметних областей, видів інформації та терміналів відповід-
но.
Потрібно скласти план розподілу інформації на порталах та передачі її на сервери з
метою мінімізації сумарного часу передачі інформації (далі критерій 1(.)F ) і максимізації
сумарного коефіцієнта якості відображення інформації (далі критерій 2 (.)F ) за умови ви-
конання таких умов:
• Обмеження 1. Невідомі k
ix набувають дискретних значень із мультимножини
1{ }sG g ,...,g , (2)
де =s m p , а в цілому вони утворюють усю цю мультимножину:
{ }k
i i,kx G . (3)
• Обмеження 2. Весь обсяг інформації k
ix передається на один із серверів із множи-
ни B , тобто передача здійснюється повним пакетом.
• Обмеження 3. Обсяг потоку інформації, що передається по каналу «предметна об-
ласть iA – сервер jB », не перевищує заданої наперед величини ijl ( )i, j .
• Обмеження 4. На кожному сервері jB має зберігатися щонайменше k
jb одиниць
інформації типу kI ( )j, k .
• Обмеження 5. Середня швидкість передачі потоку інформації обмежена знизу ве-
личиною minv , зверху – maxv .
Окрім множин (1) та відомих параметрів ijl , k
jb , minv , maxv , вхідними даними в за-
132 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
дачі є величини: а) k
ij – швидкість передачі одиниці інформації виду kI із предметної об-
ласті iA на сервер jB ; б) k
ijd – коефіцієнт якості відображення одиниці інформації виду kI
із області iA на сервері jB ( i, j,k ).
Також відомо, що сумарний коефіцієнт якості відображення інформації є сумою ко-
ефіцієнтів якості відображення по всіх предметних областях, типах інформації і серверах.
Для побудови математичної моделі задачі введемо в розгляд матрицю невідомих:
( )k p m
iX x R , (4)
що задає план передачі інформації, а також тривимірну булеву матрицю
11( ) , ={0 1}
n p mk
ij i, j,kY y ,B B (5)
для відображення плану розподілу цієї інформації на серверах. Тут 1k
ijy , якщо вся інфо-
рмація з області iA виду kI передається на сервер jB , інакше 0 .
Для зручності також будемо використовувати величину
k k k
ij i ijz x y – (6)
обсяг інформації з області iA виду kI , що передається на сервер jB .
Зауважимо, що величина k
ijz буде елементом мультимножини
0 {0}G G , де G –
це вихідна мультимножина (2):
0k k k
ij i ijz x y G ( )i, j,k .
Наша задача полягає у визначенні матриць (4, 5), які доставляють мінімум функції
1( )F . , максимум функції 2 ( )F . та задовольняють Обмеження 1–5.
Формалізуємо дану задачу як задачу евклідової комбінаторної оптимізації. З цією
метою проведемо занурення матриць невідомих (4, 5) в евклідів арифметичний простір. А
саме:
а) матриці (4) поставимо у відповідність вектор n pRx :
1 1
1 1( ,..., ,..., ,..., )
p p
m mx x x xx , після чого комбінаторне Обмеження 1 можна представити у
вигляді
( )ss'E Gx , (7)
де ( )ss'E G – загальна множина s -перестановок із мультимножини G [10, 11], де s – по-
тужність G , в s' – кількість різних елементів у ньому. Не обмежуючи загальності, вважа-
тимемо, що елементи G впорядковані по неспаданню 1 1{ }, s sG g ,...,g g ... g ;
б) матриці (5) поставимо у відповідність вектор
1 1
11 1 1( ,..., ,..., ,..., )
p p n p m
n mnmy y y y Ry , після чого обмеження на його булевість можна
представити у вигляді
={0 1} , t
t , t = m n py B . (8)
Формалізуємо критерії:
ISSN 1028-9763. Математичні машини і системи, 2017, № 4 133
• Для першого критерію – відношення
k
ij
k
ij
z
визначає час передачі інформації виду
kI з області iA на сервер jB . Оскільки, згідно з умовою задачі, передача інформації здійс-
нюється на один сервер, це відношення нульове для усіх інших серверів, тобто виконуєть-
ся умова: якщо 0 0 '
k k
ij ij'
k k
ij ij'
z z
, j j .
Сумуючи всі ці відношення, отримуємо загальний час передачі всієї інформації:
1
1 1 1 1 1 1
( )
k kp pm n m n
ij ijk
ik k
ij ijk i j k i j
z y
F , xx y . (9)
Наша мета – мінімізувати функцію (9), тобто задача полягає в тому, щоб знайти па-
ру ( )* *,x y :
1 1( , ) ( , )
s t
* *
R , R
F min F
x y
x y x y . (10)
• Другий критерій стосується якості відображення інформації. Величина k k
ij ijd z є ко-
ефіцієнтом передачі усієї інформації виду kI з області iA на сервер jB . Як і у поперед-
ньому випадку, вона набуває нульового значення для всіх серверів, крім одного:
0 0 'k k k k
ij ij ij ijd z d z , j j .
Тоді другий критерій має вигляд
2
1 1 1 1 1 1
( )
p pm n m n
k k k k k
ij ij i ij ij
k i j k i j
F , d z x d yx y , (11)
а мета задачі полягає в тому, щоб знайти ( , )* *
x y , що в тому числі максимізує функцію
(11):
2 2( , ) ( , )
s t
* *
R , R
F max F
x y
x y x y . (12)
Перейдемо до формалізації обмежень.
• Обмеження 2 на передачу інформації одного типу з порталу повним пакетом буде
мати вигляд (8, 13)
1
1, ( )
n
k
ij
j
y i,k . (13)
• Обмеження 3 на обсяги потоків інформації по предметних областях:
1 1
( , )
p p
k k k
ij ij i ij
k k
z y x l i j . (14)
• Обмеження 4 на обсяги завантаження серверів інформацією відповідних типів:
134 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
1 1
( )
m m
k k k k
ij i ij j
i i
z g y b j,k . (15)
• Сформуємо Обмеження 5 на середню швидкість передачі інформації. Оскільки,
виходячи з (3), загальний обсяг інформації
1 1
p m
k
G i
k i
g , (16)
то середня швидкість v визначається діленням величини G на загальний час передачі
інформації:
1( , )
Gv
F x y
. Відповідно, Обмеження 5 матиме вигляд min maxv v v . Його
також можна переписати як двостороннє обмеження на цільову функцію (9):
1 1
1( , )G max G minv F vx y . (17)
Зауваження 2. У формулі (9) доданки
k
ij
k
ij
z
виражають час передачі усього обсягу ін-
формації iA виду kI на сервер jB . Відповідно, 1( , )F x y – це сумарний час передачі наяв-
ної інформації, тобто час використання усіх каналів передачі інформації. Враховуючи, що
кількість цих каналів n , то 1( , )F
n
x y
– це очікуваний час використання одного каналу пере-
дачі інформації, який ми мінімізуємо, розв’язуючи задачу з критерієм (10). У разі, якщо
нас цікавить передача інформації якомога швидше, цей критерій можна замінити таким
(далі Критерій 3 (.)F ): 3
1 1 1 1
( , )
k k kp pm m
ij i ij
k kj jij ijk i k i
z x y
F max maxx y . Відповідно, формула (9)
перетворюється на 3 3( , ) ( , )
s t
* *
R , R
F min F
x y
x y x y .
Проведемо аналіз моделі (9–17) (далі Модель 1). Вона двокритеріальна, умовна,
квадратична, лінійна по кожній групі змінних (7) і (8), комбінаторна, комбінаторним прос-
тором якої є множина, що є декартовим добутком загальної множини перестановок
(G)ss'E та булевої множини tB . Отже, ми маємо справу з задачею оптимізації, яка: а)
комбінаторна на ( )ss' tE GE B ; б) двокритеріальна; в) умовна; г) нелінійна за рахунок
k
ijz (6). Більше того, вона квадратична, адже цільові функції (10, 12) квадратичні неопуклі,
та обмеження (14–17) – також квадратичні неопуклі; д) лінійна по відношенню до кожної
окремої групи змінних ,x y ((7) і (8)).
Також, вище сформульована задача дозволяє переформулювати її на множині буле-
вих поліперестановок:
( , ) ( ) (1)ss' n' E Gx y E B , (18)
де
1
2(1) (1) (1) ({0 1})
m
p
n
n n n n
i J ,
k J
B , B E ,B . Це стає можливим, враховуючи, що умови
ISSN 1028-9763. Математичні машини і системи, 2017, № 4 135
(8) і (13) можна об’єднати в єдину умову (1)ny B , відповідно, умови (7, 8, 13) можна
представити у вигляді (18). В результаті отримано нову задачу (9–12), (14–18) (далі Мо-
дель 2). Ця нова модель є моделлю задачі багатокритеріальної оптимізації на скінченній
дискретній множині точок простору NR , де N s t . Саме Модель 2 будемо розглядати в
подальшому і саме для неї пропонуватимемо методи розв’язання.
Модель 2: підходи до розв’язання
A. Постановка багатокритеріальної задачі евклідової комбінаторної оптимізації
Багатокритеріальна оптимізація передбачає оптимізацію кількох критеріїв одночасно, при-
чому ці критерії можуть як максимізуватися, так і мінімізуватися, оскільки у практичному
застосуванні часто виникає потреба у зменшенні одних критеріїв та збільшенні інших [12-
14]. Якщо при цьому оптимізація здійснюється на деякому комбінаторному просторі, зада-
ча являє собою багатокритеріальну задачу комбінаторної оптимізації [10, 15, 16]. Її мате-
матична модель виглядає таким чином:
L'
L L'
( )
( )
l
l
f x min, l J ,
f x max, l J \ J ,
x X E',
(19)
де 'E – комбінаторний простір, X – множина допустимих розв’язків задачі, а функції
L( ) lf x , l J визначені на 'E .
Набір цільових функцій у (19) можна представити у вигляді вектор-функції:
1 1( ( ) ( ) ( ) ( ))L' L' LF f x , , f x , f x , , f x , (20)
максимум якої необхідно знайти. Слід зазначити, що кожний розв’язок
1 2( )nx x ,x ,...,x X характеризується відповідною векторною оцінкою, тобто вектором
( )F x . Тому вибір оптимального розв’язку із множини всіх розв’язків зводиться до вибору
оптимальної оцінки із множини оцінок:
( ) { ( ) }lY F X y R y F x ,x X .
При цьому оптимальність оцінок (розв’язків) визначається деяким принципом оп-
тимальності, заданим у критеріальному просторі.
Надалі ми будемо вважати, що комбінаторний простір 'E – непорожня скінченна
множина точок NR і будемо розглядати векторну (багатокритеріальну) задачу ( )Z F ,X
максимізації векторного критерію 1( )LF f ,..., f , визначеного на 'E :
( )
N
Z F ,X max,
x X ' R .E
(21)
Якщо множина 'E є образом в NR деякої множини A реальних комбінаторних
об’єктів, причому між елементами 'E та A можна встановити бієкцію, то множини 'E і
A будуть евклідовими комбінаторними множинами [17], а (21) являтиме собою загальну
математичну модель багатокритеріальної задачі евклідової комбінаторної оптимізації [11].
З іншого боку, той факт, що задачу сформульовано в термінах координат вектора x , свід-
чить про те, що розглядається її постановка як задачі багатокритеріальної дискретної оп-
тимізації.
136 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
B. Багатокритеріальні задачі евклідової комбінаторної оптимізації: підходи до
розв’язання
Під розв’язанням цієї задачі, як правило, розуміють знаходження елементів однієї із таких
множин [10]:
1. Множини ідеальних ( , )I F X розв’язків:
( ) { ( ) },I F ,X x X : x,F ,X (22)
де ( ) { ( ) ( )}L i iv x,F,X y X | i J : f y f x .
2. Множини Парето ( )P F ,X , тобто множини ефективних (оптимальних за Парето)
розв’язків:
( ) { ( ) }P F,X x X : x,F ,X , (23)
де ( ) { ( ) ( ) ( ) ( )}x,F ,X y X : F y F x ,F y F x .
3. Множини Слейтера ( )Sl F ,X слабоефективних розв’язків:
( ) { ( ) }Sl F,X x X : x,F ,X , (24)
де ( ) { ( ) ( )}x,F ,X y X : F y F x .
4. Множини Смейла ( )Sm F ,X строгоефективних розв’язків:
( ) { ( ) }Sm F,X x X : x,F ,X , (25)
де ( ) { { } ( ) ( )}x,F ,X y X \ x : F y F x .
Відзначимо, що елемент множини (22) називається ідеальним розв’язком [12–14].
Цей розв’язок є найкращим відразу за всіма частковими критеріями. Оптимальність за Па-
рето (23) означає, що значення будь-якого із часткових критеріїв можна збільшити лише за
рахунок зменшення значення хоча б одного з інших часткових критеріїв. Для слабоефек-
тивної оцінки (розв’язку) (24) не знайдеться такої оцінки (розв’язку), яка була б більше ві-
дразу за всіма частковими критеріями. Внаслідок цього множини (22–25) зв’язані таким
чином: ( ) ( ) ( ) ( )I F ,X Sm F,X P F,X Sl F,X .
Проблема відшукання всіх ефективних розв’язків (оцінок) представляє не тільки те-
оретичний, але й великий практичний інтерес. Це пояснюється тим, що побудова всієї
множини ефективних розв’язків або ж деякої досить широкої її підмножини є одним із пе-
рших етапів у цілому ряді процедур оптимального вибору при багатьох критеріях [10],
[12–14]. Якщо розглядається багатокритеріальна комбінаторна задача (19), проблема її
розв’язання значно ускладнюється. Але якщо замість (19) розглядається задача (21) бага-
токритеріальної евклідової комбінаторної оптимізації, ці складнощі можна подолати за ра-
хунок використання специфіки задачі, зокрема, враховуючи властивості конкретної евклі-
дової комбінаторної множини та цільової функції на ній.
Переважна більшість методів побудови множини ефективних розв’язків ґрунтується
на тих або інших умовах оптимальності. Найчастіше використовуються необхідні умови,
що полягають у тому, що якщо точка 0x ефективна (у тому або іншому розумінні, напри-
клад, згідно з одним із критеріїв оцінки (22–25)), то вона є розв’язком задачі максимізації
або мінімізації (можливо, при деяких додаткових обмеженнях) числової функції спеціаль-
ного вигляду при належним чином призначених величинах параметрів, що входять у цю
функцію, і (або) обмеження. Отже, задача виділення всіх ефективних розв’язків зводиться
до відповідної скалярної параметричної задачі оптимізації. Таку заміну задачі з векторним
критерієм параметричним сімейством звичайних екстремальних задач часто називають
скаляризацією вхідної задачі. Якщо використовувані умови оптимальності є достатніми, то
ISSN 1028-9763. Математичні машини і системи, 2017, № 4 137
множина розв’язків параметричної задачі є шуканою множиною ефективних розв’язків ви-
хідної задачі. У протилежному випадку побудована шляхом скаляризації множина може
містити зайві точки, які варто виявити й відсіяти.
Одним із поширених методів розв’язання задач векторної оптимізації є метод зве-
дення багатокритеріальної задачі до однокритеріальної шляхом згортання векторного кри-
терію в суперкритерій [10, 12]. При цьому кожний критерій множиться на відповідний йо-
му ваговий коефіцієнт, а потім результати додаються. Так, для векторного критерію (20)
суперкритерій виглядатиме таким чином:
1
( ) ( ) 0 0
L
l l l L' l L L'
l
x F x , , l J , , l J \ J . (26)
Під час здійснення згортки (26) головне питання і основні труднощі виникають із
правильним вибором коефіцієнтів l L, l J . Існують різні способи їх вибору. Одним із
них є призначення коефіцієнта залежно від відносної важливості критеріїв [12].
Після формування суперкритерія (26) від задачі (21) здійснюється перехід до задачі
( ) ; Nx max x X ' R .E (27)
Вона являє собою задачу дискретної оптимізації, до розв’язання якої застосовувані
відповідні методи, такі як метод меж та гілок, метод відсікань, метод гілок і відсікань та ін.
[18, 19]. Також слід відзначити тут метод направленого структурування [10], який вважає-
мо перспективним для розв’язання задачі (27). Він полягає у представленні множини 'E у
вигляді орієнтованого графа, де дуга графа відповідає спаданню значень цільової функції.
У ході реалізації методу відбувається галуження і частина гілок відтинається на основі
аналізу множини допустимих розв’язків X як підмножини 'E . Якщо початкова задача
(19) – лінійна комбінаторна, тобто не тільки функції L( ) lf x , l J , але і додаткові обме-
ження, що виділяють X з 'E , – лінійні, то задача (27) буде лінійною задачею дискретного
програмування, до якої можна застосувати методи комбінаторних відсікань, у яких врахо-
вується специфіка комбінаторної множини 'E [20, 21]. Останні два методи - направленого
структурування та комбінаторних відсікань – можна віднести до методів евклідової комбі-
наторної оптимізації [11]. Ця група методів призначена для розв’язання задачі вигляду (27)
у випадку, якщо множина 'E – евклідова комбінаторна і вони передбачають комплексне
використання в них досліджених алгебро-топологічних властивостей множини 'E як мно-
жини точок евклідового простору та її опуклої оболонки, а також особливостей поведінки
функцій на цій множині.
Перед тим як викласти наступний метод, який також належить до класу методів ев-
клідової комбінаторної оптимізації, повернемося до Моделі 2 і зазначимо, що множина
(18) – евклідова комбінаторна і має таку властивість, що вона збігається з множиною вер-
шин своєї опуклої оболонки:
' vert ', ' conv 'E P P E , (28)
тобто вона є вершинно розташованою [22]. Це пояснюється тим фактом, що довільна зага-
льна множина перестановок та булева множина є вершинно розташованими [11], а опера-
ція декартового добутку зберігає вершинну розташованість множин.
З точку зору оптимізації, вершинна розташованість множини 'E , на якій прово-
диться оптимізація, важлива в тому плані, що вона дозволяє як цільову функцію, так і до-
даткові обмеження вважати опуклими або угнутими [23] в залежності від того, якими ме-
тодами ми розв’язуватимемо цю задачу.
Сформулюємо загальну задачу багатокритеріальної евклідової комбінаторної опти-
138 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
мізації на вершинно розташованій множині: знайти
( )
L'
*
l
x ', l J
x arg extr f x
E
(29)
за умови виконання обмежень:
( ) 0 ( ) 0 r R r R' Rh x , r J ; h x , r J \ J , (30)
де 'E задовольняє умову (28), а
L'
L' L
min, l J ,
extr
max, l J \ J ,
(31)
а функції ( ) ; ( ) 0 l L r Rf x , l J h x , r J визначені на 'E .
Якщо порівняти задачі (28–31) та (21), відмінністю буде те, що в першому випадку
множина допустимих розв’язків X виділяється з 'E в явному вигляді за допомогою функ-
ціональних обмежень (30), а також додається умова (28) на вершинну розташованість
множини 'E .
Отже, математична модель (28–31) є загальною постановкою багатокритеріальної
оптимізаційної задачі на вершинно розташованій множині.
Дана задача буде опуклою багатокритеріальною на комбінаторній множині E' , як-
що будуть виконані умови:
( ) - опуклі; ( ) - угнуті,l L l L' Lf x , l J f x , l J \ J (32)
( ) - опуклі; ( ) - угнуті.r R r R' Rh x , r J h x , r J \ J (33)
Зауваження 3. Не обмежуючи загальності, можна вважати, що умови (32, 33) вико-
нані, інакше можна побудувати опуклі продовження функцій ( ) l Lf x , l J , ( ) r Rh x , r J
чи угнуті продовження для ( ) l L' Lf x , l J \ J , ( ) r R' Rh x , r J \ J з множини 'E в евклідів
простір, існування яких для вершинно розташованих множин обґрунтовано у [22]. Нагада-
ємо, що опуклим продовженням функції ( )f x із множини 1E у її надмножину 2 1E E
називається функція ( )F x , що визначена на 2E і яка збігається з ( )f x на 1E , тобто
( ) ( )
E
F x f x . (34)
Внаслідок цього, відповідна однокритеріальна задача (27) матиме вигляд
( )x max (35)
за умови виконання обмежень (28, 30, 32, 33) і буде опуклою задачею евклідової комбіна-
торної оптимізації.
Враховуючи (28), її можна сформулювати як задачу неперервної оптимізації, що
має вигляд (32, 33, 35)
x P , (36)
x S , (37)
де P conv 'E – комбінаторний многогранник, який відповідає 'E , а S – строго опукла
поверхня, описана навколо 'E [24]. А це, у свою чергу, дозволяє застосувати до
розв’язання задачі (28, 32–35) поліедрально-поверхневі методи [24, 25]. Ця група методів
об’єднує як точні, так і наближені методи з оцінкою точності. Вони ґрунтуються на комбі-
нуванні двох релаксацій задачі (32–37) – поліедральній (33–36) та поверхневій (33, 35, 37),
ISSN 1028-9763. Математичні машини і системи, 2017, № 4 139
а також на можливості її редукції за рахунок декомпозиції вихідної задачі на подібні задачі
меншої вимірності. Той факт, що поліедральна релаксація є неперервною опуклою зада-
чею, дозволяє застосування апарата опуклого програмування до її розв’язання [26]. А це, у
свою чергу, дозволяє будувати якісні оцінки цільової функції у дискретній задачі (28, 32–
35), що і дозволяє створення ефективних апроксимаційних та точних методів її
розв’язання.
Як було зазначено у зауваженні 3, умова (28) дозволяє її уопуклювання, тобто здій-
снення переходу від довільної задачі вигляду (27, 28) до опуклої задачі (28, 32–35). На
практиці цей перехід зв’язаний із побудовою опуклих чи угнутих продовжень цільової фу-
нкції та обмежень, вигляд яких залежить як від самих функцій, так і від типу евклідової
комбінаторної множини E' .
Модель 2: приведення до опуклої евклідової комбінаторної задачі та застосування
У даному пункті буде продемонстровано, що до сформульованої вище задачі оптимізації
телекомунікаційних мереж застосовні поліедрально-поверхневі методи. Для цього у Моде-
лі 2 достатньо провести згортку (26) та уопуклювання, а також вказати строго опуклу по-
верхню, описану навколо множини 'E .
Як було показано вище, Модель 2 – нелінійна за рахунок присутності добутків
змінних k k
i ijx , y у цільових функціях та обмеженнях. Уопуклювання цієї комбінаторної за-
дачі буде ґрунтуватися на такому твердженні:
Твердження 1. Опукле продовження функції:
ij i jf x y , (38)
де
0 0( ) ( ) ( ) ( ) yx
n x n yx y
nnx y
i i J r j j J rx x E S x R , y y E S y R (тут ( )rS a –
гіперсфера з центром у точці a радіуса r ) з множини x yE E E на x yn n
R існує в такій
формі:
0 2 0 2 2 21
(( ) ( ) )
2
ij ij x yF f x x y y r r . (39)
Доведення.
2 2 2
2 2 0 2 2 2 0 2 2
0 2 0 2 2 2
1
(( ) )
2
1
(( ) ( ( ) ) ( ( ) ))
2
1
(( ) ( ) )
2
ij i j i j i j
E
i j i x j y
E
i j x y
f x y x y x y
x y x x x r y y y r
x y x x y y r r .
Як видно, у правій частині рівняння стоїть опукла функція, яку ми і обираємо як
опукле продовження, враховуючи (34).
Спираючись на твердження 1, побудуємо опукле квадратичне продовження k
ijZ фу-
нкції (6) у формі (39), користуючись умовою (7) та сферичною розташованістю множин
ss'E G і 1B [24]. Як сфери, описані навколо x та k
ijy , розглянемо сфери мінімального ра-
діуса. Отже, маємо
140 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
2
0 0 0 0 2 1
1
2
( ) 1
( ) ( ) ( )
2x s
s kG G
r i i J i s x G ijS R , x , x , i J , r ; y S R
s s
x x x , (40)
де G знайдено за формулою (16), а
2 2
1 1
( )
p m
k
G i
k i
g . (41)
Обираючи в виразі (39) = , k k
i i j ijx x y y , одержуємо
0 2 2 2
0 2 2
1
(( ) ( 0 5) 0 25)
2
0 5( ) 0 5( )
k k k k k k
ij i ij i ij ij x
'
k k k k
ij ij ij ij
z x y x y y , r ,
z , , y y Z .
E
x x
x x
(42)
Аналогічно побудуємо угнуте продовження ' k
ijZ функції (6) у формі (39):
0 2 2
0 2 2
( ) ( 0 5( ) 0 5( ))
0 5( ) 0 5( )
k k k k k k k k k
ij i ij i ij i ij ij ij
'
k k k ' k
ij ij ij ij
z x y x y x y , , y y
z , , y y Z .
E
x x
x x
(43)
Підставивши вирази (42, 43) у (9, 11) відповідно, отримаємо квадратичні продов-
ження: опукле для 1F ,x y та угнуте для 2F ,x y :
1
1 1 1 1 1 1 1 1 1
2
0 2 1
1 1 1 1 1 1
( )
0 5( ) ( ) 0 5
k k kp p pm n m n m n
ij ij ij
k k k'ij ij ijk i j k i j k i j
k kp pm n m n
ij ijk
ij k
ijk i j k i j
z Z z
F ,
y y
, ,
E
x y
x x
2
0 2
1 1
1 1 1
1
1 1 1
( ) 0 5 ( ) 0 5 ( )
де ( )
k kp m n
ij ij '
k
ijk i j
p m n
k
ij
k i j
y y
F , , , F , ,
.
x y x x x y
(44)
2
1 1 1 1 1 1 1 1 1
0 2 2
1 1 1 1 1 1
( )
0 5( ) 0 5 ( )
p p pm n m n m n
k k k k k k
ij ij ij ij ij ij
'
k i j k i j k i j
p pm n m n
k k k k
ij ij ij ij
k i j k i j
F , d z d Z d z
, d , d y y
E
x y
x x
ISSN 1028-9763. Математичні машини і системи, 2017, № 4 141
0 2 2
2 2
1 1 1
1 1 1
0 5 ( ) 0 5 ( ) ( )
де
p m n
k k k '
ij ij ij
k i j
p m n
k
ij
k i j
F , , D , d y y F , ,
D d .
x y x x x y
(45)
Результат згортки цільових функцій (44, 45):
1 1 2 2( ) ( ) ( )' ' 'F , F , F ,x y x y x y . (46)
Перейдемо до уопуклювання обмежень (14, 15, 17), враховуючи, що вони існують у
двох формах: а) ( )f x a , якщо ( )f x – опукла, а a – константа; б) ( )f x a , якщо ( )f x –
угнута.
• Для (14) маємо
1
1
( )
p
k
ij ij ij
k
f z l i, j ; (47)
• для (15):
2
1
( , )
m
k k
jk ij j
i
f z b j k ; (48)
• двостороннє обмеження (17) представимо у вигляді
1
1( ) G minF , vx y . (49)
1
1( ) G maxF , vx y . (50)
Для кожної з функцій (47) опукле продовження 1
ijF побудуємо з використанням фо-
рмули (42):
1 1 0 2 2 1
1 1 1
0 5 ( ) 0 5 ( )
p p p
k k k k
ij ij ij ij ij ij ij
'
k k k
f z Z z , p , y y F .
E
x x
Результуючі опуклі обмеження:
0 2 2
1 1
0 5 ( ) 0 5 ( ) ( )
p p
k k k k
i ij ij ij ij
k k
x y , p , y y l i, jx x . (51)
Опуклі продовження функцій 2
jkf побудуємо, використовуючи (43):
2 2 0 2 2
1 1 1
0 5 ( ) 0 5 ( )
m m m
k ' k k k
jk ij ij jk ij ij
'
i i i
f z Z f , m , y y
E
x x .
Шукані опуклі обмеження такі:
142 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
0 2 2
1 1
0 5 ( ) 0 5 ( ) ( )
m m
k k k k k
i ij ij ij j
i i
x y , m , y y b j,kx x . (52)
Обмеженню (49) відповідатиме таке, що містить опукле продовження з 1 ( )'F ,x y :
1
1 ( )'
G minF , vx y . (53)
Зрештою, до (50) опукле обмеження побудуємо, використовуючи (43):
0 2 1
1
1 1 1 1 1 1 1 1 1 1 1 1
2 2
0 2
1
1 1 1 1 1
( ) 0 5( ) ( )
0 5 ( ) 0 5 ( ) 0 5
k ' k kp p p pm n m n m n m n
ij ij ij k
ijk k kE'ij ij ijk i j k i j k i j k i j
k k k kp m n m n
ij ij ij ij
k k
ij ijk i j k i j
z Z z
F , ,
y y y y
, F , , ,
x y x x
x y x x
1
p
.
Тож обмеження матиме вигляд
2
0 2 1
1
1 1 1
( ) 0 5 ( ) 0 5
k kp m n
ij ij
G maxk
ijk i j
y y
F , , , vx y x x . (54)
Еквівалентна до Моделі 2 задача (далі Модель 3) пошуку вектора ( )* * N, Rx y з
евклідової комбінаторної множини (18) такого, що задовольняє обмеження (51–54) і доста-
вляє розв’язок двокритеріальної задачі:
1 1( ) ( )' * * '
, '
F , min F ,
x y E
x y x y , (55)
2 2
( )
( ) ( )' * * '
, '
F , max F ,
x y E
x y x y , (56)
у якій функції 1 ( )'F ,x y , 2( )'F ,x y задані формулами (44, 45).
Відповідна до Моделі 3 однокритеріальна модель (далі Модель 4) виду (26) має ви-
гляд
( )'F , maxx y , (57)
де ( )'F ,x y має вигляд (46), а змінні ,x y задовольняють обмеження (51–54).
Модель 4 – це математична модель вихідної задачі в вигляді опуклої задачі евклідо-
вої комбінаторної оптимізації. До того ж, евклідова комбінаторна множина 'E – сферично
розташована як декартовий добуток двох сферично розташованих множин ( )ss'E G і
(1)nB . Тобто, як поверхню S у (37) можна обрати, наприклад, сферу мінімального радіуса
( )rS S a . Для визначення її параметрів скористаємося таким твердженням.
Твердження 2. Якщо 1 ME ,...,E – сферично розташовані, а ( )
i
i
rS a – мінімальна
описана сфера для iE ( Mi J ), то
1
M
i
i
E E – сферично розташована множина і
1
M
i
i
a a ,
ISSN 1028-9763. Математичні машини і системи, 2017, № 4 143
2
1
M
i
i
r r – центр і радіус сфери мінімального радіуса, описаної навколо E .
Наслідок 1. Множина 'E виду (18) – сферично розташована і гіперсфера
( ) s t
rS Ra має такі параметри:
2
21
=
2 4
s t
GG
G
t
, , r
s s
a . (58)
Отже, обґрунтувано застосовність до Моделі 4, а, відповідно, і до вихідної задачі,
поліедрально-поверхневих методів з поверхнею – гіперсферою ( )rS a , що має параметри
(58). Більше того, в даному випадку застосовні поліедрально-сферичні методи [25]. До то-
го ж, оскільки Модель 4 – це опукла квадратична задача оптимізації на сферично розташо-
ваній евклідовій комбінаторній множині, то не тільки поліедральна релаксація (36), але і
сферична релаксація (37) можуть бути розв’язані точно [25].
4. Висновки
У роботі розглянуто досить актуальну проблему оптимізації швидкості та якості передачі
інформації, що виникає в організації будь-якої телекомунікаційної мережі та її роботі. Для
її розв’язання побудовано математичну модель у вигляді задачі векторної оптимізації на
композиційному образі загальної множини переставлень та булевої множини, побудовано
суперкритерій і здійснено перехід до квадратичної умовної задачі евклідової комбінатор-
ної оптимізації. Запропоновано декілька методів її розв’язання, що суттєво використову-
ють специфіку задачі, серед яких метод направленого структурування, опуклих продов-
жень та поліедрально-сферичний метод. Дано загальну постановку задачі багатокритеріа-
льної евклідової комбінаторної задачі. На прикладі побудованої моделі оптимізації роботи
телекомунікаційної мережі продемонстровано можливості застосування інструментарію
евклідової комбінаторної оптимізації до досить складних практичних задач.
СПИСОК ЛІТЕРАТУРИ
1. Koliechkina L.N. Modified Coordinate Method to Solve Multicriteria Optimization Problems on
Combinatorial Configurations Multicriteriality / L.N. Koliechkina, O.A. Dvirna, A.N. Nagornaya //
Cybernetics and Systems Analysis. – 2014. – N 4. – P. 154 – 161.
2. Koliechkina L.N. Solving Extremum Problems with Linear Fractional Objective Functions on the
Combinatorial Configuration of Permutations Under Multicriteriality / L.N. Koliechkina, O.A. Dvirna //
Cybernetics and Systems Analysis. – 2017. – Vol. 53, N 4. – P. 590 – 599.
3. Chiang M. Balancing Transport and Physical Layers in Wireless Multihop Networks: Jointly Optimal
Congestion Control and Power Control / M. Chiang // IEEE Journal on Selected Areas in Commun. –
2005. – Vol. 23, N 1. – P. 104 – 116.
4. Channel Assignment Strategies for Multiradio Wireless Mesh Networks: Issues and Solutions /
H. Skalli, S. Ghosh, S.K. Das [et al.] // IEEE Comm. Magazine. – 2007. – Vol. 45, N 11. – P. 86 – 95.
5. Singh K. Review on Routing Protocols in Wireless Mesh Networks / K. Singh, S. Behal // International
Journal of Application or Innovation in Engineering & Management (IJAIEM). – 2013. – Vol. 2, Iss. 2. –
P. 143 – 149.
6. Агеев Д.В. Метод проектирования телекоммуникационных систем с использованием потоковой
модели для многослойного графа / Д.В. Агеев // Проблеми телекомунікацій. – 2010. – № 2 (2). –
С. 7 – 22.
7. Семенова Н.В. Подход к решению векторных задач дискретной оптимизации на комбинаторном
множестве перестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и
системный анализ – 2008. – № 3. – С. 158 – 172.
144 ISSN 1028-9763. Математичні машини і системи, 2017, № 4
8. Гаркуша С.В. Особенности использования гиперграфов при моделировании многоканальных
mesh-сетей стандарта IEEE 802.11 / С.В. Гаркуша // Радиотехника: Всеукр. межвед. науч.-техн. сб.
– 2013. – Вып. 175. – С. 160 – 169.
9. Гаркуша С.В. Огляд та класифікація протоколів маршрутизації в mesh-мережах стандарту IEEE
802.11 / С.В. Гаркуша // Збірник наукових праць ВІТІ НТУУ „КПІ”. – 2012. – № 1. – С. 14 – 23.
10. Донець Г.П. Екстремальні задачі на комбінаторних конфігураціях / Г.П. Донець, Л.М.
Колєчкіна. – Полтава: ПУЕТ, 2011. – 328 с.
11. Стоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації / Ю.Г. Стоян, О.О. Ємець. –
К. ІСДО, 1993. – 188 с.
12. Ehrgott M. A survey and annotated bibliography of multiobjective combinatorial optimization /
M. Ehrgott, X. Gandibleux // OR Spektrum. – 2000. – Vol. 22. – P. 425 – 460.
13. Ehrgott M. Mutiobjective Programming / M. Ehrgott, M. Wiecek // Multiple Criteria Decision
Analysis: State of the Art Surveys. – New York: Springer, 2005. – P. 667 – 708.
14. Pappalardo M. Multiobjective Optimization: A Brief Overview / M. Pappalardo // Pareto Optimality,
Game Theory And Equilibria / A. Chinchuluun [et al.] (ed.). – New York: Springer, 2008. – P. 517 – 528.
15. Ehrgott M. Multiobjective Combinatorial Optimization – Theory, Methodology, and Applications /
M. Ehrgott, X. Gandibleux // Multiple Criteria Optimization: State of the Art Annotated Bibliographic
Surveys / M. Ehrgott, X. Gandibleux (ed.). – US: Springer, 2003. – P. 369 – 444.
16. Ehrgott M. Multiobjective Combinatorial Optimization / M. Ehrgott // Multicriteria Optimization. –
Berlin Heidelberg: Springer, 2005. – P. 197 – 220.
17. Стоян Ю.Г. Некоторые свойства специальных комбинаторных множеств / Стоян Ю.Г. –
Харьков: ИПМАШ, 1980. – 22 с. (Препринт АН УССР/Институт проблем машиностр.; 85).
18. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу,
К. Стайглиц. – М.: Мир, 1984. – 512 с.
19. Писарук Н.Н. Модели и методы смешанно-целочисленного программирования / Писарук Н.Н. –
Минск: Изд-во БГУ, 2008. – 250 с.
20. Ēmets O.O. Cut-off in linear partially combinatorial problems of Euclidean combinatorial optimization
/ O.O. Ēmets, Ē.M. Ēmets // Dopov. Nats. Akad. Nauk Ukr. Mat. Prirodozn. Tekh. Nauki. – 2000. –
Vol. 9. – P. 105 – 109.
21. Пичугина О.С. Поверхностные и комбинаторные отсечения в задачах евклидовой
комбинаторной оптимизации / О.С. Пичугина // Математичне та комп'ютерне моделювання. –
(Серія «Фізико-математичні науки»). – 2016. – Вип. 13. – С. 144 – 160.
22. Яковлев С.В. Теория выпуклых продолжений функций на вершинах выпуклых многогранников
/ С.В. Яковлев // Журнал вычислительной математики и математической физики. – 1994. – № 7
(34). – С. 1112 – 1119.
23. Пичугина О.С. Методы глобальной оптимизации на перестановочном многограннике в
комбинаторных задачах на вершинно расположенных множествах / О.С. Пичугина, С.В. Яковлев //
Математичне та комп’ютерне моделювання. – (Серія «Фізико-математичні науки»). – 2017. –
Вып. 15, № 1. – С. 152 – 158.
24. Pichuginа O. Convex extensions and continuous functional representations in optimization, with their
applications / O. Pichuginа, S. Yakovlev // J. Coupled Syst. Multiscale Dyn. – 2016. – Vol 2, N 4. –
P. 129 – 152.
25. Pichuginа O. Continuous Approaches to the Unconstrained Binary Quadratic Problems / O. Pichuginа,
S. Yakovlev // Mathematical and Computational Approaches in Advancing Modern Science and
Engineering / J. Bélair [et al.] (ed). – Switzerland: Springer, 2016. – P. 689 – 700.
Стаття надійшла до редакції 06.11.2017
|