Решение задачи одним из математических методов

Вид материала

Решение

Содержание 46. Решение матричной игры в чистых стратегиях 47. Решения игр в смешанных стратегиях 48. Приведение матричной игры к задаче ЛП. 49. Динамическое программирование

Подобный материал:

• Задачи нелинейной и дискретной оптимизации. Методы решения. Постановка и экономико-математическая, 25.18kb.
• Задачи линейного программирования и задачи математической экономики Методика преподавания, 19.49kb.
• Бравый Евгений Ильич, 55.95kb.
• Тематический план учебной дисциплины, 52.63kb.
• Анализ методик использования моделирования в процессе обучения дошкольников математике, 472.24kb.
• Одним из эффективных математических методов для определения зависимости по множеству, 139.29kb.
• Д э. н. М. В. Грачева, зав кафедрой «Математических методов анализа экономики», 20.32kb.
• Задачи внеклассного занятия: Рассмотреть практическое применение математических знаний, 95.15kb.
• Практических: 0 Лабораторных, 16.63kb.
• Практических: 34 Лабораторных, 24.5kb.

46. Решение матричной игры в чистых стратегиях

Если имеются седловые точки (α=β), то игра решается в чистых стратегиях. Для игры с седловой точкой нахождение решения состоит в выборе максиминной и минимаксной стратегий, которые являются оптимальными. Они определяются соответственно по формулам: α=max(min aij) и β=min(max aij).

Пример:

Игрок 1: стратегии А1, А2, А3. Игрок 2: стратегии В1, В2, В3.

	В1=1	В2=2	В3=3
А1=1	0	-1	-2
А2=2	1	0	-1
А3=3	2	1	0

Составим плетжную матрицу:

	(	0 -1 -2	)
А=		1 0 -1
		2 0 0

α=max(-2, -1, 0)=0

β =min(2, 1, 0)=0

α=β=V=0 – седловая точка. Оптимальная стратегия 1 А3, 2 – В3. Отклонение 1 от оптимальной стратегии уменьшит его выигрыш, отклонение 3 от В3 увеличит его проигрыш.


47. Решения игр в смешанных стратегиях

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

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

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

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

Пусть вектор U=(U1,… Un) – стратегия игрока 1. Ui≥0, i=1,m. i=1Σm Ui=1, а вектор Z=(Z1,… Zn) – стратегия игрока 1. Zj≥0, j=1,m. j=1Σn Zj=1.Смешанные стратегии игроков 1 и 2 обозначим через S1 = (p1p2,…, pm) и S2 =(q1, q2,…,qn), где pi≥0, qi≥0. i=1Σm=1, j-1Σn=1. p1, p2, pm - вероятности использования первым игроком стратегий U=(U1,… Un), q1, q2,…,qn - вероятности использования вторым игроком стратегий Z=(Z1,… Zn)

Зная платежную матрицу А, можно определить средний выигрыш (математическое ожидание) M(A,p’, q’) = i=1Σm j=1Σn aij pi qj, где р и q —векторы, с компонентами p1p2,…, pm и q1, q2,…,qn соответственно.

Игрок I, применяя свои смешанные стратегии, стремится увеличить свой средний выигрыш, достигая α=maxmin M(A,p’, q’). Игрок II добивается: β =minmax M(A,p’, q’).


48. Приведение матричной игры к задаче ЛП.

Рассмотрим игру m x n с матрицей А. Для оптимальной стратегии I игрока U*(U1, Un) и цене V Должно выполняться неравенств: i=1Σm aij Ui*≤V. Предположим, что цена игрыV>0 (добавлением ко всем элементам А числа С оптимальная стратегия не изменяется, цена увеличивается на С). Разделим обе части неравенства на V. : i=1Σm aij U1*/V≥1, U1*/V=yi*  Σ ai yi*≥1, yi*≥0, тогда ΣUi*=1, через Σyi=1/V. Т.к. I стремится получить максимальный выигрыш, то он должен обеспечить минимальную величину 1/V  определение оптимальной стратегии сводится к нахождению значения функции: F*=Σyi (min) при условиях:

Σaijyi≥1, j=1,n, yi≥0, i=1,m. Аналогично i=1Σm aijZj*≤V, j=1,n

Σaij Zj*/V≤1, Zj*/V=Xi*; ΣaijXi*≤1, Xj*≥0, j=1,n

Σaijxj ≤1, xj≥0, j=1,n

Чтобы найти решение игры, надо составить пару двойственных задач и решить их.


49. Динамическое программирование - раздел математического программирования, в котором процесс принятия решения и управления может быть разбит на отдельные шаги. ДП позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. ДП позволяет осуществить оптимальное планирование многошаговых управляемых процессов и процессов, зависящих от времени. Экономический процесс называется управляемым, если можно повлиять на ход его развития. Управлением называется совокупность решений, принимаемых на каждом этапе с целью влияния на ход процесса. Началом этапа управляемого процесса считается момент принятия решения. Планируя многоэтапный процесс, исходят из интересов всего процесса в целом, т.е. при принятии решения на отдельном этапе всегда необходимо иметь в виду конечную цель.