Змішане розширення матричної гри

3.3 Змішане розширення матричної гри

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

Пара (X,Y) змішаних стратегій гри Г= називається антагоністична гра Г’=, в якій множинами стратегій гравців є множини їх змішаних стратегій в початковій грі.

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

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

3.4 Методи розв”язування матричних ігор

Розглянемо деякі зручні методи розв”язування матричних ігор.

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

Так, нехай задана матрична гра з матрицею А=( а_ij) порядку m*n. Оптимальні змішані стратегії x(x₁,...,x_i,....,x_m), y(y₁,....,y_i,.....,y_n) відповідно першого і другого гравця і ціна гри v повинна задовільняти умовам:

(3.3)

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

(3.4)

Отримаємо відповідно задачі (3.3) в наступному вигляді

(3.5)

Оскільки перший гравець прагне знайти такі значеня xi, а значить і рі, щоб ціна гри v була максимальна, то розв”язування першої задачі зводиться до знаходження невід”ємних значень рі(і=1,2...m) при яких

(3.6)

Оскільки другий гравець прагне знайти такі значеня уi, а значить і qі, щоб ціна гри v була максимальна, то розв”язування першої задачі зводиться до знаходження невід”ємних значень qі(і=1,2...m) при яких

(3.7)

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

Розв”язавши ці задачі, отримаємо значення рі і qі та v. Тоді змішані стратегії, тобто значення xi i yi отримаємо за формулами

x_i=vp_i (i=1,2...m),

y_j=vq_j (j=1,2...n) . (3.8)

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

Другий метод зведення матричних ігор до задачі лінійного програмування. У цьому випадку ціна гри може бути довільною.

Відомо, що оптимальні змішані стратегії x(x₁,…,x_i,….,x_m), y(y₁,…,y_j,…,y_n) і ціна гри з матрицею А=(а_ij) порядку mxn повинні задовільняти умовам . Ввівши додаткові невід”ємні змінні x_m+1для j-ої нерівності (j=1,2,…n) з (3.3) та для і-ої нерівності (j=1,2,…m) з (3.3) отримуємо наступні рівняння

(3.9)

(3.10)

Виділимо у (3.10) першу частину рівності при j=1 і віднімемо її від усіх рівностей для j=2,…,n, отримаємо

, (3.11)

(3.12)

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

Аналогічно робимо при рішенні системи (3.12)

, (3.13)

(3.14)

Оскільки другий гравець намагається мінімізувати v за рахунок своїх стратегій, то рішення системи (3.14) зводиться до наступної задачі лінійного програмування : знайти мінімум лінійної форми (3.5) при лінійних обмеженнях (3.13)

Похожие работы

Організація збутової діяльності на підприємстві

Скачать

57177

12

6

... підприємство намагається скоротити шлях товару від заводу до споживача з метою збільшення продажу і зменшення витрат. З цією метою і вибирається один з каналів збуту, які вище розглядалися. 2. Організація збутової діяльності на підприємстві 2.1 Організаційно-економічна характеристика підприємства Відкрите акціонерне товариство “Василівський сирзавод” є колективним підприємством. Відкрите ...

Фінанси підприємств

Скачать

198415

0

0

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

Зовнішньоекономічна діяльність та її вплив на ефективність діяльності підприємств харчової промисловості на прикладі рибопереробного підприємства АТЗТ компанія "Бастіон"

Скачать

229102

13

72

... РОЗДІЛ 4 ШЛЯХИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЗЕД ПІДПРИЄМСТВА АТЗТ КОМПАНІЯ "БАСТІОН"   4.1 Заходи щодо удосконалення ЗЕД та їх вплив на ефективність діяльності підприємства АТЗТ компанія "Бастіон" На підставі аналізу діяльності АТЗТ компанія «Бастіон», представленому в розділі 3 дипломної роботи, виявлено, що основними проблемами розвитку ЗЕД підприємства є зниження ефективності його діяльност ...

Аналіз зовнішньоекономічної діяльності приватного підприємства ПП "Промен"

Скачать

120582

7

45

... ї риби та експортних поставок прісноводної риби. Отримані матеріали дозволяють у дипломному проекті провести детальний аналіз та розробку рекомендацій по оптимізації концепції управління персоналом в ПП „Промен”, яка повинна забезпечити подальший розвиток зовнішньоекономічної діяльності підприємства. СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 1. Митний Кодекс України від 11 липня 2002 року N 92-IV // Із ...