Мат_методи дослідження операційі. Навчальний посібник Київ 2008 Зміст Анотація 3 План курсу 4 Лекція Вступ. Цілі, критерії, обмеження. 4
 Скачать 0.81 Mb.
|
Лекція 11. Складні системи. Класифікація задач прийняття рішень і прийняття рішень в умовах невизначеності.Складними системами називаються сукупності об'єктів, що характеризуються численими і різноманітними за типом зв'язками між окремо існуючими елементами системи і наявністю в системи функції призначення, якої немає в її складових частин. Термін "теорія систем" відноситься до різних аспектів дослідження систем. Її основними частинами є
Найбільш близьке до терміна "системний аналіз" поняття - "дослідження операцій", що позначає математичну дисципліну, що охоплює дослідження математичних моделей для вибору величин, що оптимізують задану математичну конструкцію (критерій) Опора системного аналізу на дослідження операцій приводить до таких його математизованих розділів, як
Принципи системного підходу - це положення загального характеру, що є узагальненням досвіду роботи людини зі складними системами. Найбільш важливими принципами є:
У найбільш загальному розумінні теорія прийняття оптимальних рішень являє собою сукупність математичних і чисельних методів, орієнтованих на знаходження найкращих (оптимальних) варіантів з безлічі альтернатив і що дозволяють уникнути їх повного перебору. Моделі прийняття оптимальних рішень відрізняються універсальністю, однак їх успішне застосування залежить від професійної підготовки фахівця, що повинен мати повне уявлення про специфіку досліджуваної системи. Ці моделі можна класифікувати як задачі мінімізації (максимізації) M-векторного векторного показника ефективності Wm(x), m=1,2,...,M, N-мірного векторного аргументу x=(x1,x2,...,x), компоненти якого задовольняють системі обмежень-рівностей hk(x)=0, k = 1, 2 ... K, обмежень-нерівностей gj(x)>0, j=1,2,...J, обласним обмеженням xli Усі задачі прийняття оптимальних рішень можна класифікувати відповідно до виду функцій і розмірністю Wm(x), hk(x), gj(x) і розмірністю і змістом вектора x:
Усі рішення приймаються завжди на основі інформації, якою володіє особа, що приймає рішення (ОПР). Кожна задача у своїй постановці повинна відбивати структуру і динаміку знань ОПР про множину припустимих рішень і про показник ефективності. У ряді задач прийняття рішення вдається побудувати задовільну математичну модель. Тоді критерієм вибору того чи іншого оптимального рішення служить обчислене значення цільової функції. У реальних умовах просту математичну модель вдається відшукати не завжди. Задача називається статичною, якщо ухвалення рішення відбувається в заздалегідь відомому і не змінному інформаційному стані. Якщо інформаційні стани в процесі прийняття рішення змінюють один одного, то задача називається динамічною. Прийняття рішень в умовах ризику З точки зору знань про вихідні дані в процесі прийняття рішень можна уявити два крайніх випадки: визначеність і невизначеність. У деяких випадках невизначеність знань є мов би "неповною" і доповнюється деякими відомостями про діючі фактори, зокрема, знанням законів розподілу випадкових величин, що їх описують. Цей проміжний випадок відповідає ситуації ризику. Прийняття рішень в умовах ризику може грунтуватись на одному з таких критеріїв:
Таким чином, інформаційні стани ОПР можуть по-різному характеризувати його фізичний стан:
Прийняття рішень в умовах невизначеності Постановка задачі Більшість реальних задач містить у тому чи іншому виді невизначеність. Можна навіть затверджувати, що рішення задач з урахуванням різного виду невизначеностей є загальним випадком, а прийняття рішень без їхнього обліку - часткою. В даний час не існує єдиного методологічного підходу до рішення таких задач. Проте, накопичена досить велика кількість методів формалізації постановки і прийняття рішень з урахуванням невизначеностей. При використанні цих методів варто мати на увазі, що усі вони мають рекомендаційний характер і вибір остаточного рішення завжди залишається за людиною (ОПР). Як уже вказувалося, при вирішенні конкретних задач з урахуванням невизначеностей фахівець стикається з різними їх типами. У дослідженні операцій прийнято розрізняти три типи невизначеностей:
Урахування невизначених пасивних умов Теоретичною основою знаходження оптимального рішення в умовах невизначеності і конфліктних ситуацій є теорія ігор. Гра – це математична модель процесу функціонування конфліктуючих елементів систем, у якому дії гравців здійснюються за певними правилами, які називаються стратегіями. Назвемо стратегією (альтернативою) варіант вибору значень керування змінної. У детермінованих задачах кожна стратегія приводить до одного єдиного рішення (результату). На практиці результатом вибору стратегії є випадкова подія. У кращому випадку відомі імовірнісні характеристики цих подій, а в гіршому – імовірності подій невідомі. Невизначені фактори, закон розподілу яких невідомий, є найбільш характерними при дослідженні якості адаптивних систем. Методичне врахування таких факторів базується на формуванні спеціальних критеріїв, на основі яких приймаються рішення. Критерії Вальда, Севіджа, Гурвіца і Лапласа вже давно і міцно ввійшли в теорію прийняття рішень. Критерій Вальда (максимінний). Відповідно до цього критерію в якості оптимальної вибирається та стратегія, при якій вибирається максимальний з мінімальних виграшів. Відповідно до критерію Вальда в якості оптимальної вибирається стратегія, що гарантує виграш не менший, ніж "нижня ціна гри з природою":
Правило вибору рішення відповідно до критерію Вальда можна інтерпретувати в такий спосіб: матриця рішень [Wir] доповнюється ще одним стовпцем з найменших результатів Wir кожного рядка. Вибрати слід той варіант, у рядку якого стоїть найбільше значення Wir цього стовпця. Обране в такий спосіб рішення цілком виключає ризик. Це означає, що ОПР не може зіштовхнутися з гіршим результатом, ніж той, на який він орієнтується. Які б умови Vj не зустрілися, відповідний результат не може виявитися нижче W. Ця властивість дозволяє вважати критерій Вальда одним з фундаментальних. Тому в практичних задачах він застосовується найчастіше як свідомо, так і неусвідомлено. Однак у практичних ситуаціях зайвий песимізм цього критерію може виявитися дуже невигідним. Застосування цього критерію може бути виправдано, якщо ситуація, у якій приймається рішення, характеризується такими обставинами:
Критерій Севіджа (мінімаксний). За змістом його можна назвати критерієм крайнього песимізму. Вважається, що один виграш може бути більшим, за рахунок більш вдалих умов проведення операції. Вводиться новий показник, що характеризує доречність застосування обраної стратегії в даних умовах. Цей показник називається ризиком W. На відміну від критерію Вальда найгіршим вважається не мінімальний виграш, а максимальний ризик, тобто недоотримане значення. Відповідно до критерію Севіджа в якості оптимальної вибирається така стратегія, при якій величина ризику приймає найменше значення в найгіршій ситуації:
Тут величину W можна трактувати як максимальний додатковий виграш, що досягається, якщо в стані Vj замість варіанта Ui вибрати інший, оптимальний для цього зовнішнього стану, варіант. Відповідне критерію Севіджа правило вибору таке: кожен елемент матриці рішень [Wij] віднімається від найбільшого результату max Wij відповідного стовпця. Різниці утворять матрицю залишків. Ця матриця поповнюється стовпцем найбільших різниць Wir. Вибирається той варіант, у рядку якого стоїть найменше значення. Критерій Гурвіца. Відповідно до критерію Гурвіца вибирається така стратегія, що займає деяке проміжне положення між крайнім песимізмом і оптимізмом:
де - коефіцієнт песимізму, обираний в інтервалі [0,1]. Правило вибору відповідно до цього критерію таке: матриця рішень [Wij] доповнюється стовпцем, що містить середні зважені найменшого і найбільшого результатів для кожного рядка. Вибирається той варіант, у рядках якого стоять найбільші елементи Wir цього стовпця. При =1 критерій Гурвіца перетворюється в критерій Вальда (песиміста), а при =0 – у критерій азартного гравця. Звідси ясно, яке значення має ваговий множник . У практичних аплікаціях правильно вибрати цей множник буває так само важко, як правильно вибрати критерій. Тому найчастіше ваговий множник =0.5 приймається як середня точка зору. Критерій Гурвіца пред'являє до ситуації, у якій приймається рішення, такі вимоги:
Елементи теорії ігор. Основний постулат теорії ігор – будь-який суб'єкт системи – щонайменше так само розумний, як і сторона, що оперує, і робить усе можливе, щоб досягти своїх цілей. Від реального конфлікту гра (математична модель конфлікту) відрізняється тим, що вона ведеться за визначеними правилами, що встановлюють порядок і черговість дій суб'єктів системи, їх поінформованість, порядок обміну інформацією, формування результату гри. Існує багато класів ігор, що відрізняються кількістю гравців, числом ходів, характером функцій виграшу і т.д. Виділимо такі основні класи ігор:
Найбільше поширення на практиці мають парні стратегічні безкоаліційні кінцеві некооперативні ігри. Модель проблемної ситуації в цьому випадку має вигляд: < U, V, W1, W2, R1, R2 >, де U – множина стратегій сторони, що оперує, (конструктора); V – множина стратегій сторони, що опонує, (технолог і природа); W1 і W2 – показники якості гравців; R1 і R2 – системи переваг гравців. Системи переваг гравців, у свою чергу, ґрунтуються на двох провівдних принципах раціонального поводження: принципі найбільшого гарантованого результату і принципі рівноваги. Перший грунтується на тому, що раціональним вибором одного з гравців повинен вважатися такий, при якому він розраховує на найнесприятливішу для нього реакцію з боку іншого гравця. Другий принцип говорить, що раціональним вибором будь-якого гравця вважається така стратегія u$ (чи v$), для якої ситуація (u$, v$) взаємовигідна: будь-яке відхилення від даної ситуації гри не є вигідним ні для одного з гравців. Вирішується парна матрична гра з нульовою сумою (виграш однієї сторони дорівнює програшу іншої) на основі розгляду платіжної матриці, що являє собою сукупність значень U і V (пари стратегій (u,v) U ´ V називається ситуацією гри) а також виграшів Wij при парному сполученні всіх можливих стратегій сторін. Рішення парної матричної гри може бути в чистих стратегіях, коли для кожної зі сторін може бути визначена єдина оптимальна стратегія, відхилення від який невигідно обом гравцям. Якщо вигідно використовувати кілька стратегій з визначеною частотою їхнього чергування, то рішення знаходиться в змішаних стратегіях. Основні особливості використання методів теорії полягають у наступному. Як можливі стратегії з боку проектованої системи розглядаються можливі варіанти її побудови, з яких варто вибрати найбільш раціональний. Як стратегії супротивника розглядаються можливі варіанти його протидії, стратегії їхнього застосування. Необхідно відзначити, що при розгляді ігор з використанням адаптивної системи число її стратегій може бути істотно розширене завдяки реалізації "гнучких" рішень. Аналіз ігрових ситуацій у цьому випадку може бути спрямований не тільки на вибір раціонального варіанта проектованої системи, але і на визначення алгоритмів раціонального застосування системи в конфліктній ситуації. Інша особливість застосування методів теорії ігор полягає у виборі рішень, одержуваних на основі аналізу конфліктної ситуації. У теорії ігор доводиться теорема про те, що оптимальна стратегія для кожного з гравців є оптимальною і для іншого. Так, якщо рішення гри отримане в чистих стратегіях (є сідлова точка), то вибір рішення однозначний. Наприклад, якщо для парної антагоністичної гри 3´4 скласти матрицю, де елементами uij будуть виграші (програші) гравців, то сідлова точка знаходиться на перетині максиміну рядків і мінімаксу стовпців. Оптимальними стратегіями гри наведеної в табл. 8.1 будуть для A – 2, для B – 2. Ціна гри дорівнює 5. Відзначимо, що у випадку наявності сідлової точки жоден із гравців не може поліпшити стратегію, і стратегії такі називаються чистими. Відзначимо, що гра з чистими стратегіями може існувати тільки при наявності повної інформації про дії супротивника. Таблиця 8.1
Якщо ж рішення гри отримане в змішаних стратегіях, то це еквівалентно створенню безлічі варіантів проектованого компонента і використанню їх з оптимальними частотам, що відповідають оптимальній змішаній стратегії. У випадках, коли немає повної інформації про дії супротивника, вводяться імовірності застосування тієї чи іншої стратегії у вигляді векторів
При цьому гравець A вибирає стратегію відповідно до принципу максиміну за виразом:  а гравець B за принципом мінімаксу  Розглянемо приклад: нехай розглядається прийняття рішення в грі 2´2, де гравець A знає імовірність стратегії 1, тобто p1, тоді очевидно імовірність стратегії 2 буде 1-p, відповідно стратегії гравця B будуть q1 і 1-q1. Платіжна матриця буде мати вигляд:
На підставі матриці (8.1) і наведених вище виразів складається таблиця: Таблиця 8.2
З табл. 8.2 видно, що очікуваний виграш гравця A лінійно залежить від імовірності p1 (у даному випадку задача може бути вирішена графоаналітично). Тоді змішана стратегія гравця А буде мати вид *1, p*2>, тобто гравцю A вигідно застосовувати стратегію 1 з частотою (імовірністю) – p1, а стратегію 2 з частотою p2. Очевидно, що розробка декількох варіантів поведінки пов’язана з великими витратами, не завжди може бути реалізована й ускладнює використання системи. Тому при одержанні рішення в змішаних стратегіях рекомендуються такі випадки прийняття остаточного рішення:
Важливе значення в задачах дослідження якості адаптивних систем має не тільки рішення гри, але й аналіз платіжної матриці. Це особливо важливо в тих випадках, коли рішення в змішаних стратегіях не реалізується. Цей аналіз може проводитися на основі:
Для аналізу конфліктної ситуації потрібно на основі математичної моделі операції побудувати платіжну матрицю [Wmn] = [Wij], де Wij характеризує якість вибору при виборі i-го варіанта реалізації і при j-му варіанті протидії супротивника. Рішення може бути отримане в чистих стратегіях, коли є сідлова точка. Умова сідлової точки має вигляд
де ліва частина виразу – нижня ціна гри, права – верхня ціна гри. Якщо умова  де М – математичне очікування – не виконується, то сідлова точка відсутня і потрібна реалізація змішаної стратегії. Рішення в змішаних стратегіях полягає в реалізації чистих стратегій з різними імовірностями, що задаються розподілом: для шуканого вибору – у в идгляі вектора-стовпця
для протидії – у вигляді вектора-рядка
де gi – імовірність вибору стратегії ui; fj – імовірність вибору стратегії vj. Платіжну функцію запишемо в токому вигляді:  де індексом "т" позначена процедура транспонування. Платіжна функція W(G,F) завжди має сідлову точку, тобто завжди існує рішення матричної гри. Це твердження відповідає основній теоремі теорії матричних ігор: кожна матрична гра з нульовою сумою має, принаймні, одне рішення в чистих чи змішаних стратегіях. Послідовність вирішення гри така:
У співвідношенні стратегії і результатів в задачах прийняття рішень можливі три ситуації, які суттєво визначають моделі і процедуру рішення.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
