Практичне заняття №19

РОЗВ’ЯЗУВАННЯ ІГОР m´ n МЕТОДОМ ІТЕРАЦІЙ

Мета заняття: вивчення методів розв’язування ігор m ´ n без сідлової точки наближеним ітераційним методом Брауна-Ро­бінсон.

Стисла теоретична довідка

Метод Брауна-Робінсон є наближеним методом рішення ігор довільного розміру без сідлової точки. Ідея методу полягає у наступному.

Розігрується штучний експеримент, у якому гравці А та В по черзі застосовують один проти одного свої активні стратегії, маючи намір виграти побільше (програти найменше). Експеримент складається з декількох послідовних «партій» гри. Починається вона з того, що один з гравців (наприклад, А) обирає довільно одну із своїх активних стратегій A_i. Гравець B відповідає йому такою з своїх активних стратегій B_j , яка гірша за все для А, тобто надає виграшу гравця А при застосуванні ним стратегії A_i мінімальне значення. Надалі знов, черга гравця А — він відповідає гравцю В такою своєю стратегією A_k, яка дає максимальний виграш при застосуванні гравцем В стратегії B_j . У подальшій черговій відповіді гравець В застосовує таку свою стратегію, яка є найгіршою не для останньої стратегії A_k, а для змішаної стратегії, у якій застосовані досі стратегії A_i, A_k зустрічаються з рівними ймовірностями. І так далі: на кожному кроці ітераційного процесу кожний гравець відповідає на черговий хід другого тією своєю стратегією, яка є оптимальною для нього відносно змішаної стратегії іншого гравця, до якої всі застосовані досі стратегії входять пропорційно частотам їх застосовування.

Даний метод є дуже простим, однак йому властивий суттєвий недолік — ітераційний процес сходиться дуже повільно.

Зміст практичного заняття

Та вихідні дані до його виконання

Розв’язати ітераційним методом гру 3´ 3, умови якої задані у практичному занятті 18. Автотранспортне підприємство (А) може виділяти щодня три типи автомобілів для перевезення вантажовідправнику (В), що використовує їх на перевезеннях трьох видів вантажу. Прибуток сторін від виконання перевезень (в умовних грошових одиницях) заданий платіжною матрицею 3´ 3. Методами теорії ігор оцінити економічну доцільність виконання перевезень з боку АТП та визначити його оптимальну стратегію з метою максимізації середньоденного прибутку.

Вихідні дані до виконання завдання прийняти з практичного заняття 18 згідно таблиці 18.1. Для пошуку наближеного розв’язку заданої гри за методом Брауна-Ро­бінсон виконати 15 ітерацій.