4.2.2 Загальні відомості з теорії багатокритеріальної оптимізації

Будь-яка мережа зв'язку є складною технічною системою і характеризується багатьма властивостями, що визначають її споживчу цінність. Ефективність такої системи не може бути повністю охарактеризована за допомогою одного показника. Ефективність у синтезованому змісті означає сукупність практичних достоїнств системи [10,11,12]. Формується набір приватних критеріїв, що досить повно відображає всі аспекти ефективної системи, але має бажані властивості повноти, ненадмірності та мінімальності. Як правило, приватні критерії мають різний фізичний зміст, розмірність, інтервал виміру та найчастіше є суперечливими. Але між окремими характеристиками існує взаємна залежність і діє ряд обмежень. У результаті цього виявляється, що поза деякою областю, що має назву «область згоди», збільшення одних характеристик неминуче спричиняє зменшення інших, причому тих, чисельне значення яких бажано також збільшити, і навпаки. Область, де характеристики взаємно обумовлені, називають областю компромісів або областю Парето.

Задачі вибору ефективного рішення в цих умовах відомі як проблема багатокритеріальної оптимізації, що полягає у виборі компромісного рішення. Процедура знаходження ефективного рішення носить евристичний характер і вирішується в умовах більшої або меншої невизначеності. До певних етапів рішення задачі залучається особа, що формулює завдання та використовує результати її рішення – особа, що приймає рішення (ОПР).

Один з найпоширеніших підходів до роз’вязання такої задачі заснований на зведенні тим або іншим шляхом багатокритеріальної задачі до однокритеріальної. Теоретичною основою такого підходу є теорія корисності [10,11], відповідно до якої передбачається, що існує деяка узагальнена оцінка цінності або корисності будь-якого режиму для ОПР.

Бажано, щоб функція корисності приватних критеріїв була універсальною й добре пристосованою для обліку особливостей конкретних систем, їхніх цілей і критеріїв; була безрозмірною, мала єдиний інтервал зміни (0,1), була інваріантною до виду екстремуму часткового критерію (min або max), тобто найкращому значенню має відповідати значення 1, а найгіршому – 0.

3. Опис алгоритму багатокритеріальної оптимізації

Алгоритм, за допомогою якого в лабораторній роботі відшукується рішення задачі вибору, відноситься до області, що називається системним підходом. Це означає, що роль кожного приватного критерію зважується з погляду його впливу на властивості системи в цілому, функція корисності задається у вигляді узагальненого адитивного критерію, при формуванні якого різна значимість приватних критеріїв ураховується за допомогою вагових коефіцієнтів важливості:

(3.1)

причому .

Визначення вагових коефіцієнтів пов’язане із серйозними труднощами і зазвичай зводиться до експертної оцінки. Для спрощення роботи експертів іноді пропонується вимагати від них тільки ранжування критеріїв за важливістю. Далі ранги переводяться у вагові коефіцієнти за відповідними формулами без участі експертів. У літературі (10) наводиться кілька таких формул. У випадку ж, коли ОПР не має ні кількісної, ні якісною інформації про коефіцієнти, немає необхідності віддавати перевагу якому-небудь критерію й логічно використати «рівність» критеріїв.

У лабораторній роботі розглядаються наступні випадки наявності апріорної інформації про важливість показників:

• задано ваги показників;

• задано порівняльну важливість показників;

• відсутня інформація про важливість показників.

Ці варіанти закладені в меню програми.

Для виконання роботи студенту необхідно знати математичну постановку задачі та алгоритм її вирішення. Нехай є множина ( ) варіантів мережі зв'язку . Якість кожного -го варіанта оцінюється показниками

Всі показники множини ( ) є оптимальними. Потрібно визначити варіант із множини ( ), що відповідає максимуму у виразі (3.1), при якому забезпечуються задовільні з погляду ОПР значення всіх показників і найкращий компроміс між ними з урахуванням властивостей множини ( ) і апріорної інформації про співвідношення важливості показників.

Нижче наведено основну процедуру пошуку рішення.

1. Досліджується множина (1). Проводиться почергова оптимізація по кожному з показників. Отримані максимуми по кожному з показників утворять вектор .

,

2. Проводиться оптимізація за сумарним критерієм. Отриманий варіант , характеризується вектором , компонентами якого є значення показників:

3. Перед ОПР ставиться запитання: «Чи всі показники мають задовільне значення?» При відповіді на це питання для порівняльної оцінки використовується вектор максимумів показників . У випадку позитивної відповіді рішення є остаточним і – шуканий результат. У випадку негативної відповіді ОПР виділяє виконуваний показник , що має найменш задовільне значення, а також указує величину , таку, що при й значення показника вважається задовільним.

4. Визначається нова множина: , , . У множині повторюється крок 1, у результаті чого визначається вектор .

5. Перед ОПР ставиться запитання: «Чи припустиме зменшення максимально можливих значень окремих показників, що виникає при переході від вектора до вектора ?» У випадку негативної відповіді змінюють значення , прийняте раніше в якості задовільного, визначають нове значення . Далі повторюються всі етапи, починаючи з п.4. Даний етап процедури приводить до вибору компромісного значення , що на подальших етапах залишається незмінним.

6. Для безлічі проводиться оптимізація за сумарним критерієм, що приводить до визначення вектора й т.д. Процедура закінчується тоді, коли в результаті запитання по п. 3 отримана позитивна відповідь.

3. Вхідні дані і їх структура

Перед запуском програми на виконання необхідно визначити вхідні дані, які містяться в трьох файлах: “in.dan”, “tab.dan” й “vec.dan”.

У файлі “in.dan”, задається число критеріїв і число варіантів системи, що оптимізується, , а також міститься інформація про критерії і їхні характеристики.

Структуру файлу й приклад його заповнення наведено у табл.3.1.

Файл “tab.dan” – таблиця порівняльної важливості, містить інформацію про порівняльну важливість критеріїв, обрану відповідно до міркувань експертів. Таблиця є квадратною матрицею , кожен елемент якої містить число, що вказує ступінь важливості -го критерію відносно -го. Якщо критерій важливіший, ніж критерій , то , у протилежному випадку . Наприклад, для наведених у таблиці критеріїв таблиця переваг може мати такий вигляд:

У першому рядку «живучість» порівнюється відповідно з «живучістю», «вартістю» й «часом»; «живучість»-«живучість» мають однакову важливість – , «живучість» в 3 рази важливіше «вартості» й в 2 рази важливіше «часу» (наробітку на відмову), відповідно і . У другому рядку «вартість» менш важлива, ніж «живучість» і «час», відповідно і т.д.

Таблиця 3.1.

ВХІДНІ ДАНІ
Число критеріїв m = 3
Число векторів n = 4
Живучість
Вартість
Час
ХАРАКТЕРИСТИКИ КРИТЕРІЇВ
Номер критерію	Вид екстремуму	Вага
1	max	0.5
2	min	0.3
3	max	0.2

У файлі “vec.dan” утримуються значення приватних критеріїв по кожному з варіантів. Для варіанта 1 були розраховані значення і надійність, для варіанта три – надійності. Всі інші значення приватних критеріїв були отримані методом експертних оцінок, значення приватних критеріїв зведені в табл.3.2.