Теория игр

Свойство 2. Для того, чтобы  хо = () была оптимальной  смешанной стратегией матричной игры с  матрицей А и ценой  игры , необходимо и достаточно выполнение следующих неравенств

(j = )

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

(i = )

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

,

получим решение матричной  игры.

Итак, пусть дана матричная  игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры должны удовлетворять соотношениям.

Разделим  все уравнения  и неравенства  в (4.4) и (4.5) на (это  можно сделать, т.к. по предположению > 0) и введём обозначения:

, ,

Тогда (1) и (2) перепишется  в виде:

, , , ,

, , , .

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

, .

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

, .

Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим  значения pi , qj и .Тогда смешанные стратегии, т.е. xi и yj получаются по формулам:

4.1 Решение задач

Пример 5: Найти решение  игры, определяемой матрицей.

Решение.

Составим  теперь пару взаимно-двойственных задач :

Решим вторую из них

Б.п.	q1	q2	q3	q4	q5	q6	Решение		Отношение
	1	1	1	0	0	0	0	3
q4	1	2	0	1	0	0	1	5	--
q5	1	0	1	0	1	0	1	4
q6	2	1	0	0	0	1	1	5	--

Б.п.	q1	q2	q3	q4	q5	q6	Решение		Отношение
	0	1	0	0	1	0	1	1
q4	1	2	0	1	0	0	1	5
q3	1	0	1	0	1	0	1	4	--
q6	2	1	0	0	0	1	1	5

Б.п.	q1	q2	q3	q4	q5	q6	Решение		Отношение
		0	0		1	0
q2		1	0		0	0
q3	1	0	1	0	1	0	1	4
q6		0	0		0	1

Из  оптимальной симплекс-таблицы  следует, что

(q1, q2, q3) = (0;; 1),

а из соотношений двойственности следует, что

( p1, p2, p3) = (; 1; 0).

Следовательно, цена игры с платёжной  матрицей А1 равна

. ,

а игры с платёжной  матрицей А:

.

При этом оптимальные  стратегии игроков  имеют вид:

Х = (х1, х2, х3) = (р1; р2; р3) = =

 

Y = (y1, y2, y3) = (q1; q2; q3) = = .

5. Игры с природой (без противодействия)

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

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

1. Критерий Вальде (пессимистический).

В соответствии с этим критерием следует  применять самую  осторожную стратегию, которая сведет к  минимуму вероятность (риск) проигрыша и доставит минимальную прибыль. Эта стратегия  обеспечивается критерием:

max (min a ij ).(5.1)

где минимум выбирается по каждой строке.

То  есть этот критерий совпадает с нижней ценой игры.

2. Критерий максимума  (оптимистический).

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

max (max a ij ).(5.2)

где максимум выбирается по каждой строке.

3. Критерий Гурвица.

Критерий  Гурвица занимает промежуточное значение между критерием  Вальде и критерием максимума. Сам игрок определяет вероятность своего «везения»

max (? min a ij + (1- ?) max a ij ) .(5.3)

Ответственное лицо, принимающее  решение, определяет значение коэффициента ?. Если потери могут  быть весьма значительными, то значение коэффициента ? приближается к единице, иначе к 0.

4. Критерий Сэвиджа.

Этот  критерий анализирует  возможные риски  от применения каждой из стратегий и  выбирает такую стратегию, которая обеспечивает приемлемые потери. Риски по каждой стратегии  определяются по формуле:

r ij = max a ij - a ij.(5.4)

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

min (max (max a ij - a ij).(5.5)

где максимум выбирается в каждом конкретном столбце.

Для примера возьмем  таблицу стратегий (табл. 5.1) и составим для  нее таблицу рисков (табл. 5.2).

Если  фирма (игрок) выберет  стратегию А1, а природа реализует стратегию В1 , то фирма получит максимально возможную прибыль 5 (недополученная прибыль составит 0). Фирма угадала состояние природы. Но если природа реализует стратегию В4, то фирма вместо максимально возможной прибыли 12 получит прибыль 5, а недополученная прибыль составит 7.

Таблица 5.1

Таблица стратегий

Стратегии	В1	В2	В3	В4	В5
А1	5	8	7	5	4
А2	1	10	5	5	6
А3	2	4	3	6	2
А4	3	5	4	12	3
max a ij	5	10	7	12	6

Таблица 5.2

Таблица рисков

Стратегии	В1	В2	В3	В4	В5
А1	0	2	0	7	2
А2	4	0	2	7	0
А3	3	6	4	6	4
А4	2	5	3	0	3

5.1 Решение задач

Пример 1: Швейная фабрика  на летний сезон может  реализовать два  вида костюмов: 1200 костюмов по цене 520 руб. и 200 костюмов по цене 1000 руб., если погода будет жаркой. Если погода будет  холодной, то фабрика  может реализовать 650 костюмов первого  вида и 700 костюмов второго  вида.

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

Решение:

Швейная фабрика располагает  двумя стратегиями: А1 - погода будет жаркой и А2 - погода будет холодной.

Если  фабрика воспользуется  первой стратегией и  погода действительно  будет жаркой, то прибыль фабрики  составит:

1200 · 520 + 200 · 1000 = 624 000 + 200 000 = 824 000 руб.

Если  фабрика воспользуется  первой стратегией, но погода будет холодной, то прибыль фабрики  составит:

650 · 520 + 200 · 1000 - (1200 - 650) · 520 = 338 000 + 200 000 - 286 000 = 252 000 руб.

Если  фабрика воспользуется  второй стратегией и  погода действительно  будет холодной, то прибыль фабрики  составит:

650 · 520 + 700 · 1000 = 338 000 + 700 000 = 1 038 000 руб.

Если  фабрика воспользуется  второй стратегией, но погода будет жаркой, то прибыль фабрики  составит:

650 · 520 + 200 · 1000 - (700 - 200) · 1000 = 338 000 + 200 000 - 500 000 = 38 000 руб.

Составим  матрицу прибыли (таб. 5.3).

Таблица 5.3

Матрица прибыли

Стратегии	В1	В2
А1	824 000	252 000
А2	38 000	1 038 000

? = max (252 000; 38 000) = 252 000 руб.

? = min (824 000; 1 038 000) = 824 000 руб.

Таким образом, цена игры находится  в диапазоне от 252 000 руб. до 824 000 руб.

Минимальный гарантированный  доход швейной  фабрики составит 252 000 руб., но возможен и доход в 824 000 руб.

Определим план выпуска изделий  швейной фабрикой. Вероятность выбора стратегии А1 обозначим через х1, а вероятность выбора стратегий А2 - через х2. Учитывая, что х2 = 1 - х1,можем записать:

(a11 - a12)· х1 + a12 = (824 000 - 38 000)· х1 + 38 000 = 786 000 х1 + 38 000;

(a21 - a22)· х1 + a22 = (252 000 - 1 038 000) · х1 + 1 038 000 = -786 000 х1 + 1 038 000;

786 000 х1 + 786 000 х1 = 1 038 000 - 38 000

1 572 000 х1 = 1 000 000

х1 = 0,64; х2 = 1 - 0,64х2 = 0,36;

0,64 (1200; 200) + 0,36 (650; 700) = (1002; 380).

Цена  игры составит: 786 000 х1 + 38 000 = 541 040 руб.

Таким образом, план выпуска  изделий таков: 1002 костюма первого  вида и 380 костюмов второго  вида, и при любых  погодных условиях швейная  фабрика получит  прибыль не менее 541 000 руб.

Определим критерии.

1. Критерий Вальде:

max (min a ij) = max (38 000; 252 000) = 252 000 руб.

Швейной фабрике целесообразно  использовать стратегию  А1 .

2. Критерий максимума:

max (max a ij ) = max (824 000; 1 038 000) = 1 038 000 руб.

Швейной фабрике целесообразно  использовать стратегию  А2 .

3. Критерий Гурвица:

пусть ? = 0,4 , тогда для стратегии А1

? min a ij + (1 - ?) max a ij = 0,4 · 252 000 + (1 - 0,4) · 824 000 = 595 200 руб.

для стратегии А2

? min a ij + (1 - ?) max a ij = 0,4 · 38 000 + (1 - 0,4) · 1 038 000 = 638 000 руб.

Швейной фабрике целесообразно  использовать стратегию  А2 .

4. Критерий Сэвиджа:

Максимальный  элемент в первом столбце - 824 000, во втором столбце - 1 038 000.

Матрица рисков будет иметь  вид:

Швейной фабрике целесообразно  использовать стратегию  А1 или А2 .

Заключение

При написании курсовой работы по дисциплине «Математические  методы» на тему «Теория  игр» у меня возникли проблемы с теоретической  частью курсовой работы. Мне приходилось  брать одну литературу и искать нужную информацию, а потом, если в  ней не полностью  раскрыта тема, то брал следующую, а в  ней более труднее  приходилось разбираться, так как один автор  пишет, как он понимает, а другой - свои взгляды  на тему. Но я смог преодолеть эту непреодолимую  пропасть.

Список литературы

1. « Математические  методы в программировании  » : / Агальцов В.П., Волдайская И.В. Учебник : - М . : ИД «ФОРУМ» : ИНФРА-М, 2006. - 224с. : ил. -(Профессиональное образование). - (Учимся программировать).

2. Лекции по дисциплине  « Математические  методы ».

3. «Математические  методы: Учебник» / Партика Т.Л., Попов И.И. - М: ФОРУМ: ИНФРА, 2005.

4.«Математическое  программирование»  / Костевич Л., издательство  «Новое знание», 2003.