8.Формальное представление игр
А | А1 | А2 | Аn | Игрок А |
В | В1 | В2 | Вm | Игрок В |
AiBj=pij выигрыш игрока A и выигрыш игрока B qij
Игра с нулевой суммой Aij+Bij=0; pij выигрыш игрока A и проигрыш игрока B
Игра поиск А1 – ищет в 1 месте, А2 – ищет во 2 месте. В1 – прячется в 1 месте, В2 – прячется во 2 месте, проигрыш=отрицательный выигрыш.
Оптимальная стратегия случайное чередование.
Платежная матрица:
| В1 | В2 |
А1 | 1 | -1 |
А2 | -1 | 1 |
Игра с ненулевой суммой (делема заключенного) А, В – заключенные.
А1 – свидетельствует против В, А2 – не свидетельствует, В1 – свидетельствует против А, В2 – не свидетельствует.
| В1 | В2 |
А1 | (5;5) | (0;10) |
А2 | (10;0) | (1;1) |
9.Принцип минимакса для антагонистических игр
| В1 | В2 | Вn | min |
|
А1 | P11 | P12 | P1n | α1 | max |
А2 | P21 | P22 | P2n | α2 | |
Аm | Pm1 | Pm2 | pmn | αm | |
max | β1 | β2 | βn |
|
|
| min |
|
| ||
α – гарантированный выигрыш, β – гарантированный проигрыш.
α=maxαi=max(min pij) – максмин – нижняя цена,
β=minβj=min (max pij) – минмакс – верхняя цена.
Игрок А какую стратегию я не выбрал, игрок В выберет стратегию, при которой мой выигрыш минимален. Игрок В какую стратегию я не выбрал, игрок А выберет стратегию, при которой его выигрыш максимален.
Yandex.RTB R-A-252273-3- 1.Экономико-математическая модель транспортных задач
- 2.Общая формулировка тз
- 3.Теор. (о ранге сис-мы ограниченной закр. Тз) и следствие из нее. Открытая тз
- 4.Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.
- 5.Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.
- 6.Понятие об игровых моделях
- 7.Классификация игр.
- 8.Формальное представление игр
- 10.Фундаментальное неравенство для цен антагонистических игр
- 11.Седловая точка. Теорема о седловой точке
- 12.Понятие смешанной стратегии, чистой стратегии, активной стратегии
- 13.Теорема об активной стратегии. Решение игры 2×2 (формулы)
- 14.Графический метод решения игры 2×2
- 15.Доминирующие стратегии, заведомо невыгодные стратегии, упрощение игр.
- 16.Сведение игры m×n к двойственным задачам лп
- 17.Игры с природой: постановка задачи, матрица рисков.
- 18.Критерий принятия решений в условиях риска (Байеса I и II). Лемма (показатели эффективности и неэффективности стратегии). Теорема об эквивалентности критериев Байеса.
- 19.Критерий принятия решений в условиях неопределенности: критерий Лапласа и Сэвиджа
- 20.Критерий принятия решений в условиях неопределенности: критерий Вальда и Гурвица. Показатель оптимизма.
- 21.Общая постановка задачи динамического программирования (дп). Особенности задачи дп
- 22.Принцип оптимальности и уравнения Беллмана
- 23. Задача о распределении средств между n предприятиями (основные уравнения).
- 25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные, несвязные графы. Дерево, лес.
- 2 6. Планарные и плоские графы. Изоморфные графы. Полные графы.
- 27. Эйлеровы графы. Крит. Сущ-я эйлерова цикла в графе. Полуэйлеров граф. Задача о Кенигсбергских мостах.
- 28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.
- 29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.
- 30.Комбинаторная постановка задачи коммивояжера.
- 31. Постан-ка зад. Коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.
- 32. Постановка задачи коммивояжера на языке теории графов.
- 33. Теорема о приведения матрицы расстояний в зк. Оценка маршрута снизу (нижняя граница).
- 34. Ветвление, оценки нулевых переходов, уточнение нижней границы маршрута.
- 35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.