Ігрові методи прийняття рішень

МІНІСТЕРСТВО  ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

МАРІУПОЛЬСЬКИЙ МАШИНОБУДІВНИЙ КОЛЕДЖ

ДЕРЖАВНОГО ВИЩОГО НАВЧАЛЬНОГО ЗАКЛАДУ

«ПРИАЗОВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ»

 

 

 

 

 

 

 

 

 

КУРСОВИЙ ПРОЕКТ

 

 

з дисципліни: «Основи програмної інженерії»

на тему: «Ігрові методи прийняття рішень»

 

 

 

 

 

 

 

Виконала студентка 

групи РПЗ 10-01

Морой І. В    

 

Керівник

Михайлов Г. А   

Оцінка

 

 

 

 

 

 

 

 

 

м. Маріуполь

2013р.

РЕФЕРАТ

 

Сторінок -  Малюнків - 5 Таблиць – 3   Формул - 16

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

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

1. Математичні  методи розв'язання задач виробничого  планування: метод штрафних функцій,  метод множників Лагранжа.

2. Проектний  розділ.

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

Додатки

Додатки містять  лістинг програми, скріншоти екрану, готові діаграми UML.

 

ЗМІСТ

Вступ	5
1 Математичні методи рішення задач виробничого планування
2 Проектний розділ
2.1 Специфікація вимог
2.2 Опис моделі програмного забезпечення
2.3 Опис вихідного коду
3 Супровідна  документація
3.1 Тестування та відладка програмного забезпечення
3.2 Керівництво користувача
Висновки
Перелік використаної літератури
Діаграми UML
Екранні форми
Блок –  схема програми
Вихідний код
Опис компакт- диску

 

 

ВСТУП

 

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

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

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

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

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

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

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

 

1 МАТЕМАТИЧНІ МЕТОДИ РІШЕННЯ ЗАДАЧ ВИРОБНИЧОГО ПЛАН

УВАННЯ

 

Прийняття оптимального рішення у виробничих ситуаціях засновується на математичних методах, які відносяться до класу ігрових задач. Найчастіше використовуються методики «гри з нулевою сумою»

Розглядатимемо  парну гру, в якій беруть участь два  гравці А і В з протилежними інтересами. Під «грою» розумітимемо захід, що складається з ряду дій сторін А і В. Під «правилами гри» розуміється система умов, що регламентує можливі варіанти дій обох сторін, послідовність чергування «ходів», а також результат гри, до якого приводить дана сукупність ходів. Цей результат (виграш або програш) не завжди має кількісний вираз, але звичайно можна, встановивши деяку шкалу вимірювання, виразити його певним числом.

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

Оскільки в  грі з нульовою сумою виграш одного з гравців рівний виграшу іншого з протилежним знаком, тоді, при аналізі такої гри можна розглядати виграш тільки одного з гравців. Нехай це буде, наприклад, гравець А. Надалі для зручності сторону А умовно іменуватимемо «ми», а сторону В — «супротивник».

При цьому сторона А («ми») завжди розглядатиметься як «виграюча», а сторона В («супротивник») та, що «програє».

Розвиток гри  в часі ми представлятимемо тим, що складається з ряду послідовних етапів або «ходів». Ходом в теорії ігор називається вибір одного з передбачених правилами гри варіантів. Ходи діляться на особисті і випадкові.

Особистим ходом називається свідомий вибір одним з гравців одного з можливих в даній ситуації ходів і його здійснення.

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

Одним з основних понять теорії ігор є поняття «стратегії».

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

Залежно від  числа можливих стратегій ігри діляться на «кінцеві» і «нескінченні». Кінцевою називається гра, в якій у кожного гравця є тільки кінцеве число стратегій.

Кінцева гра, в  якій гравець А має m стратегій, а гравець В — n стратегій, називається грою m ´ n. Позначатимемо наші стратегії A1, А2,…. Аm; стратегії супротивника В1, В2,…. Вn.

Також позначатимемо  одним і тим же знаком аij як сам  виграш (у грі без випадкових ходів), так і його середнє значення (у  грі з випадковими ходами).

Нехай нам відомі значення аij виграшу (або середнього виграшу) при кожній парі стратегій. Значення аij можна записати у вигляді  прямокутної таблиці (матриці), рядки  якої відповідають нашим стратегіям (Аi), а стовпці — стратегіям супротивника (Bj). Така таблиця називається платіжною матрицею або просто матрицею гри. Матриця гри m ´n має вигляд:

 

Таблиця 1   Матриця гри

Стратегии игрока А	Стратегии игрока В
	B1	B2	….	Bn
А1			...	а1n
А2	a21	а22	...	а2n
… …	… …	… …	... ...	… …
Аm	аm1	аm2	...	аmn

 

Скорочено ми позначатимемо  матрицю гри  .

Розглянемо  гру m ´ n з вищеописаною матрицею.

Позначатимемо буквою i номер нашої стратегій; буквою j — номер стратегії супротивника.

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

Визначимо це значення виграшу, т. е. мінімальне з чисел a_ij в i-й рядку. Позначимо його :

.       (1)

 

Тут знаком (мінімум по j) позначено мінімальне із значень даного параметра при всіх можливих j.

Випишемо числа поряд з матрицею справа у вигляді додаткового стовпця:

 

Таблиця 2   Співвідношення стратегій

Стратегії гравця А	Стратегії гравця В
		B1		B2		…		Bn
А1	а11		а12		...		а1n
А2	a21		а22		...		а2n
… …	… …		… …		... ...		… …		… …
Аm	аm1		аm2		...		аmn
					...

 

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

      (2)

 

Величина a називається нижньою ціною гри; інакше — максимінним виграшем або просте максиміном.

Число a лежить в певній строчці матриці; та стратегія гравця А, яка відповідає цій строчці, називається максимінної стратегією.

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

Тому величина a і називається «нижньою ціною гри». Це — той гарантований мінімум, який ми можемо собі забезпечити, дотримуючись найобережнішої стратегії. Аналогічне міркування можна провести і за супротивника В.

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

 

      ₍₃₎

 

та знайдемо мінімальне з  :

      ₍₄₎

 

або

     ₍₅₎

 

Величина b називається верхньою ціною гри, інакше — «мінімаксом». Відповідна мінімаксному виграшу стратегія супротивника називається його «мінімаксною стратегією».

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

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

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

Проте існують деякі ігри, для яких мінімаксні стратегії є стійкими. Це ті ігри, для яких нижня ціна рівна верхньою: a = b.

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