Розробка програмного забезпечення розв’язання парних матричних ігор зі змішаними стратегіями

Міністерство освіти і  науки, молоді та спорту України

Вінницький національний технічний університет

Інститут автоматики і  електроніки та комп'ютерних систем управління

 

Кафедра КСУ

 

 

 

Розрахунково-графічна робота

з дисципліни

«Спеціальні розділи математики»

на тему:

«Розробка програмного забезпечення розв’язання парних матричних ігор зі змішаними стратегіями»

 

 

 

 

 

 

Перевірив:

к.т.н., доц., Ковтун В.В.

Виконав:

ст. гр. 3СІ-10, Шевчук Я. Ю.

 

 

 

 

 

 

Вінниця ВНТУ 2012

ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

на розрахунково-графічну роботу з дисципліни

«Спеціальні розділи математики»

студента групи 3СІ-10

Шевчука Ярослава Юрійовича

Тема:  Розробка програмного забезпечення розв’язання парних матричних ігор зі змішаними стратегіями

 Розробити програмний  комплекс для розв’язання парних матричних ігор зі змішаною стратегією який повинен виконувати наступні функції:

• вводити початкові данні;
• розв’язувати поставлену задачу;
• виводити розв’язок.

Вхідні данні :

• кількість стратегій гравців;
• матриця виграшів(програшів у певній ситуації).

Вихідні данні:

• оптимальний розв’язок.

Вихідні і вхідні дані відповідають умовам індивідуального завдання.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

АНОТАЦІЯ

Дана розрахунково-графічна робота призначена для розробки програмного забезпечення для розв’язання парних матричних ігор зі змішаними стратегіями.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ANNOTATION

This settlement and graphic work designed to develop software solutions paired matrix games with mixed strategies.

The work conducted survey of modern software development methods and analysis methods for solving matrix games paired with a mixed strategy, the structure of software and algorithm to solve this problem, which includes the development of the algorithm the main program, the algorithms of system functions, algorithms routines. The program is designed using a modular and object-oriented programming techniques, these methods are also discussed in the paper.

The developed programs tested. Test results confirm that the program performs all the necessary functions and is ready for use.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Зміст

ВСТУП 6

1 УСТОЧНЕНА ПОСТАНОВКА  ЗАДАЧІ 8

2 ПРОЕКТУВАННЯ ПРОГРАМНОГО  ЗАБЕЗПЕЧЕННЯ ЗА ДОПОМОГОЮ ЗАСОБІВ  UML 10

3 РОЗВ’ЯЗОК ОДНОТИПНИХ  ЗАВДАННЬ 12

4 ТЕСТУВАННЯ РОЗРОБЛЕНОГО  ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ 14

ВИСНОВОК 15

СПИСОК ЛІТЕРАТУРИ 16

ДОДАТОК А 17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВСТУП

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

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

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

Характерною особливістю  ігрової ситуації є взаємодія  протилежних (не завжди) інтересів двох чи більше «розумних» суперників, кожний з яких намагається оптимізувати свої рішення. Існує багато різних ігор, серед яких найпоширеніші стратегічні. У таких іграх джерелом невизначеності є відсутність інформації про його стратегію. Кожна протидіюча сторона (гравці) мають можливість вибору одного (або кількох) варіантів дій — стратегій. Стратегією гравця називають план, за яким він здійснює вибір у будь-якій можливій ситуації, і володіючи будь-якою фактично можливою інформацією.

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 УСТОЧНЕНА ПОСТАНОВКА ЗАДАЧІ

Маємо два гравці А і В (гра двох осіб з нульовою сумою). Кожний гравець обирає одну з можливих стратегій: гравець А — стратегії , гравець В — стратегії .

Результати (плата) за всіма  можливими варіантами гри задаються, як правило, спеціальними функціями (що залежать від стратегій гравців) у вигляді платіжної матриці.

Нехай (А_і; В_j) — виграш гравця А,

;

 — виграш гравця В,

.

Оскільки гра з нульовою сумою, то .

Тоді в разі маємо .

Отже, мета гравця А максимізувати  , а гравця В — її мінімізувати. Нехай , тобто маємо матрицю

,

рядки якої відповідають стратегіям А_і, а стовпці — стратегіям В_j.

Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці a_ij — виграш гравця А, якщо він вибрав стратегію A_i, а гравець В — стратегію B_j.

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

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

.

Таку стратегію гравця А називають максимінною, а розмір його гарантованого виграшу — нижньою ціною гри.

Стратегія, яка забезпечує цей виграш, називається максимінною і позначається .

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

.

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

,

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

Імовірності (або частоти) вибору кожної стратегії задаються  відповідними векторами.

Для гравця А: ,

де  ;

Для гравця В: ,

де  .

Очевидно, що , ; , .

2 ПРОЕКТУВАННЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ ЗА ДОПОМОГОЮ ЗАСОБІВ UML

 

 

Рисунок 2.1 – USE CASE- діаграма варіанті використання

 

Рисунок 2.2 – UML- діаграма класів

 

 

 

 

Рисунок 2.3 – UML- діаграма діяльності

 

 

Рисунок 2.4 – UML- діаграма станів

 

 

 

3 РОЗВ’ЯЗОК ОДНОТИПНИХ ЗАВДАННЬ

Приклад 1:

Агрофірма «Зоря» розробила три бізнес-плани (А₁, А₂, А₃) для реалізації в наступному році. Залежно від зовнішніх умов (погодних умов, стану ринку тощо) виокремлено дві ситуацій (В₁, В₂). Для кожного варіанту А_і бізнес-плану та зовнішньої ситуації обчислено прибутки, наведені в такій таблиці:

	B1	B2
A1	2	5
A2	7	1
A3	3	7

 

  матрична гра не має сідлової точки, то знаходження її розв’язку —розв’язання методами лінійного програмування

за умов

  .

Розв’язуємо цю задачу симплексним  методом

Z=t₁+t₂+t₃+0∙t₄+0∙t₅+M∙t₆+M∙t₇→min

1 ітерація

Баз.	Сб.	План	t1	t2	t3↓	t4	t5	t6	t7	Ѳ
			1	1	1	0	0	M	M
t6	M	1	2	7	3	-1	0	1	0	1/3
→t7	M	1	5	1	7	0	-1	0	1	1/7
Min		2M	7M-1	8M-1	10M-1	-M	-M	0	0

 

 

2 ітерація

Баз.	Сб.	План	t1	t2↓	t3	t4	t5	t6	t7	Ѳ
			1	1	1	0	0	M	M
→t6	M	4/7	-1/7	46/7	0	-1	3/7	1	-3/7	2/23
t3	1	1/7	5/7	7	1	0	-1/7	0	1/7	1
Min		4+1/7	-M/7 -2/7	46M/7 -6/7	0	-M	3M/7 -1/7	0	-3M/7+1/7