Итерационный метод Брауна-Робинсона
Пусть игра задана матрицей A размерности m x n. Каждое разыгрывание игры в чистых стратегиях будет далее называться партией. Метод Брауна-Робинсон — это итеративная процедура построения последовательности пар смешанных стратегий игроков, сходящейся к решению матричной игры.
В 1-ой партии оба игрока выбирают произвольную чистую стратегию. Пусть сыграно k партий, причем выбор стратегии в каждой партии запоминается. В (k + 1)-ой партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш, если противник играет в соответствии с эмпирическим вероятностным распределением, сформировавшимся за k партий. Оценивается интервал для цены игры и, если он достаточно мал, процесс останавливается. Полученные при этом вероятностные распределения определяют смешанные стратегии игроков.
Достоинства метода Брауна:
1. Этот метод ориентирован на произвольную игру G(m×n).
2. Не требует условия aij>0.
3. Легко реализуем программными методами.
Недостатки метода Брауна: скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры.
Рассмотрим метод на примере игры G(3×3).
| Ai \ Bj | B1 | B2 | B3 |
| A1 | |||
| A2 | |||
| A3 |
SA=(p1,p2,p3)
SB=(q1,q2,q3)
Строится следующая матрица:
| 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 – номер стратегии, выбираемой игроком В.
Bi– накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию Bi.
Аj – накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию Аj.
Vmin – нижняя оценка игры = min (накопленный выигрыш)/k.
Vmax – верхняя оценка игры = max (накопленный проигрыш)/k.
Доказано, что V*=(Vmin+Vmix)/2,
Ni - сколько раз выбирается Аi стратегия.
Nj - сколько раз выбирается Bj стратегия.
Итерационный процесс метода Брауна-Робинсон не является, вообще говоря, монотонным. Кроме того, скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры. Однако он обладает одним неоспоримым преимуществом, которое заключается в исключительной простоте программирования метода.
Варианты заданий:
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. Факторами, влияющими на его решение, являются: стоимость автомобиля (С), стоимость обслуживания (О), стоимость поездки по городу (Г) и сельской местности (М). Следующая таблица содержит необходимые данные, соответствующие трехгодичному сроку эксплуатации автомобиля.
Используйте указанные стоимости для построения матриц сравнений. Оцените согласованность матриц и определите модель автомобиля, которую следует выбрать.