Принятие решения в условиях конфликта

Для обоснования решений в условиях конфликта разработаны специальные математические методы, которые рассматриваются в теории игр. Её возникновение относится к 1944г., когда вышла в свет монография

Неймана и Моргенштерна «Теория игр и экономическое поведение» [38]. В настоящее время теория игр превратилась в самостоятельное математическое направление, имеющее много практических приложений.

В отличие от раздела 1.6, когда параметром z управляла «природа», в условиях конфликта параметр z отражает действия «разумного» противника, преследующего собственные цели. Столкновение противоположных интересов участников приводит к возникновению конфликтных ситуаций. Необходимость анализировать такие ситуации привела к возникновению теории игр, задачей которой является выработка рекомендаций по рациональному образу действий участников конфликта.

В дальнейшем рассматриваются только стратегические игры, в отличие от комбинаторных и азартных игр, когда источник неопределённости состоит в отсутствии информации о действиях противника, о его стратегии.

Рассмотрим модель игры более подробно. Если сталкиваются интересы двух противников, игра называется парной, если более двух – множественной.

Так как наибольшее практическое значение имеют парные игры, то рассмотрим только их. Итак, участников игры двое – А и В. Задано множество стратегий Х, игроков А и В. Соответственно:

Простейший вид стратегической игры – игра двух лиц с нулевой суммой (сумма выигрышей равна нулю). Выбор стратегии каждым из игроков производится при полном незнании выбора другого игрока. В результате выигрыш и каждого из игроков удовлетворяет соотношению:

(1.39)

откуда, если

,

 

то

 

Цель игрока А – максимизировать функцию , в свою очередь, цель игрока В – минимизировать эту же функцию.

Пусть Составим матрицу

Матрица А называется платёжной, её строки соответствуют стратегиям , столбцы – стратегиям , элемент – выигрыш игрока А, если он выбрал стратегию , а игрок В – стратегию .

Игрок А, не зная информации о выборе стратегии игроком В, должен сделать такой выбор, чтобы максимизировать свой минимальный выигрыш:

(1.40)

где a – гарантированный выигрыш игрока А – называется нижней ценой игры.

Стратегия , обеспечивающая получение a, называется максиминной.

Соответственно игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии его проигрыш не превысит максимального из значений элементов j -го столбца матрицы, т. е. меньше или равен . Естественно, что игрок В выберет такое значение j, при котором его максимальный проигрыш b минимизируется:

 

. (1.41)

Величина b называется верхней ценой игры, а соответствующая выигрышу b стратегия минимаксной.

Фактический выигрыш игрока А при разумных действиях партнёров ограничен нижней и верхней ценой игры. Если же эти выражения равны

 

, (1.42)

то выигрыш игрока А – вполне определённое число, и игра называется вполне определённой, а выигрыш (1.42) называется решением игры и равен элементу матрицы .

Вполне определённые игры называются играми с седловой точкой, а элемент называется седловой точкой.

Седловой точке соответствует оптимальные стратегии игроков, их совокупность является решением игры, которое обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого отклонение от его оптимальной стратегии не может быть выгодно.

 

Пример 1.6

 

Игры заданы платёжными матрицами:

 

 

Для матрицы А₁: a ₁ = 3, b ₁ = 4.

Для матрицы А₂: a ₂ = 2, b ₂ = 2.

Таким образом, цена второй игры n = 2, решение игры состоит в выборе игроком А стратегии х₂, а игроком В – стратегии у₂. Легко видеть, что отклонение одним из игроков от оптимальной стратегии приводит к уменьшению выигрыша для игрока А и к увеличению проигрыша для игрока В.

 

Итак, если игровая матрица содержит седловую точку, то решение игры известно. Возникает вопрос нахождения решения для игр, матрицы которых не содержат седловой точки, в этих играх .

Естественным для каждого игрока является вопрос увеличения выигрыша (уменьшения проигрыша). Поиски такого решения состоят в том, что игроки применяют не одну, а несколько стратегий, причём выбор стратегий осуществляется случайным образом. Случайный выбор игроком своих стратегий называется смешанной стратегией.

В данной игре стратегии игрока А задаются набором вероятностей:

 

 

а стратегии игрока В задаются набором вероятностей:

 

 

,

 

 

причём: .

Стратегии игроков А и В, для которых вероятности и отличны от нуля, называются активными.

Согласно основной теореме игр [38], каждая конечная игра имеет, по крайней мере, одно решение, которым может быть и смешанная стратегия. При использовании смешанной стратегии выигрыш игрока А – случайная величина с математическим ожиданием:

 

,

 

или в векторной записи . Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры n:

 

. (1.42)

 

Для оптимальных стратегий имеет место соотношение:

 

. (1.43)

 

Применение игроком А стратегии оптимальной стратегии Р* должно обеспечить ему при любых действиях игрока В математическое ожидание выигрыша не меньше цены игры n. Поэтому выполняются соотношения:

(1.44)

 

Аналогично для игрока В оптимальная стратегия должна обеспечить ему при любых действиях игрока А проигрыш, не превышающий цену игры n, т. е. справедливо соотношение:

 

(1.45)

 

Соотношения (1.44) и (1.45) могут быть использованы при построении формальных математических моделей для определения решения игры.

Рассмотрим, как выглядит модель выбора для определения стратегии при использовании соотношения (1.44). Введём новые переменные Тогда (1.44) перепишется следующим образом:

(1.46)

а из условия следует, что

. (1.47)

 

 

Так как решение игры должно максимизировать значение n, то для выбора оптимальной смешанной стратегии игрока А необходимо найти:

(1.48)

 

при

 

Аналогично может быть сформулирована задача для выбора оптимальной смешанной стратегии игрока В с использованием (1.45):

найти (1.49)

при

 

Как видно из соотношения (1.48) и (1.49) для решения игры имеем пару двойственных задач линейного программирования. Используя свойство симметричности, можно решить одну из них, требующую меньших вычислений, а решение второй задачи найти, используя результаты теории двойственности (см. главу 2).

 

Пример 1.7 [34]

 

Рассматривается игра в хоккей. В одном из периодов состояния команд А и Б характеризуется следующим образом:

 

у команды А – 4 играющих пятёрки,

у команды Б – 3 играющих пятёрки.

 

Матрица игрового преимущества имеет вид:

 

 

Задача (1.48) представлена в виде следующей модели:

 

при

 

Оптимальное решение задачи методом линейного программирования (см. главу 2) выглядит следующим образом:

 

 

Таким образом, цена игры равна , а оптимальные вероятности использования чистых стратегий в смешанной стратегии тренеров команды А определились следующим образом:

 

 

Поэтому в данном игровом периоде тренеру команды А необходимо реже выпускать первую пятёрку, а четвёртую вообще не включать в игру.

Аналогично может быть сформулирована оптимальная стратегия и для команды Б.

 

Содержание предыдущих разделов убеждает в том, что среди математических методов, используемых в теории принятия решений, особую роль играют методы решения оптимизационных задач. Они составляют фундамент системы математического обеспечения проблем принятия решений. Этим вопросам будет посвящено содержание следующего раздела.

Примеры построения операционных моделей

Пример 1.8. Линейные модели

Транспортная задача

Предположим, что однородный продукт должен быть перевезен из т пунктов производства в п пунктов потребления, причем из каждого пункта производства вывозится установленное количество и в каждый пункт потребления ввозится также установленное количество продукта, так что общие спрос и предложение равны. Пусть из i -го пункта производства (i =1, 2,..., m) вывозится a_i продукта, а в j -й пункт потребления должно быть ввезено b_j продукта, причем величины эти известны. Тогда:

, (1.50)

 

 

где для всех i ¹ j.

Пусть x_{i j} – неизвестное количество продукта, которое должно быть перевезено из i -го пункта производства в j -й пункт потребления.

Тогда:

(1.51)

, (1.52)

где ³ 0 для всех i и j.

Пусть стоимость перевозки из i -го пункта производства в j -й пункт потребления равна . Эти величины также заданы. Задача состоит в том, чтобы найти , удовлетворяющие приведенным выше ограничениям (1.51), (1.52) и минимизирующие

 

. (1.53)

 

Задача поставщика

 

Владелец кафе знает, что в связи с наступлением праздников в течение одной следующей недели ему в j -й день () потребуется r_j чистых салфеток:

 

 

Понед.	Вторник	Среда	Четверг	Пятница	Суббота	Воскр.

 

На стирку обычно требуется три дня, т.е. грязная салфетка отправленная в стирку в j -й день, вернется из стирки и может быть использована в (j+3) -ийдень. Однако в прачечной существует ускоренное обслуживание по повышенному тарифу, при котором салфетки возвращаются из стирки через два дня. Не имея на руках или в прачечной готовых к употреблению салфеток, владелец будет вынужден покупать салфетки по 25 рублей за штуку.

Стоимость стирки – 10 и 15 рублей соответственно при обычном обслуживании и при ускоренном обслуживании. Как должен вести дело владелец кафе, чтобы удовлетворить потребность кафе в салфетках и минимизировать издержки за неделю?

Построим математическую модель. Пусть x _i, () количество новых салфеток, купленных в соответствующий день недели, Аналогично, пусть y _i, z _i, () – количество салфеток, отправленных в стирку по повышенному или по обычному тарифу. Наконец, пусть u _i, () – количество грязных салфеток, не отправленных в стирку в соответствующий день.

Так как необходимо минимизировать общую сумму, требуемую для поддержания количества салфеток на должном уровне, не следует покупать салфеток больше, чем требуется в данный день, или отправлять салфетку в прачечную, если она не будет использована в дальнейшем.

 

В первый день, т.е. в понедельник, необходимо купить такое количество салфеток, какое требуется, т.е. x ₁ = 5.

В этот день можно выбирать: послать ли все или некоторые из пяти грязных салфеток в быструю, медленную прачечную или оставить их в ящике для грязных салфеток. То, что происходит с этими пятью салфетками можно представить уравнением:

 

y₁ + z₁ + u₁ = 5. (1.54)

 

Общая стоимость всех операций первого дня:

 

25x₁ +15y₁ + 10z₁ (1.55)

 

Выпишем остальные ограничения данной модели, помня о том, что в нашей системе выстиранные салфетки возвращаются через 2 или 3 дня в зависимости от того, какой прачечной мы воспользовались.

 

Во вторник необходимо купить некоторое количество салфеток, а именно x₂ = 6. После того, как их используют, мы поступим с ними и u₁ грязными салфетками согласно уравнению:

y₂ + z₂ + u₂ = 6 + u₁. (1.56)

 

Оно выражает тот факт, что у нас скопилось u₁ грязных салфеток, оставшихся с понедельника и еще 6, оставшихся со вторника. Можно их отправить в стирку (y₂ + z₂), либо оставить в ящике с грязными салфет-ками (u₂). Стоимость всех операций во вторник:

 

25x₂ + 15y₂ + 10z₂. (1.57)

 

В среду нам потребуется 7салфеток. Это первый день, когда выстиранные салфетки из быстрой стирки можно употребить в дело. Поэтому нужные 7 салфеток можно получить, купив их или взяв их из того количества салфеток, которые были сданы в стирку в понедельник. Имеем:

 

x₃ + y₁ = 7. (1.58)

Так же, как и ранее

y₃ + z₃ + u₃ = 7 + u₂, (1.59)

 

а стоимость операции в среду равна:

 

25x₃ + 15y₃ + 10 z ₃. (1.60)

 

Необходимые в четверг 8 салфеток могут быть либо новыми, либо выбранными из числа тех, которые мы посылали в быструю прачечную во вторник или в медленную прачечную в понедельник. Это можно записать как:

x₄ + y₂ + z₁ = 8 (1.61)

y₄ + z ₄ + u₄ = 8 + u₃, (1.62)

 

а стоимость операций в четверг составит:

 

25x₄ + 15y₄ + 10z₄.

 

Предположим, что нас интересует только одна неделя и, следовательно, мы не будем отдавать салфетки в стирку, если они не вернутся назад к воскресенью.

Для пятницы имеем:

x₅ + y₃ + z₂ = 7. (1.63)

y₅ + u₅ = 7 + u₄ (1.64)

а стоимость равна:

25x₅ + 15y₅. (1.65)

Для субботы:

x₆ + y₄ + z₃ = 9 (1.66)

 

u₆ = 9 + u₅,

а стоимость равна 25 x₆ .

 

Для воскресенья имеем:

x₇ + y₅ + z₄ = 10 (1.67)

u₇ = 10 + u₆,

а стоимость равна 25 x₇.

 

Объединяя полученные выше уравнения, получаем математическую модель операции:

при условиях:

Пример 1.9. Нелинейные модели