Теория игр

Постановка игровых задач Коммерческое предприятие заключило договор на централизованную поставку овощей из теплиц на сумму 10 000 руб. ежедневно. Если в течение дня овощи не поступают, магазин имеет убытки в размере 20 000 руб. от невыполнения плана товарооборота. Магазин может осуществить самовывоз овощей. Для этого он может сделать заказ в транспортном предприятии, что вызовет дополнительные расходы в размере 500 руб. Однако опыт показывает, что в половине случаев посланные машины возвращаются без овощей. Можно увеличить вероятность получения овощей до 80%, если предварительно посылать туда своего представителя, что требует дополнительных расходов в размере 400 руб. Существует возможность заказать дневную норму овощей у другого надежного поставщика по повышенной на 50% цене. Однако в этом случае, кроме расходов на транспорт (500руб.) возможны дополнительные издержки в размере 300 руб., связанные с трудностями реализации товара, если в тот же день поступит и централизованная поставка. Какой стратегии надлежит придерживаться магазину, если заранее неизвестно, поступит или не поступит централизованная поставка. Построим модель игры. Поставщик: В1 – поставка своевременная; В2 – поставки нет. Магазин: А1 – ожидать поставку без дополнительных мер; А2 – послать поставщику свой транспорт; А3 – послать к поставщику и транспорт и представителя; А4 – заказать поставку в другом месте. Всего возможны 8 совместных ситуаций, сведем их в таблицу. В таблице рассмотрим всевозможные ситуации и сделаем расчет затрат магазина за день в зависимости от выбранной стратегии. № Ситуация Стоимость овощей Убытки от недопоставки Транс. издержки Командир. издержки Издержки от реализации Всего 1 А1 В1 2 А1 В2 3 А2 В1 4 А2 В2 5 А3 В1 6 А3 В2 7 А4 В1 8 А4 В2 Стратегия магазина Стратегия поставщика В1 В2 А1 А2 А3 А4 По данным таблицы составляются уравнения затрат магазина в зависимости от надежности поставщика для каждой стратегии магазина Игра двух лиц с нулевой суммой В1 В2 … Вn А1 а11 а12 а1n А2 а21 a22 a2n … Аm am1 am2 amn aij - выигрыш игрока А при выборе игроками А и В стратегий Аi и Вj соответственно. Игрок А выбирает стратегию i. Его гарантированный выигрыш составит , где минимум берется по всем стратегиям игрока В. V1 = Игрок В среди всех своих стратегий выбирает ту, которая обеспечит ему минимальный гарантированный проигрыш V2 = Для матричной игры справедливо неравенство V1 V2. Если V1=V2, то элемент платежной матрицы называется седловой точкой. Пример. Определить нижнюю и верхнюю цену игры, заданной платежной матрицей В1 В2 В3 В4 min aij A1 6 4 3 4 A2 12 7 10 9 A3 6 6 4 9 A4 12 3 12 7 max aij Решение игры без седловой точки Пусть смешанные стратегии игроков А и В заданы векторами SA=(p1,p2,….pm) и SB=(q1,q2,…….qn), где pi – вероятность (частота) применения игроком А чистой стратегии Аi, qj – вероятность (частота) применения игроком В чистой стратегии Bj. Т.к. речь идет о вероятностях, то справедливо равенство . Преобразование платежной матрицы Рассмотрим игру без седловой точки Р= . Оптимальное решение существует и определяется парой смешанных стратегий SA =(p1, p2) и SB = (q1, q2). SA = , SB = a11p1+a21p2 = V a12p1 +a22p2 =V р1+р2=1 р1 = р2 = V =. Аналогично, при отыскании смешанной стратегии второго игрока, a11q1+a12q2 = V a21q1 +a22q2 = V q1+q2 =1 Тогда оптимальная стратегия второго игрока определяется по формулам: q1= q2= При решении любой игры рекомендуется: 1). Исключить заведомо невыгодные стратегии по сравнению с другими. 2). Определить верхнюю и нижнюю цены игры и проверить есть ли седловая точка. Если седловая точка есть, то соответствующие ей стратегии будут оптимальными и цена совпадает с нижней (верхней) игрой. 3). Если седловая точка отсутствует, то решение ищут в смешанных стратегиях. Решение игр с помощью линейного программирования Пусть дана платежная матрица В1 В2 … Вn А1 а11 а12 а1n А2 а21 a22 a2n … Аm am1 am2 amn a11p1 + a21p2 +…am1pm V, ……………………… a1np1 + a2np2 +…amnpm V, p1 + p2 + …pm=1 Разделим все ограничения на V a11+ a21+…1, ………….. a1n + a2n+ .. 1 Обозначим =xi, тогда a11x1 + a21x2 +…am1xm 1, ……………………… a1nx1 + a2nx2 +…amnxm 1, Т.к. =xi, и p1 + p2 + …pm=1, то x1 +x2 +…xm = , где V необходимо максимизировать, следовательно - минимизировать. Для игрока В задача линейного программирования примет вид a11y1 + a12y2 +…a1nyn 1, ……………………… am1y1 + am2y2 +…amnyn 1, Целевая функция Z(y) = y1 + y2 …yn стремится к максимуму. Игры с природой 1. Критерий Лапласа опирается на принцип недостаточного ос­нования, согласно которому все состояния природы Si (i=1, 2..n) по­лагаются равновероятными. Таким образом, каждому состоянию Si соответствует вероятность qi определяемая по формуле qi= 1/n Для принятия решения для каждого действия Rj вычисляется среднее арифметическое значение потерь: Mj(R) = Vji – элементы платежной матрицы. Среди Mj(R) выбирают минимальное значение, если матрица возможных результатов представле­на матрицей потерь (или максимальное, во всех других ситуациях), которое и будет соответствовать оптимальной стратегии: W = min{Mj(R)} Где W - значение параметра, соответствующее оптимальной стра­тегии. 2. Критерий Вальде. Рекомендуется применять максиминную стратегию: max min aij 3. Критерий максимума. Он выбирается из условия max max aij 4. Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле max(α min aij + (1- α)max aij), где α – степень оптимизма, которая изменяется в диапазоне (0, 1). 5. Критерий Сэвиджа. Суть критерия состоит в выборе такой стратегии, чтобы не допустить чрезмерно высоких потерь, к которым она может привести. Находится матрица рисков, элементы которой показывают, какой убыток понесет человек (фирма), если для каждого состояния природы он не выберет наилучшей стратегии. Элемент матрицы рисков (rij) находится по формуле rij = max aij – aij, где max aij – максимальный элемент в столбце исходной матрицы. Оптимальная стратегия находится из выражения min(max(max aij – aij)). Определение производственной программы в условиях риска и неопределенности. Фирма «Фармацевт» - производитель медикаментов и биомедицинских изделий в регионе. Известно, что пик спроса на некоторые лекарственные препараты приходится на летний период (сердце, анальгетики), на другие – на осенний и весенний периоды (простуда, витамины). Затраты на 1 ус.ед. продукции за сентябрь – октябрь составили: по первой группе – 20 д.ед., по второй – 15 д.ед. По данным наблюдений за несколько последних лет службой маркетинга фирмы установлено, что она может реализовать в течении рассматриваемых двух месяцев в условиях теплой погоды 3050 ус.ед. продукции первой группы и 1100 ус.ед. продукции второй группы; в условиях холодной погоды – 1525 ус.ед. продукции первой группы и 3690 ус.ед. продукции второй группы. В связи с возможными изменениями погоды ставится задача – определить стратегию фирмы в выпуске продукции, обеспечивающую максимальный доход от реализации при цене продажи 40 д.ед. за 1 ус.ед. продукции первой группы и 30 д.ед. – второй группы. Решение. Фирма располагает двумя стратегиями: А1 – в этом году будет теплая погода; А2 – пгода будет холодная.