Багатокрітеріальна задача

Реферат: Багатокрітеріальна задача

Багатокрітеріальна задача: оптимальність по конусу

Розглядається задача прийняття рішень у деякій керованій системі, якість рішення в якій оцінюється декількома критеріями. Досліджуємо поняття оптимальності в багатокрітеріальної задачі. У такій постановці проявляється невизначеність у керованій системі. Фактично в цьому випадку представлена невизначеність у виборі рішення особою, що приймає рішення (ЛПР), щодо підсумкової мети вибору. У класифікації невизначеностей у дослідженні операцій вона виділена як “невизначеність, що відбиває нечіткість знання гравцями своїх цілей” [1, c.17].

Перейдемо до математичної формалізації, при цьому використовуємо термінологію й позначення з [2]. Отже, розглядається багатокрітеріальна задача

(1)

Тут є один учасник, що приймає рішення (ЛПР). Задано множину припустимих альтернатив x X Rn, з яких ЛПР робить свій вибір. Виділено кінцевий набір бажаних властивостей, оцінюваних критеріями. У розглянутій математичній моделі використовуються кількісні критерії, які представляються цільовими функціями: кожна функція оцінює одну властивість.

Звичайно інформацію o всіх критеріях поєднують в одну, векторну функцію Значення цієї векторної функції кожній альтернативі ставлять у відповідність кількісну оцінку для виділених властивостей у критеріальному просторі . Множина всіх векторних оцінок або множина результатів .

Не зменшуючи спільності, уважаємо, що критерії є позитивними, тобто ЛПР прагнути до їхнього збільшення [3, с.55]. Тоді, на змістовному рівні, ціль ЛПР складається у виборі такої альтернативи, що доставляє можливо більші значення одночасно всім компонентам векторної функції виграшу . Відзначимо, що відповідно до [3, c.12-13] множина X і векторна функція f з (1) визначають відповідно реалізаційну й оцінну структури задачі ухвалення рішення. Використовуємо позначення для відношення переваги в Rm з [4, с.7]:

;

(2)

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

Досить загальний підхід на визначення оцінної структури в (1) пропонують конусні відносини. У багатокрітеріальних задачах такий підхід представлений в [4, с.42 - 47; 5; 6; 7]. Будемо розглядати опуклий, гострий конус К [8, с.235-255]. Часто розглядається багатогранний конус у евклідовому просторі, якім можна задати квадратною матрицею, саме,

K = { f Rm | Af ? 0m (3)

Думаємо, що елементи матриці А є ненегативними, а сама матриця невирожденою. Це гарантує те, що відповідний конус К буде опуклим, гострим і його розмірністю збігається з розмірністю критериального простору . Конус породжує у векторному просторі бінарне відношення ?k за правилом

f ?k g (4)

Відомо, що якщо конус К у (4) є опуклим, гострим і не містить початок координат, то він визначає відношення строго порядку інваріантне щодо лінійного позитивного перетворення в. Вірно й зворотне твердження [4, с.45].

Такий конус До називають конусом домінування в. Стандартним образом строгий порядок (4) у при заданому конусу До визначає оптимальне (максимальне, мінімальне) по конусу рішення в багатокрітеріальної задачі (1).

Визначення 1. Альтернатива x* X називається оптимальної по конусу К у задачі векторної оптимізації (1), якщо x X, x - x* ? K. Якщо ( ), то оптимальне рішення називається максимальним по конусу ДО (мінімальних по конусу К).

Відзначимо, що максимальні по Парето альтернативи в багатокрітеріальної задачі (1) є максимальними по конусу рішеннями й конус домінування з (2).

Підхід до рішення багатокрітеріальної задачі (1) на підставі конусних відносин переваги широко використовувалися й результати представлені в ряді робіт. Так, якщо в багатокрітеріальної задачі (1) множина альтернатив X Rn компактно, векторна функція виграшу f: X Rm безперервна, конус домінування К у критериальному просторі є опуклим, гострим, то існує альтернатива, оптимальна по конусу К. Далі, для побудови процедури уточнення оптимального по Парето рішення, буде потрібно результат, представлений в [5, с.336]. Нехай у багатокрітеріальної задачі (1) задані конуси домінування й множини альтернатив, оптимальних по конусу відповідно. Тоді із треба включення

Приклад. Розглядається двохкрітеріальна задача

, (5)

у якій множина припустимих результатів представлена на мал.1. Двохкрітеріальний виграш = і область результатів показана на мал. 2. Задано багатогранний конус домінування

K = {x R2 | Ax = }. (6)

Цей конус домінування К у просторі представлений на мал. 3.

Розглянемо оцінки припустимих результатів, представлені на мал. 2. Розташуємо конус домінування в R2 так, що його вершина збігається з оцінкою деякого результату. Якщо, у цьому випадку, множина крапок конуса не перетинається із множиною оцінок всіх припустимих результатів (за винятком загальної вершини), то відповідний результат є оптимальним по конусу К. Тоді оптимальні по конусу результати розташовані на дузі QMPNT (мал. 2), а відповідні альтернативи на стороні АВ (мал. 1). У цьому випадку r* = 1. Виділимо на дузі оцінки, оптимальні по конусу К. Вони розташовані на ділянці дуги NM (мал. 2). У просторі критеріїв координати крапки N (крапки М) перебувають із умови

( ).

У даному прикладі отримані всі максимальні по конусу K результати

Вони зображені відрізком СD на мал. 1. Множина оцінок

відзначені дугою NM на мал. 2.

Помітимо, що в даної багатокрітеріальної задачі (5) максимальні по конусу рішення є уточненням максимальних по Парето рішень. Дійсно, паретовські альтернативи представляються відрізком АВ на мал.1 і їхньої оцінки - всією дугою QMPNT на мал.2. У теж час оптимальні по конусу з (6) рішення представляються крапками відрізка CD на мал.1 і їхні образи - дугою NM на мал.2.

Мал. 3. Конус домінування в просторі

Багатокрітеріальна задача (1) є задачею в умовах невизначеності, саме в умовах невизначеності мети. Для уточнення рішення (зменшення ступеня невизначеності) можна використовувати додаткову інформацію. Це можуть бути думки експертів. Так у розглянутому прикладі два експерти оцінили важливість (вага) критеріїв. Перший експерт указав відношення важливості для критеріїв, як 3:2, а другий експерт, як 4:1. Ця інформація дозволила визначити багатогранний конус переваг K і відповідну матрицю А в (6). Отримане оптимальне по конуса К рішення має певний змістовний зміст..

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

Співвідношення між критеріями визначаються параметрами конуса, саме, що направляють векторами ребер конуса. Вони представлені на мал. 3. Це вектори d1(2,-3) і d2(-1,4). Таким чином, конусні рішення - це паретовські рішення, із числа яких виключені свідомо неприйнятні (на думку експертів) рішення. Відзначимо, що нічого не міняється, якщо інформація про важливість критеріїв отримана від ЛПР. Така інформація не входить у формулювання багатокрітеріальної задачі (1), але, безумовно, є важливою при ухваленні рішення. Використання інформації про відносну важливість критеріїв і звуження на її підставі множини Парето докладно представлене в [4].

2 Уточнене по послідовність конусув рішення

Оптимальних по конусу рішень може бути багато. Тоді уточнення по конусу можна застосувати кілька разів, послідовно уточнюючи (поліпшуючи) рішення. Відповідний підхід можна представити в матричній формі. Розглянемо наступну послідовність квадратних, нерозкладних матриць [8, с.352; c.381]

. (7)

Всі елементи стохастичної матриці ненегативні й сума елементів кожного рядка дорівнює 1 [8, с.381]. По послідовності матриць побудуємо нову послідовність

(8)

Кожна матриця з послідовності (8) буде визначати багатогранний конус аналогічно (2). Позначимо конуси цієї послідовності, як Отримана послідовність конусув дозволить побудувати уточнене по конусу рішення багатокрітеріальної задачі (1).

Твердження 1. Нехай матриці , з послідовності (7) є ненегативними, нерозкладними, стохастичними. Тоді для будь-якого натурального n

a) матриця з послідовності (8) є ненегативної, нерозкладної, стохастичної;

б) для відповідних конусув має місце включення

в) для відповідних множин оптимальних по конусу рішень задачі (1) має місце включення

Кожна матриця з послідовності (8) є стохастичної і для них вірні умови теореми Фробениуса. У кожної такої матриці максимальне власне значення Кожному власному значенню однозначно можна вибрати лівий власний вектор

(9)

З огляду на вищевикладене, для послідовності матриць (8) вірно

Твердження 2. Нехай матриці , з послідовності (7) є ненегативними, нерозкладними. Тоді існує межа послідовності матриць (8), тобто

=

Матриця є позитивної, з рангом рівним 1, всі рядки матриці рівні

,

де лівий власний вектор з (9).

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

Визначення 2. Розглядається багатокрітеріальна задача (1) і послідовність ненегативних, нерозкладних матриць (7). Нехай набір чисел

представляє рядок граничної матриці із твердження 2. Тоді альтернативу

(10)

будемо називати уточненим по послідовності конусув (7) оптимальним (максимальним) рішенням багатокрітеріальної задачі (1).

Твердження 3. Нехай у багатокрітеріальної задачі (1) множина припустимих альтернатив X Rn компактно, векторна функція виграшу f: X Rm безперервна, квадратні матриці порядку m у послідовності (7) є ненегативними, нерозкладними, стохастичними. Тоді в задачі існує оптимальне уточнене по послідовності конусув (7) оптимальне рішення (10).

Існування уточненого по послідовності конусув рішення треба їхньої компактності множини припустимих альтернатив X і безперервності функції

.

де , є рядок граничної матриці .

Твердження 4. Уточнене по послідовності матриць (7) оптимальне (максимальне) рішення в багатокрітеріальної задачі (1) є оптимальним (максимальним) по Парето рішенням, більше того, воно є оптимальним (максимальним) по будь-якому конусу, певному матрицею з послідовності (8).

Уточнення оптимального по Парето (по конусу) рішення багатокрітеріальної задачі (1) визначається послідовністю матриць (7). Зокрема така послідовність може складатися з постійних матриць, тобто в (7) , де - довільна ненегативна, нерозкладна, стохастическая матриця. У цьому випадку послідовність матриць (8) становлять натуральні ступені матриці А. Підсумовуючи результати для даної частки випадку, одержуємо

Твердження 5. Нехай квадратна матриця А порядку m є ненегативної, нерозкладної, стохастичної. Тоді

a) існує межа послідовності матриць = ;

б) гранична матриця А0 є ненегативної, нерозкладної і всі рядки цієї матриці рівні лівому власному вектору, що ставиться до максимального власного значення матриці А

;

с) для послідовності матриць , що відповідає послідовність багатогранних конусув , певна аналогічно (2), задовольняє ланцюжку включень

д) відповідна послідовність множин, оптимальних по конусу , рішень у багатокрітеріальної задачі (1) задовольняє включенням

Якщо у визначенні 2 уточнення оптимального по Парето рішення в багатокрітеріальної задачі (1) проводиться по послідовності багатогранних конусув, певних ступенями ненегативної, нерозкладної матриці А, то отримане рішення будемо називати уточненим по конусу к рішенням багатокрітеріальної задачі (1).

Розглянуті вище методи уточнення оптимального по Парето рішення істотно залежать від додаткової інформації, пов'язаної із критеріями задачі (1). Якщо така інформація відсутня, то рішенням в (1) може бути тільки Парето оптимальний результат. Причому всі такі рішення рівноправні, як рішення задачі (1). У теж час інформація про важливість критеріїв може виникати з оцінок експертів або з відношення ЛПР до критеріїв. Така інформація дозволяє уточнити оптимальне по Парето рішення.

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

Представлений вище алгоритм уточнення рішення припускає використання квадратних матриць порядку m, тобто використання m експертних оцінок відносної важливості критеріїв. Аналогічний алгоритм уточнення рішення можна визначити й для k експертів, k ? m, k ? 2. У цьому випадку матриця А1 у послідовності (7) буде мати розмір k?m і інші матриці послідовності - квадратні порядку k. Якщо ж при виробленні рішення в задачі (1) експерти виробили однозначний набір вагових коефіцієнтів для критеріїв, тобто k = 1, то багатокрітеріальна задача (1) зводиться до задачі математичного програмування. У цьому випадку знімається невизначеність, пов'язана з багатьма критеріями в задачі (1).

Якщо процес вироблення рішення в задачі (1) розвивається в часі, тобто інформація про важливість критеріїв надходить дискретними порціями, то виникає послідовний процес уточнення рішення. Якщо на черговому кроці нова інформація про критеріях відсутня, то остання матриця уточнює оптимальне по Парето рішення. Далі, в умовах відсутності нової інформації, рішення уточнюється послідовністю конусув, обумовлених ступенями останньої матриці . Але таку послідовність уточнень, починаючи із кроку, можна не виконувати, а відразу перейти до граничної матриці, як вона визначається у твердженні 5. Таким чином, застосувавши кінцеве число уточнень (саме ), рішення задачі (1) може бути зведене до задачі математичного програмування і її рішення - уточнене по конусу рішення багатокрітеріальної задачі (1).

Уточнення оптимального по конусу рішення дозволяє в деяких випадках виділити в багатокрітеріальної задачі (1) єдину найкращу альтернативу. Умови існування єдиного уточненого по конусу До рішення формулюється з використанням увігнутості векторної функції мети [9, c.169].

Нехай множина припустимих альтернатив X Rn опукло. Векторна функція векторного аргументу f: X Rm, m?1, називається ввігнутої (строго ввігнутої) на множині X, якщо кожний компонент цієї функції є ввігнутою (строго ввігнутої) на цій множині, тобто для будь-яких i = 1,…,m,xyX,виконано нерівність

( ).

Твердження 6. Нехай у багатокрітеріальної задачі (1) векторна функція f: X Rm, m?1, буде ввігнутої на компактній множині X Rn і найдеться, принаймні, одне , що скалярна функція буде строго ввігнутої на цій множині, багатогранний конус визначений квадратною матрицею А, що є ненегативної, нерозкладної, стохастичної. Тоді в задачі існує єдина уточнена по конусу альтернатива.

Відповідно до визначення 2, уточненим по конусу оптимальним рішенням багатокрітеріальної задачі (1) є альтернатива

.

По теоремі Фробениуса матриця A однозначно визначає лівий власний вектор, що ставиться до максимального власного значення . Це вектор . Тоді функція є строго ввігнутої, тому що такими ж є й функції й, принаймні, одна з них строго ввігнута. Тоді остання лінійна комбінація представляє строго ввігнуту функцію. Нарешті, строго ввігнута функція досягає максимального значення на компактній множині в єдиній крапці [9, с.170].

Приклад (продовження). Продовжимо розгляд задачі (5). Для неї конус домінування К представлений в (6). Цей конус можна задати за допомогою матриці, що, також як і в (6), позначимо А

K = { x R2 | Ax = }.

Знайдемо межу послідовності матриць = . Найбільше власне значення матриці А є = 1 Одержуємо, Тоді за твердженням 5 матриця A0 = Відповідно до визначення 2, уточненим по конусу До максимальним рішенням багатокрітеріальної задачі (5) будуть рішення задачі математичного програмування (задача максимізації)

.

Тут максимальне значення досягається при На мал.1 цьому рішенню відповідає крапці ). У просторі результатів на мал.2 йому відповідає крапка . Таким чином, уточнене по конусу (6) рішення багатокрітеріальної задачі (5) буде єдиним і векторним виграшем у цьому випадку = (0,8944, 0,4472).

Висновок

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

Оптимальне по Парето рішення входить у клас конусних рішень. Багатогранний конус у векторному критериальном просторі задає векторну впорядкованість, що дозволяє визначити оптимальне по конусу рішення. Таке рішення має певний змістовний зміст, пов'язаний з експертними оцінками важливості критеріїв.

Конусне рішення вказує прийнятний компроміс між критеріями на думку експертів при ухваленні рішення. Саме, якщо результат оптимальний по конусу й від нього можливий перехід до іншого результату, що виграш по одному критерії буде більшим, тоді найдеться інший критерій, що програш по ньому буде неприпустимо більшим.

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

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

У роботі проведене обґрунтування алгоритму уточнення рішення. Зазначено властивості послідовності стохастичних матриць, які гарантують існування граничного конуса. Виявлено умови, при яких уточнене по послідовності конусув оптимальне рішення є єдиним. Розглядається модельний приклад.

На підставі дослідження оптимальності по конусу в багатокрітеріальної задачі запропонована концепція уточнення рішення, виявлені властивості уточненого по послідовності конусув рішення й зазначений випадок одиничності такого рішення.

Література

1. Жуковський В.І. Кооперативні ігри при невизначеності. - К., 2002

2. Подиновський В.В., Ногін В.Д. Парето - оптимальні рішення багатокрітеріальних задач. - К., 2002.

3. Розен В.В. Математичні моделі прийняття рішень в економіці. - М.: Книжковий будинок "Університет", Вища школа, 2002.

4. Ногін В.Д. Прийняття рішень у багатокрітеріальному середовищу: кількісний підхід. - К., 2002.

5. Yu P.L. Cone convexity, cone extreme points and nondominated solutions in decision problems with multiobjectives // Journal of optimization theory and application. -1974. -V. 14, No3. - P. 319 - 377.

6. Kuroiwa D., Tanaka T., Truong Xuan Duc Ha. On cone convexity of set - valued maps // Pros. 2nd World Congress of Nonlinear Analysis - Elsevier Science, 1997. -P. 1487 - 1496.

7.Матвєєв В.О. Існування й одиничність уточненого по конусу рішення багатокрітеріальної задачі. - К., 2006

7. Беклемишев Д.В. Додаткови глави лінійної алгебри. - К., 2003

8. Гантмахер Ф.П. Теорія матриць. - К., 2005

9. Васильєв Ф.П. Чисельні методи рішення екстремальних задач. - К., 2005