Звіт про проходження практики за темою магістерської кваліфікаційної роботи: «оптимізація структури комп’ютерної мережі з використанням методу послідовних поступок»

2
Зміст
ВСТУП ........................................................................................................................................................................ 3
СПИСОК УМОВНИХ СКОРОЧЕНЬ ........................................................................................................................ 5 1 АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ ТА РОЗРОБКА СТРУКТУРИ ПІДСИСТЕМИ АВТОМАТИЗАЦІЇ
РОЗВ’ЯЗАННЯ ЗАДАЧ БАГАТОКРИТЕРІАЛЬНОЇ ОПТИМІЗАЦІЇ ................................................................. 6 1.1 Аналіз предметної області та її актуальність ................................................................................................. 7 1.2 Основні елементи теорії оптимізації ............................................................................................................. 11 1.3
Призначення комп’ютерних мереж та їх різновиди .............................................................................. 14 1.4 Розробка структури підсистеми для розв’язання задач багатокритеріальної оптимізації методом послідовних поступок .......................................................................................................................................... 25 2. РОЗРОБЛЕННЯ МОДЕЛІ ТА АЛГОРИТМІВ ОПТИМІЗАЦІЇ СТРУКТУР КОМП’ЮТЕРНИХ МЕРЕЖ
................................................................................................................................................................................ 28 2.1 Основні поняття та визначення задач багатокритеріальної оптимізації .................................................... 28 2.2 Методи та особливості побудови алгоритмів розв’язування задач багатокритеріальної оптимізації.... 32 2.3 Особливості розв’язання задач багатокритеріальної оптимізації ............................................................... 40
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ................................................................................................................ 43

3
ВСТУП
Методи розв’язання задач математичного програмування з одним критерієм
інтенсивно розроблялися останні 40 років. Сучасні задачі математичного програмування набули бурхливого розвитку з появою персональних комп’ютерів
(ПК). З розвитком епохи інформаційних технологій, виникла необхідність розв’язувати задачі, які характеризується більш ніж одним критерієм. Керівники підприємств, набагато більше, ніж раніше, відчувають необхідність оцінювати альтернативні рішення з погляду декількох критеріїв.
Результати дослідження задач планування і управління показують, що в реальній постановці ці задачі є багатокритерійними. Так, вираз, що часто зустрічається в житті ―досягти максимального ефекту при найменших витратах‖ вже по суті означає ухвалення рішення за двома критеріями. Оцінка діяльності підприємств і планування, як системи прийняття рішень, проводиться на основі більше десяти критеріїв: виконання плану виробництва за об'ємом, по номенклатурі, плану реалізації, оцінки за показниками рентабельності, продуктивності праці, тощо.
Раніше, при дослідженні проблеми багатокритеріальності, часто всі критерії, окрім одного, вибраного домінуючим, приймалися як обмеження і оптимізація проводилася по домінуючому критерію. Такий підхід до рішення практичних задач значно знижує ефективність ухвалюваних рішень.
Вперше проблема оптимізації векторного критерію була сформульована економістом Парето в 1896 р. Окрім того, на сьогодні, досить часто використовуються і інші методи, такі як методи цільового програмування та метод поступок. Застосування методів багатокритеріальної оптимізації дає змогу суттєво покрацити вихідні параметри об’єктів розроблення, економити матеріальні та людські ресурси. Тому тема магістерської роботи ―Оптимізація структури комп’ютерної мережі з використанням методу поступок‖ є актуальною.
Відповідно об’єктом дослідження є процеси розроблення комп’ютерних мереж, а предметом дослідження – оптимізаційна модель та засоби розв’язання задач

6
1 АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ ТА РОЗРОБКА СТРУКТУРИ
ПІДСИСТЕМИ АВТОМАТИЗАЦІЇ РОЗВ’ЯЗАННЯ ЗАДАЧ
БАГАТОКРИТЕРІАЛЬНОЇ ОПТИМІЗАЦІЇ
Сучансна наука про об'єктивні причини функціонування і розвитку суспільства користується різноманітними кількісними характеристиками, а тому використовує велику кількість математичних методів. Наприклад, в економіці використовуються оптимізаційні методи, які складають основу математичного програмування, теорії ігор, мережевого планування, теорії масового обслуговування та інших прикладних наук. Багато задач прийняття рішень, що виникають на виробництві, в економіці та інших областях людської діяльності, можуть бути зведені до побудови відповідної математичної моделі, обчисленню цільової функції, яка оцінює процес функціонування системи, і знаходження її оптимального (для визначення можна вважати мінімального) значення. Як правило, побудовані цільові функції досить складні і можуть мати ряд особливостей, у зв’язку з чим їхня мінімізація зв’язана зі значними обчислювальними складностями. До цих особливостей у першу чергу необхідно віднести властивість багатоекстремальності.
Значні обчислювальні складності, пов’язані з мінімізацією багатоекстремальних та інших видів функцій стандартними методами, а також безумовна важливість цих класів задач для різних практичних додатків (задач оптимального вибору технічних, економічних, екологічних та інших систем) робить дуже актуальною проблему створення способу оптимізації, здатного ефективно вирішувати ці задачі. Розробка систем автоматизації розв’язання сучасних економічних задач дозволяє набути практичні навички в області проектування сучасних САПР та розширити знання в цій області.

7
1.1 Аналіз предметної області та її актуальність
Багато задач прийняття рішень, що виникають на виробництві, проектуванні комп’ютерних систем, в економіці та інших областях людської діяльності, можуть бути зведені до побудови відповідної математичної моделі, обчисленню цільової функції, яка оцінює процес функціонування системи, і знаходження її оптимального (для визначення можна вважати мінімального) значення.
Як правило, побудовані цільові функції досить складні і можуть мати ряд особливостей, у зв’язку з чим їхня мінімізація зв’язана зі значними обчислювальними складностями. До цих особливостей у першу чергу необхідно віднести властивість багатоекстремальності.
Значні обчислювальні складності, пов’язані з мінімізацією багатоекстремальних та інших видів функцій стандартними методами, а також безумовна важливість цих класів задач для різних практичних додатків (задач оптимального вибору технічних, економічних, екологічних та інших систем) робить дуже актуальною проблему створення способу оптимізації, здатного ефективно вирішувати ці задачі.
Алгоритми, що пропонуються для рішення практичних задач оптимізації, базуються на адаптивному, випадковому пошуку, створеному ще в 1967 р.
Роки їх практичного використання, а також проведеного статистичного дослідження, дозволили зробити висновок про безсумнівну достатню практичну ефективність і одночасно про економічність запропонованих способів оптимізації.
Терміном оптимізація в літературі позначають процес або послідовність операцій що дозволяють одержати уточнене рішення. Причому основне завдання в даному випадку полягає у виборі серед безліч можливих рішень такого, яке було б в певному значенні кращим або, як то кажуть оптимальним. В області вичислювальних методів розв'язку задач оптимального вибору в теперішній час вже отримані основні важливі теоретичні результати, розроблені методи, видані монографії та підручники. В той же час, залишаються задачі, дослідження в яких

8 не завершені, чи завершені порівняно недавно. Задачі лінійного програмування
(ЗЛП) полягають в максимізації лінійної функції при лінійних обмеженнях. Теорія лінійного програмування містить як класичні, сформовані розділи (теорія двоїстості, алгоритм симплекс-метода, результат Хачияна про поліноміальний розв'язок задач лінійного програмування), так і розділи, які бурхливо розвиваються (алгоритми внутрішньої точки) і відкриті задачі (питання про
існування поліноміальну модифікацію симплекс-метода). Теорія лінійного програмування розвивалась в роботах таких вчених, як Л.В.Канторович,
Т.И.Купманс, Дж.Данциг, Ф.Л.Хічкок, Д.Б.Юдін, А.С.Немировский, Н.З.Шор,
Л.Г.Хачиян. Одним із основних методів лінійного програмування, які широко використовуються і розвиваються, є симплекс-метод, запропонований
Дж.Данцигом та метод внутрішньої точки, запропонований Н.Кармаркаром.
Лінійне програмування зв'язано з класичною теорією лінійних нерівностей, яка розвинута в роботах Ж.Б.Фур'є, Дж.Фаркаша, Г.Мінковского, А.Штейниця,
Г.Вейля, Т.С.Моцкіна і інших.
Значна увага в роботі приділена задачам оптимального вибору достатньо загального виду, включаючи багатокритеріальність. В теорії оптимізації для таких задач представлено два напрями: з одної сторони, дослідження по аналітичним умовах оптимальності і теорії двоїстості, з іншої - розробка теорії обчислювальних методів і побудова алгоритмів розв'язку екстремальних задач.
З проблем застосування методів багатокритеріальної (векторної) оптимізації в даний час існує багато публікацій. Розвиток і розширення масштабів використання методів векторної оптимізації було обумовлено вимогою практичної реалізації системного підходу до рішення задач в системі
інвестиційного планування, а також необхідністю значного підвищення у результаті економічної ефективності виробництва і посиленням конкурентних позицій підприємства на цільовому ринку.
Багатоцільова оптимізація є одним з універсальних і ефективних методом для розв’язання проблем між критеріями в математичних моделях. Діалектика полягає в тому, що в більшості випадків недоцільно направляти зусилля лише на досягнення однієї мети, але необхідно прагнути до отримання досить хорошого

9 шуканого плану, результату, рішення що забезпечує досягнення деякої сукупності найбільш важливих цілей. Такий погляд на рішення проблеми знаходиться в повній відповідності з вимогою використання принципів системного підходу.
Багатоцільовий підхід є необхідною методичною основою для подолання неточності та неповноти початкових даних, які виникають в сучасних задачах математичного програмування.
Найбільш відомими методами для вирішення задач багатокритеріальної оптимізації є:
- метод рівномірної оптимізації;
- метод справедливого компромісу;
- метод головного критерію;
- метод послідовних поступок;
- метод ідеальної точки;
- метод згортання критеріїв.
Можливими шляхами рішення проблем багатокритерійної оптимізації може бути застосування різних згорток і способів нормалізації. Також одним з можливих варіантів рішення задач багатокритерійної оптимізації є використання еволюційних (генетичних) алгоритмів.
Генетичні алгоритми (ГА) - адаптивні методи пошуку, які останнім часом часто використовуються для вирішення завдань функціональної оптимізації. Вони засновані на генетичних процесах біологічних організмів. Відзначимо, що ефективність ГА сильно залежить від таких деталей, як метод кодування рішень, оператори, настройки параметрів, приватний критерій успіху. Теоретична робота, відбита в літературі, присвяченій ГА, не дає підстав говорити об вироблення яких-небудь строгих механізмів для чітких прогнозів.
Останніми роками реалізовано багато генетичних алгоритмів і в більшості випадків вони мало схожі на класичний ГА. З цієї причини в теперішній час під терміном «генетичні алгоритми» розуміється не одна модель, а достатньо широкий клас алгоритмів, часом мало схожих один від одного. Дослідники експериментували з різними типами уявлень, операторів кросовера і мутації, спеціальних операторів, і різних підходів до відтворення і відбору. Рішення задачі

10 багатокритерійної оптимізації за допомогою ГА можна проводити по з тією особливістю, що визначення міри придатності хромосом можна визначати на основі якого-небудь методу багатокритерійної оптимізації (наприклад, метод справедливого компромісу) або принципу оптимальності або оптимізувати суперкритерій.
В теперішній час існують деякі проблеми багатокритеріальної оптимізації.
Перша проблема пов'язана з вибором принципу оптимальності, який строго визначає властивості оптимального рішення і відповідає на питання, в якому сенсі оптимальне рішення перевершує всі інші допустимі рішення. На відміну від завдань однокритерійної оптимізації, у яких тільки один принцип оптимальності f(xо)>=f(x), в даному випадку є велика кількість різних принципів і кожен принцип може приводити до вибору різних оптимальних рішень. Це пояснюється тим, що доводиться порівнювати вектори ефективності на основі деякої схеми компромісу. В математичному відношенні ця проблема еквівалентна задачі упорядкування векторних множин, а вибір принципу оптимальності - вибору відношення порядку.
Друга проблема пов'язана з нормалізацією векторного критерію ефективності. Вона викликана тим, що дуже часто локальні критерії, що є компонентами вектора ефективності, мають різні масштаби вимірювання, що і утрудняє їх порівняння. Тому доводиться приводити критерії до єдиного масштабу вимірювання, тобто нормалізувати їх.
Третя проблема пов'язана з урахуванням пріоритету (або різного ступеня важливості) локальних критеріїв. Хоча при виборі рішення і слід добиватися найвищої якості по всіх критеріях, проте ступінь досконалості по кожному з них, як правило, має різну значимість. Тому звичайно для врахування пріоритету вводиться вектор розподілу важливості критеріїв, за допомогою якого коректується принцип оптимальності або проводиться диференціація масштабів вимірювання критеріїв.
До вищесказаного можна додати також те, що труднощі викликає одночасна наявність в сучасних задачах багатокритеріальної оптимізації якісних і кількісних критеріїв, а саме - перехід від якісних в кількісні критерії для подальшої

11 оптимізації математичної моделі. Крім того часом є складно правильно підібрати вагові коефіцієнти.
1.2 Основні елементи теорії оптимізації
Оптимізація – визначення экстремума розглянутої функції, тобто вибір найкращого варіанта з безлічі можливих. Терміном «оптимізація» в літературі позначають процес або послідовність операцій, що дозволяють отримати уточнене рішення. Хоча кінцевою метою оптимізації є відшукання якнайкращого або «оптимального» рішення, зазвичай доводиться задовольнятися покращенням відомих рішень, а не доведенням їх до досконалості. Тому під оптимізацією розуміють скоріше прагнення до досконалості, яка, можливо, і не буде досягнута.
Завдання ухвалення рішення полягає у виборі серед множини можливих рішень
(їх називають також варіантами, планами і т. п.) такого рішення, яке було б в певному значенні кращим або, як то кажуть, оптимальним. Зручно вважати, що вибір рішення проводить деяка особа, що приймає рішення, яке переслідує цілком певну мету. Залежно від конкретної ситуації в ролі особи, що приймає рішення, може виступати як окрема людина (інженер, науковий співробітник і т. п.), так і цілий колектив (група фахівців, зайнята рішенням однієї задачі). Кожне можливе рішення характеризується певним ступенем досягнення мети. Відповідно до цього у особи, що приймає рішення, є свої уявлення про переваги і недоліки рішень, на підставі якого одному рішенню, віддається перевага над іншим. Оптимальне рішення - це рішення, яке з погляду особи, що приймає рішення, переважно інших можливих рішень. Таким чином, поняття оптимального рішення пов'язане з перевагами особи, що ухвалює рішення. Ці переваги на практиці виражаються в різній формі, і їх математична формалізація може скласти складне завдання, оскільки особа, що ухвалює рішення, як правило, не може ясно і чітко сформулювати їх.
Мета теорії прийняття рішень і полягає в розробці методів, які допомогли б особі, що приймає рішення, якнайповніше і точно виразити свої переваги в

12 рамках відповідної математичної моделі і кінець кінцем обґрунтовано вибрати дійсно оптимальне рішення.
Перш ніж приступити до обговорення питань оптимізації, введемо ряд визначень.
Проектні параметри (шукані змінні). Цим терміном позначають незалежні змінні параметри, які повністю і однозначно визначають вирішувану задачу проектування.
Проектні параметри - невідомі величини, значення яких обчислюються в процесі оптимізації. Як проектні параметри можуть служити будь-які основні або похідні величини, що служать для кількісного опису системи. Так, це можуть бути невідомі значення довжини, маси, часу, температури. Число проектних параметрів характеризує ступінь складності даного завдання проектування.
Звичайне число проектних параметрів позначають через п, а самі проектні параметри через х з відповідними індексами. Таким чином п проектних параметрів даного завдання позначатимемо через x
1
, x
2
, x
3
,..., x
n
Цільова функція (критерій якості). Це вираз, значення якого ОПР (особа, що приймає рішення) прагне зробити максимальним або мінімальним. Цільова функція дозволяє кількісно порівняти два альтернативні рішення. З математичної точки зору цільова функція описує деяку (n+1) -вимірну поверхню. Її значення визначається проектними параметрами
L L(x
1
, x
2
,..., x
n
) .
Прикладами цільової функції, що часто зустрічаються в інженерній практиці, є вартість, вага, міцність, габарити, ККД. Якщо є тільки один проектний параметр, то цільову функцію можна представити з допомогою кривої на площині. Якщо проектних параметрів два, то цільова функція зображатиметься поверхнею в просторі трьох вимірювань. При трьох і більш проектних параметрах поверхні, що задаються цільовою функцією, називаються гіперповерхнями і не піддаються зображенню звичайними засобами. Топологічні властивості поверхні цільової функції відіграють велику роль в процесі оптимізації, оскільки від них залежить вибір найбільш ефективного алгоритму.
Цільова функція у ряді випадків може приймати найнесподіваніші форми.

13
Наприклад, її не завжди вдається виразити в замкнутій математичній формі, в
інших випадках вона може бути шматково-гладкою функцією. Для задання цільовій функції іноді може знадобитися таблиця технічних даних (наприклад таблиця стану водяної пари) або може знадобитися провести експеримент. В ряді випадків проектні параметри приймають тільки цілі значення. Прикладом може служити число зубів в зубчатій передачі або число болтів у фланці. Іноді проектні параметри мають тільки два значення - так чи ні. Якісні параметри, такі як задоволення, яке випробовує покупець, що придбав виріб, надійність, естетичність, теж можливо враховувати в процесі оптимізації, хоча їх складно охарактеризувати кількісно. Проте в якому б вигляді не була представлена цільова функція, вона повинна бути однозначною функцією проектних параметрів.
В ряді завдань оптимізації потрібне введення більш однієї цільової функції.
Іноді одна з них може виявитися несумісною з іншою. Прикладом служить проектування літаків, коли одночасно потрібно забезпечити максимальну міцність, мінімальну вагу і мінімальну вартість. В таких випадках конструктор повинен ввести систему пріоритетів і поставити у відповідність кожній цільовій функції деякий безрозмірний множник. В результаті з'являється «функція компромісу», що дозволяє в процесі оптимізації користуватися однією складеною цільовою функцією.
Пошук мінімуму і максимуму. Одні алгоритми оптимізації пристосовані для пошуку максимуму, інші - для пошуку мінімуму. Проте незалежно від типу вирішуваної задачі на екстремум можна користуватися одним і тим же алгоритмом, оскільки завдання мінімізації можна легко перетворити на завдання пошуку максимуму, помінявши знак цільової функції на зворотний.
Множина допустимих рішень (МДР) - простір рішення. Так називається область, визначена всіма п проектними параметрами. Простір рішення не такий великий, як може здаватися на перший погляд, оскільки вона зазвичай обмежена рядом умов, пов'язаних з фізичною суттю завдання. Обмеження можуть бути такими сильними, що завдання не матиме жодного задовільного рішення. Слід зазначити, що дуже часто у зв'язку з обмеженнями оптимальне значення цільової функції досягається на одній з меж області множини допустимих рішень задачі.

14
Локальний оптимум. Так називається точка простору рішень, в якій цільова функція має найбільше значення в порівнянні з її значеннями в усіх інших точках
її найближчого околу.
Досить часто простір проектування містить багато локальних оптимумів і слід дотримуватися обережності, щоб не прийняти перший з них за оптимальне рішення задачі.
Глобальний оптимум. Глобальний оптимум - це оптимальне рішення для всієї множини допустимих рішень. Воно краще за всі інші рішення, відповідні локальному оптимуму, і саме його шукає ОПР. Можливий випадок декількох рівних глобальних оптимумів, розташованих в різних частинах простору проектування.