Решение игр 2хn и mx2

Не доказывая, отметим, что любая конечная игра mxn имеет решение, в котором число активных стратегий каждого игрока не превосходит l, где l=min(m,n). Следовательно, у игры2хn или mx2 всегда имеется решение, содержащее не более двух активных стратегий у каждого из игроков. Если эти активные стратегии игроков будут найдены, то игра 2хn или mx2 превращается в игру 2х2, решение которой осуществляется элементарно.

Практически решение игры 2хn осуществляется следующим образом:

1) Строится графическое изображение игры;

2) Выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры γ;

3) Определяется пара стратегий, пересекающихся в точке оптимума.

Эти стратегии являются активными стратегиями игрока II. Таким образом, игра 2хn сведена к игре 2х2. Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них.

Решение игры 2х2 осуществляется аналогично. Следует, однако. Отметить, что при решении игры mx2 выделяется точка оптимума с наименьшей ординатой.

57. Приведение матричной игры к задаче линейного программирования.

Для игр, у которых один из игроков имеет три стратегии, а другой – произвольное количество, можно построить пространственную геометрическую интерпретацию. Однако такая геометрическая интерпретация менее наглядна, чем плоская. В случае игры mxn, где m>3, n>3, графическое изображение вообще построить невозможно. Однако такую игру с конечными значениями m и n можно свести к паре двойственных задач линейного программирования.

Рассмотрим игру, заданную платежной матрицей размерности mxn (см.табл.1).

Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое достаточно большое число L, переводящее платежи в область неотрицательных значений). При этом цена игры увеличится на L, а решение задачи не изменится. Следовательно, можно принять, что γ>0.

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

p_A^*=(р₁,р₂,…,p_m); q_B^*=(q₁, q₂,…,q_n).

Применение игроком I оптимальной смешанной стратегии p_A^*=(р₁,р₂,…,p_m) гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цене игры γ.

1, n

Предположим, что игрок II применяет свою чистую стратегию B_j, а игрок I – свою оптимальную стратегию p_A^*. Тогда средний выигрыш игрока I будет равен γ_j=a_1jp₁+a_2jp₂+…+a_ijp_i+…+a_mjp_m, j=.

Таблица 1

II I	B1	B2	…	Bj	…	Bn
A1	a11	a12	…	a1j	…	a1n
A2	a21	a22	…	a2j	…	a2n
…	…	…	…	…	…	…
Ai	ai1	ai1	…	aij	…	ain
…	…	…	…	…	…	…
Am	am1	am1	…	am1	…	amn

1, n

Учитывая, что γ_j, j= не может быть меньше γ, можем записать условия:

a₁₁p₁+a₂₁p₂+…+a_i1p_i+…+a_m1p_{m ≥γ;}

a₁₂p₁+a₂₂p₂+…+a_i2p_i+…+a_m2p_{m ≥γ;}

………………………………………

a_1jp₁+a_2jp₂+…+a_ijp_i+…+a_mjp_{m ≥γ;}

a_1np₁+a_2np₂+…+a_1np_i+…+a_mnp_{m ≥γ;}

a₁₁p₁+a₂₁p₂+…+a_i1p_i+…+a_m1p_{m ≥}γ_;

a₁₂p₁+a₂₂p₂+…+a_i2p_i+…+a_m2p_{m ≥}γ_;

……………………………………… (12.4)

a_1jp₁+a_2jp₂+…+a_ijp_i+…+a_mjp_{m ≥}γ_;

a_1np₁+a_2np₂+…+a_1np_i+…+a_mnp_{m ≥}γ_;

Разделив левую и правую части каждого из неравенств (12.4) на цену игры γ>0, получим:

1, n.

Pm γ

Pi γ

P2 γ

P1 γ

a_{1j +} a_2j +…+a_ij +…+ a_{mj ≥1,} j = (12.5)

Введем новые обозначения:

	Pi γ		1, n.

=x_i, i= (12.6)

Тогда неравенства (12.5) запишутся в виде:

a₁₁x₁+a₂₁x₂+…+a_i1x_i+…+a_m1x_{m ≥1;}

a₁₂x₁+a₂₂x₂+…+a_i2x_i+…+a_m2x_{m ≥1;}

……………………………………… (12.7)

a_1jx₁+a_2jx₂+…+a_ijx_i+…+a_mjx_{m ≥1;}

………………………………………

a_1nx₁+a_2nx₂+…+a_1nx_i+…+a_mnx_{m ≥1,}

где все x_i≥0, так как p_i≥0, γ>0.

Из равенства p₁+p₂+…+p_m=1 и в силу выражения (12.6) следует, что переменные (x_i) удовлетворяют условию:

γ

x₁+x₂+…+x_n+…+x_m =,

Учитывая, что игрок I стремится максимизировать γ, получаем линейную функцию: f(x)=x₁+x₂+…+x_k+…+x_m → min. (12.8)

1, m,

Следовательно, задача решения игры свела к следующей задаче линейного

программирования: найти неотрицательные значения переменных xi, i=

минимизирующие линейную функцию (12.8) и удовлетворяющие ограничениям (12.7).

Из решения задачи линейного программирования находим цену игры γ и оптимальную стратегию p_A^*=(р₁,р₂,…,p_m) игрока I по формулам:

; ,

Оптимальную стратегию q_B^*=(q₁, q₂,…,q_n) игрока II находим из выражения , где uj – неотрицательные переменные задачи линейного программирования:

f(u)=u₁+u₂+…+u_j+…+u_n → max;

a₁₁u₁+a₂₁u₂+…+a_1ju_j+…+a_1nu_{n ≤1;}

a₁₂u₁+a₂₂u₂+…+a_2ju_j+…+a_2nu_{n ≤1;}

……………………………………

a_m1u₁+a_mju₂+…+a_mju_j+…+a_mnu_{n ≤1,}

которая является двойственной по сравнению к задаче, представленной условиями (12.7) и (12.8).

Здесь, как и ранее, переменные

Таким образом, оптимальные стратегии p_A^*=(р₁,р₂,…,p_m) и q_B^*=(q₁,q₂,…,q_n) игры с платежной матрицей (a_ij) mхn могут быть найдены путем решения симметричной пары двойственных задач линейного программирования.

Исходная задача Двойственная задача

При этом

ПРИМЕР Найти решение и цену игры, платежная матрица которой представлена в таблице Математические модели пары двойственных задач линейного программирования будут выглядеть следующим образом.

Исходная задача Двойственная задача

Найти неотрицательные значения Найти неотрицательные значения переменных x₁, x₂, x₃, минимизирующие u₁, u₂, u₃, максимизируюшие функцию функцию

f(x)=x₁+x₂+x₃ f(u)=u₁+u₂+u₃

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

x₁+3x₂+x₃≥1; u₁+2u₂+3u₃≤1;

2x₁+x₂+3x₃≥1; 3u₁+u₂+u₃ ≤1;

3x₁+x₂+x₃ ≥1. u₁+3u₂+u₃ ≤1.

Таблица 2

II I	B1	B2	B3
A1
A2
A3

Решим вторую задачу симплексным методом, для чего условие поместим в табл. 12.24 (БП – базисная переменная; СП – свободная переменная).

Таблица 3

СП БП	-u1	-u2	-u3
v1
v2
v3
f(u)	-1	-1	-1

Проводя последовательные преобразования симплексных таблиц, на третьей итерации получим оптимальное решение (табл. 12.25).

Таблица 4

СП БП	-v2 -v3 -v4
u3 u1 u2		1/9 2/9 2/9
f(u)	2/9 1/9 2/9	5/9

Оптимальное решение задачи линейного программирования (ЛП) следующее: v₁=v₂=v₃=0; u₁=u₂=2/9; u₃=1/9; f(u)=5/9.

Находим оптимальную смешанную стратегию игрока II и цену игры γ:

; ;

; ;

Следовательно, q_B^*=(q₁, q₂,…,q_n)= .

Оптимальное решение первой задачи найдем, используя двойственные оценки; находящиеся в строке функции f(u) талб.12.25:

.

Отсюда определяем вероятности применения стратегий игроком I:

; ;

.

Таким образом, p_A^*=(р₁,р₂,…,p_m)= .

58. Теория принятия решений.

М с тоды прим я г и я он г и м а л ьн ы х р с шс и и й, в к л ю чая и с е л е л о в а н и с опера ц и и: • оптимальное (математическое) программирование (линейное, нелинейное, дискретное, блочное, стохастическое программирование и др.);

• сетевые модели планирования и управления;

• программно-целевые методы планирования и управления;

• теория управления запасами;

• теория массового обслуживания;

• теория игр;

• теория расписаний;

• теория решений и др.

Э к о н о м и ч е с к а я к и б е р н е т и к а:

• системный анализ экономики;

• теория экономической информации, включая экономическую

семиотику;

• теория автоматизированных систем управления.

Методы э к с п е р и м с н т а л ь н о г о изучения э к о н о м и ч е с к и х явлений:

• методы машинной имитации;

• «деловые игры»;

• методы реального экономического эксперимента.

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

Элементы теории принятия решений.

Классификация решений

Будем говорить о принятии решений при управлении; опираясь на интуитивное понятие решения, как способа устранения проблемной ситуации.

Проблемная ситуация предполагает наличие:

• цели;

• ресурсов;

• альтернатив (способов действий);

• свойств окружающей среды.

Проблемная ситуация предполагает неудовлетворенность лица, принимающего решения («целеустремленное состояние»), и необходимость действий для устранения проблемы. Это может быть:

• снятие проблемной ситуации, т. е. такое изменение целей, при котором неудовлетворенность исчезает;

• разрешение — изменение свойств окружающей среды или ресурсов;

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

Пример 1. Проблемная ситуация: мальчик показывает пальчиком на Луну и говорит «Мама, дай!».

1. Снятие ситуации — мамочка популярно объясняет сынуле: «Луна — это бяка, возьми-ка лучше яблочко!». Целеустремленное состояние переведено в другое русло и проблемная ситуация снята.

2. Разрешение ситуации — Луна срывается с орбиты и прилетает в руки мальчика (изменение физических законов и свойств окружающей среды). Вряд ли это хорошо кончится для мальчика, да и для всего населения Земли (см. в качестве иллюстрации рассказ Г. Дж. Уэллса «Человек, который творил чудеса»).

3. Решение ситуации. Этот мальчик - - Нил Армстронг. Он вырастает, поступает в отряд астронавтов НАСА и в августе 1969 г. первым в истории человечества оказывается на лунной поверхности. Целеустремленный индивид не изменяет своей цели, а достигает ее в рамках имеющихся ресурсов, альтернатив и физических законов.

Для описания проблемной ситуации можно использовать целевую функцию управляемого объекта, это некоторая зависимость (это может быть вектор-функция G):

G =G(x) = G(m,u),

где х — переменные, влияющие на G, причем х = {m,u}, где, в свою очередь, т — управляемые переменные (management); и - неуправляемые (т. с. действия внешней среды).

Множество альтернатив задастся ограничениями x ,Х = {M,U} где m M — множество допустимых значений управляемых переменных; г U — пределы изменения неуправляемых переменных.

Целью в этом случае обычно является оптимизация.

Построение G предполагает наличие математической модели объекта

G(m,u)=G(m,u,Y)=G(m,u,P(m,u)).

Классификацию решений можно провести по ситуации выбора:

А. Условия определенности — если С(m,u) известна и u — фиксирована (детерминированная модель объекта).

Б. Условия риска — здесь функция G(m,u) известна, а внешние неуправляемые переменные (u e U) являются случайными величинами с известными законами распределения (стохастическая, или вероятностная модель).

В. Условия конфликта — G(m,u) известна, u U — выход враждебно настроенной системы (например, игровая модель).

Г. Условия неопределенности — G(m,u) неточно известна или не полностью построена (формализована), либо нет информации об u или U.

59. Область применимости теории принятия решений.

Проблемная ситуация: мальчик показывает пальчиком на Луну и говорит «Мама, дай!».

1. Снятие ситуации — мамочка популярно объясняет сынуле: «Луна — это бяка, возьми-ка лучше яблочко!». Целеустремленное состояние переведено в другое русло и проблемная ситуация снята.

2. Разрешение ситуации — Луна срывается с орбиты и прилетает в руки мальчика (изменение физических законов и свойств окружающей среды). Вряд ли это хорошо кончится для мальчика, да и для всего населения Земли (см. в качестве иллюстрации рассказ Г. Дж. Уэллса «Человек, который творил чудеса»).

3. Решение ситуации. Этот мальчик - - Нил Армстронг. Он вырастает, поступает в отряд астронавтов НАСА и в августе 1969 г. первым в истории человечества оказывается на лунной поверхности. Целеустремленный индивид не изменяет своей цели, а достигает ее в рамках имеющихся ресурсов, альтернатив и физических законов.

Для описания проблемной ситуации можно использовать целевую функцию управляемого объекта, это некоторая зависимость (это может быть вектор-функция G):

G =G(x) = G(m,u),

где х — переменные, влияющие на G, причем х = {m,u}, где, в свою очередь, т — управляемые переменные (management); и - неуправляемые (т. с. действия внешней среды).

Множество альтернатив задастся ограничениями x ,Х = {M,U} где m M — множество допустимых значений управляемых переменных; г U — пределы изменения неуправляемых переменных.

Целью в этом случае обычно является оптимизация.

Построение G предполагает наличие математической модели объекта

G(m,u)=G(m,u,Y)=G(m,u,P(m,u)).

Классификацию решений можно провести по ситуации выбора:

А. Условия определенности — если С(m,u) известна и u — фиксирована (детерминированная модель объекта).

Б. Условия риска — здесь функция G(m,u) известна, а внешние неуправляемые переменные (u e U) являются случайными величинами с известными законами распределения (стохастическая, или вероятностная модель).

В. Условия конфликта — G(m,u) известна, u U — выход враждебно настроенной системы (например, игровая модель).

Г. Условия неопределенности — G(m,u) неточно известна или не полностью построена (формализована), либо нет информации об u или U.

Пример 59.2. Пусть некоторая организация покупает единицу товара по 10 долл., упаковывает и продает по 20 долл. Тогда, в зависимости от стратегии закупки (т,) и состояния внешней среды (спрос и,), которые (предположим) имеют следующие допустимые значения:

М= < m₁, m₂, m₃ >; = < 100, 200, 300 >;

U= < u₁,…, u₄ >; = <0, 100, 200, 300 >;

может быть заполнена табл. (модель проблемной ситуации — платежная матрица).

Таблица 1.1. Пример платежной матрицы проблемной ситуации и классификация методов принятия решений

Спрос/закупка	uj	Принятие решений в условиях
u1	u2	u3	u4	Определенности, риска конфликта	Неопределенности
				А	Б	В	Г.1	Г.4
mi	m1		-1000						-1000*	500*
m2		-2000				2000*	1400*	-2000	500*
m3		-3000	-1000					-3000		1200*

В левой части таблицы размещены значения Y_ij(m_i,, u _j ).

Элемент Y_ij{m_i,, и _j) данной части показывает, какова будет прибыль организации, если закупки составляют m_i „ а спрос равен и _j.

Нетрудно удостовериться, что Y_ij{m_i,, u _j ). вычисляется по следующему правилу:

Y_ij =min< m_i,, u _j>*20- m_i *10= Y{m, u )

например, Y₁₂ =-1000+2000=1000

В правой части размещены результаты применения различных критериев принятия решений.

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

A. Условия о п р е д е л е н н о с т и — пусть известно, что и = и₃= 200, тогда очевидно, что оптимальным решением является m* = m₂= 200; G(m_i) = G(m_i, u₃)

Это оптимизация в условиях определенности. Метод решения здесь — простой перебор альтернатив (столбец «А»).

Б. У с л о в и я риска — здесь может быть задана f{u) — функция распределения вероятностей различных значений u U.

Предположим, известно, что P(u₁) =0, Р{и₂) =0,3, Р(и₃) =0,5, Р{и₄) = 0,2.

Тогда (математическое ожидание значения прибыли):

G(m₁) = -1000*0+1000*0,3+1000*0,5+1000*0,2=1000

G(m₂) = -2000*0+0*0,3+2000*0,5+2000*0,2=1400

G(m₃) = -3000*0 - 1000*0,3+1000*0,5+3000*0,2=800

Отсюда оптимальное управление есть т*= т₂ (столбец «Б»).

B. У с л о в и я ко н ф л и к т а (подробно решение в таких условиях будет рассматриваться при анализе прямоугольных игр). Здесь вводится предположение о том, что для любых mi «стратегия внешней среды» (или «природы») — убудет наименее благоприятной (для всех m_i,, u _j такова, что гарантирует min Y_ij).

Поэтому здесь выбирают «наименьшее зло» — выписываются минимумы строк: m₁ → – 1000, m₂ → – 2000, m ₃ → – 3000

из которых выбирается максимум (что соответствует здесь стратегии m₁).

Г. Условия н е о п р е д е л е н н о с т и — поскольку здесьнет информации (даже стохастического характера) для предсказания значения и U, приходится использовать методы искусственного снятия неопределенности.

60. Критерий принятия решений в условиях неопределенности.

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

В отношении вероятностей различных реализаций исхода операции возможны два случая:

1). Вероятности возможных исходов операции не имеют физического смысла;

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

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

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

1). Стратегические неопределенности – неопределенные факторы, появляющиеся за счет участия в операции нескольких оперирующих сторон;

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

Несовпадение целей оперирующих сторон многосторонней операции создает конфликтную ситуацию принятия решений. Подобные задачи принятия решений (ЗПР) называются конфликтными. Конфликтные ЗПР можно разделить на одноуровневые и многоуровневые. В одноуровневых ЗПР участники операции не связаны никакими формами подчинения, действующими на одном уровне власти. Многоуровневые ЗПР возникают в сложных системах управления, имеющих иерархическую структуру. Для них характерно наличие нескольких уровней управления, из которых низшие подчинены высшим, но в тоже время обладают некоторыми правами в отношении принятия самостоятельных решений. Цели низших уровней управления не всегда совпадают с целями высших уровней.

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

Воспользуемся данными примера 59.2 для определения критериев.

1. Критерий Лапласа— Байеса (предполагается, что вероятности наступления различных состояний среды

u U= < u₁,…, u₄ >; = <0, 100, 200, 300 >,

равны между собой (P(u_i)= 0,25 для всех i)).

Тогда (столбец Г. 1):

Здесь две оптимальные стратегии

2. Критерий Вальда (пессимистический, или максиминный), ситуация сводится к ситуации в условиях конфликта:

3. Оптимистический (или максимаксный)

G(m₁) = 1000, G(m₂) = 2000, G(m₃) = 3000, G(m_i) =

4. Критерий Гурвица (или смешанный критерий, строящийся на основе оптимистического и пессимистического критериев):

здесь α — «степень пессимизма» (при а = 1 критерий превращается в критерий Вальда и наоборот).

Пусть α = 0,3, что ближе к «оптимистическому критерию» (столбец Г.4):

5. Критерий Сэвиджа — минимальных сожалений или упущенных возможностей. Строится таблица (табл.) сожалений () по следующим правилам:

в каждом столбце выбирается ;

«мера сожаления» вычисляется как разность:

Таблица К определению критерия «минимальных сожалений»

	-1000	+1000	+2000	+3000
mi	m1	-1000-(-1000)=0	+1000-1000=0	2000-1000=1000	3000-1000=2000
m2	-1000-(-2000)=1000	+1000-0=1000	2000-2000=0	3000-2000=1000	1000*
m3	-1000-(-3000)=2000	+1000-(-1000)=2000	2000-1000=1000	3000-3000=0

Элементы этой таблицы соответствуют нашим сожалениям о том, что мы не знаем ожидаемой «стратегии природы».

Затем таблица сожалений () обрабатывается по «пессимистическому критерию»: в каждой строке определяется максимум (последняя колонка таблицы), из которых выбирается минимум (т.е. )

Такова классификация методов принятия решений по ситуациям решения.

[2] Напомним, что при многократном повторении игры средний выиг­рыш близок к математическому ожиданию.