Ім'я файлу: Задачі багатокритеріальної оптимізації та методи їх розв'язуванн
Розширення: docx
Розмір: 937кб.
Дата: 03.04.2020
скачати
Розширення: docx
Розмір: 937кб.
Дата: 03.04.2020
скачати
Вступ
Практично будь-яка серйозна реальна задача характеризується бiльш нiж одним критерiєм. При дослiдженнi складних систем i об’єктiв використання математичних моделей, якi призводять до постановок задач лише скалярної оптимiзацiї, не є адекватним. Реальнi потреби практики проектування i експлуатацiї складних систем потребують врахування i узгодження кiлькох рiзних цiлей. Аналiз задач планування та управлiння на виробництвi також показує, що у реальнiй постановцi цi задачi є багатокритерiальними. Оцiнка дiяльностi пiдприємств проводиться на основi бiльше десятка критерiїв: виконання плану виробництва за обсягом, за номенклатурою; плану реалiзацiї продукцiї, прибутку i т. д. Таким чином, для ефективного розв’язування подiбних задач необхiдно побудувати багатокритерiальну математичну модель, яку потiм потрiбно оптимiзувати, попередньо вибравши найкращий для цього метод (або кiлька методiв).
Математична модель задачi багатокритерiальної оптимiзацiї
Всюди далi будемо розглядати задачi прийняття рiшень в умовах визначеностi при числовiй оцiнцi наслiдкiв, тобто коли зв’язок мiж альтернативами та наслiдками детермiнований (кожнiй альтернативi вiдповiдає лише один наслiдок), i цiль ототожнюється з максимiзацiєю чи мiнiмiзацiєю деякої дiйснозначної функцiї, яка називається частковим критерiєм або цiльовою функцiєю. Будемо розглядати скiнченновимiрнi задачi багатокритерiальної максимiзацiї: 𝑓(𝑋) → max 𝑋∈𝐷 , (1) де 𝐷 ∈ R 𝑛 — допустима область. Елементи 𝑋 = (𝑥1, . . . , 𝑥𝑛) множини 𝐷 називаються допустимими розв’язками або альтернативами, а 𝑓(𝑋) = (𝑓1(𝑋), . . . , 𝑓𝑚(𝑋)) — вектор-функцiя часткових критерiїв 𝑓𝑖 : 𝐷 →
, 𝑖 = 1, 𝑚. У таких задачах допустима множина 𝐷 найчастiше задається у виглядi нерiвностей: 
Класифiкацiя методiв багатокритерiальної оптимiзацiї
Основнi, найбiльш поширенi методи розв’язання задач багатокритерiальної оптимiзацiї представленi на рис. 1.
2. Методи зведення багатокритерiальних задач оптимiзацiї до однокритерiальних
Усi методи розв’язування задач багатокритерiальної оптимiзацiї заснованi на зведеннi початкової задачi з векторним критерiєм до оптимiзацiйної задачi iз скалярним критерiєм. Мiж собою методи вiдрiзняються тiльки механiзмом реалiзацiї такого зведення. Розглянемо найбiльш поширенi з них: згортання часткових критерiїв, головного часткового критерiю, послiдовних поступок, цiльового програмування.
2.1 Методи згортання часткових критерiїв
Замiсть часткових критерiїв 𝑓1, 𝑓2, . . . , 𝑓𝑚 розглядається один скалярний критерiй, отриманий шляхом їх комбiнацiї. Розрiзняють адитивну, мультиплiкативну та максимiнну згортки. Будемо вважати, що усi частковi критерiї нормалiзованi одним iз способiв. Окрiм цього, нехай визначений вектор вагових коефiцiєнтiв критерiїв 𝑎 = (𝑎1, 𝑎2, . . . , 𝑎𝑚), якi характеризують важливiсть вiдповiдного критерiю: 𝑎𝑖 ≥ 𝑎𝑗 , якщо частковий критерiй 𝑓𝑖 має прiоритет над частковим критерiєм 𝑓𝑗 , тобто 𝑓𝑖 ≻ 𝑓𝑗 . При цьому
2.1.1 Метод адитивної згортки критерiїв
У цьому методi узагальнений скалярний критерiй будується за правилом
Пiсля цього розв’язується задача оптимiзацiї критерiю :
Часто отриманий цим методом розв’язок є нестiйким: малим змiнам вагових коефiцiєнтiв 𝑎𝑖 вiдповiдають великi змiни критерiю.
Приклад 1
Розглянемо задачу БО iз двома критерiями
𝑓1 = 𝑥1 → max
𝑓2 = 𝑥2 → max
при обмеженнях
Розв’яжемо задачу оптимiзацiї за кожним з критерiїв окремо. Використовуючи графiчний метод (рис. 4а), одержимо оптимальний розв’язок за першим критерiєм 𝑋* 1 = (2; 0) та оптимальний розв’язок за другим критерiєм 𝑋2 = (0; 1). На рис. 4б зображена множина досяжностi 𝐹 i зазначенi значення
2 та 
Виконаємо згортку критерiїв:
𝑧 = 𝑎1𝑓1(𝑋) + 𝑎2𝑓2(𝑋) = 𝑎1𝑥1 + 𝑎2𝑥2 → max,
де 𝑎1 + 𝑎2 = 1, 𝑎1 ≥ 0, 𝑎2 ≥ 0.
Графiчна iнтерпретацiя розв’язання задачi оптимiзацiї за двома локальними критерiями:
Цiльова функцiя є лiнiйною, тому залежно вiд 𝑎1 та 𝑎2 оптимальними будуть кутовi точки допустимої областi
або 
, або всi точки вiдрiзку 
Якщо 𝑎1 = 𝑎2 = 1/2 , то отримаємо оптимальний розв’язок
= = (2; 0).2.1.2 Метод мультиплiкативної згортки критерiїв
Для цього методу узагальнений скалярний критерiй береться у формi добутку:
Де
Поясненням мультиплiкативного методу є уявлення про ваговi коефiцiєнти 𝑎𝑖 як про ймовiрностi досягнення деяких показникiв якостi.
2.1.3 Метод максимiнної згортки критерiїв (гарантованого результату)
Розглядаються методи гарантованого результату, якi дають найкращий результат навiть для самого найменшого iз часткових критерiїв, тобто компромiсний розв’язок отримується шляхом розв’язання наступної задачi оптимiзацiї:
Основний недолiк методiв згортання критерiїв полягає у суб’єктивностi вибору вагових коефiцiєнтiв
2.2 Метод головного часткового критерiю (метод задоволених вимог)
Визначається головний на думку ОПР (чи експертiв) частковий критерiй. Наприклад, 𝑓𝑗 (𝑋). Всi iншi частковi критерiї переводяться у розряд обмежень за наступним правилом. Вiдповiдно до вимог ОПР на всi iншi частковi критерiї накладаються певнi обмеження — призначаються мiнiмальнi допустимi значення 𝑓̃︀𝑖 для кожного критерiю:
Пiсля цього розв’язується задача однокритерiальної оптимiзацiї:
при умовах:
Як результат розв’язування задачi (13), (14) визначається ефективна альтернатива 𝑋* i її оцiнка
𝑦 * = (𝑓1 (𝑋* ), . . . , 𝑓𝑚 (𝑋* )).
ОПР аналiзує отримане значення
головного часткового критерiю 𝑓𝑗 . Якщо це значення не задовольняє її, то ОПР намагається збiльшити значення головного критерiю за рахунок змiн мiнiмально допустимих рiвнiв iнших критерiїв. Якщо значення головного критерiю задовольняє ОПР, то вона розмiрковує — можливо чи нi деяке погiршення значення головного критерiю з метою покращення значень iнших. Якщо нi, то процедура закiнчується. У протилежному випадку можна зробити спробу призначити iнший головний критерiй.Приклад 2.
Методом головного часткового критерiю розв’язати задачу iз прикладу 1
Нехай перший частковий критерiй 𝑓1 обраний у якостi головного. Призначимо мiнiмальне допустиме значення критерiю 𝑓2 на рiвнi
.Тодi отримаємо наступну однокритерiальну задачу:
при умовах:
Очевидно, що оптимальним розв’язком є точка 𝑋* = (1.2; 0.4), а max 𝑓1(𝑋) = 𝑓1 (𝑋* ) = 1.2.
Якщо це значення головного критерiю 𝑓1 задовольняє ОПР, то процедура методу закiнчується. Якщо нi, то ОПР намагається його збiльшити, замiнюючи мiнiмальний рiвень для часткового критерiю 𝑓2. Якщо при цьому значення другого часткового критерiю стає неприпустимо малим, то, можливо, треба замiнити прiоритети критерiїв (якщо це не буде суперечити змiсту задачi).
2.3 Метод послiдовних поступок
Частковi критерiї нумеруються у порядку спадання їх важливостi для ОПР.
Нехай критерiї 𝑓1, 𝑓2, . . . , 𝑓𝑚 вже записанi у порядку зменшення їх прiоритету, тобто
𝑓1 ≻ 𝑓2 ≻ . . . ≻ 𝑓𝑚.
Крок 1. Розв’язується задача оптимiзацiї за першим частковим критерiєм :
де множина
Нехай 
— оптимальний розв’язок задачi. Позначимо через
вiдповiдну оцiнку значень часткових критерiїв.
Крок 2. ОПР аналiзує отриману оцiнку. У випадку, коли вона не задовольняє ОПР, призначається величина поступки Δ𝑓1 за першим критерiєм, на яку ОПР може погодитися з метою покращення значень iнших, менш важливих критерiїв. Далi будується «уточнена» множина альтернатив 𝐺2 ⊂ 𝐺1:
на якiй розв’язується задача оптимiзацiї за другим частковим критерiєм:
Нехай
— оптимальний розв’язок задачi, а 
- вiдповiдна оцiнка.Крок 𝑚. Призначається поступка
за (𝑚 − 1)-м критерiєм, будується множина
i розв’язується задача
розв’язок якої позначимо
О
ПР повинна чи погодитися з отриманою альтернативою 𝑋𝑚, чи повторно виконати процедуру, замiнивши величини поступок Варто зазначити: якщо на перших кроках методу призначити занадто великi значення поступок, то ефективна альтернатива, отримана в кiнцi процедури, може мати вищi показники за менш важливими критерiями. I навпаки, якщо ОПР намагається отримати високi показники за бiльш важливими критерiями, то вона може отримати ефективну альтернативу iз неприпустимо малими показниками за менш важливими критерiями. Звiдси можна зробити висновок, що дуже важливо вiрно впорядкувати частковi критерiї. Тодi ОПР може обмежитись аналiзом попарного зв’язку критерiїв.
Приклад 3. Методом послiдовних поступок розв’язати таку трикритерiальну задачу:
На рисунку зображено множину альтернатив 𝐷; лiнiї рiвнiв першого, другого та третього критерiїв, вiдповiдно (1), (2), (3); 𝑋′ , 𝑋′′ , 𝑋′′′ — найкращi, вiдповiдно за першим, другим та третiм критерiями задачi, альтернативи.
Будемо вважати, що критерiї вже впорядкованi за зменшенням їхньої важливостi та знайдемо максимум першого критерiю на множинi альтернатив:
Отримаємо ефективну альтернативу 𝑋1 = (4; 1), яка має оцiнку 𝑦 1 = (9; 6; −5). Припустимо, що отриманий результат не задовольняє ОПР. Тодi визначимо величину поступки Δ𝑓1, на яку можна погодитися, щоб покращити значення iнших критерiїв. Нехай Δ𝑓1 = 1, «уточнена» множина альтернатив: 𝐺2 = {︀ 𝑋 : 𝑋 ∈ 𝐺1, 𝑓1(𝑋) >
− Δ𝑓1 = 8}︀ .На другому кроцi максимiзуємо другий критерiй на уточненiй множинi альтернатив:
Iз рисунку бачимо, що розв’язком задачi буде ефективна альтернатива 𝑋2 = (3; 2), яка має оцiнку
= (8; 7; −5). Припустимо, що отриманий результат також не задовольняє ОПР. Тодi визначимо величину поступки Δ𝑓2, на яку можна погодитися, щоб покращити значення третього критерiю. Нехай Δ𝑓2 = 1, «уточнена» множина альтернатив 𝐺3 = {︀ 𝑋 : 𝑋 ∈ 𝐺2, 𝑓2(𝑋) > 
− Δ𝑓2 = 6}︀ . Тепер (крок 3) на цiй множинi максимiзуємо третiй критерiй
Звiдси (це можна побачити на рис. 7) знаходимо ефективну альтернативу
= (︂ 10 3 ; 4 3 )︂ , яка має оцiнку 
= (︂ 8; 6; − 14 3 )︂ .
Якщо ОПР не влаштовують отриманi результати, вона повертається на вiдповiдний крок, де було зроблено (на думку ОПР) невiрну поступку. В iншому випадку процедура закiнчується.
2.4 Метод цiльового програмування (iдеальної точки)
Назва методу пов’язана з тим, що при його реалiзацiї ОПР задає певнi цiльовi значення
для кожного часткового критерiю. Даний метод у загальному випадку не потребує iнформацiї про перевагу на множинi критерiїв. Задача багатокритерiальної оптимiзацiї перетворяюється на задачу мiнiмiзацiї суми вiдхилень вiд цiльових значень iз деяким показником 𝑝 ≥1 
Д
е 
— деякi ваговi коефiцiєнти. Якщо частковi критерiї вважаються рiвноцiнними, то У межах методу робиться припущення про наявнiсть так званої «iдеальної точки»
у просторi критерiїв, де 
Тодi при
одержимо задачу мiнiмiзацiї семи квадратiв вiдхилень:
у якiй мiнiмiзується евклiдова вiдстань вiд множини досяжностi 𝐹 до «iдеальної точки» 𝑓 max («абсолютного максимуму»). Таким чином, у цьому методi правило вибору компромiсу полягає у знаходженнi альтернативи, оцiнка якої є найближчою до «iдеальної точки» у деякiй метрицi. Ускладнення, обумовленнi рiзномасштабнiстю величин
можна усунути за допомогою нормалiзацiї критерiїв:
Приклад 4. Методом цiльового програмування розв’язати задачу з прикладу 1:
𝑓1(X) = 𝑥1 → max
𝑓2(X) = 𝑥2 → max
при обмеженнях
В умовах прикладу 3 маємо
та , тому задача прийме вигляд:
при умовах
При постiйному значеннi 𝑍 лiнiї рiвня цiльової функцiї
являтимуть собою елiпси iз центром у точцi 𝑀(2; 1) та пiвосями 𝑎 = 2𝑍 й 𝑏 = 𝑍. Необхiдно знайти мiнiмальне значення 𝑍, для якого вiдповiдний елiпс буде мати спiльнi точки з областю 𝐷. На рис. 8 показано графiчний розв’язок даної задачi.
Оптимальною є точка 𝑋* = (︂ 1;
)︂ , у якiй елiпс дотикається межi областi 𝐷.3. Iнтерактивнi методи багатокритерiальної оптимiзацiї
Часто для визначення найкращого рiшення ОПР доводиться розв’язувати задачi структурної та параметричної оптимiзацiї. При цьому модель прийняття рiшень описується як задача багатокритерiальної оптимiзацiї. У даний час набули поширення iнтерактивнi методи розв’язування задач векторної оптимiзацiї, у яких уточнення узагальнених критерiїв та упорядкування часткових критерiїв за важливiстю виробляється на основi дiалогу з ЕОМ. При цьому користувач може змiнити процес розв’язування задачi на будь-якому етапi. Основною проблемою тут є розробка ефективних пакетiв прикладних програм, сценарiїв дiалогу, евристичних i точних алгоритмiв розв’язування задач.
3.1 Метод послiдовного вводу обмежень
Характерною особливiстю цiєї дiалогової процедури є послiдовне (на кожному кроцi) введення обмежень на альтернативи, якi мають незадовiльнi, iз погляду ОПР, значення критерiїв. 𝑘-й крок
(𝑘 = 1, 2, . . .). Обчислюються оптимальнi значення кожного критерiю окремо на «уточненiй» множинi альтернатив:
i формується вектор «iдеальної» оцiнки на уточненiй множинi альтернатив:
Далi визначаються ваговi коефiцiєнти критерiїв
та складається матриця 
переваг ОПР на множинi критерiїв, кожна пара симетричних елементiв якої 
характеризує вiдносну важливiсть 𝑖-го критерiю порiвняно з 𝑗-м. Значення кожної пари елементiв цiєї матрицi вибирається так: (8, 1) — при явнiй перевазi 𝑖-го критерiю над 𝑗-м; (4, 1) — при значнiй перевазi; (2, 1) — при «звичайнiй» перевазi; (1, 1) — при рiвноцiнностi критерiїв. Тепер розраховуються ваговi коефiцiєнти критерiїв за такою формулою:
Унаслiдок розв’язку задачi
визначається альтернатива 
i її оцiнка 
ОПР аналiзує отриману альтернативу й оцiнку 𝑦 𝑘 шляхом її зiставлення з «iдеальною» оцiнкою
. Якщо оцiнка 
задовольняє ОПР, то процедура закiнчується, а альтернатива приймається за розв’язок вихiдної задачi. Iнакше, вказується номер 
критерiю, значення якого найменш, на думку ОПР, його задовольняє; визначається, до якого рiвня 
потрiбно покращити значення цього критерiю, формується нова «уточнена» множина альтернатив 
i здiйснюється перехiд на наступний крок.3.2 Метод бажаної точки
Особливiстю цiєї дiалогової процедури є необхiднiсть задання ОПР бажаних значень критерiїв для визначення переваги на множинi критерiїв. 0-й крок. Розраховуються «найкращi» i «найгiршi» значення критерiїв:
здiйснюється 31 монотонне перетворення критерiїв до нормованого безрозмiрного вигляду:
𝑘-й крок (𝑘 = 1, 2, . . .). ОПР аналiзує отриманий на попередньому кроцi розв’язок i його оцiнку порiвняно з «найкращими» i «найгiршими» значеннями критерiїв i вказує бажанi значення критерiїв
Здiйснюється перетворення бажаних значень цiльових функцiй до нормованого безрозмiрного вигляду:
Обчислюються ваговi коефiцiєнти критерiїв:
Ефективна альтернатива
знаходиться як розв’язок однокритерiальної задачi: 
Обчислюється оцiнка
Якщо отриманi значення цiльових функцiй задовольняють ОПР, то процедура закiнчується, у протилежному випадку — переходимо на наступний крок. Цей метод використовує тiльки один тип iнформацiї вiд ОПР про бажанi значення критерiїв.Приклад вирішення задачі багатокритеріальної оптимізації
Розглянемо задачу розподілу вагонів по вантажним фронтам залізничної станції, яка, зазвичай, вирішується методами лінійного програмування, у багатокритеріальній постановці. До вантажної станції прибуває m = 50 ваг, які необхідно вивантажити впродовж доби на трьох вантажних фронтах місткістю відповідно m1 = 25 ваг, m2 = 28 ваг, m3 = 20 ваг. Через різне технічне обладнання вантажних фронтів витрати залізниці пов’язані з вивантаженням вагонів на них, різні і складають C1 = 20 у.о./ваг, C2 = 30 у.о./ваг, С3 = 35 у.о./ваг. Плата клієнтів за вивантаження вантажів складає П1 = 60 у.о./ваг, П2 = 55 у.о./ваг, П3 = 45 у.о./ваг. Необхідно знайти ефективне рішення, яке забезпечує мінімум витрат залізниці та клієнтів при виваженні вагонів. При формалізації задачі в якості змінних обираємо кількість вагонів, які розвантажуються на вантажних фронтах: x1 – на першому фронті, x2 – на другому фронті, x3 – на третьому фронті. Тоді отримаємо дві цільові функції, які матимуть такий вигляд:
Задача має такі обмеження:
– по загальній кількості вагонів, які розвантажуються:
x1 + x2 + x3 = 50;
– по місткості вантажних фронтів:
x1 25; x2 28; x3 20;
Слід також зазначити, що кількість вагонів не може бути від'ємним числом: xі ≥ 0. Таким чином, задача розподілу вагонів по вантажним фронтам матиме такий вигляд:
Вирішимо поставлену задачу за допомого розглянутих вище методів. Для цього необхідно привести її до основної задачі лінійного програмування.
Вводимо додаткові змінні: y1, y2, y3 (відповідно резерви місткості 1-го, 2-го та 3-го вантажних фронтів), щоб перетворити нерівності на рівняння:
За допомогою симплекс методу вирішуємо задачу для першого критерію (С→min). Отримаємо такий розв'язок (1): x1 = 25 ваг, x2 = 25 ваг, x3 = 0 ваг. Витрати залізниці складатимуть С* = 1250 у.о. Витрати клієнтів складатимуть П* = 2875 у.о. За допомогою симплекс методу вирішуємо задачу для другого критерію (П→min). Отримаємо такий розв'язок (2): x1 = 2 ваг, x2 = 28 ваг, x3 =20 ваг. Витрати клієнтів складатимуть П* = 2560 у.о. Витрати залізниці складатимуть С* = 1580 у.о. Отже отримано 2 граничних рішення, при чому обидва вони є ефективними. Таким чином, отримаємо лінійну залежність витрат клієнтів на розвантаження вантажу від витрат залізниці, яка наведена на рисунку.
Лінійна залежність витрат клієнтів від витрат залізниці
Виконаємо розв'язок задачі за допомогою методу згортки критеріїв. Для прикладу припустимо, що критерії С та П рівні за значенням, тобто 1 =0,5 та 2 =0,5. Таким чином отримаємо таку систему рівнянь:
Або після згортки критеріїв:
За допомогою симплекс методу вирішуємо задачу для загального критерію (СП→min). Отримаємо такий розв'язок (3): x1 = 25 ваг, x2 = 5 ваг, x3 =20 ваг. Витрати залізниці складатимуть С* = 1350 у.о. Витрати клієнтів складатимуть П* = 2675 у.о.
Тепер виконаємо розв'язок задачі за допомогою методу послідовних поступок. При вирішенні задачі симплекс-методом для першого критерію (С → min) було отримано ефективний розв'язок, при якому С* = 1250 у.о. Приймаємо максимальну величину поступки по цьому критерію Δ1 = 20 % та вирішуємо задачу у відповідності до алгоритму. Для цього вводимо додаткове обмеження C
1 , деде * C = 1250 у.о., а 1 = 0,2 · 1250 = 250 у.о. Тоді:
За допомогою симплекс методу вирішуємо задачу для другого критерію (П→min) при додатковому обмеженні C
1.Отримаємо такий розв'язок:
x1 = 10 ваг, x2 = 20 ваг, x3 =20 ваг.
Витрати клієнтів складатимуть П* = 2600 у.о. Витрати залізниці складатимуть С* = 1500 у.о.