WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 ||

Рассмотрим другой итеративный алгоритм, который избавлен от i указанного недостатка.

v1 1 = min (1 1)= ij i j i 7.2. Монотонный итеративный алгоритм решения МИ = min{(2 1+ 3 0 +1 0); (11+ 0 0 + 2 0); (31+1 0 +1 0)}= j Рассмотрим смешанное расширение МИ с GA = (X,Y, K) (m n)= max{2; 1;3}= 1;

матрицей А.

i N N 2 Обозначим приближение оптимальной xN =(1,...,m)I v 2 = max (2 2)= ij j i j N N стратегии игрока 1 на N-й итерации и – вспомоcN Rn, cN = (1,...,n ) = max{(2 1 2 +11 2 + 3 0); (31 2 + 0 1 2 +1 0); (11 2 + 2 1 2 +1 0)}= гательный вектор. Алгоритм позволяет находить (точно и приближенно) i оптимальную стратегию игрока 1 и значение игры v.

= max{3 2; 3 2; 3 2}= 3 2;

i Итеративный процесс строится следующим образом. В начале процесса игрок 1 выбирает произвольную чистую стратегию i0, т. е.

v2 2 = min (i 2)= ij j i aix0 = (0,...,1i0,...,0), и вспомогательный вектор вида c0 = ai0, где – = min{(21 2 + 31 2 +1 0); (11 2 + 0 1 2 + 2 0); (31 2 +11 2 +1 0)}= j строка матрицы А, имеющая номер i0.

= max{5 2; 1 2;4 2}= 1 2;

Пусть выполнена -1.

N итерация и получены векторы xN -1, cN -i cN Тогда xN и вычисляются по следующим итеративным v3 3 = max (3 3)= ij j i формулам:

j N N -1 N ~ (7.3) x = (1- N )x + x, = max{(2 1 3 +1 2 3); (31 3); (11 3 + 2 2 3)}= max{4 3; 1; 5 3}= 5 3; N i i N ~ cN = (1- N )cN -1 + N c, (7.4) v3 3 = min (3 3)= min{(2 1 3 + 3 2 3); (11 3); (31 3 +1 2 3)}= ij i j j i N N ~ ~ где параметр 0 N 1. Векторы x и c будут получены ниже.

е.

= max{8 3; 1 3;5 3}= 1 3.

i 52 N N Рассмотрим вектор cN -1 = (1 -1,..., n -1) и выберем такие индексы м jk, на которых достигается минимум N -1 N -1 N -min = = N -1 =... =.

j j1 j2 jk j =1,n Обозначим N -vN -1 = min j, (7.5) j =1,n N -а J = {j1,..., jk} – множество индексов, на которых достигается N -min j.

j =1,n Пусть GA GN GA – подыгра игры с матрицей N N -AN ={ij -1}, i = 1, m, а индекс. Решаем подыгру и находим j J ~N.

N N ~ ~ стратегию игрока 1. Пусть x = (~,..., m ) 1N x X m N N N ~ ~ Вычислим вектор. Пусть вектор c имеет c = ai ~i i=компоненты ~N. Рассмотрим c = (~,..., n ) (2 n)- игру с матрицей 1N ~N N N 1 -1,..., n -.

N ~ ~ 1N,..., n Найдем оптимальную стратегию (N, 1- N ), 0 N 1, игрока в этой подыгре.

Подставляя найденные значения ~N ~N N в (7.3), (7.4), находим x, c, N N о и c. Процесс продолжаем до тех пор, пока не выполнится равенство x N = 0 или не будет достигнута требуемая точность вычислений.

Сходимость алгоритма гарантируется следующей теоремой.

54 Итеративный метод Брауна – Робинсона Теорема 7.2. Пусть – итеративные последовательности, {vN}, {xN} ~ x1 = 1 2 x0 +1 2 x1 = (1 2,0,1 2);

определяемые (7.3), (7.5). Тогда справедливы следующие утверждения:

~ c1 = 1 2c0 +1 2c1 = (3 2, 3 2, 2);

1) vN > vN -1, т. е. последовательность -1 строго монотонно {vN } v1 = min 1j = 1 = 1 = 3 2 > v0 = 1.

возрастает; 1 j lim vN = v = v; (7.6) 2) Множество индексов имеет вид.

J1 = {1,2} N lim xN = x*, где x* * – оптимальная стратегия игрока 1. 2 3) N I A2 = Итерация 2. Рассмотрим подыгру с матрицей Пример 7.2. Решим, используя монотонный алгоритм, игру с G2 GA 3.

1 матрицей 2 1 3 Первая строка в этой матрице доминируема, поэтому достаточно A = 0 1.

3 1 2 1 рассмотреть подматрицу 1 2.

Оптимальной стратегией игрока 1 в этой игре является вектор Итерация 0. Пусть игрок 1 выбрал 1-ю строку матрицы А, т. е.

~, поэтому (1 4,3 4) c = 1 4 a2 + 3 4 a3 = x = (0,1 4,3 4). Вычислим ~v0 = min 0 = 0 = 1, J = {2}. Вычислим.

и x0 = (1, 0, 0) c0 = a1 = (2, 1, 3) j j 3 2 3 2 и рассмотрим (2 3)-игру с матрицей = (3 2,3 2,1) 1 3 2 3 2 1.

Итерация 1. Рассмотрим подыгру с матрицей A1 = G1 GA 0.

Первая стратегия игрока 1 доминирует вторую, поэтому 1 =. Таким x* = x1 = (1 2,0, 1 2) образом, вычисления закончены: ; значение v игры Оптимальной стратегией ~1 игрока 1 является вектор ~1. Тогда да x = (0,0,1) x равно. Оптимальная стратегия игрока 2 имеет вид v = v1 = 3 ~.

c1 = a3 = (1,2,1) y* = (1 2,1 2,0) (см. пример 7.1, вторая строка в таблице).

2 1 Решаем. Заметим, что 3-й столбец (2 3)-игру с матрицей ец 1 2 Самостоятельная работа № 2 Найти значение игры в смешанных стратегиях с помощью итераматрицы доминируем, поэтому смотрим матрицу. В силу 1 тивных методов симметрии оптимальной стратегией игрока 1 в этой игре является вектор (N,1- N ) = (12, ).

Вычисляем x1 и c1 по формулам (7.3), (7.4). Имеем 56 ПРИЛОЖЕНИЕ 7 8 1 2 2 3 4 1 0 1 - Самостоятельная работа № 1 -1 2 2 1 -1 2 0 2 1 1 - Исследовать все ситуации на равновесие по Нэшу 4 7 3 1 2 -1 2 1 1 3 и оптимальность по Парето 3 3 3 - 2 1 - 6 3 1 5 - 8 - 5 -12 14 7 12 - 1 2 3 4 10 11 (1,2) (2,1) (3,2) (2,1) (5,2) (2,0) (3,2) (2,0) (3,4) (2,1) 1 1 1 (0,3) (4,6) (0,3) (4,4) (1,1) (5,6) (1,3) (5,5) (2,1) (5,4) 2 1 -1 1 1 2 5 6 7 8 9 10 2 1 1 1 3 - 4 2 2 1 3 (1,4) (2,0) (5,2) (2,3) (5,6) (3,2) (5,4) (3,2) (7,5) (3,2) 11 12 11 3 3 -1 2 5 8 2 19 - 6 - 5 (2,1) (5,3) (2,1) (4,6) (2,1) (5,3) (2,3) (4,6) (2,1) (7,4) 11 12 13 14 15 13 14 (6,5) (3,2) (6,7) (3,3) (7,4) (3,2) (8,7) (4,2) (9,6) (4,3) 2 2 1 4 1 - 2 -1 2 1 4 2 (2,3) (5,8) (2,4) (7,5) (2,1) (6,5) (2,1) (9,8) (5,1) (8,5) 3 0 2 0 2 -1 3 3 7 3 2 5 1 11 1 -1 -1 - 4 - 2 5 Самостоятельная работа № 3 8 1 18 2 0 - 4 - 7 3 1 - Найти все максминные и минимаксные стратегии игроков, нижнее и верхнее значения игры; указать все ситуации равновесия Пример 1. Решим каноническую задачу симплекс-методом.

и значение игры 1 2 3 z = 3x1 + 2x2 max Введем базисные -3x1 - 2x2 min F = - 3 1 - переменные - x1 + x2 - x1 + x2 -1+ s1 = - 4 3 - 3 5 2 3 4 5 - 3 1 4 2 x 2 x - 2 + s2 = 2 si, i = 1,4 ; 1 - 2 3 -1 1 - 2 1 5 3 1 1 4 3 3 x + 2x2 x + 2x2 - 6 + s3 = 1 x1, x2 – свободные 1 - 4 - 7 - 5 - 2 4 - 34 0 5 12 11 2x + x2 2x + x2 - 8 + s4 = 4 5 переменные, x2, x2 xx -1 -1 2 2 0 4 10 -1 3 4 8 18 1 3 1 5 3 1 - 5 0 1 1 5 - 7 4 -1 1 5 10 18 40 Определение 1. Решение системы, соответствующее нулевым значениям свободных переменных, называется базисным. Очевидно, что 2 3 - 3 14 3 -13 - 6 1 7 17 базисное решение будет допустимым, если все.

si 0, i = 1,Составим симплекс-таблицу.

58 x2 x1 s1 s2 s3 sx2 x1 s1 s2 s3 s1* s1 –1 1 0 0 0 x2 1 0 0 0 2/3 –1/3 4/s2 1 0 0 1 0 0 2 0 1 0 0 –1/3 2/3 10/xs3 2 1 0 0 1 0 6 0 0 1 0 –1 1 ss4 1 2 0 0 0 1 s2 0 0 0 1 –2/3 1/3 2/F 2 3 0 0 0 0 0 0 0 0 –1/3 –4/3 - 38 F Если все элементы последнего столбца меньше нуля (кроме Fmin = -12 2 3 zmax = 12 2 3; x1 = 10 3; x2 = 4 3.

последнего элемента последней строки F ), то решение неограниченное е Пример 2. Метод искусственного базиса для основной задачи.

и оптимального решения не существует.

Условия оптимальности: если все элементы последней строки F 0, то полученное решение оптимально.

z = 2x1 - 3x2 + 4x3 max Умножив обе части первого Выбор генерального столбца (кроме последнего): в последней строке выбираем положительный элемент. 2x1 - 2x2 - x3 = -2 уравнения на (–1) и прибавив к Выбор генеральной строки: за генеральную строку берется та левым частям обоих уравнений - x1 + 3x2 - 2x3 =строка (кроме последней), в которой отношение свободного члена x 0, j =1,искусственные неизвестные к положительному элементу генерального столбца было бы минимальным.

j w1 и w2, получим - 2x1 + 2x2 + x3 + w1 = x2 x1 s1 s2 s3 s расширенную систему x2 –1 1 0 0 0 - x1 + 3x2 - 2x3 + w2 =s2 0 1* –1 1 0 0 x 0, j =1,j s3 0 3 –2 0 1 0 s4 0 3 –1 0 0 1 Составим на множестве планов F 0 5 –2 0 0 0 –(x) = w1 + w2 min расширенной системы вспомогательную функцию Повторяем итерации.

x2 x1 s1 s2 s3 s4 x2 x1 s1 s2 s3 sx2 1 0 0 1 0 0 2 x2 1 0 0 1 0 0 x1 0 1 –1 1 0 0 1 x1 0 1 0 –2 1 0 (x) = w1 + w2 = 13 + 3x1 - 5x2 + x3;

s3 0 0 1* –3 1 0 1 s1 0 0 1 –3 1 0 (x)- 3x1 + 5x2 - x3 = 13.

s4 0 0 2 –3 0 1 4 s4 0 0 0 3* –2 1 F 0 0 3 –5 0 0 –7 0 0 0 4 –3 0 –F 60 z = 4x1 + x2 min = R1 + R2 min x1 x2 x3 w1 w2 Свободный член так как «=»;

3x1 + x2 = 3 3x1 + x2 + R1 = 4x + 3x2 6 4x + 3x2 - s1 + R2 = 6 так как s1 x1 =0 = -6 < 0;

w1 –2 2* 1 1 0 2 I 1 x2 =x + 2x2 4 x + 2x2 + s2 = w2 –1 3 –2 0 1 11 II - 3 I 1 так как «все нормально»;

–3 5 –1 0 0 13 III - 5 I x1, x2 0 x1, x2 => s2 – базисный x2 –1 1 1/2 1/2 0 1 I + II = R1 + R2 = 3 - 3x1 - x2 + 6 - 4x1 - 3x2 + s1 = 9 - 7x1 - 4x2 + s1.

w2 2* 0 –7/2 –3/2 1 8 II 2 0 –7/2 –5/2 0 III - II x1 x2 s1 R1 R2 sx2 0 1 –5/4 –1/4 1/2 R3* 1 0 1 0 0 x1 1 0 –7/4 –3/4 1/2 R4 3 –1 0 1 0 0 0 0 –1 –1 s1 2 0 0 0 1 7 4 –1 0 0 0 Так как, то решим задачу min = x1 1/3 0 1/3 0 0 z = 2x1 - 3x2 + 4x3 max;

R0 5/3* –1 –4/3 1 0 x - 5 4 x3 = 5, - 7 4 x3 = 4;

sx1 0 5/3 0 –1/3 0 1 z = 2(4 + 7 4 x3)- 3(5 + 5 4 x3)+ 4x3 = -7 +15 4 x3;

0 5/3 –1 –7/3 0 0 F = -2x1 + 3x2 - 4x3 = 7 -154 x. x1 0 1/5 3/5 –1/5 0 3/x0 1 –3/5 –4/5 3/5 0 6/xx1 xs0 0 1 1 –1 1 x2 I 0 1 –5/4 0 0 0 –1 –1 0 x1 II 1 0 –7/4 4 - 3I Так как, решим задачу:

:

min = III 0 0 –15/4 7 - 5I F z = 4(3 5 -1 5s1)+ (6 5 + 3 5 s1)=18 5 -1 5 s1;

Следовательно, оптимального плана не существует.

x1 = 3 5 -1 5s1, Пример 3. Рассмотрим общую задачу. Двухфазный симплекс = 6 5 + 3 5 s1.

xметод.

62 Самостоятельная работа № Найти ситуацию равновесия и значение игры в смешанных стратегиях x1 x2 s1 x1 = при помощи ЛП. Сделать проверку x1 1 0 1/5 3/x2 = 5 1 2 3 4 x2 0 1 –3/5 6/ - 3 1 2 3 4 2 -1 -1 2 -1 3 4 2 zmin = 5 s2 0 0 1* 0 5 4 1 1 4 1 3 1 3 1 - 5 2 1 -1 - 2 3 4 5 1 1 1 5 4 -1 1 1 3 0 0 1/5 18/z 6 7 8 9 x1 1 0 0 2/1 -1 2 1 -1 1 0 1 2 1 -1 2 3 2 1 1 1 3 - 4 1 -1 x2 0 1 0 9/5 4 7 3 -1 2 1 2 1 - 6 1 5 - 8 - 3 3 3 1 12 11 - 6 - s1 0 0 1 11 12 13 14 0 0 0 17/5 1 2 5 2 2 3 -1 4 2 3 2 -1 4 2 z 2 1 3 0 2 -1 - 3 7 - 3 2 1 3 2 1 -8 - 2 19 3 8 -1 -1 -1 1 1 - 3 1 3 Упражнения: решить П3 и Д3 симплекс-методом:

Самостоятельная работа № z = 21x1 + 4x2 + 5x3 -13x4 + 7x5 max Найти ситуацию равновесия и значение игры в смешанных стратегиях 2x1 + 3x2 - x4 + 4x5 графоаналитическим методом x - x2 + 2x3 + x4 - 2x5 3x - x2 + x3 - 2x4 - x5 = 1 2 3 4 2 x j 0, j = 1,5 - 2 - 3 2 - 2 3 4 1 -1 2 4 0 5 4 -1 1 1 4 1 5 3 - 6 - 2 f =12y1 + 8y2 + y3 min 6 7 8 9 2y1 + y2 + 3y3 1 0 1 3 2 3y - y2 - y3 = 4 2 1 - 2 4 3 2 5 2 1 -1 1 - 3 5 - 2 1 2 1 3 4 1 2y + y3 = - y1 + y2 - 2y3 = -13 11 12 13 14 4y1 - 2y2 - y3 1 2 - 12 4 10 4 - 2, y2 1 -1 - 2 2 y - 4 8 18 2 3 7 - 3 0 2 - 4 -1 2 - 64 Самостоятельная работа № 5 Самостоятельная работа № Рассмотреть игру на доминирование и найти ситуацию равновесия Найти значение игры в смешанных стратегиях с помощью итеративного метода 1 2 1 2 3 4 - 3 1 - - 4 3 - 3 5 1 2 3 5 - 3 1 2 3 4 2 -1 -1 2 -1 3 4 2 - 3 1 4 2 0 5 4 1 1 4 1 3 1 3 1 - 5 2 1 - 1 - 2 3 -1 1 2 1 5 3 2 -1 -1 1 1 1 - 2 3 4 5 1 1 1 5 4 -1 1 1 3 1 - 4 - 7 - 5 - 2 4 - 34 0 3 4 6 6 7 8 9 4 5 1 -1 2 1 -1 1 0 1 2 1 -1 2 3 -1 -1 2 -1 3 3 0 4 10 2 1 1 1 3 - 4 1 -1 4 7 3 -1 2 1 4 8 18 1 3 1 5 3 1 - 5 0 2 1 - 6 1 5 - 8 - 3 3 3 1 12 11 - 6 - 1 1 5 - 7 4 -1 1 5 10 -18 40 17 2 3 - 3 14 3 -13 - 6 1 7 17 11 12 13 14 1 2 5 2 2 3 -1 4 2 3 2 -1 4 2 7 8 2 1 3 0 2 -1 - 3 7 - 3 2 1 3 2 1 -1 2 2 3 4 1 0 1 - 8 - 2 19 3 8 - 1 -1 -1 1 1 - 3 1 3 - 3 1 2 2 1 -1 2 0 2 1 1 1 5 - 4 - 5 - 3 -1 2 1 1 3 3 3 3 - 4 1 - 3 - 4 - 1 5 - 8 - 5 -12 14 7 12 - 10 11 1 9 1 2 1 -1 1 1 2 5 2 1 1 1 3 - 4 2 1 -1 2 5 2 1 3 1 12 11 3 3 - 6 - 5 6 2 19 13 14 2 2 1 4 - 2 -1 2 1 4 2 3 0 2 0 2 -1 3 3 7 3 2 5 1 11 1 -1 -1 - 4 - 2 5 3 8 1 18 2 0 - 4 - 7 3 1 - 66 Рекомендуемая литература ОГЛАВЛЕНИЕ 1. Воробьев Н. Н. Философская энциклопедия. – М., 1970. – Т. 5. – С. 208– Занятие № 1................................................................................................................. 210. 1.1. Содержание теории игр.................................................................................... 2. Воробьев Н. Н. Основы теории игр: бескоалиционные игры. – М., 1984. 1.2. Классификация игр........................................................................................... 3. Дж. Ролз. Теория справедливости. – Новосибирск: Изд-во НГУ, 1995. 1.3. Игра в нормальной форме................................................................................ 4. Дюбин Г. Н., Суздаль В. Г. Введение в прикладную теорию игр. – М.: 1.4. Равновесие по Нэшу......................................................................................... Наука, 1981. 1.5. Оптимальность по Парето............................................................................. 5. Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. – М.: Высшая Занятие № 2................................................................................................................школа, 1998. 2.1. Антагонистические игры. Седловая точка....................................................6. Печерский С. Л., Беляева А. А. Теория игр для экономистов. – СПб.: Изд- 2.2. Принцип максмина и минимакса.................................................................. во Европейского университета, 2001. Занятие № 3............................................................................................................... 7. Полтерович В. М. Кризис экономической теории // Труды семинара «Не- 3.1. Смешанные стратегии матричных игр......................................................... известная экономика». – М.: ЦЭМИ РАН, 1997. 3.2. Ситуация равновесия в смешанных стратегиях.......................................... 8. Aumann R. J. Lectures on Game Theory. – San Francisco: Westview Press, 3.3. Свойства оптимальных смешанных стратегий............................................ 1989. 3.4. Равновесие по Нэшу в смешанных стратегиях в биматричной игре......... 9. Dixit A., Nalebuff B. Thinking Strategically: The Competitive Edge in Business, Занятие № 4. Нахождение значения игры при помощи линейного Politics and Everyday Life. – N.Y.: Norton, 1991. программирования (ЛП).......................................................................................... 10. Kreps D. M. A Couse in Microeconomic Theory. – Princeton University Press, Занятие № 5. Графоаналитический метод решения (2 n)- либо 1990.

(m 2)- матричных игр........................................................................................... 11. Maynard Smith J. The Theory of Game and Evolution in Animal Conflicts // Journal of Theoretical Biology. – 1974, 47. – 209–221. Занятие № 6............................................................................................................... 12. Moulin H. The Strategy of Social Choice. Advanced Textbooks in Economics. 6.1. Доминирование стратегий в биматричной игре.......................................... N 18. – Amsterdam: North-Holland, 1983. 6.2. Доминирование стратегий в антагонистической игре................................ 13. Moulin H. Game Theory for Social Sciences. – N.Y.: University Press, 1986. Занятие № 7. Итеративные методы решения матричных игр.............................. 14. Ordeshook P. Game Theory and Political Theory. – N.Y.: University Press, 7.1. Итеративный метод Брауна – Робинсона (метод фиктивного 1978. разыгрывания)........................................................................................................... 15. Ordeshook P. Game Theory and Political Theory: An Introduction. – Cambrige 7.2. Монотонный итеративный алгоритм решения матричных игр................. University Press, 1986. Приложение............................................................................................................... 16. Ordeshook P. A Political Theory Primer. – N.Y.; London: Routledge, 1992. Рекомендуемая литература....................................................................................... 17. Riker W. The Theory of Political Coalitions. – New Haven, 1962.

18. Riker W., Ordeshook P. Introduction to Positive Political Theory. – New Jersey:

Prentice-Hall, 1973.

19. Shubik M. Game Theory in the Social Sciences. – Princeton University Press, 1984.

20. Swan A. de. Coalition Theories and Cabinet Formations. – Amsterdam: NewHolland, 1973.

21. Van Deemen Ad. M. A. Coalition Formation and Social Choice. – Dordrecht:

Kluwer Academic Publishers, 1997.

68 ДЛЯ ЗАПИСЕЙ Учебное издание Ксения Владимировна Григорьева БЕСКОАЛИЦИОННЫЕ ИГРЫ В НОРМАЛЬНОЙ ФОРМЕ Часть Редактор О. Д. Камнева Корректор К. И. Бойкова Компьютерная верстка И. А. Яблоковой Подписано к печати 19.11.2007. Формат 60 84 1/16. Бум. офсетная.

Усл. печ. л. 4,5. Уч.-изд. л. 4,62. Тираж 200 экз. Заказ 209. «С» 95.

Санкт-Петербургский государственный архитектурно-строительный университет.

Pages:     | 1 |   ...   | 3 | 4 ||






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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