Добавил:
Меня зовут Катунин Виктор, на данный момент являюсь абитуриентом в СГЭУ, пытаюсь рассортировать все файлы СГЭУ, преобразовать, улучшить и добавить что-то от себя Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
18
Добавлен:
10.08.2023
Размер:
577.54 Кб
Скачать

Пример 1

таблица 1

Аi Вj

В1

В2

В3

В4

В5

А1

А2

А3

А4

3

1

10

4

4

8

3

5

5

4

1

3

2

3

7

4

3

4

6

8

таблица 2

Аi Вj

В1

В2

В3

В4

В5

аi

А1

А2

А3

А4

3

1

10

4

4

8

3

5

5

4

1

3

2

3

7

4

3

4

6

8

2

1

1

«3»

βj

10

8

«5»

7

8

( ) ≤ ( )

Пример 2.

таблица 3

Вj Аi

В1

В2

В3

В4

аi

А1

А2

А3

2

7

5

4

6

3

7

8

4

5

7

1

2

«6»

1

βj

7

«6»

8

7

( ) = ( ).

pi ≥ 0,

qj ≥ 0.

.

Пример 3. Рассмотрим игру, заданную платёжной матрицей.

7 6 5 4 2

5 4 3 2 3

5 6 6 3 5

2 3 3 2 4 4х5

Найдём оптимальные стратегии игроков и цену игры.

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

После исключения заведомо невыгодных стратегий обоих игроков

получаем матрицу В4 В5

А1 4 2

А3 3 5 2х2

Так как р 2 = р 4 = q 1 = q 2 = q 3 = 0, то р3 = 1 - р1, q 5 = 1 – q 4.

Ожидаемый выигрыш первого игрока при применении вторым игроком стратегии В4 составит

4. р1 + 3. р3 = 4. р1 + 3. (1 – р1) = 4. р1 + 3. 1 – 3р1 = (4 – 3)р1 + 3 = р1 + 3.

Ожидаемый выигрыш первого игрока при использовании вторым игроком стратегии В5 составит (2 – 5). р1 + 5 = -3 р1 + 5.

Графическое решение игры для первого игрока:

N

5 К

O 4

3

М

ν 2 L

р

р1=0 р1=0,5 р1=1

Первый игрок должен выбирать такие стратегии, чтобы максимизировать свой минимальный ожидаемый выигрыш.

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

Т.е. оптимальная стратегия первого игрока определяется из равенства выражений х1 + 3 и -3х1 + 5: х1 = 1/2; х3 = 1 – х1 = 1 – 1/2 = 1/2.

Цена игры ν = х1 + 3 = 7/2 соответствует ординате точки пересечения прямых МК и NL. Ломаная MOL – это нижняя граница выигрыша, полученного первым игроком. В точке O он максимален и равен её ординате.

Итак, оптимальная стратегия первого игрока: = (1/2; 0; 1/2; 0),

при этом цена игры ν = 7/2.

Графическое решение игры для второго игрока:

чистые стратегии ожидаемые проигрыши

первого игрока второго игрока

А1 (4 – 2) q4 +2 = 2q4 + 2

А 3 (3 – 5) q4 + 5 = -2 q4 + 5

N 5

O K 4

М ν 3 L

2

q4=0 q4=0,75 q4=1

Значит, 2 q4 +2 = -2 q4 +5, q4 = 3/4, q5 = 1 - q4 = 1/4,

ν =2 q4 + 2 = 3/2 + 2 = 7/2.

Ломаная NOК – верхняя граница проигрыша второго игрока, в точке О он минимален и равен её ординате

Оптимальная стратегия второго игрока = (0, 0, 0, ¾, ¼), при этом цена игры ν = 7/2.

Пример 4. Швейное предприятие, выпускающее детские платья и костюмы, реализует свою продукцию через фирменный магазин. Сбыт продукции зависит от состояния погоды. По данным прошлых наблюдений предприятие в течение апреля – мая в условиях тёплой погоды может реализовать 600 костюмов и 1975 платьев, а при прохладной погоде – 1000 костюмов и 625 платьев. Известно, что затраты на единицу продукции в течение указанных месяцев составляли для костюмов 27 руб., для платьев – 8 руб., а цена реализации равна соответственно 48 руб. и 16 руб.

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

Предприятие располагает в этих условиях двумя чистыми стратегиями: стратегия А1 – в расчёте на тёплую погоду и стратегия А2 – в расчёте на холодную погоду. Природу будем рассматривать как второго игрока также с двумя стратегиями: холодная погода – стратегия В1 и тёплая погода – стратегия В2. Если предприятие выбирает стратегию А1, то в случае холодной погоды (стратегия природы В1) доход составит

600 (48 - 27) + 625 (16-8) – (1975 – 625) 8 = 6800 рублей,

а в случае тёплой погоды (стратегия природы В2) доход будет равен

600 (48 - 27) + 1975 (16 – 8) = 28400 рублей.

Если предприятие выберет стратегию А2, то реализация продукции в условиях холодной погоды даст доход

1000 (48 –27) + 625 (16 – 8) = 26000 рублей,

а в условиях тёплой погоды

600 (48 –27) + 625 (16 – 8) – (1000 – 600) 27 = 6800 рублей.

Следовательно, матрица данной игры (платёжная матрица) имеет вид:

6800 28400

26000 6800

Первая и вторая строки этой матрицы соответствуют стратегиям А1 и А2 предприятия, а первый и второй столбцы – состояниям В1 и В2 природы.

погода предприятие

холодно

тепло

В1

В2

αi=minαij

α=maxαi

тепло

А1 (р)

6800

28400

6800

6800

холодно

А2 (1-р)

26000

6800

6800

βj = тах αij

26000

28400

β = min βj

26000

По платёжной матрице видно, что первый игрок (предприятие) никогда не получит доход меньше 6800 рублей. Но если погодные условия совпадают с выбранной стратегией, то выручка (выйгрыш) составит 26000 или 28400 рублей. Отсюда напрашивается вывод, что в условиях неопределённости погоды наибольший гарантированный доход предприятие обеспечит, если будет попеременно применять то стратегию А1, то стратегию А2. Такая стратегия, как известно, является смешанной. Из таблицы и основной теоремы теории игр следует, что при этом будет получен доход ν в промежутке:

6800≤ ν ≤ 26000.

Оптимизация смешанной стратегии позволит первому игроку всегда получать среднее значение выигрыша независимо от стратегии второго игрока — погоды.

Будем искать стратегию ЛПР в виде вектора SA = (p, 1 — p), где р означает частоту применения первым игроком стратегии А1, тогда частота применения им стратегии А2 равна (1–р).

В случае оптимальной смешанной стратегии первый игрок получит при любой стратегии второго игрока (В1 или В2) одинаковый средний доход:

6800 х + 26000 (1 – р) = 28400 р + 6800 (1 – р).

Отсюда находим: р = 8/17; (1 – p) = 9/17, т.е. SA = ( ).

Следовательно, первый игрок, применяя чистые стратегии А1 и А2 в соотношении 8 : 9, будет иметь оптимальную смешанную стратегию, обеспечивающую ему в любом случае средний доход в сумме

ν = 6800 . 8/17 + 26000 . 9/17 = 16965 рублей

– эта величина и будет в данном случае ценой игры.

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

(600костюмов + 1975платьев).8/17 + (1000костюмов + 625платьев).9/17

= 812 костюмов + 1260 платьев.

Следовательно, оптимальная стратегия предприятия заключается в выпуске 812 костюмов и 1260 платьев, что обеспечит ему при любой погоде средний доход в сумме 16 965 рублей.

Решение матричных игр сведением к З.Л.П.

Пусть игровая ситуация задана платежной матрицей

а11 а 12 а13а1n

а21 а2 2 а23а2n

…………………

аm1 аm2 аm3аmn

Будем искать решение игры, т.е. две оптимальные смешанные стратегии противников:

A = (p1, p 2, p 3,…, p m);

B = (q1, q 2, q3,…,q n).

Игрок А стремится сделать свой выигрыш (цену игры ν) максимальным, т.е. целью нашей задачи является максимизировать ν:

.

При использовании вторым игроком стратегии Вj математическое ожидание выигрыша игрока А составит

p1а1j + p 2а2 j + p 3а3j+…+ p mаmj.

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

j-ой стратегии игрока В получаем неравенство

p1а1j + p 2а2 j + p 3а3j+…+ p mаmj ν.

Для всех стратегий получаем систему неравенств:

p 1а11 + p 2а2 1 + p 3а31+…+ p mаm1 ν,

p1а12 + p 2а2 2 + p 3а32+…+ p mаm2 ν,

……………………………………….

p1а1n + p 2а2n + p 3а3n+…+ p mаmn ν,

где pi ≥ 0, i=1,m..

Полагая ν > 0, систему ограничений можно записать так:

… … … … … … …

Т.к. , то

Обозначим , тогда т.к. то

Получим З.Л.П. вида при ограничениях

Y

… … … … … … …

Если каждoму ограничению этой задачи поставить в соответствие новую переменную Yj , то двойственной к такой задаче будет следующая:

при ограничениях:

… … … … … … …

где

Пример 5. Торговая фирма разработала несколько вариантов плана продажи товаров на предстоящей ярмарке с учётом имеющейся конъюнктуры рынка и спроса покупателей. Получающиеся от их возможных сочетаний показатели дохода представлены в таблице

План

продаж

Величина дохода, ден.ед.

В1

В2

В3

А1

А2

А3

8

2

1

4

8

2

2

4

8

Определите оптимальный план продажи товаров.

Пусть p1—вероятность применения торговой фирмой стратегии А1; p2—вероятность применения стратегии А2; p3—А3, т.е. вектор вероятностей стратегий, используемых первым игроком:

А = (p1; p2; p3).

Вектор вероятностей стратегий второго игрока: В = (q1; q2; q3), где q1, q2, q3 – соответственно состояния рынка.

Для торговой фирмы (первый игрок) математическая модель задачи имеет вид: при ограничениях:

Здесь ; .

Для конъюнктуры рынка и спроса покупателей (второй игрок) математическая модель задачи имеет вид:

при ограничениях:

Здесь

Найдём оптимальное решение задачи для второго (почему?) игрока симплексным методом. Для этого модель задачи необходимо привести к каноническому виду введением балансовых переменных Y4 ,Y5 и Y6 :

Б.п.

Ci

1

1

1

0

0

0

L(x)

bj

Y1

Y2

Y3

Y4

Y5

Y6

Y4

0

8

4

2

1

0

0

1

Y5

0

2

8

4

0

1

0

1

Y6

0

1

2

8

0

0

1

1

Δk

-1

-1

-1

0

0

0

0

После симплексных пребразоианий последняя таблица будет иметь вид

Б.п.

Ci

1

1

1

0

0

0

L(x)

bj

Y1

Y2

Y3

Y4

Y5

Y6

Y1

1

1

0

0

1/7

-1/14

0

1/14

Y2

1

0

1

0

-3/98

31/196

-1/14

11/196

Y3

1

0

0

1

-1/98

-3/98

1/7

5/49

Δk

0

0

0

5/49

11/196

1/14

45/196

Из таблицы следует, что

= (1/14, 11/196, 5/49),

F ( ) = 45/196.

Цена игры

.

Стратегию первого игрока найдём из последней строки (Δk) симплексной таблицы:

т.к. , то оптимальная стратегия первого игрока

= (20/45, 11/45, 14/45).

Таким образом, торговая фирма на ярмарке должна придерживаться стратегии = (20/45, 11/45, 14/45), т.е. завозить товар на ярмарку следует в пропорции 20:11:14 , тогда гарантируется доход не менее ден. ед.≈ 4,36 ден.ед.

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

  1. Исключить из платёжной матрицы заведомо невыгодные стратегии. Такими стратегиями для игрока А являются те, которым соответствуют строки с элементами, заведомо меньшими по сравнению с элементами одной из строк или равными соответствующим элементам этой строки. (Для игрока В — столбцы с элементами, заведомо большими по сравнению с элементами других столбцов).

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

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

Принятие решений в условиях полной неопределённости

Для принятия решений в условиях неопределённости используют ряд критериев: критерий Вальде, критерий Сэвиджа, критерий Гурвица.

Пример 6. В Северном округе Москвы планируется строительство овощехранилища. Имеются три возможных проекта создания такого хранилища площадью S1= 200 кв.м, S2= 300 кв.м и S3= 400 кв.м.

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

Si

Доход от занимаемой площади

ai=min aij

j

W

max aij

j

100

200

300

400

S1=200m2

S2=300m2

S3=400m2

130

60

-140

350

410

290

350

520

560

350

520

670

130

60

-140

130

350

520

670

βj= max aij

i

130

410

560

670

Надо определить наиболее целесообразный вариант строительства овощехранилища.

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

Наихудшее из того, что может случиться, состоит в том, что мы получим чистую выгоду в размере а = тах ai = max min aij= 130 –нижняя цена игры.

По принципу максимина, придерживаясь стратегии S1, мы получим не менее maxmin aij = 130. Этот принцип является основой критерия Вальда (критерия «крайнего пессимизма»), в соответствии с которым оптимальной стратегией при любом состоянии среды, позволяющей получить максимальный гарантированный выигрыш в наихудших условиях, является максиминная стратегия:

W =

Принцип максимина называют также принципом наибольшего гарантируемого результата.

При принятии решения в условиях полной неопределённости часто рассматривают матрицу рисков.

Риск—это разность между результатом, который можно получить, если знать действительное состояние «природы», и результатом, который будет получен при j–ой стратегии лица, принимающего решение (ЛПР).

Элементы матрицы рисков || rij || связаны с элементами платёжной матрицы соотношением:

,

где aij –максимальный элемент в j-ом столбце исходной матрицы.

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

Cоставим матрицу рисков для нашей игры || rij ||:

100

200

300

400

mах rij

S

S1

S2

S3

0

70

270

60

0

120

210

40

0

320

150

0

320

150

270

150

Риск является основой минимаксного критерия Сэвиджа, согласно которому выбирается такая стратегия, при которой величина риска принимает минимальное значение в самой неблагоприятной ситуации:

S =

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

При анализе «игры с природой» разумнее придерживаться некоторой промежуточной позиции. При использовании критерия Гурвица ЛПР выбирает стратегию, определяемую формулой

G = ,

где qстепень оптимизма, или «коэффициент пессимизма», изменяющийся в диапазоне [0; 1].

При q = 1 критерий Гурвица приводит к критерию Вальдакрайнего пессимизма»), а при q = 0 – к критерию «крайнего оптимизма», которому соответствует самый большой выигрыш. На q оказывает влияние степень ответственности ЛПР: чем хуже последствия ошибочных решений и больше желание застраховаться, тем q ближе к единице.

Допустим, в нашем примере мы придерживаемся ближе к пессимистической оценке и полагаем, что q = 0,8, тогда для каждой i-ой стратегии по формуле Gi = q·minaij+(1-q)·maxaij получим соответственно:

G1 = 0,8·130 + (1—0,8)·350 = 174

G2 = 0,8·60 + (1—0,8)·520 = 152

G3 = 0,8·(-140) + (1—0,8)·670 = 22

G = mах G i = mах (174, 152, 22) = 174 (что соответствует стратегии S1).

Следовательно, наоболее целесообразным вариантом является строительство овощехранилища площадью S = 200 кв.м.

Приведённые методы и модели позволяют с разных сторон провести анализ хозяйственных решений в условиях неопределённости.

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

Пример 1. Каждый из двух участников игры независимо и тайно от другого пишет одну из трёх цифр: 1, 2 или 3 (одна цифра—один ход). Если разность записанных цифр положительна, то первый игрок выигрывает количество очков, равное разности между цифрами. Если же разность отрицательна, то выигрывает второй игрок. Если разность равна нулю, то игра заканчивается вничью.

У первого игрока есть три стратегии: А1—записать цифру 1, А2—записать цифру 2 и А3—записать цифру 3. У второго игрока также три стратегии: В1, В2 и В3. Такую игру можно представить в виде матрицы размером 3х3,в которой строки—стратегии первого игрока,столбцы—стратегии второго, а элементы матрицы—выигрыши первого игрока (или проигрыши второго). Т.е. для данного примера платёжная матрица имеет вид:

0 -1 -2

аij = 1 0 -1 .

2 1 0

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

Выберем наилучшую стратегию для первого игрока. Для этого найдём минимальные выигрыши первого игрока при различных стратегиях Аi: в первой строке (при первой стратегии)—это число –2, во второй строке -1, в третьей – 0.

: 1 = -2, 2 = -1, 3 = 0.

Зная минимальные выигрыши, первый игрок выберет ту стратегию, при которой этот минимум максимален: = 0.

Величина = 0 – гарантированный доход, который может обеспечить себе первый игрок, — называется нижней ценой игры, или максимином.

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

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

В нашей игре -- такая игра называется игрой с седловой точкой, а пара оптимальных стратегий (Аоптим.; Воптим.) – седловой точкой матрицы (аij) . В этом случае элемент аij = 0 называется ценой игры . Ответ задачи: (А3; В3), т.е. оптимальная стратегия первого игрока А3, второго -- В3, цена игры = 0.

Пример 2. На базе торговой фирмы имеется n типов товара. В магазин фирмы должен быть завезён только один из этих типов товара. Если товар типа j будет пользоваться спросом, то магазин от его реализации получит прибыль рj. Если же этот товар не будет пользоваться спросом,то издержки на его хранение принесут убыток qj. Требуется выбрать тип товара, который целесообразно завести в магазин.

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

Пусть первый игрок – магазин, второй игрок – покупательский спрос. Каждый из игроков имеет по n стратегий. Завоз i-го товара -- i-я стратегия первого игрока, спрос на j-ый товар – j-я стратегия второго игрока. Тогда матрица выигрышей первого игрока имеет вид квадратной матрицы n-го порядка:

p1 -q1 … -q1

-q2 p2 … -q2

. . . . . . . .

-q n -qn … pn

Пример 3. Найдите оптимальные стратегии поведения игроков, если платёжная матрица игры имеет вид:

2 10 3 14 5

8 9 5 6 7 .

10 8 4 8 12

Минимальный элемент первой строки (первой стратегии первого игрока) равен 2, второй –5, третий – 4; максимальное значение из этих величин равно 5.

Максимальный элемент первого столбца (первой стратегии второго игрока) равен 10, второго – 10, третьего – 5, четвёртого – 14, пятого – 12; минимальное значение из них равно 5.

Следовательно, данная игра имеет седловую точку (2;3) и задача разрешима в чистых стратегиях.

Придерживаясь чисто второй стратегии, первый игрок обеспечивает себе выигрыш, не меньший 5; второй игрок, применяя чисто третью стратегию, проигрывает не более 5. Обе стратегии i =2 и j =3, являются оптимальными для первого и второго игроков, при этом цена игры V =5. ij

Пример 4. Найдите оптимальную смешанную стратегию руководителя предприятия и гарантированный средний выигрыш при выборе из двух новых технологий А1 и А2. Известны выигрыши каждого вида новых технологий по сравнению со старыми.

Матрица игры имеет вид:

игрок II

игрокI

В1

В2

αi

А1

0,4

0,9

0,4

А2

0,6

0,5

0,5

βj

0,6

0,9

0,9

0,6

0,5 а12

а21 ν = 0,55 0,4

а22 а11

0 1 р

р2= 0,375 р1= 0,625

Предпочтительная стратегия руководителя предприятия А2. При этой стратегии гарантированный выигрыш равен по сравнению

со старой технологией. Определим графически pоптим.= (р1, р2) и ν (см. рис.).

Применение руководителем стратегии роптим.= (0,375; 0,625) даёт выигрыш по сравнению с прежней технологией ν = 0,55.

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

2 2 3 -1

4 3 2 6 .

Так как а = max{-1; 2}=2, = min{4; 3; 3; 6}=3 a ,

то седловой точки нет и 2 3.

Обозначим:

х — вероятность использования первым игроком стратегии А1 , тогда

1-х — вероятность использования им стратегии А2.

Ожидаемые выигрыши первого игрока:

  • при использовании вторым игроком стратегии В1— -2х + 4;

  • при использовании вторым игроком второй стратегии В2— -х + 3;

  • В3х + 2;

  • В4— -7х + 6.

6

4

3 3

2 ν 2

х=0 х=0,5 х=1 х

-1

ν = -х + 3 = -0,5 + 3 = 2,5.

Оптимальная смешанная стратегия первого игрока опт. = (0,5; 0,5).

Пример 6. Диспетчер автобусного парка в летние месяцы в конце каждой недели должен принять решение о целесообразности выделения дополнительных автобусов на загородный маршрут. При этом он имеет три варианта решений: увеличить количество автобусов на 10 (стратегия А1), увеличить это количество на 5 (стратегия А2) или оставить без изменения (стратегия А3). Возможны два состояния погоды: В1 – плохая погода, В2 – хорошая погода. Причём в момент принятия решения нет возможности определить ожидаемое состояние погоды. Если в выходные дни будет хорошая погода и много жилающих выехать за город, а выделено мало автобусов, то парк понесёт убытки, связанные с недополученной прибылью. Если же выделить дополнительные автобусы, а погода окажется плохой, то возникнут потери вследствиe эксплуатации незаполненных автобусов.

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

В1 В2

А1 -4 5 4 0

(аij ) = А2 -2 2 ; тогда матрица рисков (rij ) = 2 3 .

А3 0 -6 0 11

Если нет сведений о вероятностях различных состояний погоды, то, по критерию Вальда и по критерию Сэвиджа оптимальной является стратегия А2. По критерию Гурвица при «коэффициенте пессимизма»

q = 1 оптимальной окажется стратегия А2, а при q = 0 — стратегия А1.

Здесь ;

Т Е С Т по теме «Элементы теории игр», автор Сергеева Л.В.

В заданиях 1— 7 выберете правильные продолжения фраз: