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

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

 

 

 

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

Стратегії гравця А	Стратегії гравця В
	B1	B2	B3	B4
А1	0,4	0,5	0,9	0,3	0,3
А2	0,8	0,4	0,3	0,7	0,3
А3	0,7	0,6	0,8	0,9	0,6
А4	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.

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