й метод вирішення ігр
Позначення:
; (1.71)
- будь-яка квадратна подматріца матриці порядку [3]
- матриця (1);
- матриця, транспонована до;
- матриця, приєднана до В;
- (1) матриця отримана з X викреслюванням елементів, які відповідають рядкам, викресленим з при отриманні;
- (1) матриця отримана з викреслюванням елементів, які відповідають рядкам, викресленим з при отриманні.
Алгоритм:
1. Виберемо квадратну підматрицю матриці порядку () і обчислимо
, (1.72)
. (1.73)
2. Якщо деякий або, то відкидаємо знайдену матрицю і пробуємо іншу матрицю.
3. Якщо (), (), обчислюємо і будуємо X і з і, додаючи у відповідних місцях нулі.
(1.74)
Перевіряємо, задовольняються чи нерівності
для кожного (1.75)
і нерівності
для кожного (1.76)
Якщо одне з співвідношень не виконана, то пробуємо інше. Якщо все співвідношення справедливі, то X, і шукані рішення. [3]
. 8 Метод послідовного наближення ціни гри
При дослідженні ігрових ситуацій часто може трапитися так, що немає необхідності в отриманні точного рішення гри або в слідстві яких-небудь причин знайти точне значення ціни гри та оптимальних змішаних стратегій неможливо або дуже важко. Тоді можна скористатися наближеним методами вирішення матричної гри. [2]
Наведемо одне із таких методів - метод послідовного наближення ціни гри. Кількість обчислених при використанні методу збільшується приблизно пропорційно числу рядків і стовпців матриці виграшів.
Суть методу полягає в наступному: мислення гра проводиться багато разів, тобто послідовно, в кожній партії гри гравець вибирає ту стратегію, яка дає йому найбільший спільний (сумарний) виграш.
Після такої реалізації деяких партій обчислює середні значення виграшу першого гравця, програшу другого гравця, і їх середнє арифметичне приймається за наближене значення ціни гри. Метод дає можливість знайти наближене значення оптимальних змішаних стратегій обох гравців: треба підрахувати частоту застосування кожної чистої стратегії і прийняти її за наближене значення в оптимальній змішаної стратегії відповідного гравця.
Можна довести, що з необмеженим збільшенням числа програмних партій середній виграш першого гравця і середній програш другого гравця буде необмежено наближатися до ціни гри, а наближені значення змішаних стратегій в тому випадку, коли рішення гри єдине, буде прагнути до оптимальних змішаним стратегіям кожного гравця. Взагалі кажучи, прагнення наближених значень вище зазначених величин до істинним значенням відбувається повільно. Однак цей процес легко механізувати і тим самим допомогти отриманню рішення гри з необхідної ступенем точності навіть при матрицях виграшів порівняно великого порядку. [2]
. Практична частина
2.1 Игра 2 2
Пара вирішує куди піти погуляти і з користю для двох провести час.
Дівчина вирішує піти погуляти в парк подихати свіжим повітрям, ввечері сходити на перегляд кінофільму в найближчий кінотеатр.
Хлопець пропонує піти сходити в технопарк, після подивитися матч футболістів місцевого клубу в центральному стадіоні.
Відповідно до цього потрібно знайти за який час буде досягнута мета одного з гравців. Матриця виграшів буде виглядати таким чином:
Таблиця 1. Матриця виграшів
СтратегііІгрок 1 Гравець 2 73 45
Рішення:
1=max {3,4}=4
2=min {7,5}=5
Так як 1, 2, Очевидно, в цій грі немає седловой точки в чистих стратегіях. Тому скористаємося наступними формулами, і отримаємо:
V 4.5
Відповідь:,,,
2.2 Гра 2xn і mx2
Завдання 1 (2xn)
Вирощується два зернові культури для сухого і вологого клімату.
А стан природи можна розглядати як: сухе, вологе, помірне.
Рішення:
