Итерационный метод Брауна-Робинсона

Пусть игра задана матрицей A размерности m x n. Каждое разыгрывание игры в чистых стратегиях будет далее называться партией. Метод Брауна-Робинсон — это итеративная процедура построения последовательности пар смешанных стратегий игроков, сходящейся к решению матричной игры.

В 1-ой партии оба игрока выбирают произвольную чистую стратегию. Пусть сыграно k партий, причем выбор стратегии в каждой партии запоминается. В (k + 1)-ой партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш, если противник играет в соответствии с эмпирическим вероятностным распределением, сформировавшимся за k партий. Оценивается интервал для цены игры и, если он достаточно мал, процесс останавливается. Полученные при этом вероятностные распределения определяют смешанные стратегии игроков.

Достоинства метода Брауна:

1. Этот метод ориентирован на произвольную игру G(m×n).

2. Не требует условия a_ij>0.

3. Легко реализуем программными методами.

Недостатки метода Брауна: скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры.

Рассмотрим метод на примере игры G(3×3).

Ai \ Bj	B1	B2	B3
A1
A2
A3

S_A =(p₁,p₂,p₃)

S_B =(q₁,q₂,q₃)

Строится следующая матрица:

k	i	B1	B2	B3	j	A1	A2	A3	Vmin	Vmax	V*
			0				9				4.5
			9				18		4.5		6.75
				11			18		3.67		4.84
				11		22		22	…	…	…
	…	…	…	…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…	…	…	…	…

где:
k – номер партии.

i – номер стратегии, выбираемой игроком A.

j – номер стратегии, выбираемой игроком В.

B_i– накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию B_i.

А_j – накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию А_j.

Vmin – нижняя оценка игры = min (накопленный выигрыш)/k.

Vmax – верхняя оценка игры = max (накопленный проигрыш)/k.

Доказано, что V^*=(Vmin+Vmix)/2,

N_i - сколько раз выбирается А_i стратегия.

N_j - сколько раз выбирается B_j стратегия.

Итерационный процесс метода Брауна-Робинсон не является, вообще говоря, монотонным. Кроме того, скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры. Однако он обладает одним неоспоримым преимуществом, которое заключается в исключительной простоте программирования метода.

Варианты заданий:

1.

	В1	В2	В3	В4	В5
А1	-3				-1
А2	-1
А3	-2
А4			-1	-2	-1
А5	-1

 

2.

	В1	В2	В3	В4	В5
А1		-3		-5
А2	-3	-4		-9	-2
А3				-8	-9
А4		-2		-9
А5				-7

 

3.

	В1	В2	В3	В4	В5
А1	-5			-2	-2
А2	-2
А3
А4		-2
А5	-1

 

4.

	В1	В2	В3	В4	В5
А1	-3				-4
А2	-2				-2
А3			-1
А4		-2
А5	-3				-5

 

5.

	В1	В2	В3	В4	В5
А1
А2
А3					-3
А4		-3
А5	-6

 

6.

	В1	В2	В3	В4	В5
А1
А2				-6
А3
А4					-2
А5		-5			-5

 

7.

	В1	В2	В3	В4	В5
А1
А2	-3	-2	-1
А3
А4			-4
А5

 

8.

	В1	В2	В3	В4	В5
А1
А2					-3
А3
А4
А5			-1		-5

 

9.

	В1	В2	В3	В4	В5
А1
А2
А3		-2
А4
А5	-1	-2	-3	-4	-5

 

10.

	В1	В2	В3	В4	В5
А1
А2			-4
А3				-1
А4
А5					-4

 

11.

	В1	В2	В3	В4	В5
А1					-2
А2
А3		-1		-2
А4	-4
А5

 

12.

	В1	В2	В3	В4	В5
А1					-7
А2
А3					-2
А4	-5	-2
А5				-2

 

13.

	В1	В2	В3	В4	В5
А1
А2
А3		-2		-5
А4	-4
А5					-1

 

14.

	В1	В2	В3	В4	В5
А1		-1
А2
А3
А4		-3			-3
А5

 

15.

	В1	В2	В3	В4	В5
А1		-6
А2
А3
А4		-1			-4
А5			-1

 

16.

	В1	В2	В3	В4	В5
А1
А2
А3			-3
А4
А5				-5

 

 

17.

	В1	В2	В3	В4	В5
А1					-5
А2
А3
А4
А5

 

18.

	В1	В2	В3	В4	В5
А1		-6
А2
А3				-7
А4
А5					-5

 

19.

	В1	В2	В3	В4	В5
А1
А2			-3
А3				-5
А4
А5		-7

 

20.

	В1	В2	В3	В4	В5
А1	-2
А2
А3					-2
А4		-1
А5			-2

 

21.

	В1	В2	В3	В4	В5
А1
А2			-4
А3
А4		-5	-2
А5

 

22.

	В1	В2	В3	В4	В5
А1
А2				-5
А3
А4				-1
А5					-3

 

23.

	В1	В2	В3	В4	В5
А1
А2
А3
А4			-1
А5

 

 

24.

	В1	В2	В3	В4	В5
А1
А2
А3					-4
А4			-1
А5

 

25.

	В1	В2	В3	В4	В5
А1
А2
А3			-2
А4
А5				-5

 

 

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

 

 

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

Тема: Решение многокритериальной задачи

Задание: решить задачу согласно варианту методом анализа иерархий или методом ранжирования.

Требования к выполнению работы:

1. Нарисовать иерархическую структуру задачи.

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

3. Определить согласованность матриц.

4. Рассчитать количественный индикатор качества каждой альтернативы и сделать выводы.

Для метода ранжирования

1. Разбить множество критериев на подмножества для каждой гипотезы.

2. Рассчитать индексы согласия и несогласия.

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

4. Продолжить выделение ядер до получения решения.

Варианты заданий

 

1. Отдел кадров фирмы сузил поиск будущего сотрудника до трех кандидатур: Стив (S), Джейн (J) и Майса(M). Конечный отбор основан на трех критериях: собеседование (С), опыт работы (О) и рекомендации (Р). Отдел кадров ис­пользует матрицу А (приведенную ниже) для сравнения трех критериев. После проведенного собеседования с тремя претендентами, сбора данных, относящихся к опыту их работы и рекомендациям, построены матрицы А_С, А_О и А_Р. Какого из трех кандидатов следует принять на работу? Оцените согласованность данных.

2. Жена и муж выбирают участок для строительства дома. Критериями выбора являются: инфраструктура, время поездки на работу и стоимость. Имеется три участка А, В и С, которые характеризуются следующими параметрами:

 

Критерии   Участки	Инфраструктура Шкала 1-10	Стоимость Тыс руб.	Время поездки на работу, мин
Муж	Жена
А
В
С

 

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

Мнение мужа в два раза весомее жены.

3. Кевин и Джун Парки (Kи Д) покупают новый дом. Рассматриваются три вари­анта — А, В и С. Парки согласовали два критерия для выбора дома: площадь зеленой лужайки (Л) и близость к месту работы (Б), а также разработали матрицы сравнений, приведенные ниже. Необходимо оценить три дома в поряд­ке их приоритета и вычислить коэффициент согласованности каждой матрицы.

4. Жена и муж выбирают участок для строительства дома. Критериями выбора являются: время поездки на работу, инфраструктура и стоимость. Имеется пять участков А, В, С, D и E которые характеризуются следующими параметрами:

 

Критерии   Участки	Стоимость Тыс руб.	Инфраструктура Шкала 1-10	Время поездки на работу, мин
Муж	Жена
А
В
С
D
E

 

Определите оптимальный вариант методом ранжирования, если 20 экспертов определили веса критериев следующим образом:

Стоимость – 8;

Расстояние до магазина – 1;

Расстояние до школы – 1;

Время жены – 6;

Время мужа – 4.

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

Критерии   Спорт.	Стоимость оборудования Тыс руб.	Оплата тренера, тыс. руб.	Количество желающих
Шахматы
Волейбол
Шпаги

Определены девять матриц сравнения для ЛПР на втором иерархическом уровне и определены относительные веса.

ЛПР	Школьный совет	Районо	Родители
Критерий   Секция	С	О	К	С	О	К	С	О	К
Шахматы	0,1	0,2	0,3	0,3	0,5	0,2	0,7	0,1	0,3
Волейбол	0,5	0,4	0,2	0,4	0,2	0,4	0,1	0,4	0,2
Шпаги	0,4	0,4	0,5	0,3	0,3	0,4	0,2	0,5	0,5

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

При вынесении окончательного решения мнение школьного совета, районо и родителей учитываются в соотношении 2:3:1.

6. Автор книги по исследованию операций определил три критерия для выбора из­дательства, которое будет печатать его книгу: процент авторского гонорара (R), уровень маркетинга (M) и размер аванса (A). Издательства H и P проявили ин­терес к изданию книги. Используя приведенные ниже матрицы сравнения, необ­ходимо дать оценку двум издательствам и оценить согласованность решения.

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

Критерии   Спорт.	Стоимость инвентаря Тыс руб.	Оплата тренера, тыс. руб.	Количество желающих	Затраты родителей, тыс. руб
Шахматы				0,7
Волейбол				2,5
Шпаги
Баскетбол				2,5
Спортивная гимнастика		5,5		3,5

 

Определите оптимальный вариант методом ранжирования, если 20 экспертов определили веса критериев следующим образом:

Стоимость инвентаря – 8;

Оплата тренера – 6;

Количество желающих – 5;

Затраты родителей – 3;

8. Садовник и хозяин решают вопрос о разбивке сада. Они хотят посадить яблоню или вишню или яблоню и вишню пополам. Критериями выбора являются: затраты на покупку саженцев и будущая прибыль от полученных плодов.

Критерии   Спорт.	Покупка саженцев Тыс. руб.	Прибыль, тыс. руб.
Яблоня
Вишня

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

При вынесении окончательного решения мнение садовника в 3 раза важнее мнения хозяина.

 

9. Профессор политологии планирует предсказать исход выборов в местный школьный совет. Кандидаты I, B и S баллотируются на одно место. Профес­сор делит всех избирателей на три категории: левые (L), центристы (C) и пра­вые (R). Оценка кандидатов основывается на трех факторах: педагогический опыт (О), отношение к детям (Д) и характер (X). Ниже приведены матрицы сравнения для первого иерархического уровня, связанного с градацией изби­рателей (левые, центристы и правые).

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

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

10. Брат и сестра выбирают спортивную секцию, руководствуясь стоимостью абонента и затратами на инвентарь и спортивное снаряжение. У них есть следующие варианты: конный спорт, волейбол, теннис или фехтование.

Критерии   Спорт.	Единовременные затраты руб.	Стоимость абонемента, руб.
Конный спорт
Волейбол
Фехтование
Теннис

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

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

 

11. Школьный округ крайне заинтересован в сокращении своих расходов, что вызвано очередным уменьшением бюджетного финансирования начальных школ. Есть две возможности решить эту проблему: ликвидировать програм­му физического воспитания (Ф) или программу музыкального образования (M). Управляющий округа сформировал комитет с равным представительст­вом от местного школьного совета (С) и ассоциации родителей и учителей (P) для изучения ситуации и выработки предложения. Комитет принял решение изучить ситуацию с точки зрения ограничения бюджета (Б) и потребностей учеников (П). Проведенный анализ дал следующие матрицы сравнения.

Проанализируйте ситуацию, связанную с принятием решения, и выработай­те соответствующее предложение.

12. Решив купить автомобиль, человек сузил свой выбор до трех моделей: М1, М2 и М3. Факторами, влияющими на его решение, являются: стоимость ав­томобиля (С), стоимость обслуживания (О), стоимость поездки по городу (Г) и сельской местности (М). Следующая таблица содержит необходимые дан­ные, соответствующие трехгодичному сроку эксплуатации автомобиля.

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