Тема: Підбір кадрів для служб залізниці
Завдання: на основі запропонованих прикладів розробити власну систему підтримки прийняття рішень
. Введення
Теорія ігор займається вивченням т.зв. конфліктних ситуацій, де стикаються інтереси індивідів, партій, держав і т. п.
Як стверджував Г. Лейбніц, ... та ігри заслуговують вивчення; і якщо який-небудь проникливий математик присвятить себе їх вивченню, то отримає багато важливих результатів, бо ніде людина не показує стільки винахідливості, як у грі .
Ні математичної теорії, яка могла б дати алгоритм будь реальної гри, але існують ситуації, подібні ігровим й допускають математичний аналіз.
Зупинимося на класифікації ігор.
Інтереси учасників гри (гравців) можуть виявитися незбіжними і навіть протилежними. В останньому випадку гра називається антагоністичною.
У грі можуть брати участь два або більше гравців. Випадок гри з одним учасником (пасьянс, управління фізичним об'єктом і т.д.) по суті є грою двох осіб, де другий учасником виступає природа (доля, рок, провидіння).
Гравці можуть в грі виступати кожен за себе або об'єднуватися в групи. В останньому випадку гра називається коаліційної.
Ігри, в яких гравці обізнані про стан своєму і партнерів, а також про минуле поведінці учасників гри, відносяться до категорії ігор з повною інформацією (типові приклади - шахи, хрестики-нулики і т. п.). Більшість же ігор протікає в умовах неповної інформації, де відомості про стан партнерів вичерпуються лише імовірнісними характеристиками (доміно, карткові ігри, ігри проти природи ).
антагоністичних гру, де виграш одного колективу дорівнює програшу іншого, називають грою з нульовою сумою.
Система правил, однозначно визначає вибір ходу гравця в залежності від ситуації, що склалася, називається стратегією.
Кожна фіксована стратегія гравця, де будь-якій ситуації зіставлений конкретний вибір, називається чистим. У реальності частіше використовуються т.зв. змішані стратегії, де чисті стратегії змішуються з деякими частотами.
Найпростішими є ігри 2 осіб з нульовою сумою.
Нехай в такій грі гравець 1 має m виборів і гравець 2 - n виборів. Якщо гравець 1 робить свій i-й вибір, а гравець 2 - свій j-й вибір, то виграш гравця 1 (програш гравця 2) дорівнює Rij. Така гра називається матричної і матриця R=[Rij/i=1..m, j=1..n] називається матрицею виграшів (пла-тіжних матрицею).
При веденні гри гравець повинен орієнтуватися на оптимальну політику партнера і карати його за відступи від такої.
Проведемо міркування за гравця 1. Якщо Я скористаюся i-му вибором, мій противник для мінімізації мого виграшу зробить той зі своїх виборів, який дасть min Rij. Відповідно, Я повинен використовувати той вибір, який гарантує мені виграш, не менший
Противник, розмірковуючи аналогічно, приходить до висновку про гарантоване програші, що не перевищує
Якщо в матриці виграшів існує елемент Rkl=V1=V2, то говорять про наявність оптимальної політики в просторі чистих стратегій і оптимальними виборами для гравців відповідно є вибори k і l. Пару (k, l) називають сідловою.
Приклад 1. Нехай гра визначається матрицею
сідловою - (4, 1) і (4, 2). Ціна гри=6; оптимальний вибір для гравця 1 - четвертий, для гравця 2 рівнозначні перший і другий (під ціною гри розуміють гарантований виграш-програш при оптимальній політиці обох гравців).
Приклад 2. Нехай гра визначається матрицею
Тут рівність V1=V2 не виконується; оптимальної чистої стратегії для гравців немає.
При аналізі ігор часто вдаються до спроб виявити домінування між рядками і стовпцями. Так у прикладі 1 елементи четвертого рядка більше елементів інших рядків: використання вибору 4 вигідніше інших виборів при будь-якій політиці супротивника. Противник бачить, що в такій ситуації використати вибори 3 і 4 нерозумно.
Використання домінування т.о. дозволяє зменшити розміри досліджуваної матриці винятком невигідних рядків і стовпців.
При відсутності седловой точки серед чистих стратегій доводиться шукати таку серед змішаних.
Якщо гравець 1 прибігає до свого вибору i з імовірністю Pi, а гравець 2 - до свого j-му вибору з імовірністю Qj, то о...