Лабораторная работа №2 (Лабораторная работа №2)

Посмотреть архив целиком

2.Основные понятия теории игр. Матричные игры

Лабораторная работа № 2

Тема: Основные понятия теории игр. Матричные игры

Цель работы: 1.Ознакомиться с разделом исследования операций - теорией игр.

2.Научиться моделировать задачи и находить их решение в чистых стратегиях.

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

Основные понятия теории игр

Под термином “игра” понимается “математическая модель конфликта”. Обозначим U - множество конфликтующих сторон. Произвольно взятая сторона AU располагает некоторым набором (множеством) SA допустимых (определённых правилами игры) стратегий S1A,S2A,..., т.е. SA={S1A,S2A,...}. Стратегией называется совокупность правил, определяющих выбор варианта действий в зависимости от сложившейся ситуации. Формально, стратегия -функция x=(y,z), отображающая NZM, где N - неопределенные, Z - случайные, M - контролируемые факторы.

Использование каждой стороной какой либо из своих стратегий определяет один из возможных исходов конфликта, принадлежащий множеству J всех возможных исходов. Реализацией игры называется отображение SA1SA2SA3...  J. На множестве J задаётся числовая функция CA(j), jJ, называемая платёжной функцией. Она определяет размеры выигрыша (положительного или отрицательного), получаемого стороной A при исходе j. Таким образом, давая формальное определение игры, можно сказать, что игра-это система J, объединяющая компоненты U, {SA}AU, J, {CA(j)}AU, jJ.

Классификация игр по различным признакам

  1. Если у каждого участника игры имеется конечное число стратегий, то игра называется конечной. Если хотя бы один участник имеет в своём распоряжении бесконечно много стратегий, то игра называется бесконечной.

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

  3. Противником оперирующей стороны может быть:

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

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

Антагонистические игры

Рассмотрим конечную бескоалиционную игру G, в которой участвуют два игрока A и B.

Пусть A1 ... Am - стратегии игрока A,

B1 ... Bn - стратегии игрока B,

CA(i,j) - выигрыш игрока A, если он применяет стратегию Ai, а B применяет стратегию Bj

CB(i,j) - выигрыш игрока B, таком же случае.

Если CA(i,j) + CB(i,j) = 0 для  i, j, то игра называется игрой с нулевой суммой или антагонистической. В таких играх выигрыш одного игрока определяется проигрышем другого (CA(i,j)= - CB(i,j)), поэтому её можно задать матрицей C(i,j) с элементами {aij}, являющимися выигрышами для игрока А (проигрышами игрока В), строки которой соответствуют стратегиям A, а столбцы - стратегиям B. Эту матрицу называют платёжной.

Ai\Bj

B1

B2

...

Bn

A1

a11

a12

...

a1n

A2

a21

a22

...

a2n

...

...

...

...

...

Am

am1

am2

...

amn

Сторона A пытается найти наилучшую из своих стратегий, оценивая выигрыши aij поочерёдно для A1,A2, ... Am. Очевидно, при использовании стратегии Ai безусловно достижимым (гарантированным) будет . Тогда наилучшей с точки зрения A оказывается та стратегия, для которой i максимально и - наилучший гарантированный результат для игрока A. Если A будет придерживаться этой стратегии, то выиграет не меньше  при любом поведении B. В силу этого величина  называется нижней ценой игры.

Аналогично для игрока B. В этом случае речь идёт о проигрышах стороны A, так как в антагонистической игре CB(i,j)= - CA(i,j)= - aij. Следовательно, произвольно взятая стратегия Bj (1jn) должна характеризоваться показателем , определяющим наибольший из ожидаемых проигрышей. Тогда наилучшей для B становится стратегия, дающая минимум j, равный она называется минимаксной стратегией. Величина  называется верхней ценой игры. Если второй игрок будет применять оптимальную стратегию, то больше чем  он не проиграет. Легко показать, что   .

Рассмотрим два случая:

  1.  = ;

  2.  < .

1)Равенство  =  означает, что в платёжной матрице присутствует элемент aij, который одновременно оказывается минимальным в i-й строке и максимальным в j-м столбце (1im, 1jn, aij==). В этом случае элемент aij называется седловой точкой.

Примером может служить матрица:

Ai\Bj

B1

B2

B3

B4

i

A1

2

4

7

5

2

A2

7

6

8

7

6

A3

5

3

4

1

1

j

7

6

8

7


В игре с седловой точкой стороны A и B, решившие придерживаться минимаксных стратегий, попадают в ситуацию, когда и для A, и для B невыгодно изменять стратегии. Если в какой-то момент один из участников попытается изменить свою стратегию, то выгоду из этого извлечёт другой участник. Положение, при котором ни одна из сторон не имеет никаких разумных оснований для изменения своей стратегии, называется ситуацией равновесия. В играх с седловой точкой такая ситуация возникает если стороны A и B используют Ai и Bj. Величина aij== называется ценой игры, стратегии Ai и Bj - оптимальными.

2)В случае  <  в матрице не существует седловой точки и не возникает ситуации равновесия, поэтому игроки вынуждены менять свои стратегии. В этом случае для определения решения игры вводится понятие смешанной стратегии. Смешанной стратегией игрока A называется полный набор вероятностей применения стратегий A1 ... Am, т.е. вектор P т.ч. P=(p1,p2,...pm), pi0, , где pi - вероятность выбора i-й стратегии (). Стратегии A1 ... Am при этом называются чистыми. Стратегии Ak , для которых pk>0, называются активными. Аналогично для игрока B, смешанной стратегией называется вектор Q т.ч. Q=(q1,q2,...qn), qj0, , где qj - вероятность выбора j-й стратегии (). Оценка эффективности смешанных стратегий производится с точки зрения среднего выигрыша, который представляет собой математическое ожидание выигрыша игрока А (проигрыша игрока В):

.

Наилучший гарантированный результат для игрока A - , для игрока B - . Стратегии, при которых достигаются a и b называются оптимальными смешанными стратегиями. Теорема о минимаксе утверждает, что величины a и b связаны между собой: в конечной игре двух лиц с нулевой суммой и полной информацией имеет место равенство a = b. Величина =a=b называется ценой игры. При этом существует пара оптимальных стратегий P* и Q*, таких что a(P*,Q*)=.

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

Пример 1. Игра “Три пальца”.

Два игрока выкидывают одновременно и независимо друг от друга один, два или три пальца. Выигрыш - число выкинутых пальцев. Если сумма - числа чётное, то платит A, а если нечётное, то платит B.

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

A1, B1 : 1 + 1 = 2 - чётное, поэтому A получает 2

A1, B2 : 1 + 2 = 3 - нечётное, поэтому A платит 3 и т. д.

A\B

B1

B2

B3

i

A1

2

-3

4

-3

A2

-3

4

-5

-5

A3

4

-5

6

-5

j

4

4

6

Находим i - минимальные числа в строках, j - максимальные числа в столбцах. Из них выбираем

, и .

Получаем: -3 < 4 ( < ), т.е. игра не имеет седловой точки и не имеет решения в чистых стратегиях.


Пример 2. Противовоздушная оборона.

У игрока A имеется три типа вооружений A1, A2, A3 (зенитки, ракеты, самолёты), а у игрока В самолёты трёх типов. А - обороняется, В - нападает. Цель игрока А перехватить и сбить самолет противника, а цель В - сохранить свой самолёт. Если А применяет зенитки A1, то поражает самолёты В с вероятностями 0.5, 0.6, 0.8; игрок В при этом старается применить самолёт, для которого вероятность поражения наименьшая. Если А применяет ракеты A2, то поражает самолёты В с вероятностями 0.9, 0.7, 0.8. Когда А пускает в ход самолёты - истребители A3, то поражает самолёты В с вероятностями 0.7, 0.5, 0.6. Определить оптимальную стратегию для игрока А.

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

A\B

B1

B2

B3

i

A1

0.5

0.6

0.8

0.5

A2

0.9

0.7

0.8

0.7

A3

0.7

0.5

0.6

0.5

j

0.9

0.7

0.8


Находим нижнюю и верхнюю цену игры

,

.

Игра имеет седловую точку (α2;β2). Оптимальными стратегиями для A и B будут соответственно A2 и B2.


Задание к лабораторной работе № 2

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

1.Два противника А и В ведут борьбу за два стратегических пункта. Под командованием А находится два (три) полка, под командованием В - три (три). Обе стороны должны распределить свои силы между двумя пунктами. Пусть n1 и n2 числа полков, посланных со стороны А на пункты 1 и 2 соответственно. Аналогично, пусть m1 и m2 - распределения полков противника по соответствующим пунктам. Выигрыш А подсчитывается следующим образом: если n1>m1, то он получает m1+1, и, если n2>m2, он получает m2+1. С другой стороны, если n1<m1, то он теряет n1+1, и, если n2<m2, он теряет n2+1. Если число полков на каждой стороне одно и тоже, то каждая сторона получает нуль. Определить оптимальные стратегии для каждого игрока.

2.Два предприятия предполагают выпустить конкурирующие товары. Первое - А или В, второе - С или D, причем одновременный выпуск двух типов товаров каждым из предприятий признан экономически невыгодным. По прогнозам специалистов найдет сбыт 1(2) тысяча изделий. В случае выпуска товаров двумя предприятиями спрос на них распределится в соответствии с данными таблицы:


A

B

C

D

A

40(35)%

70(60)%

90(85)%

B

60(65)%

30(25)%

50(50)%

C

30(40)%

70(75)%

20(30)%

D

10(15)%

50(50)%

80(70)%

т.е. при выпуске товаров A и D, 90(85)% покупателей отдадут предпочтение товару D. Определить оптимальные стратегии руководства предприятий. (В качестве выигрышей взять прогнозируемый спрос (число изделий)).

3.Распределение сил в наступлении и обороне.

Сторона А, располагающая тремя(четырьмя) батальонами пехоты, стремится захватить некоторый объект В; сторона В, располагающая четырьмя батальонами пехоты, стремится воспрепятствовать этому. Каждый из наступающих батальонов может быть направлен к объекту по любой из двух дорог: I и II. Сторона В также может расположить любой из своих батальонов на любой из дорог. Если на дороге силы стороны В встречаются с превосходящими силами стороны А, последние оттесняют оборону, проходят к объекту и занимают его; если же на дороге оборона численно превышает нападение, атака отбивается, силы стороны А отходят и больше не возобновляют нападение. Если на дороге встречаются силы одинаковой численности, сторона А с вероятностью 0.4(0.3) побеждает и проходит к объекту, а с вероятностью 0.6(0.7) атака оказывается отбитой. Определить оптимальное количество батальонов, которое следует направить на каждую из дорог.

(обозначить выигрыш А - вероятность захвата объекта В)

4.Две конкурирующие фирмы собираются освоить два новых рынка сбыта продукции. Фирма А имеет возможность вложить в освоение рынков 10(12) тыс. долл., состоящие из двух неделимых пакетов по 5(6) тыс. долл., фирма В - 14(10) тыс. долл., состоящие из двух неделимых пакетов по 7(5) тыс. долл. Считая, что прибыль с продажи продукции на рынках пропорциональна вложенным средствам, но не превосходит максимально возможной прибыли с 1-го рынка -130(120) тыс. долл., со 2-го - 120(140) тыс. долл., определить оптимальные стратегии вложения средств для фирм А и В.

5.Сторона А планирует нанесение удара по одному из 4-х объектов стороны В, которая в силу ограниченного количества защитных средств может организовать эффективную оборону только одного объекта. Ценность объектов представлена в таблице:

Номер объекта

1

2

3

4

Ценность (усл. ед)

10(9)

7(8)

9(7)

6(5)

Определить оптимальные стратегии сторон, если вероятность уничтожения обороняемого объекта - 0,4(0.3), необороняемого - 1. (В качестве проигрышей стороны А взять математическое ожидание ущерба).

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

Район

1

2

3

Вероятность обнаружения

0.3(0.4)

0.5(0.2)

0,6(0.5)

Считаем, что обнаружение подводной лодки каждым из противолодочных кораблей является независимыми событиями. Сторона А должна распределить противолодочные корабли по районам, а сторона В - выбрать район действия подводной лодки. (В качестве элементов платежной матрицы взять вероятность обнаружения подводной лодки).

7.Фирма А производит некоторый сезонный товар, который имеет спрос в течение 4-х (3-х) единиц времени. Этот товар поступает на рынок в момент i {i=1..4}( i=1..3). Конкурентная фирма В производит аналогичный товар, который поступает на рынок в момент j {j=1..4}(j=1..3). Качество конкурирующих товаров зависит от времени их поступления на рынок - чем позже товар выбрасывается на рынок, тем качество его выше. Реализуется только товар более высокого качества. В том случае, когда на рынок одновременно поступают оба товара, считаем что эти товары имеют одинаковый спрос. Определить время поступления товара фирмы А на рынок, обеспечивающее максимальный доход, если прибыль от продажи товара в единицу времени одинакова для обеих фирм и равна 20 (30) усл.ед.

8.Бомбардировщики и истребитель.

Сторона А посылает в район расположения противника В два(три) бомбардировщика I и II(I, II и III); I летит спереди, II - сзади(I летит спереди, за ним II, III - сзади). Один из бомбардировщиков, заранее неизвестно какой, должен нести бомбу; другие выполняет только функцию сопровождения. В районе противника бомбардировщики подвергаются нападению истребителя стороны В. Все бомбардировщики вооружены пушками. Если истребитель атакует последний бомбардировщик, то по нему ведут огонь пушки только этого бомбардировщика, поражающие истребитель с вероятностью 0.3. Если истребитель атакует первый(второй) бомбардировщик, по нему ведут огонь пушки как первого(второго) так и последнего бомбардировщика. (Если истребитель атакует первый бомбардировщик, по нему ведут огонь пушки всех трех бомбардировщиков.) Если истребитель не сбит ответным огнем бомбардировщиков, то он поражает выбранную им цель с вероятностью 0.8. Задача бомбардировщиков - донести бомбу до цели; задача истребителя - воспрепятствовать этому. Определить оптимальные стратегии сторон.

9.Сторона А - средства ПВО - обороняет от воздушного налета участок территории, располагая орудиями №1 и №2(№1, №2 и №3), зоны действия которых S1, S2 (S1, S2 и S3) не перекрываются. Каждое орудие может обстрелять только самолет, проходящий через его зону действия, но для этого оно должно заранее (до входа цели в зону) следить за ним и вырабатывать прицельные данные. Если цель обстреляна, она поражается с вероятностью p=1, иначе не поражается. Сторона В располагает двумя самолетами, каждый из которых может быть направлен в любую зону. В момент, когда сторона А осуществляет целераспределение - назначает, какому орудию за каким самолетом следить, сторона В решает какому самолету в какую область лететь. Задача стороны А - обратить в максимум, а стороны В - обратить в минимум число пораженных целей. Найти оптимальные стратегии для обоих сторон.

10.Предположим, что в некотором городе имеются два предприятия, которые выпускают продукцию одного и того же назначения. Первое предприятие (А) может выпускать продукцию типа Д1, Д2,...,Д5. Второе (В)- продукцию типа М1, М2,...,М5. Себестоимость и продажная цена всех видов продукции одинакова. Социологи установили, что в городе найдет сбыт 10000(5000) единиц товара всех видов, причем, если первое предприятие будет выпускать продукцию Дi, а второе - типа Мj, то вероятность спроса товара Дi равна рij. Прогнозируемая доля товаров предприятия А:


М1

М2

М3

М4

М5

Д1

0.5(0.3)

0.5(0.6)

0.4(0.5)

0.5(0.4)

0.2(0.6)

Д2

0.5(0.1)

0.4(0.5)

0.7(0.3)

0.1(0.7)

0.6(0.3)

Д3

0.2(0.5)

0.3(0.7)

0.4(0.3)

0.1(0.6)

0.7(0.4)

Д4

0.3(0.4)

0.6(0.2)

0.7(0.1)

0.3(0.7)

0.2(0.5)

Д5

0.4(0.6)

0.4(0.3)

0.3(0.2)

0.1(0.4)

0.2(0.3)

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

11.Авианосное ударное соединение “зеленых” планирует нанесение ударов по авианосному ударному соединению “синих” в период Т, который состоит из 4-х (3-х) единиц времени. Удары, начиная с момента i, наносятся в каждую последующую единицу времени. В свою очередь, “синие” для защиты кораблей предполагают в тот же период Т использовать средства радиоэлектронного противодействия (РЭП), которые после постановки в момент j создают противодействие в каждый последующий момент времени без изменения своих характеристик. Допустим, что средства РЭП, поставленные до начала нанесения ударов, обнаруживаются средствами разведки, в результате чего эффективность этих средств снижается до нуля. С другой стороны, если удары наносятся ранее постановки РЭП, то эти средства снижают эффективность оружия до нуля. Кроме того, будем считать, что запланированное время нанесения ударов и постановки средств РЭП, не может быть изменено, а удары наносятся с одинаковой интенсивностью. Пусть математическое ожидание числа уничтоженных кораблей “синих” в единицу времени при нанесении ударов без противодействия средств РЭП равно с=0.4 (0.6). Кроме того, примем, что если удары наносятся одновременно с использованием средств РЭП, то математическое ожидание числа уничтоженных кораблей “синих” в единицу времени равно с/2 и остается постоянным для соответствующего отрезка периода Т.

12. Пусть игрок В для уклонения от самонаводящихся торпед может применить j-е {j=1,2,3} средство гидроакустического противодействия (ГПД), а сторона А - использовать в устройстве самонаведения i-e {i=1,2,3} помехозащитное устройство. Считаем, что помехозащитное устройство i снижает эффективность средства i гидроакустического противодействия до нуля. В остальных случаях будем полагать, что 1-е помехозащитное устройство “проигрывает” по 20(30) единиц 2-м и 3-м средствам ГПД, 2-е помехозащитное устройство “проигрывает” по 10 (20) единиц 1-м и 3-м средствам ГПД, а 3-е помехозащитное устройство “проигрывает” по 1 (2) единиц 1-м и 3-м средствам ГПД. Определить оптимальные стратегии использования помехозащитных устройств и ГПД.

4