Смешанное расширение матричной игры

Смешанное расширение матричной игры   Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то игра не имеет решения в чистых оптимальных решениях, но можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью. Смешанные стратегии в теории игр представляют собой модель гибкой, изменчивой тактики, когда ни один игрок не знает, как поведет себя противник в данной партии (сам игрок тоже не знает, как он поступит). Лучший способ скрыть от противника свое поведение - придать ему случайный характер. Рассмотрим модель смешанных стратегий. ! Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий. Будем обозначать смешанные стратегии (набор чисел) игроков A и B соответственно:    P = (p1, p2, …, pm) ; Q = (q1, q2, …, qn)  где pi вероятность применения игроком A i-й стратегии  Ai,  qj – вероятность применения игроком B своей j-й стратегии Bj pi  0     (i = 1,m), Аналогично для игрока 2, который имеет n чистых стратегий qj  0,   (j = 1,n), Если при решении задачи оптимизации получается, что пара каких либо вероятностей равна единице - pm = 1 и qn = 1 (остальные равны нулю), то игра имеет решение в чистых стратегиях: (Am ; Bn ). Такая тактика (правда, обычно безо всяких математических обоснований) часто применяется в карточных играх. В теории игр на этот счет существует одна  из  основных теорем: ЛЮБАЯ КОНЕЧНАЯ ИГРА ДВУХ СТОРОН С НУЛЕВОЙ СУММОЙ ИМЕЕТ ПО КРАЙНЕЙ МЕРЕ ОДНО РЕШЕНИЕ – ПАРУ ОПТИМАЛЬНЫХ СТРАТЕГИЙ, В ОБЩЕМ СЛУЧАЕ СМЕШАННЫХ –(io; jo) И СООТВЕТСТВУЮЩУЮ ЦЕНУ (V) Оптимальные стратегии обладают следующим свойством:  ЕСЛИ ОДНА ИЗ СТОРОН ПРИДЕРЖИВАЕТСЯ СВОЕЙ ОПТИМАЛЬНОЙ СТРАТЕГИИ, ТО ДРУГОЙ СТОРОНЕ НЕ МОЖЕТ БЫТЬ ВЫГОДНО ОТСТУПАТЬ ОТ СВОЕЙ. Пример  Пусть предприятие ожидает поступления одного из двух взаимоисключающих крупных заказов Z1 и Z2, требующих выполнения токарных и слесарных работ. По данным расчётов при поступлении заказа Z1 максимальный объём затрат труда по токарным работам составит 600 чел.-дней, а максимальный объём затрат труда слесарей составит 1900 чел.-дней. Аналогичные показатели при поступлении заказа Z2 равны 1000 и 625 чел.-дней соответственно. Согласно договорам заказчики возмещают затраты предприятия из расчёта 48 ден.ед. за 1 чел.-день токарных работ и 16 ден.ед. за 1 чел.-день слесарных работ. Затраты предприятия, включая оплату труда рабочих, занятых на выполнении заказов, составляют 27 ден.ед. за 1 чел.-день для токарей и 8 ден. ед. для слесарей. Задача заключается в максимизации средней величины прибыли предприятия с учётом неопределённости, так как неизвестно, какой из двух заказов поступит. Решение Предприятие в данных условиях должно определить оптимальную стратегию в выделении трудовых ресурсов , обеспечивающих при любой ситуации с заказами определённый средний доход. Таким образом задача относится к теории игр, причём игра в данном случае будет относится к типу игр с природой. Предприятие как игрок располагает в этих условиях двумя чистыми стратегиями: стратегия P1 с расчётом на поступление заказа Z1 стратегия P2 с расчётом на поступление заказа Z2 Природу будем рассматривать как второго игрока также с двумя стратегиями: заказ Z1(стратегия Q1) и заказ Z2(стратегия Q2). Необходимо составить платёжную матрицу А: Если предприятие выберет стратегию P1, то в случае поступления заказа Z1 доход будет равен 600(48-27)+1900(16-8)=27800 ден.ед. (элемент а11). А в случае поступления заказа Z2 доход составит 600(48-27)+625(16-8)-(1900-625)8=7400 ден. ед. (элемент а12). Если предприятие выберет стратегию P2, то при поступлении заказа Z1 будет получен доход в размере 600(48-27)+625(16-8)-(1000-600)27=6800 ден.ед. (элемент а21). А при поступлении заказа Z2 доход будет равен 1000(48-27)+625(16-8)=26000 ден.ед. (элемент а22) Таким образом, платёжная матрица данной игры имеет вид: Первая и вторая строки этой матрицы соответствуют стратегиям P1 и P2предприятия, а первый и второй столбцы – стратегиям Q1 и Q2 природы. Из платёжной матрицы видно, что первый игрок (предприятие) никогда не получит доход меньше 6800 ден.ед. Однако если реальная ситуация с заказами совпадёт с выбранной стратегией предприятия, то его выигрыш (доход) составит 26000 или 27800 ден. ед. Отсюда можно сделать вывод, что в условиях неопределённости с заказами наибольший гарантированный доход предприятие получит, если оно будет применять то стратегию P1, то стратегию P2. Такая стратегия , как отмечалось ранее, называется смешанной. Оптимизация смешанной стратегии позволит первому игроку всегда получать среднее значение выигрыша независимо от стратегии второго игрока. Пусть х означает частоту применения первым игроком (предприятием) стратегии P1, тогда частота применения им стратегии P2 будет равна (1-x).В случае оптимальной смешанной стратегии первый игрок получит и при стратегии Q1(заказZ1), и при стратегии Q2(заказ Z2) второго игрока одинаковый средний доход, что соответствует следующему уравнению: а11x+ а21(1-x) = а12x+ а22(1-x), что соответствует: 27800х+6800(1-х) = 7400х+26000(1-х) В результате решения уравнения получаем: х=16/33; (1-х)=17/33. Следовательно, первый игрок, применяя чистые стратегии P1 и P2 в соотношении 16:17, будет иметь оптимальную смешанную стратегию, обеспечивающую ему в любом случае гарантированный средний доход в размере 27800(16/33)+6800(17/33) = 16981,82 ден. ед., который и будет в данном случае ценой игры. Легко рассчитать количество ресурсов труда токарей и слесарей, которое  должно обеспечить предприятие при оптимальной стратегии: (600 чел.-дн. токарей+1900 чел.-дн. слес.)(16/33) + (1000 чел.-дн. Ток.+625чел.-дн. Слес.)(17/33)= =806 чел.-дн. токарей+1243,2 чел.-дн. слесарей. Таким образом, оптимальная стратегия предприятия в управлении трудовыми ресурсами в данных условиях заключается в обеспечении ресурса труда токарей в размере 806 чел.-дн. и ресурса труда слесарей в размере 1243,2 чел.-дн. Эта стратегия гарантирует предприятию при любом стечении обстоятельств средний доход в сумме 16981,82 ден.ед.