Теорія ігор 2

Федеральне державне освітній заклад середньої професійної освіти

«Омський промислово-економічний коледж»

Курсова робота

з дисципліни «Математичні методи»

Тема: «Теорія ігор"

Виконав:

Карімов Руслан Рінатовіч

3 курс, БП 2 - 117

Керівник:

Белгородцева Наталія Олександрівна

Оцінка :________________

Дата захисту :___________

2010

Зміст

Введення

Огляд літератури

1. Основні поняття теорії ігор

2. Ігри з протидією і нульовою сумою

3. Графічний метод рішення ігрових завдань з нульовою сумою

3.1 Рішення задач графічним методом

4. Зведення задач теорії ігор до задач лінійного програмування

4.1 Рішення задач

5. Ігри з природою (без протидії)

5.1 Рішення задач

Висновок

Список використаної літератури

Введення

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

Огляд літератури

Для написання курсової роботи з дисципліни «Математичні методи» на тему «Теорія ігор» я скористався такою літературою:

- «Математичні методи в програмуванні»: / Агальцов В.П., Волдайская І.В. Підручник: - М. : ВД «ФОРУМ»: ИНФРА-М, 2006. - 224с. : Іл. - (Професійна освіта). - (Вчимося програмувати).

-Лекції з дисципліни «Математичні методи».

- «Математичні методи: Підручник» / Партика Т.Л., Попов І.І. - М: ФОРУМ: ИНФРА, 2005.

- «Математичне програмування» / Костевич Л., видавництво «Нове знання», 2003.

В одній з книг наприклад «Математичні методи в програмуванні»: / Агальцов В.П., Волдайская І.В. Підручник: - М. : ВД «ФОРУМ»: ИНФРА-М, 2006 написано зрозуміліше, якщо порівнювати з іншими книгами, якими я користувався. Але в цій книзі є теми, які відсутні або пояснені без теорії, а на конкретному прикладі і тоді складніше зрозуміти, про що йде мова даній темі. Тоді я звертаюся до інших джерел літератури в них, звичайно, є теорія, але вона складніша і більш поглиблена. В одному з джерел мені сподобалася тема «Ігри з природою (без протидії)» і я вирішив вивчити її самостійно.

1. Основні поняття теорії ігор

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

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

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

Конфліктна ж ситуація, строго кажучи, розвивається спонтанно.

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

Можливі варіанти (випадки) ігри зводяться в прямокутну таблицю (табл. 1.1) - платіжну матрицю, в якій рядки відповідають різним стратегіям гравця А, стовпці - стратегіям гравця В, ai j називається виграш першого гравця.

Таблиця 1.1

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

Стратегія, що приносить гравцеві максимальний виграш, називається оптимальною. Для знаходження оптимальної стратегії необхідно проаналізувати всі можливі стратегії і розраховувати на те, що розумний противник на кожну з них буде відповідати такий, при якій виграш гравця А мінімальний. Зазвичай мінімальні числа в кожному рядку позначаються α i і виписуються у вигляді додаткового стовпця матриці (табл. 1.2). У кожному рядку буде своє α i = min aij. Бажаною для гравця А є стратегія, при якій α i звертається в максимум, тобто

α = max (min aij),

де α - гарантований виграш (максимин).

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

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

β = min (max aij),

яке дає мінімаксний виграш, або минимакс.

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

Якщо α = β = С, то число С називають чистою ціною гри або сідловою.

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

Таблиця 2

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

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

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

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

2. Ігри з протидією і нульовою сумою

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

Нехай фірма А розробила чотири стратегії, а фірма В - п'ять стратегій.

Тобто фірма А - А1; А2; А3; А4 А i, де i = 1,4.

Фірма В відповідно - В1; В2; В3; В4; В5 У j, де j = 1,5.

Кожна фірма від реалізації своєї стратегії передбачає отримати якийсь дохід (табл. 2.1).

Таблиця 2.1

Якщо фірма А вибере першу стратегію, то мінімальний дохід складе 4. Мінімальний дохід від другої стратегії - 1; від третьої - 2; від четвертої - 3. У фірми У є в наявності п'ять стратегій. Використання першої стратегії обернеться збитками в 1 одиницю; другий (збиток) - 4; третій - 3, четвертої - 4 і п'ятою - 2.

На перший погляд фірма А повинна обрати другу стратегію (А2), щоб отримати виграш 10, але у відповідь друга фірма обере першу стратегію (В1) і виграш фірми А складе лише 1.

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

Таблиця 2.2

Виходячи з даних (табл. 2.2) фірмі А треба дотримуватися стратегії А1, а фірмі В - стратегії В1. Таким чином, гарантований мінімальний дохід фірми А складе 4, а мінімально можливий збиток, який понесе фірма В, складе 5 (мінімально можливий програш).

Мінімальний гарантований виграш називається нижньою ціною гри. При поганій грі фірми У виграш може бути і більшим.

Мінімально можливий програш називається верхньою ціною гри.

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

Таким чином, наведені обережні стратегії є нестійкими по відношенню до додаткової інформації.

На практиці іноді трапляється, що нижня ціна гри дорівнює верхній ціною гри. У цьому випадку говорять про стійкі стратегіях гравців (конкуруючих фірм) або про завдання з сідловою. Завдання з сідловою представлена ​​в (табл. 2.3).

Таблиця 2.3

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

Якщо ігрова задача не має сідлової точки, то на практиці конкуруючі фірми (гравці) використовують змішані стратегії, тобто поперемінно використовують дві або більше стратегій. У цьому випадку використання фірмою А декількох стратегій можна записати як суму ймовірностей використання кожної стратегії Sa = p 1 + p 2 + ... + pm.

Відповідно, використання декількох стратегій фірмою В можна записати Sb = q 1 + q 2 + ... + qn. Тому в загальному випадку дослідження ігрової моделі зводиться до визначення ймовірностей використання конкретних стратегій кожною фірмою (гравцем).

3. Графічний метод рішення ігрових завдань з нульовою сумою

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

Скористаємося табл. 2.1.

Рядок (стратегія) А1 є домінуючою по відношенню до рядка (стратегії) А4, тому що містить елементи, великі відповідних елементів рядка А4. Відповідно рядок А4 є поглинається і з подальшого розгляду віддаляється (табл. 3.1).

Таблиця 3.1

Перший крок спрощення таблиці

Перший стовпець є домінуючим по відношенню до другого, третього і четвертого стовпцях (поглинається). Вступаємо аналогічно (табл. 3.2).

Таблиця 3.2

Другий крок спрощення таблиці

Ще раз розглядаємо рядка. Перший рядок поглинає третій рядок. Поглинаються рядки (стовпці) містять найгірші стратегії. Остаточно отримаємо (табл. 3.3).

Таблиця 3.3

Третій крок спрощення таблиці

Імовірність використання першою фірмою першої стратегії позначимо через p 1. Тоді ймовірність використання другої стратегії першим гравцем буде p 2 = 1 - p 1. Очікуваний виграш фірми А від застосування

(3.1)

другим гравцем першої стратегії складе:

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

(3.2)

У вираження (3.1) і (3.2) підставимо конкретні значення.

На осі х відкладемо дві точки 0 і 1. Через ці точки проведемо прямі лінії, паралельні осі у. Потім у перший вираз підставимо 0 замість p 1, а потім - одиницю. І по двох точках побудуємо пряму лінію.

Аналогічно побудуємо другу пряму лінію. Перетин двох прямих ліній і дасть вирішення завдання (рис. 3.1).

Рис. 3.1. Графічний спосіб визначення стратегій фірми А

4p1 + 1 = - 2p1 + 6

4p1 + 2p1 = - 1 + 6

6p1 = 5

p1 = 0,83

Отже, ймовірність використання першої стратегії фірмою А становить 0,83 (p ₁ = 0,83), а другий стратегії p ₂ = 1 - 0,83 - відповідно 0,17 (p ₂ = 0,17).

Аналогічно визначимо оптимальну стратегію поведінки фірми В:

Нехай у1 - ймовірність вибору другої грою 5 стратегією, у2 - 6 стратегією. (P 4 + p 5 = 1, p 5 = 1 - p 4)

(A 11 - a 12) · у1 + a 12 = (5 - 4) у1 + 4 = у1 + 4;

(A 21 - a 22) · у1 + a 22 = (1 - 6) у1 + 6 = -5 у1 + 6.

Рис. 3.2. Графічний спосіб визначення стратегій фірми

у ₁ + 4 = -5 у ₁ + 6

6 у ₁ = 2

у ₁ = 0,33

Імовірність використання першої стратегії фірмою В становить 0,33 (у ₁ = 0,33), а другий стратегії у ₂ = 1 - 0,33 - відповідно 0,67 (у ₂ = 0,67).

3.1 Рішення задач графічним методом

Приклад 1: Розглянемо гру заданої платіжною матрицею:

Рішення:

Перевіримо чи є сідлова точка:

α = max (2,2,3,2) = 3

β = min (7,6,6,4,5) = 4 α ≠ β

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

Нехай p ₁ - ймовірність з якої перший гравець повинен застосовувати 1 стратегію, p ₃ - ймовірність застосування 3 стратегією, p ₃ = 1 - p ₁ .

Очікуваний виграш 1 гравця, якщо другий вибрав 4 стратегію:

p 1 · 4 + (1 - p 1) · 3 = p 1 + 3;

Очікуваний виграш 1 гравця, якщо другий обрав 5 стратегію:

p 1 · 2 + (1 - p 1) · 5 = -3 p 1 + 5;

p ₁ + 3 = -3 p ₁ + 5

4 p ₁ = 2

p ₁ = ₁ / 2, p ₃ = 1 / 2.

Першому гравцеві для отримання гарантованого виграшу 3,5 (1 / 2 +3) рекомендується чергувати стратегії 1 і 3.

Розглянемо другого гравця.

Нехай p 4 - ймовірність вибору другим гравцем 4 стратегією, p 5 - 5 стратегією. (P 4 + p 5 = 1, p 5 = 1 - p 4)

Очікувані програш другого гравця, якщо перший вибере 1 стратегію.

p 4 · 4 + (1 - p 4) · 2 = 2 p 4 + 2

Очікувані програш другого гравця, якщо перший обере 3 стратегію.

p 4 · 3 + (1 - p 4) · 5 = -2 p 4 + 5

2 p ₄ + 2 = -2 p ₄ +5

4 p ₄ = 3

p ₄ = 3 / 4

p ₅ = 1 / 4

ν = 3 / 4 · 2 + 2 = 3,5

Відповідь: З 4 ігор 3 треба зіграти 4 стратегією, 1 гру - 5 стратегією, і тоді програш буде не більше 3,5, для першого гравця 1 треба зіграти 2 стратегією і 1 - другою стратегією.

Приклад 2: Вирішити гру, задану матрицею

Рішення:

Перевіримо чи є сідлова точка:

α = max (2,4) = 4

β = min (6,5) = 5 α ≠ β

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

Очікуваний виграш 1 гравця якщо другий вибрав 1 стратегію:

А1 · 2 + (1 - А1) · 6 =-4А1 + 6;

Очікуваний виграш 1 гравця якщо другий вибрав 2 стратегію:

А1 · 5 + (1 - p 1) · 4 = А1 + 4;

- 4 А ₁ + 6 = А ₁ + 4

- 4 А ₁ + А ₁ = 4 - 6

- 5 А ₁ = - 2

А ₁ = 2 / 5, А ₂ = 3 / 5.

Першому гравцеві для отримання гарантованого виграшу 4 ,

(2 / 5 +4) рекомендується грати 1 стратегією.

Розглянемо другого гравця.

Нехай В1 - ймовірність вибору другої грою 4 стратегією,

(В1 + В2 = 1, В2 = 1 - В1)

Очікуваний програш другого гравця, якщо перший вибере 1 стратегію.

В1 · 2 + (1 - В1) · 5 = - 3 В1 + 5

Очікуваний програш другого гравця, якщо перший вибере 2 стратегію.

В1 · 6 + (1 - В1) · 4 = 2 В1 + 4

- 3 В ₁ + 5 = 2 В ₁ + 4

- 3 В ₁ - 2 В ₁ = 4 - 5

- 5 В ₁ = - 1

У ₁ = 1 / 5, В ₂ = 4 / 5.

ν = 1 / 5 · 2 + 4 = 4

Відповідь: З 2 ігор 2 треба зіграти 1 стратегією, 1 гру - 2 стратегією, і тоді програш буде не більше 4 .

Приклад 3: Вирішити гру, задану матрицею

Перевіримо чи є сідлова точка:

α = max (7,6) = 7

β = min (10,9,9) = 9 α ≠ β

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

Очікуваний виграш 1 гравця, якщо другий вибрав 1 стратегію:

p ₁ · 7 + (1 - p ₁₎ · 10 = -3 p ₁ + 10;

Очікуваний виграш 1 гравця, якщо другий вибрав 2 стратегію:

p 1 · 9 + (1 - p 1) · 6 = 3 p 1 + 6;

- 3 p ₁ + 10 = 3 p ₁ + 6

- 3 p ₁ - 3 p ₁ = -10 + 6

- 6 p ₁ = -4

p ₁ = 2 / 3, p ₂ = 1 / 3.

Першому гравцеві для отримання гарантованого виграшу 7 , (2 / 3 +7) рекомендується грати 1 стратегією.

Розглянемо другого гравця.

Очікувані програш другого гравця якщо перший вибере 1 стратегію.

p 4 · 7 + (1 - p 4) · 9 = -2 p 4 + 9

Очікувані програш другого гравця якщо перший вибере 2 стратегію.

p 4 · 10 + (1 - p 4) · 6 = 4 p 4 + 6

- 2 p ₄ + 9 = 4 p ₄ + 6

- 2 p ₄ - ₄ p ₄ = 6 - 9

- 6 p ₄ = -3

р ₄ = 1 / 2, p ₅ = 1 / 2.

Відповідь: З 2 ігор (для першого) 2 треба зіграти 3 стратегією і 1 - 3 стратегією, (для другого) 1 треба зіграти 2 стратегією і 1 - 2 стратегією.

Приклад 4: Вирішити гру, задану матрицею

Перевіримо чи є сідлова точка:

α = max (5,4,2,1) = 5

β = min (6,8) = 6 α ≠ β

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

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

Очікуваний виграш 1 гравця, якщо другий вибрав 1 стратегію:

p ₁ · 6 + (1 - p ₁₎ · 1 = 5 p ₁ + _1;

Очікуваний виграш 1 гравця, якщо другий вибрав 2 стратегію:

p ₁ · 5 + (1 - p ₁₎ · 8 = -3 p ₁ + 8;

5 p ₁ + ₁ = -3 p ₁ + 8

5 p ₁ + 3 p ₁ = 8 - 1

8 p ₁ = 7

p ₁ = 7 / 8, p ₂ = 1 / 8.

Розглянемо другого гравця.

Очікувані програш другого гравця, якщо перший вибере 1 стратегію. P 4 · 6 + (1 - p 4) · 5 = p 4 + 5

Очікувані програш другого гравця, якщо перший вибере 2 стратегію.

p4 · 1 + (1 - p4) · 8 = -7 p4 + 8

p ₄ + 5 = -7 p ₄ + 8

p ₄ + 7 p ₄ = 8 - 5

8 p ₄ = 3

р ₄ = 3 / 8, p ₅ = 5 / 8.

u = .

Відповідь: З 4 ігор (для першого) 7 треба зіграти 8 стратегією і 1 - 8, (для другого) 3 треба зіграти 8 стратегією та 5 - 8.

4. Зведення задач теорії ігор до задач лінійного

програмування

Припустимо, що ціна гри позитивна (u> 0). Якщо це не так, то відповідно до властивості 6 завжди можна підібрати таке число с, додаток якого до всіх елементів матриці виграшів дає матрицю з позитивними елементами, і отже, з позитивним значенням ціни гри. При цьому оптимальні змішані стратегії обох гравців не змінюються.

Властивість 1. Трійка (хо, y о, u) є рішенням гри G = (Х, Y, А) тоді і тільки тоді, коли (хо, y о, до u + а) є рішенням гри G (Х, Y, кА + а ), де а - будь-яке дійсне число, до> 0.

Властивість 2. Для того, щоб хо = ( ) Була оптимальною змішаною стратегією матричної гри з матрицею А і ціною гри u, необхідно і достатньо виконання наступних нерівностей

(J = )

Аналогічно для гравця 2: щоб y о = ( , ..., , ..., ) Була оптимальною змішаною стратегією гравця 2 необхідно і достатньо виконання наступних нерівностей:

(I = )

З останнього властивості випливає: щоб встановити, чи є передбачувані (х, y) і u рішенням матричної гри, достатньо перевірити, чи задовольняють вони нерівностям (*) і (**). З іншого боку, знайшовши невід'ємні рішення нерівностей (*) і (**) спільно з наступними рівняннями

,

отримаємо рішення матричної гри.

Отже, нехай дана матрична гра з матрицею А порядку m х n. Відповідно до властивості 7 оптимальні змішані стратегії х = (х1, ..., х m), y = (y 1, ..., yn) відповідно гравців 1 і 2 та ціна гри u повинні задовольняти співвідношенням.

Розділимо всі рівняння і нерівності в (4.4) і (4.5) на u (це можна зробити, тому що за припущенням u> 0) і введемо позначення:

, ,

Тоді (1) і (2) перепишеться у вигляді:

, , , ,

, , , .

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

, .

Оскільки другий гравець прагне знайти такі значення yj і, отже, qj, щоб ціна гри u була найменшою, то рішення другого завдання зводиться до знаходження таких невід'ємних значень qj, , При яких

, .

Формули (3) і (4) висловлюють двоїсті одна одній задачі лінійного програмування (ЛП).

Вирішивши ці завдання, отримаємо значення pi , Qj і u. Тоді змішані стратегії, тобто xi і yj виходять за формулами:

4.1 Рішення задач

Приклад 5: Знайти рішення гри, яка визначається матрицею.

Рішення.

Складемо тепер пару взаємно-двоїстих задач:

Вирішимо другу з них

Б.п.	q1	q2	q3	q4	q5	q6	Рішення	å	Ставлення
	- 1	- 1	- 1	0	0	0	0	- 3
q4	1	2	0	1	0	0	1	5	-
q5	1	0	1	0	1	0	1	4
q6	2	1	0	0	0	1	1	5	-

Б.п.	q1	q2	q3	q4	q5	q6	Рішення	å	Ставлення
	0	- 1	0	0	1	0	1	1
q4	1	2	0	1	0	0	1	5
q3	1	0	1	0	1	0	1	4	-
q6	2	1	0	0	0	1	1	5

Б.п.	q1	q2	q3	q4	q5	q6	Рішення	å	Ставлення
		0	0		1	0
q2		1	0		0	0
q3	1	0	1	0	1	0	1	4
q6		0	0		0	1

З оптимальної симплекс-таблиці випливає, що

(Q 1, q 2, q 3) = (0; ; 1),

а з співвідношень подвійності випливає, що

(P 1, p 2, p 3) = ( ; 1; 0).

Отже, ціна гри з платіжною матрицею А1 дорівнює

. ,

а ігри з платіжною матрицею А:

.

При цьому оптимальні стратегії гравців мають вигляд:

Х = (х1, х2, х3) = (u р1; u р2; u р3) = =

Y = (y1, y2, y3) = (u q1; u q2; u q3) = = .

5. Ігри з природою (без протидії)

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

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

1. Критерій Вальді (песимістичний).

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

max (min a ij). (5.1)

де мінімум вибирається по кожному рядку.

Тобто цей критерій збігається з нижньою ціною гри.

2. Критерій максимуму (оптимістичний).

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

max (max a ij). (5.2)

де максимум вибирається по кожному рядку.

3. Критерій Гурвіца.

Критерій Гурвіца займає проміжне значення між критерієм Вальді і критерієм максимуму. Сам гравець визначає ймовірність свого «везіння»

max (α min a ij + (1 - α) max a ij). (5.3)

Відповідальна особа, яка приймає рішення, визначає значення коефіцієнта α. Якщо втрати можуть бути дуже значними, то значення коефіцієнта α наближається до одиниці, інакше до 0.

4. Критерій Севіджа.

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

r ij = max a ij - a ij. (5.4)

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

min (max (max a ij - a ij). (5.5)

де максимум вибирається в кожному конкретному стовпці.

Для прикладу візьмемо таблицю стратегій (табл. 5.1) і складемо для неї таблицю ризиків (табл. 5.2).

Якщо фірма (гравець) вибере стратегію А1, а природа реалізує стратегію В1, то фірма отримає максимально можливий прибуток 5 (недоотриманий прибуток складе 0). Фірма вгадала стан природи. Але якщо природа реалізує стратегію В4, то фірма замість максимально можливої ​​прибули 12 отримає прибуток 5, а недоотриманий прибуток складе 7.

Таблиця 5.1

Таблиця стратегій

Таблиця 5.2

Таблиця ризиків

5.1 Рішення задач

Приклад 1: Швейна фабрика на літній сезон може реалізувати два види костюмів: 1200 костюмів за ціною 520 руб. і 200 костюмів за ціною 1000 руб., якщо погода буде спекотною. Якщо погода буде холодною, то фабрика може реалізувати 650 костюмів першого виду і 700 костюмів другого виду.

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

Рішення:

Швейна фабрика має у своєму розпорядженні двома стратегіями: А1 - погода буде спекотною й А2 - погода буде холодною.

Якщо фабрика скористається перший стратегією і погода дійсно буде спекотною, то прибуток фабрики становитиме:

1200 · 520 + 200 · 1000 = 624 000 + 200 000 = 824 000 руб.

Якщо фабрика скористається перший стратегією, але погода буде холодною, то прибуток фабрики становитиме:

650 · 520 + 200 · 1000 - (1200 - 650) · 520 = 338 000 + 200 000 - 286 000 = 252 000 руб.

Якщо фабрика скористається другою стратегією і погода дійсно буде холодною, то прибуток фабрики становитиме:

650 · 520 + 700 · 1000 = 338 000 + 700 000 = 1 038 000 руб.

Якщо фабрика скористається другою стратегією, але погода буде спекотною, то прибуток фабрики становитиме:

650 · 520 + 200 · 1000 - (700 - 200) · 1000 = 338 000 + 200 000 - 500 000 = 38 000 руб.

Складемо матрицю прибутку (таб. 5.3).

Таблиця 5.3

Матриця прибутку

α = max (252   000; 38 000) = 252 000 руб.

β = min (824 000; 1 038 000) = 824 000 руб.

Таким чином, ціна гри знаходиться в діапазоні від 252 000 руб. до 824 000 руб.

Мінімальний гарантований дохід швейної фабрики складе 252 000 руб., Але можливий і дохід в 824 000 руб.

Визначимо план випуску виробів швейною фабрикою. Імовірність вибору стратегії А1 позначимо через х1, а ймовірність вибору стратегій А2 - через х2. Враховуючи, що х2 = 1 - х1, можемо записати:

(A 11 - a 12) · х1 + a 12 = (824   000 - 38 000) · х1 + 38   000 = 786   000 х1 + 38   000;

(A 21 - a 22) · х1 + a 22 = (252000 - 1 038 000) · х1 + 1 038 000 = -786 000 х1 + 1038000;

786 000 х1 + 786 000 х1 = 1038000 - 38 000

1572000 х1 = 1 000 000

х1 = 0,64; х2 = 1 - 0,64 х2 = 0,36;

0,64 (1200, 200) + 0,36 (650; 700) = (1002; 380).

Ціна гри становитиме: 786 000 х1 + 38 000 = 541 040 руб.

Таким чином, план випуску виробів такий: 1002 костюма першого виду і 380 костюмів другого виду, і при будь-яких погодних умовах швейна фабрика отримає прибуток не менш 541 000 руб.

Визначимо критерії.

1. Критерій Вальді:

max (min a ij) = max (38 000; 252 000) = 252 000 руб.

Швейній фабриці доцільно використовувати стратегію А1.

2. Критерій максимуму:

max (max a ij) = max (824 000; 1 038 000) = 1 038 000 руб.

Швейній фабриці доцільно використовувати стратегію А2.

3. Критерій Гурвіца:

нехай α = 0,4, тоді для стратегії А1

α min a ij + (1 - α) max a ij = 0,4 · 252 000 + (1 - 0,4) · 824 000 = 595 200 руб.

для стратегії А2

α min a ij + (1 - α) max a ij = 0,4 · 38   000 + (1 - 0,4) · 1   038   000 = 638   000 руб.

Швейній фабриці доцільно використовувати стратегію А2.

4. Критерій Севіджа:

Максимальний елемент у першому стовпці - 824 000, у другому стовпці - 1 038 000.

Матриця ризиків буде мати вигляд:

Швейній фабриці доцільно використовувати стратегію А1 або А2.

Висновок

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

Список літератури

1. «Математичні методи в програмуванні»: / Агальцов В.П., Волдайская І.В. Підручник: - М. : ВД «ФОРУМ»: ИНФРА-М, 2006. - 224с. : Іл. - (Професійна освіта). - (Вчимося програмувати).

2. Лекції з дисципліни «Математичні методи».

3. «Математичні методи: Підручник» / Партика Т.Л., Попов І.І. - М: ФОРУМ: ИНФРА, 2005.

4. «Математичне програмування» / Костевич Л., видавництво «Нове знання», 2003.