9.4. Принятие решений в условиях неопределенности
Пусть Sf - состояние «природы», при этом / = 1, л, где п — число возможных состояний. Все возможные состояния известны, не известно только, какое состояние будет иметь место в условиях, когда планируется реализация принимаемого управленческого решения. Будем считать, что множество управленческих решений (планов) Rj также конечно и равно т. Реализация Rj плана в условиях, когда «природа» находится в состоянии, приводит к опре-деленному результату, который можно оценить, введя количественную меру. В качестве этой меры могут служить выигрыши от принимаемого решения (плана); потери от принимаемого решения, а также полезность, риск и- другие количественные критерии.
Данные, необходимые для принятия решения в условиях нео-пределенности, обычно задаются в форме матрицы, строки которой соответствуют возможным действиям (управленческим решения) Rp а столбцы — возможным состояниям «природы» 5,.
Допустим, каждому Rj-ыу действию и каждому возможному 5гму состоянию «природы» соответствует результат (исход), опре-деляющий результат (выигрыш, полезность) при выборе 7-ГО действия и реализации /-го состояния, — Vp. Sx s2 . .. St . Vn Vli ¦ ¦¦ vu . •• Vu r2 V2x v22 . ¦¦ v2i . ¦¦ V2n Rj vi{ Vp. • .. Vjt . : Vj:n Rm V •
r mi K»2 ¦ V •
•• r mi V
•• Y mn •
Следовательно, математическая модель задачи принятия решений определяется множеством состояний {5/}, множеством планов (стратегий) {/?у} и матрицей возможных результатов В качестве результатов в отдельных задачах рассматривается матрица рисков ||гу/||.
Риск — мера несоответствия между разными возможными результатами принятия определенных стратегий (действий).
Элементы матрицы рисков связаны с элементами матрицы полезностей (выигрышей) следующим соотношением:
Гр = К - Vji, (9.23)
где Vi = max Vp — максимальный элемент в столбце і матрицы по- j лезностей.
Если матрица возможных результатов представляет собой матрицу потерь (затрат), то элементы матрицы рисков следует определять по формуле
Гр = Vp - Vh (9.24)
где Vi = min Vp — минимальный элемент в столбце / матрицы потерь J (результатов).
Таким образом, риск — это разность между результатом, который можно получить, если знать действительное состояние «природы», и результатом, который будет получен при у-й стратегии.
Матрица рисков дает более наглядную картину неопределенной ситуации, чем матрица выигрышей (полезностей).
Непосредственный анализ матриц выигрышей ||^7|| или рисков ||/yj| не позволяет в общем случае принять решение по выбору оп-тимальной стратегии (плана), за исключением тривиального случая, когда выигрыши при одной стратегии выше, чем при любой другой для каждого состояния «природы» (элементы матрицы выигрышей в некоторой строке больше, чем в любой из других).
Другими словами, имеется в наличии «доминирующая» стратегия.Для принятия решения в условиях неопределенности используется ряд критериев. Рассмотрим некоторые из них. Это критерий Лапласа, критерий Вальда, критерий Сэвиджа, критерий Гурвица.
Критерий Лапласа. Этот критерий опирается на «принцип недостаточного основания» Лапласа, согласно которому все состояния «природы» Sh і = 1 ,п полагаются равновероятными. В соответствии с этим принципом каждому состоянию $ ставится вероятность qh определяемая по формуле
* (9.25)
При этом исходной может рассматриваться задача принятия решения в условиях риска, когда выбирается действие RJ9 дающее наибольший ожидаемый выигрыш. Для принятия решения для каждого действия Rj вычисляют среднее арифметическое значение выигрыша:
Mj(R) = -iVji. (9.26)
3 Ям 3
Среди Mj(R) выбирают максимальное значение, которое будет соответствовать оптимальной стратегии Rj.
Другими словами, находится действие Rj , соответствующее
\Z^VJi\- (9-27)
Rj [«/=i
Если в исходной задаче матрица возможных результатов представлена матрицей рисков ||/yj|, то критерий Лапласа принимает следующий вид:
Пример 9.4. Одно из транспортных предприятий должно определить уровень своих провозных возможностей так, чтобы удовлетворить спрос клиентов на транспортные услуги на планируемый период. Спрос на транспортные услуги не известен, но ожидается (прогнозируется), что он может принять одно из четырех значений: 10, 15, 20 или 25 тыс. т. Для каждого уровня спроса существует наилучший уровень провозных возможностей транспортного предприятия (с точки зрения возможных затрат). Отклонения от этих уровней приводят к дополнительным затратам либо из-за превышения провозных возможностей над спросом (из-за простоя подвижного состава), либо из-за неполного удовлетворения спроса на транспортные услуги. Ниже приводится табл. 9.3, определяющая возможные прогнозируемые затраты на развитие провозных возможностей:
Таблица 9.3 Варианты провозных возможностей транспортного предприятия Варианты спроса на транспортные услуги, д.
е. 1 2 3 4 1 6 12 20 24 2 9 7 9 28 3 23 18 15 19 4 27 24 21 15Необходимо выбрать оптимальную стратегию.
Решение
Согласно условию задачи имеются четыре варианта спроса на транспортные услуги, что равнозначно наличию четырех состояний «природы»: Sx, S2, іS4. Известны также четыре стратегии развития провозных возможностей транспортного предприятия: Rb R2, Л3, Л4. Затраты на развитие провозных возможностей при каждой паре Sj и Rj заданы следующей матрицей (таблицей): Лі 6 12 20 24 r2 9 7 9 28 Ъ 23 18 15 19 Я4 27 24 21 15.
Принцип Лапласа предполагает, что S{i S2, S3i S4 равновероят-ны. Следовательно, />{5 = ?/} = — = j = 0,25, / = 1, 2, 3, 4 и ожидае-мые затраты при различных действиях Rx, R2, R3, R4 составляют:
W{RX) = 0,25 (6 + 12 + 20 + 24) = 15,5;
W[R2) = 0,25 (9 + 7 + 9 + 28) = 13,25;
JV{R3) = 0,25 (23 + 18 + 15 + 19) = 18,75;
W{R4) = 0,25 (27 + 24 + 21 + 15) = 21,75.
Таким образом, наилучшей стратегией развития провозных воз-можностей в соответствии с критерием Лапласа будет R2.
Критерий Вальда (минимаксный или максиминный критерий). Применение данного критерия не требует знания вероятностей состояний 5/. Этот критерий опирается на принцип наибольшей ос-торожности, поскольку он основывается на выборе наилучшей из наихудших стратегий Rj.
Если в исходной матрице (по условию задачи) результат V^ представляет потери лица, принимающего решение, то при выборе оптимальной стратегии используется минимаксный критерий. Для определения оптимальной стратегии Rj необходимо в каждой строке матрицы результатов найти наибольший элемент тах{Ку7}, а затем
выбирается действие Rj (строка Д которому будет соответствовать наименьший элемент из этих наибольших элементов, т. е. действие, определяющее результат, равный
W = min max j Ку7}. (9.29)
Если в исходной матрице по условию задачи результат V^ представляет выигрыш (полезность) лица, принимающего решение, то при выборе оптимальной стратегии используется максиминный кри-терий.
(9.30)
W = тіптах{ку7}.
Для определения оптимальной стратегии Rj в каждой строке матрицы результатов находят наименьший элемент min , а затем выбирается действие Rj (строка J), которому будут соответство-вать наибольшие элементы из этих наименьших элементов, т.
е. действие, определяющее результат, равныйПример 9.5. Рассмотрим пример 9.4. Так как Vгц в этом примере представляет потери (затраты), применим минимаксный критерий. Необходимые результаты вычисления приведены в табл. 9.4:
Таблица 9.4 Состояния \ St Стратегия Rj Затраты, (Vji) д. е. шах
{Vji\ = min max {V-,} SI s2 6 12 20 24 24 — R2 9 7 9 28 28 — ъ 23 18 15 19 23 23 r4 27 24 21 15 27 —
Таким образом, наилучшей стратегией развития провозных возможностей в соответствии с минимаксным критерием «лучшим из худших» будет третья, Т. е. Ry
Минимаксный критерий Вальда иногда приводит к нелогичным выводам из-за своей чрезмерной «пессимистичности». «Пессимистичность» этого критерия исправляет критерий Сэвиджа.
Критерий Сэвиджа использует матрицу рисков Элементы данной матрицы можно определить по формулам (9.23), (9.24), которые перепишем в следующем виде:
піахІкЛ-Ку/, если К- выигрыш
г~=\ у (9.31)
Jl Ky/-min{Ky/}, если К-потери.
Это означает, что /у, есть разность между наилучшим значением в столбце і и значениями Vгц при том же /. Отметим, что независимо ОТ ТОГО, является ЛИ Vji доходом (выигрышем) или потерями (затратами), гв обоих случаях определяет величину потерь лица, принимающего решение. Следовательно, можно применять к rjt только минимаксный критерий. Критерий Сэвиджа рекомендует в условиях неопределенности выбирать ту стратегию RJ9 при которой величина риска принимает наименьшее значение в самой неблагоприятной ситуации (когда риск максимален).
Пример 9.6. Рассмотрим пример 9.4. Заданная матрица определяет потери (затраты). По формуле (9.31) вычислим элементы матрицы рисков |Ы|: Л, 0 5 11 9 R2 3 0 0 13, Ry 17 11 6 4 ra 21 17 12 0
Полученные результаты вычислений с использованием критерия минимального риска Сэвиджа оформим в табл. 9.5.
Введение величины риска гпривело к выбору первой стратегии Rb обеспечивающей наименьшие потери (затраты) в самой не-благоприятной ситуации (когда риск максимален).
Применение критерия Сэвиджа позволяет любыми путями из-бежать большого риска при выборе стратегии, а значит, избежать большего проигрыша (потерь).
Критерий ГУрвица.
Основан на следующих двух предположениях: «природа» может находиться в самом невыгодном состоянии с вероятностью (1 — а) и в самом выгодном состоянии с вероятностью а, где а — коэффициент доверия. Если результат Vгц — прибыль, полезность, доход ит. п., то критерий Гурвица записывается так:W - шах
j
(9.32)
a max Vji + (l - a) min Vji
Когда V^ представляет затраты (потери), то выбирают действие, дающее
Жтіп=шіп
a min Vji + (l - а) max Vji
Если а = 0, получим пессимистический критерий Вальда.
Если а = 1, то приходим к решающему правилу вида
max min К,-/ или к так называемой стратегии «здорового оптими- j і
ста», т. е. критерий слишком оптимистичный.
Критерий Гурвица устанавливает баланс между случаями крайнего пессимизма и крайнего оптимизма путем взвешивания обоих способов поведения соответствующими весами (1 — а) и а, где О < а < 1. Значение а от 0 до 1 может определяться в зависимости от склонности лица, принимающего решение, к пессимизму или к оптимизму. При отсутствии ярко выраженной склонности а = 0,5 представляется наиболее разумной.
Пример 9.7. Критерий Гурвица используем в примере 9.4. Положим а = 0,5. Результаты необходимых вычислений приведены в табл. 9.6.
Таблица 9.6 Wj max Vji min Vji a • min Vji + (1 - a) • max Ky7 min Wj wl 6 24 15 15 w2 7 28 17,5 — щ 15 23 19 — щ 15 27 21 -
Оптимальное решение заключается в выборе W. Таким образом, в примере предстоит сделать выбор: по критерию Лапласа — выбор стратегии Я2; по критерию Вальда — выбор стратегии R3; по критерию Сэвиджа — выбор стратегии по критерию Гурвица — выбор стратегии Rx при а = 0,5, а если лицо, принимающее решение, - пессимист (а = 0), то выбор стратегии R3.
Какое из возможных решений предпочтительнее? Это определяется выбором соответствующего критерия (Лапласа, Вальда, Сэвиджа или Гурвица).
Выбор критерия принятия решений в условиях неопределенности является наиболее сложным и ответственным этапом в исследовании операций.
При этом не существует каких-либо общих советов или рекомендаций. Выбор критерия должно производить лицо, принимающее решение (ЛПР), с учетом конкретной специфики решаемой задачи и в соответствии со своими целями, а также опираясь на йрошлый опыт и собственную интуицию.В частности, если даже минимальный риск недопустим, то следует применять критерий Вальда. Если, наоборот, определенный риск вполне приемлем и ЛПР намерено вложить в некоторое предприятие столько средств, чтобы потом оно не сожалело, что. вложено слишком мало, то выбирают критерий Сэвиджа.
9.5. Теория игр
В отличие от рассмотренных выше задач принятия решений в условиях определенности, риска и неопределенности, в которых внешняя среда (природа) предполагалась пассивной, в конфликтных ситуациях имеются противодействующие стороны, интересы которых противоположны. При конфликтных ситуациях решения принимаются в условиях неопределенности двумя и более разумными противниками, каждый из которых стремится оптимизиро-вать свои решения за счет других. Теория, занимающаяся принятием решений в условиях конфликтных ситуаций, называется теорией игр. Математическая модель конфликтной ситуации представляет собой игру.
Игра — это совокупность правил, описывающих сущность конфликтной ситуации. Эти правила устанавливают:
выбор образа действия игроков на каждом этапе игры;
информацию, которой обладает каждый игрок при осуществлении таких выборов;
плату для каждого игрока после завершения любого этапа игры.
Игру можно определить следующим образом:
имеются п конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;
сформулированы правила выбора допустимых стратегий, известные игрокам;
определен набор возможных конечных состояний игры (например, выигрыш, ничья, проигрыш);
всем игрокам (участникам игры) заранее известны платежи, соответствующие каждому возможному конечному состоянию. Платежи задаются в виде матрицы А = {{а^.
В зависимости от числа конфликтующих сторон игры делятся на парные (с двумя игроками) и множественные (имеющие не менее трех игроков). Каждый игрок имеет некоторое множество (конечное или бесконечное) возможных выборов, т. е. стратегий.
Стратегией игры называется совокупность правил, определяющих поведение игрока от начала игры до ее завершения. Стратегии каждого игрока определяют результаты или платежи в игре. Игра называется игрой с нулевой суммой, если проигрыш одного игрока равен выигрышу другого, в противном случае она называется игрой с ненулевой суммой.
В подразд. 9.5 рассматриваются только игры двух лиц с нулевой суммой. Задание стратегий (А и В) двух игроков в парной игре полностью определяет ее исход, т. е. выигрыш одного или проигрыш другого. Игра называется конечной, если у каждого игрока имеется конечное число стратегий. Результаты конечной парной игры с нулевой суммой можно задавать матрицей, строки и столбцы которой соответствуют различным стратегиям, а ее элементы — выигрышам одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры.
Если первый игрок имеет т стратегий, а второй — п стратегий, то говорят, что мы имеем дело с игрой т хп.
Рассмотрим игру т х п. Пусть заданы множество стратегий: для первого игрока {Л,}, для второго игрока {Bj}, платежная матрица А тхп = ||яД где а у — выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий At и Bj соответственно. Каждый из игроков выбирает однозначно с вероятностью 1 некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры будет в чистых стратегиях. Поскольку интересы игроков противоположны, то первый игрок стремится макси-мизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш.
Решение игры состоит в определении наилучшей стратегии каждым игроком. Выбор наилучшей стратегии одним игроком про-водится при полном отсутствии информации о принимаемом решении вторым игроком. Следует отметить, что и первый, и второй игрок являются разумными противниками, которые находятся в состоянии конфликта. Поэтому для решения игры двух лиц с нулевой суммой используется очень «пессимистичный» критерий, так называемый критерий мини-макса-максимина. Этот критерий рассмотрен в подразд. 9.4. Основное отличие заключается в том, что ранее «природа» не рассматривалась как активный противник, тогда как в теории игр каждый игрок действует разумно и, следова-тельно, пытается активно помешать своему противнику. Так, если первый игрок применяет стратегию Ah то второй будет стремиться К тому, чтобы выбором соответствующей стратегии Bj свести выигрыш первого игрока к минимуму, что равнозначно сведёнию своего проигрыша к минимуму. Величина этого минимума
a/=minay, i = l,m. (9.34)
Первый игрок (при любых ответах противника) будет стремиться найти такую стратегию, при которой а, обращается в максимум:
a = maxa/ = maxmina/y. /9 35)
і і j
Величина а называется нижней ценой игры. Ей соответствует максиминная стратегия, придерживаясь которой первый игрок при любых стратегиях противника обеспечит себе выигрыш, не мень-
ший а. Другими словами, нижняя цена игры является гарантированным выигрышем первого игрока при любых стратегиях второго игрока.
Аналогично определим по каждому столбцу матрицы Ру = шаха^. j = 1, я, найдем минимальное значение Ру: /
(9.36)
Р = minp ; = min max я/У.
j J j і
Величина P называется верхней ценой игры. Ей соответствует минимаксная стратегия второго игрока. Величина Р представляет собой гарантированный проигрыш второго игрока при любой стратегии первого игрока.
Пример 9.8. Дана платежная матрица 3x4, которая определяет выигрыши игрока А. Вычислить нижнюю и верхнюю цены заданной игры. 10 4 11 7" 7 6 8 20 6 2 1 А=\Ыг
Решение
Представим нашу игру в виде табл. 9.7:
Таблица 9.7 Стратегии первого игрока,
л, Стратегии второго игрока, Bj Значение, «/ а Bx В2 А, 10 4 И 7 4 — А2 7 6 8 20 6 6 Аъ 6 2 1 И 1 — Значение Р 10 6 И 20 - Р — 6 — — — —
Если игрок А выбирает первую стратегию, он может получить выигрыш в размере 10, 4, 11 или 7 д. е. в зависимости от выбранной стратегии игроком В. При этом выигрыш игрока будет не меньше (Xj = min{10; 4; 11; 7) = 4 д. е. независимо от поведения игрока В. Аналогично при выборе игроком А второй стратегии гарантированный выигрыш а2 = min{7; 6; 8; 20} = 6 д. е. При выборе игроком А третьей стратегии выигрыш а3 = min{6; 2; 1; 11} = 1 д. е.
Таким образом, минимальные значения а,-, / = 1,3 определяют минимально гарантированный выигрыш для игрока А,
если он выбирает соответствующую стратегию /. Величина
шаха,- =max{4; 6; l}=6 д.е. будет гарантированным выигрышем иг/
рока А при любых стратегиях игрока В. Выбранная игроком А вторая стратегия называется максиминной стратегией, а соответствующее ее значение выигрыша а2 = 6 д. е. будет нижней ценой игры.
Второй игрок стремится минимизировать свой проигрыш. Вы-брав первую стратегию (31} игрок В может проиграть не более чем (3j = max{10; 7; 6} = 10 д. е. независимо от выбора стратегии игроком А. Аналогично рассуждая, получим следующие результаты (д. е.):
Р2 = шах {4; 6; 2} = 6; Р3 = шах {11; 8; 1} = 11;
Р4 = шах {7; 20; 11} = 20.
Игрок В выбирает стратегию (32, которая минимизирует его максимальные проигрыши:
P = minP; =min{10;6;ll;20} = 6 д.е.
j
Величина Р = 6 д. е. будет гарантированным проигрышем игрока В при любых стратегиях игрока А. Выбранная игроком В вторая стратегия называется минимаксной стратегией, а соответствующее ее значение проигрыша Р2 = 6 д. е. будет верхней ценой игры.
Следует отметить, что для любой матрицы А = выполняется неравенство
Р > а. (9.37)
Если Р = а, т. е. верхняя цена равна нижней цене игры, то со-ответствующие чистые стратегии называются оптимальными, а про игру говорят, что она имеет седловую точку. Седловая точка является минимальным элементом соответствующей строки и максимальным элементом соответствующего столбца. Эта точка есть точка равновесия игры, определяющая однозначно оптимальные стратегии. Оптимальность здесь означает, что ни один игрок не стремится изменить свою стратегию, так как его противник может на это ответить выбором другой стратегии, дающей худший для первого игрока результат.
Величина С — Р = а называется ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при использовании ими оптимальных стратегий. В нашем примере цена игры С = 6 д. е., оптимальная пара стратегий — А2 и В2.
Если в платежной матрице А все элементы строки А{ = (аІЬ ai2, ..., аіп) не меньше соответствующих элементов строки Ак = (акЬ ак2,
акп), а по крайней мере один строго больше, то строка А{ называется доминирующей, а строка Ак — доминируемой.
Аналогичны понятия «доминирующий столбец» и «доминируемая строка».
Первому игроку невыгодно применять стратегии, которым соответствуют доминируемые строки; второму игроку невыгодно применять стратегии, которым соответствуют доминирующие столбцы. Поэтому при решении игры можно уменьшить размеры платежной матрицы путем удаления из нее доминирующих столбцов и доминируемых строк.
Пример 9.9. Для игры с платежной матрицей
2-3 5 А = 4 -2 3 6-14
найдите стратегии игроков и цену игры.
Решение
Элемент #32 = — 1 является наименьшим в третьей строке и на-ибольшим во втором столбце, т. е. он является седловой точкой. Поэтому цена игры С = — 1, а оптимальные стратегии игроков: первого — у43, а второго — В2.
Используя понятия доминируемых строк и доминирующих столбцов, задачу можно решить следующим образом.
В матрице А третья строка доминирует над второй, поэтому вторую можно изъять из платежной матрицы. В результате получится матрица
А =
2 -3 6 -1
В матрице Ах первый и третий столбцы доминируют над вторым, следовательно, их можно изъять. В результате платежная матрица принимает вид
-1
В матрице А2 вторая строка доминирует. После вычеркивания получится матрица А3, состоящая из одного элемента:
А3 = (-1).
Элемент матрицы А3 и определяет решение нашей задачи.
/> =
Отдельные игры могут не иметь седловых точек, т. е. у каждого игрока не существует единственной, наиболее надежной стратегии. В этом случае используют смешанную стратегию. Смешанная стратегия состоит в том, что в ходе игры происходит случайный выбор стратегии из некоторого множества смешанных стратегий и для каждой смешанной стратегии указывается вероятность ее выбора. Смешанная стратегия для игрока А представляет собой вектор
А? = (9.38)
где Pi — вероятность выбора /-й стратегии игроком и удовлетворяет следующим условиям:
Pi > о, / = Tjii;
(9.39)
/=і
Аналогично смешанная стратегия игрока В представляет собой вектор
Q =
(9.40)
где qj — вероятность выбора у-й стратегии игроком В — удовлетворяет следующим условиям;
ty>0,y= 1, п\
у=1
Платежная матрица игры имеет следующий вид (табл. 9.8): Xs\ в А Я\ Я2 Яъ Яп Р\ «11 «12 «13 «1 „ Pi «21 а22 «23 «2/1 Pi «31 «32 «33 ... «3 п К «ml «ет2 «етЗ ... «/я п
Игрок А выбирает стратегию Pt так, чтобы максимизировать на-именьший ожидаемый выигрыш по столбцам платежной матрицы, тогда как игрок В выбирает стратегию qj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически критерий минимакса при смешанных стратегиях может быть описан следующим образом. Игрок А выбирает стратегию Р,-, дающую
tn rtx rtx
(9.43)
max і mm
Р> I
ЪЩуРь Y,(*in-Pb
/=1 /=1 /=1
Игрок В выбирает стратегию qp дающую
minjmaxl 1
n n n
(9.44)
?ciij-qj, X a2j-qj,..., ? amj 'Qj
j=1 j=\ j=\
Когда стратегии P{- и qj оптимальны, то выполняется строгое равенство между максиминным ожидаемым выигрышем и мини-максным проигрышем, а результирующее значение равно оптимальному (ожидаемому) значению игры.
Этот вывод следует из теоремы фон Неймана о минимаксе. Теорема утверждает, что выражения (9.43), (9.44) имеют одно и то же значение M(Pq,Qq), называемое ценой игры. Если Рf и — оптимальные решения для обоих игроков, каждому элементу платежной матрицы atj соответствует вероятность /у . qj*. Следовательно, оп-тимальное ожидаемое значение игры
(9.45)
м{Ро,Оо)=ЪЪагР?.д/. /=1у=1
Цена игры заключена между нижней и верхней ценами, т. е. а < М(Р0, Со) * Р.
Решить конечную игру — это значит нужно найти векторы Р и Q (оптимальные стратегии), удовлетворяющие теореме о минимак- се, а следовательно, получить величину ожидаемого платежа М(Р0, С?о) ~ ЦенУ игры.
Свойство оптимальности означает, что любое отступление од-ного из игроков от оптимальной стратегии (при условии, что второй игрок продолжает придерживаться своей оптимальной стратегии) при многократном повторении игры может только уменьшить его средний выигрыш (увеличить средний проигрыш).
Решение игры обладает одним важным свойством: если игрок А использует свою оптимальную стратегию, а игрок В смешивает свои стратегии в любых пропорциях, то средний выигрыш игрока А не уменьшается. Стратегии, которые смешиваются для получения оптимальной стратегии, будем называть полезными. Доказано, что у игры т х п существует такое оптимальное решение, что число полезных стратегий с каждой стороны не превосходит минимального из чисел т мп.
Известно несколько методов нахождения оптимальных стратегий в играх двух лиц с нулевой суммой. Рассмотрим один из методов — метод линейного программирования для нахождения решения игр.
Пусть игра т х п не имеет оптимального решения непосредственно в чистых стратегиях, т. е. отсутствует седловая точка (а Ф Р). Оптимальное решение необходимо искать в области смешанных стратегий. Предположим, что все т стратегий игрока А полезные. Определим вероятности их применения в смешанной оптимальной стратегии. Обозначим эти вероятности через Ph і = 1,/и, а цену игры — через М. Оптимальная смешанная стратегия игрока А опреде-ляется из условия (9.43):
maxjmin
Пусть /
ТП тп тп
/=1 /=1 /=1
тп m тп
(9.46)
М - min
? ап ¦ Pi, ? о/2 • ph -, 2 am • Pi /=1 /=1 (=1 j
Поскольку при оптимальной стратегии средний выигрыш не меньше М при любой стратегии противника, то справедлива система п неравенств:
Рх-ап + Р2-а2х + ... + Pm-amX>M-,
Р\ ¦ «12 + Р2 ¦ "22 + - + Рпг ¦ ««2 * М\ ^ ^
Р\ ¦ а\п + р2 • о2п + ... + Рт ¦ атп > М,
т
или
%агР<>М, j = l,n. (9.48)
/=і
Тогда задача отыскания оптимальной смешанной стратегии игрока А может быть сформулирована в виде задачи линейного про-граммирования.
Для этого необходимо максимизировать Z = М при ограничениях
т —
SarPj>M, ./ = 1,л; /=1
(9.49)
т
Z/J = 1, i>>0, / = 1,т.
/=1
Введем новые неизвестные:
V -А v -А V Рт
Хх~М' Х2~М"'" т~ М'
Чтобы исключить возможность деления на нуль, увеличим цену игры на положительное число С. Для этого достаточно ко всем элементам матрицы Цд^-Ц прибавить одно и то же положительное число С, при этом все элементы ау сделать положительными. Следует отметить, что эта операция не меняет искомых оптимальных стратегий, поскольку
т т і
23=1, ТО 2*,—.
/=1 /=1 м
Разделим левую и правую части неравенств (9.48) и (9.49) на М, получим:
апхх + а21х2 + ... + атХхт > 1;
«12*1 + «22*2 + - + «т2*т * U
(9.50)
+ «2^2 + - + *
х!+х2+ ... + хт=—. (9.51)
В силу ТОГО ЧТО
max М = min-7- = mini*! + х2 + +
М 1 J
задача принимает вид
при ограничениях
Z= х{ + х2 + ... + хп
larXi> 1, j = l,n. /=1
Для игрока В оптимальная стратегия определяется из условия (9.44):
min j max
qj I
при ограничениях / \
n n n
X a2j X amjqj,
j=1 y=l y=l
(9.54)
qx + q2 + ... + qn = 1.
Эта задача записывается как симметричная двойственная задача линейного программирования к задаче игрока Л(9.52), (9.53): максимизировать
L = Y{ + У2 + ... + У„ (9.55)
при ограничениях
(9.56)
у=1
Yj>0,j = Т7п,
г 1 v qj • Г~
где
м'
Задачи игроков Л и 2? решают обычным симплекс-методом. Пример 9.10. Рассмотрим игру 3x4:
В 1 2 3 4 а, 1 4 3 2 -5 -5 2 -2 5 -1 4 -2 3 -3 2 -3 6 -3 Ру 4 5 2 6
Определим а,- и ру,
где а,- - минимум в /-й строке; Ру — максимум в j-м столбце.
Нижняя цена игры равна максимину а = —2, верхняя цена игры равна минимаксу (3 = 2. Так как а * 3, то седловая точка игры отсутствует, задача должна решаться в смешанных стратегиях.
Нижняя цена игры — число отрицательное (а = —2), поэтому, возможно, значение игры М не будет положительным. Число С, которое необходимо прибавить ко всем элементам матрицы, должно быть не меньше 2. Пусть С = 6. Тогда матрица принимает вид
В
1
9 11
1 10 12
1
2 3
10 4 3
Задача игрока В записывается в форме задачи линейного программирования
^max = Yl + Y2 + Y3 + У4 при ограничениях:
10У] + 9Y2 +8У3 + У4 <1;
4Уі +ПУ2 +5У3 +ЮУ4 <1;
3Yi + 8Г2+ЗУз+12Г4<1; Yj> 0, j =М.
Решая задачу симплекс-методом, получим:
Lmax = 0,16; Yi = 0; Y2 = 0; Г3 = 0,12; Y4 - 0,04. Таким образом, решением исходной задачи будет следующее:
О_Ї4_0,04
^-т-^іб"0,25-
В нашем примере первая и вторая стратегии игрока В бесполезны, так как = q2 = 0. При случайном чередовании третьей и четвертой стратегий с относительными частотами q3° = 0,75 и q4° = 0,25 соответственно игроку В обеспечен средний выигрыш в размере М = 0,25.
Оптимальные стратегии игрока А получаются из решения двойственной задачи.
В настоящее время развитие теории игр вышло далеко за пре-делы рассмотренного нами простейшего случая парных игр с нулевой суммой. Однако ограниченный объем книги не позволяет дать представление о более сложных разделах современной теории игр, таких, как множественные коалиционные игры, дифференциальные игры и др.
Задачи
9.1. Для пяти проектов технических систем определены относительные единичные показатели технического совершенства конструкции и коэффициенты весомости единичных показателей. Численные значения единичных показателей и коэффициентов весомости приведены в следующей таблице: Относительные единичные показатели Варианты времени технических слож веса автома мощно унифи систем ности подго-товки тизации сти кации I 1,0 0,088 1,0 1,0 0,72 0,614 II 0,72 1,0 0,8 0,78 0,81 0,420 III 0,658 0,358 0,765 0,782 0,525 0,915 IV 0,425 0,97 0,755 0,70 0,98 0,31 V 0,467 0,555 0,865 0,705 0,865 0,650 Коэффици енты веса 0,157 0,124 0,210 0,195 0,174 0,140
Проведите ранжирование проектов технических систем по комплексному критерию.
9.2. Одной из фирм требуется выбрать оптимальную стратегию по техническому обеспечению процесса управления производством. С помощью статистических данных и информации соответст- вующих заводов-изготовителей были определены локальные критерии функционирования необходимого оборудования. Исходные данные представлены в следующей таблице: Варианты оборудования Локальные критерии эффективности оборудования* производи-тельность, д. е. стоимость оборудования, д. е. объем памяти, у. е. надежность, у. е.
Коэффици-енты веса
* Значения л 100 150 120 200
0,25 окальных крит
4 7
0,20 ериев даны в у< 8
6,5
0,32 :ловных единиі 8
4
0,23
дах.
9.3. Для шести проектов транспортных устройств определены относительные единичные показатели технического совершенства конструкций. Численные значения единичных показателей и соответствующие весовые коэффициенты приведены в следующей таблице: Варианты Относительные единичные показатели транспорт скорос прочно пере устойчи металло мощно ных ти, сти, грузки, вости, емкости, сти, устройств Кг к¦ к5 V I 1,0 0,798 0,92 1,0 1,0 0,77 II 1,0 1,0 0,65 0,92 0,94 0,92 III 1,0 0,93 0,924 1,0 0,98 0,95 IV 0,87 0,96 0,91 0,915 0,99 0,85 V 0,85 0,97 1,0 0,90 0,7 0,82 VI 0,88 0,78 0,75 0,967 0,8 1,0 Коэффици енты веса 0,210 0,195 0,174 0,157 0,124 0,140
Проведите ранжировку проектов технических систем по комплексному критерию.
9.4. Абсолютные показатели качества двигателей различных вариантов приведены в следующей таблице: Варианты двигателей Показатели качества мощность, л. с. крутящий момент, кгс . м масса, кг 1 180 67 850 2 176 70 1000 3 176 68 860 4 181 67 820 5 177 68 860 6 180 66 800 7 175 69 900 8 176 67 850 9 180 68,2 880 10 179 38,5 870 Коэффициенты веса 0,4 0,24 0,36
Найдите оптимальный вариант двигателя.
9.5. Показатели эффективности работы предприятий приведе-ны в следующей таблице: Показатели эффективности работы предприятий N9 пред-приятия прибыль, д. е. себестои-мость единицы продукции, д. е. доходы, Д. е. фондо-отдача, у. е. произво-дитель-ность,
у. е. I
Весовые коэффи-циенты 30,0 25,0 40,0 28,0 15,0 50,0
0,32 40,0 20,0 45,0 30,0 12,0 30,0
0,23 20,0 30,0 54,0 35,0 20,0 40,0
0,15 0,2 0,3 0,1 0,4 0,25 0,21
0,20 300 200 250 160 280 120
0,10
Выберите наиболее эффективно работающее предприятие. 9.6. Рассмотрим следующую платежную матрицу (матрицу доходов): SI S4 15 12 1 -3 18 20 2 15 9 7 1 3 0 6 15 21 -2 5 R4 8 20 12 3 0 4
Вероятности состояний природы {5)} неизвестны. Определите оптимальную стратегию Rh используя критерии Лапласа и макси- мина. Сравните полученные решения.
Сравните решения в задаче 9.6 при использовании критериев Сэвиджа и Гурвица (положите а = 0,4).
Один из пяти станков должен быть выбран для изготовления партии изделий, размер которой Q может принимать три значения: 150; 200; 350. Производственные затраты Q для і станка задаются следующей формулой
С, = Р, + с, . Q.
Данные Pi и Сі приведены ниже в таблице: Показатели Модель станка 1 2 3 4 5 Р>
Сі ЗО 14 80 6 50 10 160 5 100 4
Решите задачу для каждого из следующих критериев Лапласа, Вальда, Сэвиджа и Гурвица (положите а = 0,6). Полученные решения сравните.
9.9. При выборе стратегии Rj (j = 1,3) каждому возможному со-стоянию природы S,{i = 1,4) соответствует один результат (исход) Vjid = 1,3; / = 1,4). Элементы Vjh являющиеся мерой потерь при принятии решения, приведены ниже в таблице (д. е.): Стратегии Состояние природы Ri 2 6 5 8 Ri 3 9 1 4 Ri 5 1 6 2
Выберите оптимальное решение в соответствии с критериями Лапласа, Вальда, Сэвиджа и Гурвица (при а = 0,5).
9.10. Намечается крупномасштабное производство легковых автомобилей. Имеются четыре варианта проекта автомобиля Rj(j = 1,4). Определена экономическая эффективность V» каждого проекта в зависимости от рентабельности производства. По истече-нии трех сроков St{i =1,3) рассматриваются как некоторые состояния среды (природы). Значения экономической эффективности для различных проектов и состояний природы приведены в следующей таблице (д. е.): Проекты Состояние природы Яг 20 25 15 я2 25 24 10 Яг 15 28 12 Я4 9 30 20
Требуется выбрать лучший проект легкового автомобиля для производства, используя критерии Лапласа, Вальда, Сэвиджа и Гурвица при а = 0,1. Сравните решения и сделайте выводы.
9.11. Определите тип электростанции, которую необходимо по-строить для удовлетворения энергетических потребностей комплекса крупных промышленных предприятий. Множество возможных стратегий в задаче включает следующие параметры:
Я{ — сооружается гидростанция;
Я2 — сооружается теплостанция;
Я3 — сооружается атомная станция.
Экономическая эффективность сооружения электростанции зависит от влияния случайных факторов, образующих множество со-стояний природы Sj[i =1,5).
Результаты расчета экономической эффективности приведены в следующей таблице: Тип станции Состояние природы Si Я* Ях 40 70 30 25 45 я2 60 50 45 20 30 Яз 50 30 40 35 60
9.12. Фирма рассматривает вопрос о строительстве станции технического обслуживания (СТО) автомобилей. Составлена смета расходов на строительство станции с различным количеством обслуживаемых автомобилей, а также рассчитан ожидаемый доход в зависимости от удовлетворения прогнозируемого спроса на предлагаемые услуги СТО (прогнозируемое количество обслуженных автомобилей в действительности). В зависимости от принятого решения — проектного количества обслуживаемых автомобилей в сутки (проект СТО) Rj и величины прогнозируемого спроса на услуги СТО — построена нижеследующая таблица ежегодных финансовых результатов (доход, д. е.): Проекты СТО Прогнозируемая величина удовлетворяемости спроса 0 10 20 30 40 50 20 — 120 60 240 250 250 250 30 -160 15 190 380 390 390 40 -210 -30 150 330 500 500 50 -270 -80 100 280 470 680
Определите наилучший проект СТО с использованием критериев Лапласа, Вальда, Сэвиджа и Гурвица (при а = 0,5).
9.13. Найдите седловую точку и значение игры для каждой из двух следующих игр. Платежные матрицы имеют вид:
6) -1 -5 6
'8 8 7
А=Ш\ =
ґ 4 -5 -4 -5 -6 -7
в=Ыг
10 -3 2 -10
9.14. Определите области значений х, для которых стратегии А2 и В2 будут оптимальными в следующих играх: (\ 4 (2 4 А = 5 X 9 ; 5 = 10 X 6 7
\ 3 4
) 4
V, 8 3
/
9.15. Определите, будут ли значения следующих игр больше, меньше или равны нулю:
' 2 10 5 0 > Г 4 8 -2 "31 3 4 9 6 1 0 А = 5 = 5 9 -5 3 -2 -4 -8 -3 5 5 8 5 -3 -5 ч / \ J {-2 8 5 7 г> 4 8 1 > -3 9 3 5 0 5 С = ; d = 2 4 2 0 6 1 -3 5 8
\ -1 9 3 ) < J
В задачах 9.16 — 9.30 решите игру с платежной матрицей.
9.16. ґ2 1 3 Ї 9.17. ґ3 1 2N А = 4 -1 -2 А = 2 4 -1 1
Ч 0 -3
J 5
\ 7 6 / 9.18. (2 3 6 5" 9.19. {4 5 6N А = 1 -2 1 3 А = 7 3 2 5
\ 4 3 0
> 2
\ 1 8
) 9.20. (2 3 1 2^ 9.21. 1 -1 3 А = 3 1
\ 5 2 2 4 3
1 ,
) А = 5 3
\ 2 7 5 9.22. 1 1 \ 9.23. ' 1 3 А = 2 -2 2 А = -1 4 і 3
к. 3 -3 > 6
ч -] I
9.24. 2 -1 3 4 9.25. 1 -1 3 > А = 1
0
\ 2 3 -2 5
/ 5 3
V 2 4 -4 0
) 9.26. (2 6 4 9.27. Г2 4 1 51 Л = 5 3 6 2 1 -1 3 2 . 7
\ 2 1 3 5
\ 2 -4 0
) 9.28. (2 1 Ъ 0' 9.29. (2 3 -1 4) А = 2 4 -1 5 3 2 4 1 5
\ 7 -4 3
J ,4 -1 0 -2
/ 9.30. А = ґ3 5 0 4 2 3 2 П 0 3 5 4
J