Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

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

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

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

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

групи РПЗ 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 Матриця гри

Стратегии игрока А	Стратегии игрока В
Стратегии игрока А	B₁	B₂	….	B_n
А₁			...	а_1n
А₂	a₂₁	а₂₂	...	а_2n
… …	… …	… …	... ...	… …
А_m	а_m1	а_m2	...	а_mn

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

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

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

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

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

. (1)

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

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

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

Стратегії гравця А	Стратегії гравця В
		B₁		B₂		…		B_n
А₁	а₁₁		а₁₂		...		а_1n
А₂	a₂₁		а₂₂		...		а_2n
… …	… …		… …		... ...		… …		… …
А_m	а_m1		а_m2		...		а_mn
					...

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

(2)

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

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

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

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

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

₍₃₎

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

₍₄₎

або

₍₅₎

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

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

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

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

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

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

Розглянемо приклад. Нехай гра 4X4 задана матрицею:

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

Стратегії гравця А	Стратегії гравця В
Стратегії гравця А	B₁	B₂	B₃	B₄
А₁	0,4	0,5	0,9	0,3	0,3
А₂	0,8	0,4	0,3	0,7	0,3
А₃	0,7	0,6	0,8	0,9	0,6
А₄	0,7	0,2	0,4	0,6	_0,2
	0,8	0,6	0,8	0,9

Знайдемо нижню ціну гри: a = 0,6.

Знайдемо верхню ціну гри: b = 0,6.

Вони виявилися однаковими, отже, у гри є чиста ціна: a = b = n = 0,6.

Елемент 0,6 є одночасно мінімальним в своєму рядку і максимальним в своєму стовпці. У геометрії точку на поверхні, володіючи аналогічною властивістю (одночасний мінімум по одній координаті і максимум по іншій), називають сідловою точкою; аналогічно цей термін застосовується і в теорії ігор. Елемент матриці, володіючий цією властивістю, називається сідловою точкою матриці, а про гру говорять, що вона має сідлову точку.

Сідловій точці відповідає пара мінімаксних стратегій (у даному прикладі А₃ і В₂). Ці стратегії називаються оптимальними, а їх сукупність — рішенням гри.

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

1. Якщо обидві сторони дотримуються своїх оптимальних стратегій, то середній виграш рівний чистій ціні гри n.

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

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

2 ПРОЕКТНИЙ РОЗДІЛ

2.1 Специфікація вимог до програмного забезпечення

Пояснювальну записку слід реалізувати у двох варіантах: як окрему програму, створену за допомогою середовища Delphi, та у якості алгоритмів, розроблених в середовищі Excel. Математична метода, за якою створене окреме програмне забезпечення викладено у цьому розділі.

Середовище Excel має власні вбудовані можливості для рішення задач цього класу.

В рішенні постановленої задачі всі вхідні данні повинен внести користувач (аналітик), він же повинен вибрати метод рішення задачі, вибрати стратегію та зробити розрахунки. Всі дії ми можемо побачити в UML діаграмі прецедентів, яка зображена в додатку А – діаграма прецедентів.

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

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

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

В чинному завданні аналітик (користувач) на пряму пов’язан з трьома варіантами використання: введення даних, вибір метода рішення, виведення та аналіз результатів. Вибір метода рішення полягає з вибору з двох варіантів використання: визначення стратегії А та визначення стратегії Б. Виведення та аналіз результатів в свою чергу пов’язан з кількома варіантами використання: визначення верхньої ціни, визначення нижньої ціни, визначення максимуму строк, визначення мінімуму стовбців, обчислення сідлової точки.

2.2 Опис моделі програмного забезпечення.

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

В завданні потрібно вибрати варіант розміщення електростанції за допомогою програми, та за допомогою Excel.

Розглянемо варіант з використанням програми.

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

Архітектурно програма представляється декількома діаграмами: класів, активності, компонентів, варіантів використання.

Діаграма активності (станів). Поняття станів є фундаментальним не тільки в метамоделі UML, але і в прикладному системному аналізі. Вся концепція динамічної система ґрунтується на понятті стані системи. Під станом розуміється абстрактний клас, використовуваний для моделювання окремої ситуації, протягом якої має місце виконання деякого умови. Стан може бути задано у вигляді набору конкретних значень атрибутів класу або об'єкта, при цьому зміна їх окремих значень буде відображати зміну стану модельованого класу або об'єкта.

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

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

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

Представлений алгоритм реалізує циклічний обчислювальний процес з відомим числом повторень за параметром i та параметру k (і включає в себе наступні блоки:

1) Початок алгоритму.

2) Введення вихідних даних.

3) Цикл

4) Прорахунок ходів (вибір стратегій)

5) Умова перевірки рівності значень, якщо значення рівні, то дія переходить до іншого стану, якщо ні - йде на введення даних.

6) Розрахунок чистої ціни

7) Умова перевірки рівності значень після прорахунку, якщо значення рівні, то дія переходить до іншого стану, якщо ні - йде на введення даних.

8) Знаходження сідлової точки

9) Перевірка наявності сідлової точки, якщо сідлова точка є, то дія переходить до іншого стану, якщо ні - йде на введення даних.

10) Знаходження мінімаксних значень

11) Висновок результату

12) Кінець алгоритму.

Діаграма класів зображена в додатку А – UML діаграма класів.

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

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

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

Діаграма компонентів зображена в додатку А – UML діаграма компонентів.

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

Компонент "MainMenu" є виконуваним файлом програми, від якого походять два інших компонента: Lograng та Shtraf, від яких в свою чергу походять компоненти розрахунків.

Всі класи унаслідуються від двох абстрактних класів Form та Application. Основні класи призначені для створення форм та проведення розрахунків. Класи Form 1 та Form 2 завлекають додаткові процедури обробки для розрахунків методом Лагранжа та методом штрафних функцій – класи Shtraf та Lagrang. Клас Form 1 пов’язан з інтерфейсом MainMenu для введення початкових даних.

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

Для представлення фізичних сутностей в UML застосовується спеціальний термін - компонент (component). Компонент реалізує деякий набір інтерфейсів і служить для загального позначення елементів фізичного представлення моделі. Для графічного представлення компонента може використовуватися спеціальний символ - прямокутник зі вставленими зліва двома більш дрібними прямокутниками.

2.3 Опис вихідного коду

У даному пункті будуть описані всі формули та їх смислові значення, зв'язки між осередками Excel.

Підготуємо таблицю з готовими вхідними даними. Зразок з цими даними у вигляді скріншоту зображено додатку Б.

Ігрові методи прийняття рішень 📙 Курсовая → 🆔 99809