Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж
Розглядається комбінаторна математична модель багатокритеріальної оптимізації, що використовується при побудові комп’ютерних мереж. Запропоновано новий підхід для розв’язання даного типу задач, заданих на конфігурації сполучень, з урахуванням їх представлення у вигляді графа....
Saved in:
| Date: | 2016 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2016
|
| Series: | Математичні машини і системи |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/113766 |
| 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: | Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж / Л.М. Колєчкіна, А.М. Нагірна // Математичні машини і системи. — 2016. — № 4. — С. 68-75. — Бібліогр.: 18 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-113766 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1137662017-02-14T03:02:29Z Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж Колєчкіна, Л.М. Нагірна, А.М. Інформаційні і телекомунікаційні технології Розглядається комбінаторна математична модель багатокритеріальної оптимізації, що використовується при побудові комп’ютерних мереж. Запропоновано новий підхід для розв’язання даного типу задач, заданих на конфігурації сполучень, з урахуванням їх представлення у вигляді графа. Рассматривается комбинаторная математическая модель многокритериальной оптимизации, используемая при построении компьютерных сетей. Предложен новый подход для решения данного типа задач, заданных на конфигурации сочетаний, с учетом их представления в виде графа. A combinatorial mathematical model of multi-criteria optimization used under the construction of computer networks is considered in this paper. It is proposed a new approach to solve this type of problems defined on configuration of interfaces, taking into account their representation as a graph. 2016 Article Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж / Л.М. Колєчкіна, А.М. Нагірна // Математичні машини і системи. — 2016. — № 4. — С. 68-75. — Бібліогр.: 18 назв. — укр. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/113766 519.8 uk Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформаційні і телекомунікаційні технології Інформаційні і телекомунікаційні технології |
| spellingShingle |
Інформаційні і телекомунікаційні технології Інформаційні і телекомунікаційні технології Колєчкіна, Л.М. Нагірна, А.М. Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж Математичні машини і системи |
| description |
Розглядається комбінаторна математична модель багатокритеріальної оптимізації, що використовується при побудові комп’ютерних мереж. Запропоновано новий підхід для розв’язання даного типу задач, заданих на конфігурації сполучень, з урахуванням їх представлення у вигляді графа. |
| format |
Article |
| author |
Колєчкіна, Л.М. Нагірна, А.М. |
| author_facet |
Колєчкіна, Л.М. Нагірна, А.М. |
| author_sort |
Колєчкіна, Л.М. |
| title |
Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж |
| title_short |
Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж |
| title_full |
Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж |
| title_fullStr |
Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж |
| title_full_unstemmed |
Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж |
| title_sort |
математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2016 |
| topic_facet |
Інформаційні і телекомунікаційні технології |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/113766 |
| citation_txt |
Математична модель багатокритеріальної оптимізації на множині сполучень при побудові комп’ютерних мереж / Л.М. Колєчкіна,
А.М. Нагірна // Математичні машини і системи. — 2016. — № 4. — С. 68-75. — Бібліогр.: 18 назв. — укр. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT kolêčkínalm matematičnamodelʹbagatokriteríalʹnoíoptimízacíínamnožiníspolučenʹpripobudovíkompûternihmerež AT nagírnaam matematičnamodelʹbagatokriteríalʹnoíoptimízacíínamnožiníspolučenʹpripobudovíkompûternihmerež |
| first_indexed |
2025-07-08T06:21:52Z |
| last_indexed |
2025-07-08T06:21:52Z |
| _version_ |
1837058716064546816 |
| fulltext |
68 © Колєчкіна Л.М., Нагірна А.М., 2016
ISSN 1028-9763. Математичні машини і системи, 2016, № 4
УДК 519.8
Л.М. КОЛЄЧКІНА
*
, А.М. НАГІРНА
**
МАТЕМАТИЧНА МОДЕЛЬ БАГАТОКРИТЕРІАЛЬНОЇ ОПТИМІЗАЦІЇ
НА МНОЖИНІ СПОЛУЧЕНЬ ПРИ ПОБУДОВІ КОМП’ЮТЕРНИХ МЕРЕЖ
*
Полтавський університет економіки і торгівлі, Полтава, Україна
**
Інститут кібернетики імені В.М. Глушкова НАН, Київ, Україна
Анотація. Розглядається комбінаторна математична модель багатокритеріальної оптимізації,
що використовується при побудові комп’ютерних мереж. Запропоновано новий підхід для
розв’язання даного типу задач, заданих на конфігурації сполучень, з урахуванням їх представлення
у вигляді графа.
Ключові слова: граф, підграф, функція, модель, багатокритеріальна оптимізація, конфігурація
сполучень, генерування, мережа, вершина, локалізація.
Аннотация. Рассматривается комбинаторная математическая модель многокритериальной
оптимизации, используемая при построении компьютерных сетей. Предложен новый подход для
решения данного типа задач, заданных на конфигурации сочетаний, с учетом их представления в
виде графа.
Ключевые слова: граф, подграф, функция, модель, многокритериальная оптимизация, конфигура-
ция сочетаний, генерирование, сеть, вершина, локализация.
Abstract. A combinatorial mathematical model of multi-criteria optimization used under the construction
of computer networks is considered in this paper. It is proposed a new approach to solve this type of prob-
lems defined on configuration of interfaces, taking into account their representation as a graph.
Keywords: graph, undirected graph, function, model, multi-criteria optimization, configuration of inter-
faces, generation, network, apex, localization.
1. Вступ
Однією з важливих задач України на шляху до європейського інформаційного суспільства
виступає побудова цифрової інфраструктури, основним показником якої є Інтернет, його
користувачі і можливості доступу. Дослідження, спрямовані на підвищення продуктивнос-
ті праці комп’ютерних мереж, стосуються протокольних засобів від фізичного до мереже-
вого рівнів моделі взаємодії в комп’ютерних мережах [1, 2]. Але існує ряд способів підви-
щення продуктивності комп’ютерних мереж, зокрема, використання технології інтелекту-
альних антен, зміна територіального розташування станцій, рознесення сигналу по поляри-
зації, використання технології, об'єднання каналів, використання багатоканального багато-
інтерфейсного режиму роботи, забезпечення ефективного маршруту передачі інформації
[1, 3–7]. У зв'язку c цим є актуальним представлення математичної моделі і методу її
розв’язання, яка могла б бути покладена в основу оптимізації роботи комп’ютерних мереж.
З цією метою є доцільним застосувати математичні моделі багатокритеріальної оптимізації
на комбінаторних конфігураціях, які широко використовуються як формальні моделі реа-
льних систем.
Дана робота продовжує дослідження робіт [2, 7–10], в яких описуються моделі ком-
бінаторної та векторної оптимізації, підходи до розв’язання та їх застосування при реаліза-
ції прикладних задач. Зокрема, в роботі описується застосування нового підходу до
розв’язання комбінаторних задач локалізації функції на комбінаторній конфігурації сполу-
чень [11–13], для якої визначено графове дерево [2].
ISSN 1028-9763. Математичні машини і системи, 2016, № 4 69
2. Постановка математичної моделі задачі
Для постановки математичної моделі задачі сформулюємо суть досліджуваної проблема-
тики: при проектуванні комп’ютерних мереж необхідно враховувати їх складну багаторів-
неву архітектуру, в якій рівні технологічної ієрархії є накладеними мережами і використо-
вують різні технології. Важливим аспектом при функціонуванні комп’ютерних мереж є
оптимізація її ресурсів. Особливо гостро питання оптимізації роботи мережі стоїть, коли
при вирішенні задач необхідно передати інформацію, зокрема, визначити фізичні і логічні
зв'язки між елементами на різних рівнях системи, забезпечивши при цьому сумісність різ-
них комп’ютерних технологій і мереж. З цією метою доцільно використати математичний
апарат векторної комбінаторної оптимізації [11–18].
Отже, є доцільним представити опис багаторівневої комп’ютерної системи за до-
помогою структурного графа на комбінаторних конфігураціях, який складається з підгра-
фів [2]. Враховуючи показники ефективності роботи комп’ютерних мереж, які можна ви-
значити лінійними функціями, модель задачі є задачею багатокритеріальної комбінаторної
оптимізації на комбінаторних конфігураціях [8].
На підставі встановленого взаємозв'язку між задачами оптимізації на комбінаторних
конфігураціях та графами многогранників комбінаторних конфігурацій використовуються
деякі структурні властивості допустимої області, сформульовано ряд тверджень [2, 8–9],
які можна застосувати для побудови методу розв’язання комбінаторної задачі з викорис-
танням графів і для вирішення прикладних задач оптимізації роботи комп’ютерних мереж.
Введемо необхідні поняття. Нехай дано множину (1,2,..., )A n . Сполучення без
повторень з n елементів по r це r -елементна підмножина множини A . Оскільки поря-
док запису елементів множини неістотний, то запишемо елементи в кожному сполученні у
порядку зростання. Сполучення 1 2( , ,..., )ra a a розглядатимемо як рядок чисел 1 2, ,..., ra a a ,
де 1 2 ... ra a a . r
nC – кількість усіх сполучень без повторень з n елементів по r , де n ,
r – додатні цілі числа, причому r n . За даним сполученням можна знайти наступне, від-
повідно до лексикографічного порядку, сполучення, що і буде використано в подальшому
викладі матеріалу.
Розглянемо таку математичну модель задачі: визначити набір функцій, які оптимі-
зують деякі характеристики роботи комп’ютерних мереж:
( )F x
1 1 1
max
t
p m n
k k
ij ij
x R k i j
c x , (1)
де 1...s при комбінаторній умові, яка враховує сполучні властивості області допусти-
мих розв’язків задачі:
x
1 1
11 1 1
( , ..., , ..., ,..., )
p p
n mpp
x x x x ( )mpS G , (2)
і при додаткових умовах, що можуть відображати інтенсивність надходження від користу-
вачів запитів на резервування пропускної здатності каналу для передачі потоків інформа-
ції:
1
m
k k k
ij ij i
i
x b , де ,m pi J k J , де t pmn ; (3)
пропускну здатність каналу для потоку інформації, що надходить на передачу по каналу
комп’ютерної мережі ijl , ,m ni J j J :
70 ISSN 1028-9763. Математичні машини і системи, 2016, № 4
min max
k
ijq q q ; (4)
число, що обмежує кількість запитів на передачу потоків інформації, які знаходяться в ка-
нальній черзі:
( ) min( ( ))ip t p t . (5)
Представлена вище модель задачі (1)–(5) є моделлю багатокритеріальної оптиміза-
ції на комбінаторній конфігурації сполучень і дає можливість оптимізувати характеристи-
ки роботи комп’ютерних мереж та заощадити ресурси підприємства чи організації. Безу-
мовно, при розв’язуванні конкретної практичної задачі кількість функцій цілі може зміню-
ватися, а також можуть коригуватися додаткові умови.
Для подальшої реалізації даної багатокритеріальної моделі розглянемо побудову
послідовності значень лінійних цільових функцій по точках конфігурації сполучень, розк-
ладених по підграфах. З точки зору економіко-математичних методів, є доцільним розгля-
нути задачу комбінаторної оптимізації виду
( , ) : max{ ( , ) | , }Z F P F x c x P c C ,
яка полягає в максимізації функцій ( )F a на комбінаторній конфігурації сполучень
( )mpS G , де
1
( , ) ( , )
n
i i
i
F x c c x c x .
Також має сенс розглянути задачу, де значення цільової функції перебуває в інтер-
валі ( ) ( ) ( )F x F x F x . Тоді попередня задача буде набувати такого вигляду: визначити
( )
arg max ( )
x А
x F x при ( )y F x ,
( )
arg max ( )
x А
x F x при ( )y F x
при умові minx x .
Така модель задачі дозволяє знайти діапазон пропускної здатності в сучасних
комп’ютерних мережах.
Важливою задачею, яка може виникати при побудові моделі оптимізації
комп’ютерних мереж, може бути математична модель залежності між елементами конфі-
гурації сполучень за значенням лінійної цільової функції, що відображає упорядкування
користувачів у комп’ютерній мережі.
Тоді є доцільним розглянути елементи конфігурації сполучень як точки арифметич-
ного евклідового простору nR або вершини структурного графа і задача (1), (2) може бути
представлена в іншому математичному форматі запису.
Оптимізаційна задача вигляду
( ( ), ( )) : max{ ( ) ( )}k k
n qnZ Ф а S A Ф а а S A , (6)
яка полягає в максимізації функції ( )Ф a на комбінаторній конфігурації сполучень ( )k
nS A ,
де
1
( )
n
j j
j
Ф а с x при додаткових обмеженнях (3)–(5).
ISSN 1028-9763. Математичні машини і системи, 2016, № 4 71
Для реалізації вище сформульованих математичних моделей задач доцільно засто-
сувати підходи, що ґрунтуються на властивостях комбінаторних конфігурацій, та їх пред-
ставлення в вигляді графових структур [2, 9, 17, 18].
Зокрема, застосуємо координатний метод, що належить до класу методів направле-
ного структурування і описаний в [2]. Даний метод запропоновано для однокритеріальної
задачі з лінійною цільовою функцією, заданою на перестановках. Але може бути адапто-
ваний і для моделей багатокритеріальних задач на інших конфігураціях.
Враховуючи, що у загальному випадку багатокритеріальна задача оптимізації – це
задача одночасної оптимізації декількох цільових функцій на множині допустимих
розв’язків, то у багатокритеріальних задачах відшукання розв’язку майже завжди прово-
диться у межах компромісів або розв’язків, оптимальних за критерієм Парето.
Найбільш розповсюджені методи розв’язання багатокритеріальних задач можна
розділити на такі групи:
– зведення сукупності локальних критеріїв (векторного критерію) до одного (ска-
лярного критерію) за допомогою вагових коефіцієнтів, вибраних для кожного критерію
(при цьому більш важливий критерій отримує більшу вагу);
– оптимізація за одним скалярним критерієм (найбільш вагомим) при включенні
інших критеріїв у систему обмежень;
– мінімізація відхилень значень функцій мети від найкращих значень за всіма кри-
теріями;
– ранжування сукупності критеріїв і послідовна оптимізація за кожним із них.
Джерелом додаткової інформації щодо вибору методу розв’язання багатокри-
теріальної задачі виступає особа, що приймає рішення (ОПР). Інакше кажучи, ефективний
план, який приймається за розв’язок багатокритеріальної задачі, вибирається згідно з сис-
темою переваг ОПР, яка уточнюється або навіть лише формується у процесі розв’язування
конкретної задачі. Таким чином, пошук розв’язку багатокритеріальної задачі проводиться
у вигляді діалогу (в інтерактивному режимі) з ОПР, яка несе відповідальність за обране
рішення та його наслідки. Тому для розв’язання запропонованої задачі застосуємо зведен-
ня її до скалярного вигляду.
Для зведення локальних критеріїв до скалярного виду застосовують метод рів-
номірної оптимізації і метод згортання критеріїв.
Отже, на початковому етапі розв’язування задачі (1)–(5) слід звести задачу або до
однокритеріальної зазначеними вище методами, або застосовувати запропонований нижче
метод окремо до кожної функції, об’єднавши при цьому отримані розв’язки.
3. Координатний метод локалізації значень лінійних функцій, заданих на конфігура-
ції сполучень
Для подальшого викладу методу визначимо структуру конфігурації сполучень та можливі
варіанти генерування її елементів. Застосуємо один із методів генерування конфігурації
сполучень, який дає можливість, у залежності від складності задачі, представити елементи
комбінаторної конфігурації у вигляді графа і описаний в [2]. Даний метод генерування по-
лягає у виборі елементів з заданої упорядкованої множини за зростанням, тобто вибира-
ються елементи для прикладу по два: перший – другий; перший –третій; перший – четвер-
тий і т.д. Таким чином будується верхній підграф загального графа послідовності, далі –
другий – третій; другий – четвертий і т.д.
За допомогою даного підходу до генерування елементів комбінаторної конфігурації
сполучень можна зобразити елементи конфігурації у вигляді графового дерева. Дане дере-
во можна представити у вигляді розкладу на піддерева, тоді кожне піддерево формується з
вершин, в яких елемент на останньому місці фіксується і є вибраним з початкової множи-
ни 1 2 na ,a , , a як максимальний, а останні перебираються рекурсивним методом.
72 ISSN 1028-9763. Математичні машини і системи, 2016, № 4
Слід зазначити, що дане дерево є орієнтованим, в якому визначений корінь – вер-
шина, яка є лексикографічно більша останніх. Таким чином отримуємо орієнтоване (спря-
моване) дерево – ациклічний орграф (орієнтований граф, що не містить циклів) – той, в
якому тільки одна вершина має нульову напівстепінь входу, а всі інші вершини мають на-
півстепінь входу 1. Формально дерево конфігурації сполучень визначається як скінченна
множина одного або більше вузлів.
Також відмітимо, що значення функції дерева сполучень у напрямку знизу вверх
зростає, а зверху вниз – спадає з однаковим інтервалом при рівномірному розподілі зна-
чень коефіцієнтів, що обумовлено ієрархічною будовою дерева та лінійністю цільової фу-
нкції. При цьому поняття «верх» або «низ» мають стабільний структурний зміст у відно-
шенні піддерев і в рамках об’єднуючого дерева [2].
Для подальшого розв’язання поставленої задачі (1)–(5) визначимо такі правила:
а) якщо в даній вершині значення функції менше заданого, то далі треба шукати це
значення в сусідній вершині, збільшуючи ( 2)n , або ( 1)n координату;
б) якщо в даній вершині значення функції більше заданого, то далі треба шукати це
значення в сусідній вершині, зменшуючи ( 2)n , або ( 1)n координату.
Розв’язання задачі проводиться для всіх типів вершин досліджуваного графа. Кож-
ній вершині графа, в залежності від її типу, можна поставити у відповідність свій підграф
iG . На підграфі визначається тип вершини, під яким розуміється таке: якщо остання коор-
дината для вершин усього підграфа постійна, то передостання і та, що передує їй, зміню-
ються від більшої можливої координати до меншої.
Граф представляє мережу, де витоком є найвища і найлівіша вершина, а стоком –
найнижча і найправіша вершина. В мережі кожна вершина визначається кодом
1 2( , , ..., ),ni i i тобто номерами координати, які потім будуть переставлятися.
Для фіксованого типу вершин послідовно для кожного піддерева знаходяться необ-
хідні вершини * ,x в яких * *( ) y .f x Початкову вершину дерева iG будемо називати вер-
шиною-витоком.
Алгоритм пошуку необхідної вершини для піддерева ( 1, 2, , )iG i n можна поді-
лити на три етапи.
Перший етап: побудова коду (що таке, означити) початкової вершини для iG .
Другий етап: розгортання (що мається під розгортанням) дерева вздовж координати
1nx .
Третій етап: розгортання дерева вздовж координати nx .
Розглянемо детально кожний етап.
І. Нехай вибрано тип вершини 1 2( , ,..., ),ni i i де 1 2 ... {1, 2, ..., },ni i i n та номер
піддерева i . Тоді покладемо: ;nx i 1 max{ \ },n n nx N x 2 1max{N \ ( , )}.n n n nx x x Упо-
рядкуємо числа 2 1{ \ ( , , )}n n n nN x x x по зростанню 1 2 3.j j j Тоді
11 ,ix j
22 ,ix j
33 .ix j Це і буде код головної вершини мережі iG , який будемо позначати 1p або 1q . Об-
числимо значення цільової функції в цій вершині 1( ).f p
II. Розглянемо в цьому коді значення ( 1, 2, 3, 4)kx k та упорядкуємо за спаданням
4 4 3 2 1.x j j j j Розгортанням графа вздовж координати 4x (або вниз) назвемо послі-
довність транспозицій 4 3 2 1,j j j j які, крім коду головної вершини, приводять до
створення ще трьох кодів, які ми позначимо 2p , 3p та 4p і запишемо один під одним. Щоб
знайти значення функції на цих сполученнях, необов’язково використовувати всі її коор-
динати. Достатньо знайти різницю значень функцій у сусідніх вершинах. Позначимо ( )
ISSN 1028-9763. Математичні машини і системи, 2016, № 4 73
номер місця числа j в коді перестановки 1( 1, 2, 3).p Тоді значення 2( )f p буде менше
1( )f p на величину 1 4 3 4 (3)( )( ).j j c c У другому множнику постійно буде величина
4c , тому що у транспозиції завжди бере участь координата 4x . Аналогічно знаходимо дру-
гу та третю різниці. Очевидно, що у процесі подальшого пошуку необхідно використову-
вати тільки ті сполучення, для яких
*
1( ) .f p y
III. Розглянемо в коді вершини kp (яку позначимо 1q , ( 1, 2, 3, 4)k значення
5 4 3 2 1, , , ,x x x x x та упорядкуємо їх за спаданням 5 5 4 3 2 1 .x j j j j j Розгортанням
графа вздовж координати 5x (або праворуч) назвемо послідовність транспозицій
5 4 3 2 1,j j j j j які, крім коду головної вершини, повинні привести до створення
ще чотирьох кодів, які ми позначимо 2 3 4, ,q q q та 5q . Але ці коди створювати необов’яз-
ково. Так само, як і при розгортанні графа вниз, значення функції 2( )f q у вершині 2q буде
меншим від значення 1( )f q на величину 1 5 4 5 (4)( )( ).j j c c За цією формулою знахо-
димо всі інші різниці. Послідовно віднімаючи (4 1) від 1( ),f q можемо отримати дві
такі ситуації:
1. Всі значення функцій більші
*y . В цьому випадку переходимо до розгортання
наступного коду kp .
2. На деякому кроці * отримаємо значення функції у вершині, рівне *y (або менше
*y ). В першому випадку запам’ятовуємо код відповідної вершини. Переходимо до розгор-
тання наступного коду kp . При цьому кількість кроків обмежується до * 1.
Після розгортання всіх ( 1, 2,..., )kp k n пошук необхідних вершин підграфа iG з
фіксованим i закінчується. Далі проводяться необхідні обчислення для всіх підграфів, ви-
користовуючи описані три етапи.
Основна пріоритетність алгоритму пошуку необхідних вершин координатним мето-
дом полягає у зменшенні виконуваних обчислень, оскільки обчислюються лише різниці
значень функції, тоді як у горизонтальному методі кожний раз необхідно обчислювати зна-
чення функції в новій вершині і відтворювати код вершини. Крім того, координатний ме-
тод дозволяє декілька модифікацій, пов’язаних з обчисленням не тільки в кодах головних
вершин (витоках), а і симетричним підходом відносно вершин-стоків та ін.
4. Висновки
У роботі описано модель багатокритеріальної оптимізації на конфігурації сполучень, яку
можна використовувати при проектуванні комп’ютерних мереж, що мають складну бага-
торівневу архітектуру. Сучасна комп’ютерна мережа характеризується сукупністю різного
роду новітніх технологій зв’язку, але особливої уваги заслуговує оптимізація її функціону-
вання як на рівнях апаратури і програмного забезпечення, так і в цілому в єдиній системі
взаємодій. Запропонована модель забезпечує опис багаторівневої комп’ютерної системи за
допомогою структурного графа на комбінаторних конфігураціях сполучень.
Оскільки ефективність роботи комп’ютерної мережі характеризується значною кі-
лькістю показників, то в роботі визначено цільові функції лінійними, а модель вважається
багатокритеріальною на конфігурації сполучень.
Встановлений взаємозв'язок між задачами оптимізації на комбінаторних конфігура-
ціях та графами многогранників комбінаторних конфігурацій забезпечує використання
74 ISSN 1028-9763. Математичні машини і системи, 2016, № 4
структурних властивостей допустимої області сполучень, представляючи граф у вигляді
орієнтовного дерева.
Координатний метод локалізації значення лінійної функції, заданої на конфігурації
сполучень, забезпечує знаходження оптимальних розв’язків за скінченну кількість кроків і
зменшення числа обчислень у порівнянні з горизонтальним методом.
Подальші дослідження будуть спрямовані на знаходження нових методів
розв’язання даного типу задач, що моделюють комп’ютерні мережі, на інших конфігураці-
ях з можливістю застосування графових моделей.
СПИСОК ЛІТЕРАТУРИ
1. Koliechkina L.N. Modified Coordinate Method to Solve Multicriteria Optimization Problems on Com-
binatorial Configurations / L.N. Koliechkina, O.A. Dvernaya, A.N. Nagornaya // Cybernetics and Systems
Analysis. – 2014. – N 4. – P. 154 – 161.
2. Донець Г.П. Екстремальні задачі на комбінаторних конфігураціях / Г.П. Донець, Л.М. Колєчкіна.
– Полтава: РВВ ПУЕТ, 2011. – 309 с.
3. Akyildiz I.F. Wireless mesh networks: a survey / I.F. Akyildiz, X. Wang, W. Wang // Computer
Networks. – 2005. – Vol. 47, N 2. – P. 445 – 487.
4. Capone A. Multi-Layer Network Design with Multicast Traffic and Statistical Multiplexing / A. Ca-
pone, G. Carello, R. Matera // IEEE Global Telecommunications Conference (IEEE GLOBECOM). –
Washington, USA, 2007. – Р. 2565 – 2570.
5. Chiang M. Balancing Transport and Physical Layers in Wireless Multihop Networks: Joint Optimal
Congestion and Power Control / M. Chiang // IEEE Journal on Selected Areas in Commun. – 2005. –
Vol. 23, N 1. – P. 104 – 116.
6. Singh K. Review on Routing Protocols in Wireless Mesh Networks / K. Singh, S. Behal // Internation-
al Journal of Application or Innovation in Engineering & Management (IJAIEM). – 2013. – Vol. 2, Iss. 2.
– P. 143 – 149.
7. Агеев Д.В. Представление модели в виде многослойного графа для решения задач планирования
инфокоммуникационной системы с учетом структурированной кабельной системы [Электронный
ресурс] / Д.В. Агеев // Проблемы телекоммуникаций. – 2013. – № 3 (12). – С. 16 – 26. – Режим до-
ступа: http://pt.journal.kh.ua/2013/3/12/102_ageyev_layer.pdf.
8. Семенова Н.В. Подход к решению векторных задач дискретной оптимизации на комбинаторном
множестве перестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и систем-
ный анализ. – 2008. – № 3. – С. 158 – 172.
9. Емеличев В.А. Многогранники, графы, оптимизация / Емеличев В.А., Ковалев М.М., Кравцов
М.К. – М.: Наука, 1981. – 344 с.
10. Сергиенко И.В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации /
И.В. Сергиенко, М.Ф. Каспшицкая. – К.: Наукова думка, 1981. – 288 с.
11. Семенова Н.В. Поліедральний підхід до розв’язання одного класу векторних задач комбінатор-
ної оптимізації / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Доповіді НАН України. – 2009. –
№ 6. – С. 46 – 53.
12. Колечкина Л.Н. Многокритериальные комбинаторные задачи оптимизации на множестве поли-
размещений / Л.Н. Колечкина, Е.А. Родионова // Кибернетика и системный анализ. – 2008. – № 2. –
С. 152 – 160.
13. Колєчкіна Л.М. Властивості задач багатокритеріальної оптимізації на комбінаторних множинах
та методи їх розв’язання / Колєчкіна Л.М. – Полтава: РВВ ПУСКУ, 2008. – 162 с.
14. Донец Г.А. Построение гамильтонова пути в графах перестановочных многогранников /
Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. – 2010. – № 1. – С. 10 – 16.
15. Донец Г.А. Экстремальные покрытия графов / Г.А. Донец, А.Я. Петренюк. – Кировоград: ОАО
«Кіровоградське видавництво», 2009. – 170 с.
16. Донец Г.А. Об одном подходе к решению комбинаторной задачи оптимизации на графах /
Г.А. Донец, Л.Н. Колечкина // Управляющие системы и машины. – 2009. – № 4. – С. 36 – 42.
17. Донец Г.А. Локализация значения линейной функции, заданной на перестановках / Г.А. Донец,
Л.Н. Колечкина // Радиоэлектроника и информатика. – 2009. – № 1. – С. 76 – 81.
http://link.springer.com/search?facet-author=%22L.+N.+Koliechkina%22
http://link.springer.com/search?facet-author=%22L.+N.+Koliechkina%22
http://link.springer.com/search?facet-author=%22O.+A.+Dvernaya%22
http://link.springer.com/search?facet-author=%22A.+N.+Nagornaya%22
http://pt.journal.kh.ua/2013/3/12/102_ageyev_layer.pdf
ISSN 1028-9763. Математичні машини і системи, 2016, № 4 75
18. Донец Г.А. Метод упорядочения значений линейной функции на множестве перестановок /
Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. – 2009. – № 2. – С. 50 – 61.
Стаття надійшла до редакції 22.07.2016
|