Лекції - Теорія систем і системний аналіз

Тема 1.Лекція 1_Вводная.doc (1 стор.)
Тема 2.Лекція 2_Основние понятія.doc (1 стор.)
Тема 3_Реалізація СА, показателі.doc (1 стор.)
Тема 4_Вибор.doc (1 стор.)
Тема 5.Лекція 5_ЛП.doc (1 стор.)
Тема 5.Лекція 6_НП.doc (1 стор.)
Тема 6_Лекція 7_ Багатокритеріальні задачі.doc (1 стор.)
Тема 7_Лекція 8_Вибор в умовах ріска.doc (1 стор.)
Тема 8-9_Лекція 10_Ігра з природою, СА істочніков.doc (1 стор.)
Тема 8_Лекція 9_Теорія ігр.doc (1 стор.)
Оригінал







ТЕМА 6. Лекція 7.

Вибір альтернатив у багатокритеріальних задачах


  1. Зведення багатокритеріальної задачі до однокрітеріальним

  2. Умовна максимізація

  3. Пошук альтернативи із заданими властивостями

  4. Знаходження безлічі Парето



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

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

Отже, нехай для оцінювання альтернатив використовується кілька критеріїв q i (x), i = 1,2,3 ..., р. Теоретично можна уявити собі випадок, коли в безлічі Х виявиться одна альтернатива, що володіє найбільшими значеннями р усіх критеріїв; вона і є найкращою. Однак на практиці такі випадки майже не зустрічаються, і виникає питання, як здійснювати вибір (наприклад, на рис. 1 безлічі Х відповідають внутрішні точки фігури на площині значень двох критеріїв q 1 і q 2; обидва критерії бажано максимізувати).

З уществует кілька способів вибору альтернатив в умовах декількох критеріїв. До них, зокрема, відносяться такі як



1. Зведення багатокритеріальної задачі до однокрітеріальним


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


q 0 (x) = q 0 (q 1 (x), q 2 (x), ... q p (x)) (1)


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


q 0 (x) = (2)


1-q 0 (x) = (3)

Коефіцієнти S i забезпечують, по-перше, безрозмірність числа q i (x) / S i, так як приватні критерії можуть мати різну розмірність і тоді деякі арифметичні операції, наприклад, додавання, можуть не мати сенсу. По-друге, в необхідних випадках c їх допомогою виконується умова нормування. Коефіцієнти i,i відображають відносний внесок приватних критеріїв у суперкрітерій, тобто є ваговими коефіцієнтами.

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

q 0 (x) = (4)

Таким чином, завдання зводиться до максимізації суперкрітерія:

x * = arg max q 0 (q 1 (x), q 2 (x), .... q p (x)). (5)

x  X

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

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

Інший варіант пошуку альтернативи, найвіддаленішої від нуля, дає максимізації мінімального критерію:


x * = arg max {min [ ], (6)

x  X


що означає пошук навколо напрямку методом «підтягування самого відсталого». Цей критерій називається також Максимін.


2. Умовна максимізація


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

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

x * = arg {Max q 1 (x) | qi (x) = Ci}, (7)

x  X

за умови, що додаткові критерії залишаються на заданих їм рівнях. Так, рис. 1б ілюструє розв'язок задачі

x * = arg {Max q 2 (x) | q 1 (x) = C 1},

x  X


У деяких завданнях виявляється можливим або навіть необхідним задавати обмеження на супутні критерії не настільки жорстко як в (7). Наприклад, якщо супутній критерій характеризує вартість витрат, то замість фіксації витрат розумно задавати їх верхній рівень, тобто формулювати завдання з обмеженнями типу нерівностей:

На рис. 2 наведено рішення завдання

x 2 * = arg {max q 2 (x) | q1 (x)  C1}.

x  X

Н етрудно побачити, що тут ми переходимо до задачі математичного програмування (лінійного або нелінійного, в залежності від виду q 2 (x)).

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

Нехай приватні критерії впорядковані в порядку убування їхньої важливості. Візьмемо перший з них і знайдемо найкращу за цим критерієм альтернативу. З рис. 2 видно, що якщо найважливішим є критерій q 2 найкраща альтернатива - це х 2 *, якщо ж найважливішим є критерій q 1, то найкраща альтернатива - х 4. Потім визначається «поступка»  q i, тобто величина, на яку ми готові зменшити досягнуте значення найважливішого критерію, щоб за рахунок поступки спробувати збільшити значення наступного за важливістю критерію. На малюнку - альтернативи, отримані таким чином, зображені точками х 3 * та х 5 *.


3. Пошук альтернативи із заданими властивостями


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

1) знайти альтернативу, що задовольняє ці вимоги;

2) якщо встановлено, що така альтернатива на множині Х відсутня, знайти в Х альтернативу, яка підходить до поставлених цілей більш всього.

Характеристики вирішення такого завдання (складність процесу обчислень, швидкість збіжності, кінцева точність) залежать від багатьох факторів.

Зручність методу. Тут можливо задавати бажані значення критерію як точно, так і у вигляді верхніх або нижніх меж. Призначувані таким чином значення називають іноді «рівнями домагань», а точка їх перетину в р-мірному просторі критеріїв - метою, опорною точкою, ідеальною точкою. При цьому важливо відзначити наступне:


оскільки рівні домагань задаються без точного знання структури безлічі Х в просторі приватних критеріїв, цільова точка може виявитися як всередині, так і поза Х. Це відповідає досяжною або недосяжної мети. На рис.3 наведені обидва варіанти - відповідно точки х 1 * і х 2 *.




І дея оптимізації полягає в тому, щоб, почавши з певної альтернативи, наближатися до х * за деякою траєкторії в просторі Х. Для цього вводиться числова міра близькості між черговий альтернативою х і метою х *, тобто між векторами q (x) = (q 1 (x), q 2 (x), .... q p (x)) і Кількісно ця близькість може бути описана по-різному, наприклад, відстані типу:

S (q, ) = Min  i (q i - ) +  p +1 , (9)

i

де вважається, що q i , i - коефіцієнти, що призводять доданки до однакової розмірності і одночасно враховують рівну важливість критеріїв. p +1 враховує наше ставлення до того, що важливіше - збільшити близькість до мети будь-якого з приватних критеріїв або ж сумарну близькість всіх критеріїв до цільових значень.


4. Знаходження безлічі Парето


До аналізу багатокритеріальних задач можна підійти і з інших позицій: спробувати скоротити безліч вихідних варіантів, тобто виключити з неформального аналізу ті варіанти рішень, які будуть свідомо погані. Один з подібних шляхів був запропонований італійським економістом В. Парето в 1904 р.

Е той четвертий, повністю формалізуються спосіб багатокритеріального вибору полягає у відмові від виділення єдиною «найкращої» альтернативи і угоди про те, що перевага однієї альтернативі перед іншою можна віддавати тільки якщо перша за всіма критеріями краще другий. Якщо ж перевагу хоча б за одним критерієм розходиться з перевагою по іншому, то ці альтернативи визнаються незрівняними. В результаті попарного порівняння альтернатив все гірші за всіма критеріями альтернативи відкидаються, а все решту незрівнянні між собою (недомініруемие) приймаються. Далі, якщо все максимально досяжні значення приватних критеріїв не відносяться до однієї і тієї ж альтернативу, то прийняті альтернативи утворюють безліч Парето і вибір на цьому закінчується. На рис. 4 виділено безліч Парето для розглянутого прикладу. При необхідності ж вибору єдиної альтернативи слід залучати додаткові міркування: вводити нові, додаткові критерії й обмеження, або кидати жереб, або вдаватися до послуг експертів.

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

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

Прикладом множини Парето може служити діаграма «вантажопідйомність-дальність» для транспортних засобів (рис.6).








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

Одним словом, ситуація виявляється принципово багатокритеріальної, і цілі проектувальника можуть бути виписані у вигляді

f i (x)  max, i = 1,2, ....... n.

Проектувальник виявляється, таким чином, перед необхідністю шукати компроміс. І одним із шляхів відшукання цього компромісу є побудова Множини Парето, вивчення якого дає велику інформацію. Особа, що приймає рішення бачить, зокрема, скільки «коштує» збільшення одного з показників, як воно позначається на решті показниках, значення яких неодмінно погіршуються. Шукане безліч має, як правило, дуже складну природу, і аналіз його одними лише інтуїтивними методами навряд чи можливий.

Однак, крім критеріїв f i (х) у розпорядженні проектувальника досить часто є ще й певний загальний критерій F (х). Іноді буває можливо формалізувати його, записати в явному вигляді. Наприклад, таким критерієм може бути вартість проекту. У цьому випадку «досліднику операцій» надається можливість вирішити завдання до кінця. Для цього досить визначити вектор х, який дає рішення задачі: F (x)  max при x  P G (f 1, f 2,... f n), де P G (f 1, f 2,... f n) - множина Парето для функцій f 1, f 2,... f n на безлічі G допустимих векторів х. Наприклад, у випадку водогосподарського комплексу безліч G визначається таким розподілом води по об'єктах х i, при якому її кількість не перевершує припливу Q i.

Важливо відзначити, що введення «загального» критерію F (x) і максимізація його значень на множині Парето також є деякою гіпотезою, оскільки із сукупності критеріїв у f 1, f 2,...., f n, F один з критеріїв ми спеціальним чином виділяємо.

Наближене побудова множини Парето відноситься до числа дуже важливих і важких завдань чисельного аналізу. Їх значення постійно зростає, однак чисельні методи побудови точок множин Парето почали інтенсивно розвиватися лише в останні десятиліття.
Навчальний матеріал
© uadoc.zavantag.com
При копіюванні вкажіть посилання.
звернутися до адміністрації