- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Нелинейное программирование презентация
Содержание
- 1. Нелинейное программирование
- 2. Тема занятия Антагонистические игры
- 3. Домашнее задание (60 баллов) Придумать парную, конечную
- 4. Основные понятия Конфликтные ситуации Это ситуации в
- 5. Основные понятия Теория игр Это математическая теория
- 6. Основные понятия Игра Это упрощенная, схематизированная модель
- 7. Основные понятия Игры бывают Парными – когда
- 8. Основные понятия Игра с нулевой суммой Это
- 9. Основные понятия Ход Ходом в теории игр
- 10. Основные понятия Ходы бывают Личные Это
- 11. Основные понятия Стратегия Стратегией называют совокупность правил, определяющих выбор варианта действий при каждом личном ходе.
- 12. Основные понятия В зависимости от числа возможных
- 13. Основные понятия Оптимальная стратегия Это такая стратегия,
- 14. Платежная матрица Рассмотрим конечную, парную игру двух
- 15. Пример Игра «поиск» Имеется два игрока А
- 16. Игра «поиск» Решение Игра состоит из двух
- 17. Игра «поиск» Решение Имеем игру 2х2. Платежная матрица: Bj Ai
- 18. Игра «поиск» Решение Имеем игру 2х2. Платежная матрица: Bj Ai
- 19. Основные понятия Смешанная стратегия Это такая стратегия
- 20. Смешанные стратегии Обозначение смешанных стратегий Пусть имеется
- 21. Смешанные стратегии Обозначение смешанных стратегий SB=(q1,q2,…,qn) Обозначение смешанной стратегии игрока, где q1+q2+…+qn=1
- 22. Игра «три пальца» Игра «три пальца» Игроки
- 23. Игра «три пальца» Решение Имеем игру 3х3. Платежная матрица: Bj Ai
- 24. Игра «три пальца» Решение Имеем игру 3х3. Платежная матрица: Bj Ai
- 25. Пример Игра «вооружение и самолет» В нашем
- 26. Игра «вооружение и самолет» Решение Имеем игру 3х3. Платежная матрица: Bj Ai
- 27. Нижняя и верхняя цена игры Принцип минимакса
- 28. Нижняя и верхняя цена игры Принцип минимакса
- 29. Нижняя и верхняя цена игры Принцип минимакса
- 30. Нижняя и верхняя цена игры Принцип минимакса
- 31. Пример Найти верхнюю и нижнюю цены в играх «Поиск» «Три пальца» «Вооружение и самолет»
- 32. Игра «поиск» Решение α=? β=? Bj Ai
- 33. Игра «поиск» Решение α=? β=? Bj Ai
- 34. Игра «поиск» Решение α=-1 β=1 Bj Ai
- 35. Игра «три пальца» Решение α=? β=? Bj Ai
- 36. Игра «три пальца» Решение α=-3 β=4 Bj Ai
- 37. Игра «вооружение и самолет» Решение α=? β=? Bj Ai
- 38. Игра «вооружение и самолет» Решение α=0,7 β=0,7 Bj Ai
- 39. Седловая точка игры Игры в которых нижняя
- 40. Седловая точка игры Игры в которых нижняя
- 41. Решение игры В общем случае решением игры
- 42. Основные понятия Активные стратегии Это те стратегии
- 43. Тема следующего занятия Статистические игры с единичным экспериментом
- 44. Спасибо за внимание
Тема занятия Антагонистические игры
Слайд 3Домашнее задание (60 баллов)
Придумать парную, конечную игру с нулевой суммой, состоящую
только из личных ходов, формализовать ее, построить платежную матрицу и найти седловую точку (или показать, что ее нет).
Слайд 4Основные понятия
Конфликтные ситуации
Это ситуации в которых сталкиваются интересы двух или более
сторон, преследующих различные цели
Любой шаг каждой из сторон зависит от того какой образ действий выберет противник
Любой шаг каждой из сторон зависит от того какой образ действий выберет противник
Слайд 5Основные понятия
Теория игр
Это математическая теория конфликтных ситуаций
Задача теории – выработка рекомендаций
по рациональному образу действий участников конфликта
Слайд 6Основные понятия
Игра
Это упрощенная, схематизированная модель ситуации
От реальной конфликтной ситуации игра отличается
тем, что ведется по определенным правилам
Слайд 7Основные понятия
Игры бывают
Парными – когда в игре сталкиваются интересы двух противников
Множественными
- более двух противников
Мы будем рассматривать только первые
Мы будем рассматривать только первые
Слайд 8Основные понятия
Игра с нулевой суммой
Это такая игра, когда один игрок выигрывает
ровно столько, сколько проигрывает второй
Мы будем рассматривать только такие игры
Мы будем рассматривать только такие игры
Слайд 9Основные понятия
Ход
Ходом в теории игр называется выбор одного из предусмотренных правилами
игры действий и его осуществление.
Развитие игры во времени состоит из последовательности ходов.
Развитие игры во времени состоит из последовательности ходов.
Слайд 10Основные понятия
Ходы бывают
Личные
Это сознательный выбор игроком одного из вариантов действий
и его осуществление
Случайные
Выбор осуществляется не решением игрока, а каким-либо механизмом случайного выбора
Теория игр занимается анализом игр, содержащих только личные ходы
Случайные
Выбор осуществляется не решением игрока, а каким-либо механизмом случайного выбора
Теория игр занимается анализом игр, содержащих только личные ходы
Слайд 11Основные понятия
Стратегия
Стратегией называют совокупность правил, определяющих выбор варианта действий при каждом
личном ходе.
Слайд 12Основные понятия
В зависимости от числа возможных стратегий игры делятся на
Конечные
У каждого
игрока имеется конечное число стратегий
Бесконечные
Хотя бы у одного игрока число стратегий бесконечно
Бесконечные
Хотя бы у одного игрока число стратегий бесконечно
Слайд 13Основные понятия
Оптимальная стратегия
Это такая стратегия, которая при многократном повторении игры обеспечивает
игроку максимально возможный средний выигрыш.
При выборе этой стратегии основой рассуждений является предположение, что противник так же разумен как и мы, и делает все для того, чтобы помешать нам добиться цели.
При выборе этой стратегии основой рассуждений является предположение, что противник так же разумен как и мы, и делает все для того, чтобы помешать нам добиться цели.
Слайд 14Платежная матрица
Рассмотрим конечную, парную игру двух игроков А и В, в
которой игрок А имеет m стратегий, а игрок В n
Ai возможные стратегии игрока А
Bj возможные стратегии игрогка В
ai,j выигрыш игрока А (проигрыш игрока В)
Ai возможные стратегии игрока А
Bj возможные стратегии игрогка В
ai,j выигрыш игрока А (проигрыш игрока В)
Bj
Ai
Слайд 15Пример
Игра «поиск»
Имеется два игрока А и В. Первый прячется, второй его
ищет. Прятаться можно только в двух местах, любое из которых игрок А выбирает по своему усмотрению.
Если при очередном ходе игрок А спрятался в одном из мест, и
игрок В его нашел, то В получает 1 рубль
игрок В его не нашел, то А получает 1 рубль
Если при очередном ходе игрок А спрятался в одном из мест, и
игрок В его нашел, то В получает 1 рубль
игрок В его не нашел, то А получает 1 рубль
Слайд 16Игра «поиск»
Решение
Игра состоит из двух ходов, оба – личные
У игрока А
две стратегии
Прятаться в месте №1
Прятаться в месте №2
У игрока В тоже две стратегии
Искать в месте №1
Искать в месте №2
Прятаться в месте №1
Прятаться в месте №2
У игрока В тоже две стратегии
Искать в месте №1
Искать в месте №2
Слайд 19Основные понятия
Смешанная стратегия
Это такая стратегия в которой, отдельные «чистые» стратегии чередуются
случайным образом с какими-то вероятностями.
При использовании смешанных стратегий перед каждым ходом путем механизма случайного выбора обеспечивается появление каждой стратегии с некоторой вероятностью.
При использовании смешанных стратегий перед каждым ходом путем механизма случайного выбора обеспечивается появление каждой стратегии с некоторой вероятностью.
Слайд 20Смешанные стратегии
Обозначение смешанных стратегий
Пусть имеется игра в которой игрок А имеет
m стратегий (A1, A2,…, Am), а игрок В - n (B1, B2,…, Bn)
SA=(p1,p2,…,pm)
Обозначение смешанной стратегии игрока А, в которой стратегии A1, A2,…, Am применяются с вероятностями p1,p2,…,pm
Причем p1+p2+…+pm=1
SA=(p1,p2,…,pm)
Обозначение смешанной стратегии игрока А, в которой стратегии A1, A2,…, Am применяются с вероятностями p1,p2,…,pm
Причем p1+p2+…+pm=1
Слайд 21Смешанные стратегии
Обозначение смешанных стратегий
SB=(q1,q2,…,qn)
Обозначение смешанной стратегии игрока, где
q1+q2+…+qn=1
Слайд 22Игра «три пальца»
Игра «три пальца»
Игроки А и В одновременно и независимо
друг от друга показывают один два или три пальца.
Выигрыш (в рублях) равен общему числу показанных пальцев:
Если оно четное – выиграл игрок А
Если оно нечетное – выиграл игрок В
Выигрыш (в рублях) равен общему числу показанных пальцев:
Если оно четное – выиграл игрок А
Если оно нечетное – выиграл игрок В
Слайд 25Пример
Игра «вооружение и самолет»
В нашем распоряжении имеется три вида оружия, а
у противника три вида самолетов
Первым оружием самолеты поражаются с вероятностями соответственно 0,5; 0,6 и 0,8
Вторым - соответственно 0,9; 0,7 и 0,8
Третьим - соответственно 0,7; 0,5 и 0,6
Наша задача – поразить самолет, задача противника – сохранить его непораженным
Первым оружием самолеты поражаются с вероятностями соответственно 0,5; 0,6 и 0,8
Вторым - соответственно 0,9; 0,7 и 0,8
Третьим - соответственно 0,7; 0,5 и 0,6
Наша задача – поразить самолет, задача противника – сохранить его непораженным
Слайд 27Нижняя и верхняя цена игры
Принцип минимакса
Рассмотрим игру m х n
Как определить
наилучшую из стратегий игрока А?
Проанализируем все возможные стратегии Ai
Выбирая Ai мы должны рассчитывать, что противник ответит на нее той, из своих стратегий Вi, для которой наш выигрыш минимален
Проанализируем все возможные стратегии Ai
Выбирая Ai мы должны рассчитывать, что противник ответит на нее той, из своих стратегий Вi, для которой наш выигрыш минимален
Bj
Ai
Слайд 28Нижняя и верхняя цена игры
Принцип минимакса
Найдем минимальной из чисел aij в
i–й строке и обозначим его ai :
αi=min aij
Действуя наиболее осторожно мы должны предпочесть ту стратегию, для которой α i максимально:
α =max α i
αi=min aij
Действуя наиболее осторожно мы должны предпочесть ту стратегию, для которой α i максимально:
α =max α i
j
i
Слайд 29Нижняя и верхняя цена игры
Принцип минимакса
Объеденив обе формулы, получим :
α =max min aij
Величина α называется нижней ценой игры, максиминным выигрышем или максимином.
Стратегия игрока А, соответствующая максимину α называется максиминной стратегией.
Величина α называется нижней ценой игры, максиминным выигрышем или максимином.
Стратегия игрока А, соответствующая максимину α называется максиминной стратегией.
j
i
Слайд 30Нижняя и верхняя цена игры
Принцип минимакса
Рассуждая аналогично для игрока В :
β =min max aij
Величина β называется верхней ценой игры, минимаксным выигрышем или минимаксом.
Стратегия игрока B, соответствующая минимаксу β называется минимаксной стратегией.
Величина β называется верхней ценой игры, минимаксным выигрышем или минимаксом.
Стратегия игрока B, соответствующая минимаксу β называется минимаксной стратегией.
i
j
Слайд 39Седловая точка игры
Игры в которых нижняя цена игры равна верхней называют
играми с седловой точкой.
Общее значение нижней и верхней цены игры называется чистой ценой игры.
Стратегии соответствующие седловой точке называются оптимальными, а их совокупность – решением игры.
В этом случае говорят, что игра имеет решение в чистых стратегиях.
Общее значение нижней и верхней цены игры называется чистой ценой игры.
Стратегии соответствующие седловой точке называются оптимальными, а их совокупность – решением игры.
В этом случае говорят, что игра имеет решение в чистых стратегиях.
Слайд 40Седловая точка игры
Игры в которых нижняя цена игры равна верхней называют
играми с седловой точкой.
Общее значение нижней и верхней цены игры называется чистой ценой игры.
Стратегии соответствующие седловой точке называются оптимальными, а их совокупность – решением игры.
В этом случае говорят, что игра имеет решение в чистых стратегиях.
Общее значение нижней и верхней цены игры называется чистой ценой игры.
Стратегии соответствующие седловой точке называются оптимальными, а их совокупность – решением игры.
В этом случае говорят, что игра имеет решение в чистых стратегиях.
Слайд 41Решение игры
В общем случае решением игры называется пара оптимальных смешанных стратегий
SA*, SB*, обладающих следующим свойством:
Если один игрок придерживается своей оптимальной стратегии, то другому не выгодно отклоняться от своей оптимальной стратегии.
Каждая конечная игра имеет по крайней мере одно решение, возможно, в области смешанных стратегий
Если один игрок придерживается своей оптимальной стратегии, то другому не выгодно отклоняться от своей оптимальной стратегии.
Каждая конечная игра имеет по крайней мере одно решение, возможно, в области смешанных стратегий
Слайд 42Основные понятия
Активные стратегии
Это те стратегии игроков, которые входят в его оптимальную
смешанную стратегию с отличными от нуля вероятностями
