Презентация на тему Нелинейное программирование

Презентация на тему Презентация на тему Нелинейное программирование, предмет презентации: Разное. Этот материал содержит 44 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Нелинейное программирование

Практическое занятие №6


Слайд 2
Текст слайда:

Тема занятия

Антагонистические игры


Слайд 3
Текст слайда:

Домашнее задание (60 баллов)

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


Слайд 4
Текст слайда:

Основные понятия

Конфликтные ситуации
Это ситуации в которых сталкиваются интересы двух или более сторон, преследующих различные цели
Любой шаг каждой из сторон зависит от того какой образ действий выберет противник


Слайд 5
Текст слайда:

Основные понятия

Теория игр
Это математическая теория конфликтных ситуаций
Задача теории – выработка рекомендаций по рациональному образу действий участников конфликта


Слайд 6
Текст слайда:

Основные понятия

Игра
Это упрощенная, схематизированная модель ситуации
От реальной конфликтной ситуации игра отличается тем, что ведется по определенным правилам


Слайд 7
Текст слайда:

Основные понятия

Игры бывают
Парными – когда в игре сталкиваются интересы двух противников
Множественными - более двух противников



Мы будем рассматривать только первые


Слайд 8
Текст слайда:

Основные понятия

Игра с нулевой суммой
Это такая игра, когда один игрок выигрывает ровно столько, сколько проигрывает второй




Мы будем рассматривать только такие игры


Слайд 9
Текст слайда:

Основные понятия

Ход
Ходом в теории игр называется выбор одного из предусмотренных правилами игры действий и его осуществление.
Развитие игры во времени состоит из последовательности ходов.


Слайд 10
Текст слайда:

Основные понятия

Ходы бывают
Личные
Это сознательный выбор игроком одного из вариантов действий и его осуществление
Случайные
Выбор осуществляется не решением игрока, а каким-либо механизмом случайного выбора

Теория игр занимается анализом игр, содержащих только личные ходы


Слайд 11
Текст слайда:

Основные понятия

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


Слайд 12
Текст слайда:

Основные понятия

В зависимости от числа возможных стратегий игры делятся на
Конечные
У каждого игрока имеется конечное число стратегий
Бесконечные
Хотя бы у одного игрока число стратегий бесконечно


Слайд 13
Текст слайда:

Основные понятия

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


Слайд 14
Текст слайда:

Платежная матрица

Рассмотрим конечную, парную игру двух игроков А и В, в которой игрок А имеет m стратегий, а игрок В n

Ai возможные стратегии игрока А
Bj возможные стратегии игрогка В
ai,j выигрыш игрока А (проигрыш игрока В)

Bj

Ai


Слайд 15
Текст слайда:

Пример

Игра «поиск»
Имеется два игрока А и В. Первый прячется, второй его ищет. Прятаться можно только в двух местах, любое из которых игрок А выбирает по своему усмотрению.
Если при очередном ходе игрок А спрятался в одном из мест, и
игрок В его нашел, то В получает 1 рубль
игрок В его не нашел, то А получает 1 рубль


Слайд 16
Текст слайда:

Игра «поиск»

Решение
Игра состоит из двух ходов, оба – личные
У игрока А две стратегии
Прятаться в месте №1
Прятаться в месте №2
У игрока В тоже две стратегии
Искать в месте №1
Искать в месте №2



Слайд 17
Текст слайда:

Игра «поиск»

Решение
Имеем игру 2х2.
Платежная матрица:

Bj

Ai


Слайд 18
Текст слайда:

Игра «поиск»

Решение
Имеем игру 2х2.
Платежная матрица:

Bj

Ai


Слайд 19
Текст слайда:

Основные понятия

Смешанная стратегия
Это такая стратегия в которой, отдельные «чистые» стратегии чередуются случайным образом с какими-то вероятностями.
При использовании смешанных стратегий перед каждым ходом путем механизма случайного выбора обеспечивается появление каждой стратегии с некоторой вероятностью.


Слайд 20
Текст слайда:

Смешанные стратегии

Обозначение смешанных стратегий
Пусть имеется игра в которой игрок А имеет m стратегий (A1, A2,…, Am), а игрок В - n (B1, B2,…, Bn)
SA=(p1,p2,…,pm)
Обозначение смешанной стратегии игрока А, в которой стратегии A1, A2,…, Am применяются с вероятностями p1,p2,…,pm
Причем p1+p2+…+pm=1


Слайд 21
Текст слайда:

Смешанные стратегии

Обозначение смешанных стратегий
SB=(q1,q2,…,qn)

Обозначение смешанной стратегии игрока, где
q1+q2+…+qn=1


Слайд 22
Текст слайда:

Игра «три пальца»

Игра «три пальца»
Игроки А и В одновременно и независимо друг от друга показывают один два или три пальца.
Выигрыш (в рублях) равен общему числу показанных пальцев:
Если оно четное – выиграл игрок А
Если оно нечетное – выиграл игрок В


Слайд 23
Текст слайда:

Игра «три пальца»

Решение
Имеем игру 3х3.
Платежная матрица:

Bj

Ai


Слайд 24
Текст слайда:

Игра «три пальца»

Решение
Имеем игру 3х3.
Платежная матрица:

Bj

Ai


Слайд 25
Текст слайда:

Пример

Игра «вооружение и самолет»
В нашем распоряжении имеется три вида оружия, а у противника три вида самолетов
Первым оружием самолеты поражаются с вероятностями соответственно 0,5; 0,6 и 0,8
Вторым - соответственно 0,9; 0,7 и 0,8
Третьим - соответственно 0,7; 0,5 и 0,6
Наша задача – поразить самолет, задача противника – сохранить его непораженным


Слайд 26
Текст слайда:

Игра «вооружение и самолет»

Решение
Имеем игру 3х3.
Платежная матрица:

Bj

Ai


Слайд 27
Текст слайда:

Нижняя и верхняя цена игры Принцип минимакса

Рассмотрим игру m х n
Как определить наилучшую из стратегий игрока А?
Проанализируем все возможные стратегии Ai
Выбирая Ai мы должны рассчитывать, что противник ответит на нее той, из своих стратегий Вi, для которой наш выигрыш минимален

Bj

Ai


Слайд 28
Текст слайда:

Нижняя и верхняя цена игры Принцип минимакса

Найдем минимальной из чисел aij в i–й строке и обозначим его ai :
αi=min aij

Действуя наиболее осторожно мы должны предпочесть ту стратегию, для которой α i максимально:
α =max α i

j

i


Слайд 29
Текст слайда:

Нижняя и верхняя цена игры Принцип минимакса

Объеденив обе формулы, получим :
α =max min aij

Величина α называется нижней ценой игры, максиминным выигрышем или максимином.
Стратегия игрока А, соответствующая максимину α называется максиминной стратегией.

j

i


Слайд 30
Текст слайда:

Нижняя и верхняя цена игры Принцип минимакса

Рассуждая аналогично для игрока В :
β =min max aij

Величина β называется верхней ценой игры, минимаксным выигрышем или минимаксом.
Стратегия игрока B, соответствующая минимаксу β называется минимаксной стратегией.

i

j


Слайд 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
Текст слайда:

Решение игры

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


Слайд 42
Текст слайда:

Основные понятия

Активные стратегии
Это те стратегии игроков, которые входят в его оптимальную смешанную стратегию с отличными от нуля вероятностями


Слайд 43
Текст слайда:

Тема следующего занятия

Статистические игры с единичным экспериментом


Слайд 44
Текст слайда:

Спасибо за внимание


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика