Аксіома Парето і ефективні варіанти

Тема 1. ПРИЙНЯТТЯ РІШЕНЬ В УМОВАХ ВИЗНАЧЕНОСТІ

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

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

Постановка задачі. Основні поняття

При постановці задачі критеріального аналізу передбачається, що в ОПР є декілька варіантів вибору, декілька альтернатив u ϵ U, де U – множина можливих альтернатив, яка містить не менше двох елементів. Залежно від характеру завдання множина U може бути як безперервною, так і дискретною. Якщо вирішується задача стратегічного плану, то під u зазвичай розуміється стратегія, тобто набір правил, які визначають склад і порядок дій у будь-якій з можливих ситуацій, а множина U є дискретною і скінченною.

Під час вирішення задач тактичного плану, наприклад, вибір варіанту якого-небудь проекту, розподіл засобів між об'єктами, визначення складу різних видів міського транспорту множина U може бути як безперервною, так і дискретною.

У нашому курсі вважатимемо, що U дискретна і скінченна, а u – це емпіричний об'єкт, що задається "своїм іменем" (наприклад, назва банків).

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

У загальному вигляді: k – функція від альтернативи u : k(u).

U = ( u₁, u₂,.. u_n ), n – число альтернатив

K( k₁(u), k₂(u),.. k_m(u)), де m – число часткових критеріїв k_i(u)

Можливі варіанти:

1) якщо m=1 – то маємо однокритеріальну задачу, тобто задачу лінійного програмування;

2) якщо m>1, але k(u) P k(v) – маємо тривіальний варіант, оскільки u завжди є кращим за v;

3) якщо за одними критеріями варіант u є більш прийнятним за варіант v, а за іншими – навпаки, то це – завдання критеріального аналізу, способи вирішення якого будуть розглянуті нижче.

Введемо позначення:

K (u) P K (v) – варіант u є більш прийнятним,

K (u) I K (v) – мають однакові переваги,

K(u) N K(v) – незрівнянні.

Формування критеріальної системи

Для формулювання задачі критеріального аналізу необхідно:

1) чітко сформулювати мету, завдання і необхідний результат;

2) класифікувати характеристики варіантів;

3) неупереджено вибрати критерії.

Вимоги до критеріальної системи:

1) відповідність критеріїв меті і завданню;

2) критичність (критерій має бути "чутливим" до зміни варіанту вибору);

3) критерії мають бути обчислюваними;

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

5) декомпозиційність (векторний критерій повинен допускати спрощення задачі шляхом переходу до розгляду окремих часткових критеріїв незалежно від інших; ця вимога зводиться до питання про незалежність часткових критеріїв згідно з існуючою перевагою).

Аксіома Парето і ефективні варіанти

Порівняння між собою векторних критеріїв є досить складною проблемою.

Приклад. U = (u, v, s, t) – множина альтернатив

	k1	k2	k3
u
v
s
t

k(u) ³ k(v), "i=1:3, тому K(u) P K(v).

k(u) ³ k(s), "i=1:3, тому K(u) P K(s),

Тому варіанти s і v виявилися домінованими, інші векторні оцінки порівняти неможливо: k(u) N k(t).

Таким чином уся множина векторних оцінок ділиться на дві підмножини: ефективних {k(u), k(t)} і неефективних {k(v), k(s)} векторних оцінок.

З наведеного прикладу можна зробити важливий висновок: якщо варіант має абсолютний максимум для якого-небудь показника, то він не може бути домінованим.

Аксіома Парето :

Нехай дано дві векторні оцінки:

K( k₁(u), k₂(u), .. k_m(u)) і K( k₁(v), k₂(v), .. k_m(v))

Тоді кажуть, що K(u) P K(v), (P – читається як "перевага в сенсі Парето")

якщо існує хоч би одне j (від 1 до m) таке що:

" i¹j k_i(u) I k_i(v), або k_i(u) P k_i(v), тоді як k_j(u) P k_j(v).

Усі векторні оцінки, для яких не існує більш прийнятних в сенсі Парето векторних оцінок, утворюють множину H^о ефективних векторних оцінок, а відповідні варіанти – множину v^о – ефективних варіантів.

Для нашого прикладу: H = {K(u), K(v), K(s), K(t)}, H^о = {K(u), K(t)} – множина ефективних векторних оцінок.

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

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