Состязательные задачи

Состязательные задачи (игры) могут быть:

по вариантности стратегий - с чистой (применяется одна из возможных стратегий) или смешанной (если применяется несколько стратегий);

по числу применяемых стратегий – на конечные и бесконечные;

по количественному результату – с нулевой или ненулевой суммой;

по характеру взаимоотношений игроков – некооперативные (антагонистические) и кооперативные (коалиционные);

по числу сторон – двух или многих игроков;

по характеру протекания – непрерывные и дискретные;

по количеству информации у сторон – с полной, с вероятностной или с отсутствием, в т.ч. игры с природой, когда партнера заменяет среда, безразличная к действиям игрока.

Простейшей и наиболее разработанной является теория "матричных" игр двух сторон с нулевой суммой.

Исходные данные задаются в виде матрицы выигрышей c_ij (таблица 3.33).

Таблица 3.33 – Пример матрицы выигрышей

В этом примере сторона А имеет три возможные стратегии А1, А2, А3, а В – четыре (В1, В2, В3, В4). Сторона А не знает, как поступит сторона В, однако действуя наиболее целесообразно, она должна выбирать стратегию А2, которая гарантирует ей наибольший (11) из трех наименьших выигрышей (10,11,9).

Принято называть, что сторона руководствуется принципом максиминного выигрыша:

.

Определяемая таким образом величина (а) называется нижней ценой игры, максиминным выигрышем или максимином. Для приведенного примера а=11.

Если рассуждать аналогично, то сторона В должна выбирать стратегию В1, которая гарантирует ей наименьший (12) из четырех возможных наибольших проигрышей, т.е. она руководствуется принципом максиминного проигрыша:

.

Величина (b) называется верхней ценой игры, или минимаксом. Для приведенного примера b=12.

Справедливо, что b≥a.

Такая стратегия игроков называется принципом минимакса или принципом осторожности.

Если а = в, то такая точка называется седловой.

Рациональные правила поведения сторон:

1. Если известна стратегия стороны В, то сторона А должна выбрать A_i, которая дает максимальный выигрыш.

2. Если стратегия В неизвестна, то сторона А должна воспользоваться своей максиминной стратегией.

3. Если стратегия В неизвестна, но состязательная игра имеет седловую точку, то наиболее выгодно для стороны А не отклоняться от оптимальной точки, соответствующей седловой.

Если матрица игры не имеет седловой точки, то оказывается, что для определения успеха необходимо выбирать стратегии А и В с определенными вероятностями (частотами) при многократной игре. Такие стратегии называются смешанными.

Решение игровых задач в смешанных стратегиях осуществляется по итеративным алгоритмам Брауна или Неймана или сводится к задаче линейного программирования.

В основе алгоритма Брауна (фиктивной игры) лежит предположение, что игра играется много раз, а игроки выбирают свои стратегии, руководствуясь опытом ранее сыгранных партий.

Если считать, что выполнено k итераций и в результате получены оценки смешанных стратегий A_c = (A₁, A₂,..., A_k) игрока А и B_c = (B₁, B₂,..., B_k) игрока В, то на очередной итерации игроком А выбирается такая чистая стратегия, которая обеспечит ему максимум в предположении, что игрок В применит смешанную стратегию B_c. Аналогично В применяет чистую стратегию, которая дает минимум выигрыша А, если последним будет использована смешанная стратегия A_c.

Для парной игры с нулевой суммой обозначим вероятность применения стратегии A_i через p_i, а B_j через q_j (A_i – стратегия стороны А, B_j – стратегия стороны В).

Сумма вероятностей всех стратегий для каждой из сторон равна 1:

Тогда ; .

Средний выигрыш стороны А

,

где m и n – соответственно число различных стратегий сторон А и В.

Для поиска оптимума необходимо взять частные производные и приравнять их к нулю

;

.

Решение системы дает оптимальные значения вероятностей p_iопт и q_jопт , которые должны быть больше нуля и меньше единицы.

Решение может быть получено реализацией итерационного процесса путем многократного имитационного моделирования игры. Например, следующей стратегией стороны А для приведенного примера является стратегия А1, дающую максимум при стратегии противоположной стороны В1, а сторона В применит стратегию В3, которая дает минимум выигрыша стороной А при ее предыдущей стратегии А2. При следующей итерации сторона А должна применить стратегию А1, дающую максимум выигрыша (14+14=28) при предыдущих стратегиях (В1,В3) противоположной стороны, а стороне В необходимо применить стратегию В3, которая дает минимум выигрыша стороной А при ее предыдущих стратегиях А2 и А1(11+14=25). Аналогично итерационный процесс моделирования проводят до равенства значений цен игры сторон с заданной точностью. Пример игры для пяти итераций приведен в таблице 3.34. Для рассматриваемого примера на 5-й итерации средняя цена игры стороны А равна 11.4 (57/5) и стороны В – 11.8 (59/5).

Таблица 3.34 – Пример моделирования игры двух сторон по алгоритму Брауна

Для решения задачи на основе итерационного алгоритма Брауна может быть использована его компьютерная реализация. Пример учебной программы приведен в приложении 11.

3.1. Основная литература

1. Зайченко, Ю.П. Исследование операций. -Киев,Выща шк.,1988. -549 с.

2. Герасимович, А.И.,Матвеева, Я.И. Теория вероятностей и математическая статистика.-Мн.:Выш.шк.,1978.-301с.

3. Банди, Б. Методы оптимизации. Вводный курс:Пер. с англ.-М.:Радио и связь,1988.-128 с.

4. Банди, Б. Основы линейного программирования: Пер. с англ. -М.:Радио и связь, 1989. -176 с.

5. Геронимус, Б.Л.,Царфин, Л.В. Экономико-математические методы в планировании на автомобильном транспорте. -М.: Транспорт,1988. -192 с.

3.2. Дополнительная литература

1. Акулич, И.Л. Математическое программирование в примерах и задачах.-Мн.:Высш.шк.,1993.–336с.

2. Балашевич, В.А. Алгоритмизация математических методов планирования и управления.-Мн.:Выш.шк.,1978.-144с.

3. Ванчукевич, В.Ф., Седюкевич, В.Н., Холупов, В.С. Грузовые автомобильные перевозки. -Мн.:Выш.шк.,1989. -272 с.

4. Гринчишин, Я.Т., Ефимов, В.И., Ломакович, А.Н. Алгоритмы и программы на Бейсике. - М.:Просвещение, 1988.-160 с.

5. Дайитбеков, Д.М., Калмыкова, О.В., Черепанов, А.И. Программное обеспечение статистической обработки данных.-М.: Финансы и статистика, 1984.-192 с.

6. Дьяконов, В.П. Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ.-М.:Наука,1987.-240с.

7. Задания и методические указания к контрольным работам по дисциплине "Математические модели в расчетах на ЭВМ" для студентов специальностей 24.01 и 24.04. -Мн.:БГПА, 1992. -38 с.

8. Иносэ, Х., Хамада, Т. Управление дорожным движением.-М.:Транспорт, 1983.

9. Кожин, А.П. Математические методы в планировании и управлении грузовыми автомобильными перевозками. -М.: Высш.шк., 1979. -304 с.

10. Кудрявцев, Е.М. Исследование операций в задачах, алгоритмах и программах. -М.:Радио и связь,1984.-184с.

11. Кузнецов, А.В., Холод, Н.И., Костевич, Л.С. Руководство к решению задач по математическому программированию. –Мн.:Выш.шк., 2001. –448 с.

12. Лабораторные работы по дисциплине "Математические модели в расчетах на ЭВМ" для студентов специальностей 24.01-"Организация перевозок и управление на транспорте" и 24.04-"Организация дорожного движения".-Мн.:БГПА,1993.-76с.

13. Лабораторные работы (практикум) по курсу "Экономико-математические методы на автомобильном транспорте" для студентов специальности 1617 -"Эксплуатация автомобильного транспорта". -Мн.:БПИ,1987.-48с.

14. Лабораторный практикум к лабораторным работам по курсу "Экономико-математические методы на автомобильном транспорте"/Подготовка данных для обработки на ЭВМ/ для студентов специальности 1617-"Эксплуатация автомобильного транспорта". -Мн.:БПИ,1986.-51 с.

15. Нейлор Т. Машинные имитационные эксперименты с моделями экономических систем.-М.:Мир,1975.-500с.

16. Нивергельт, Ю., Феррар, Дж.,Рейнголд, Э. Машинный подход к решению математических задач.-М.:Мир, 1977.-346с.

17. Сакович, В.А. Исследование операций (детерминированные методы и модели): Справочное пособие.-Мн.: Выш. шк., 1985. -256 с.

18. Сильянов, В.В. Теория транспортных потоков в проектировании дорог и организации движения.-М.: Транспорт, 1977.

19. Советов, Б.Я., Яковлев, С.А. Моделирование систем.-М.: Высш.шк.,1985. -271 с.

20. Харин, Ю.С. и др. Основы имитационного и статистического моделирования. –Мн.:ДизайнПро, 1997. –288 с.

21. Фурунжиев, Р.И., Гурский, Н.Н., Фурунжиев, Р.И. Применение математических методов и ЭВМ: Прогр. моделирование систем. –Мн.:Выш.шк.,1991. –247 с

22. Таха, Х. Введение в исследование операций. Пер.с англ. Кн.1 и Кн. 2.-М.:Мир,1985. - 479 с. и 496 с.

Поиск по сайту: