Эффективность шага в задаче динамического программирования. Как оценивается эффективность всего процесса в задаче динамического программирования? Поясните обозначения.

 Определение: Смешанной стратегией SА игрока А называ-

ется применение чистых стратегий A1, A2, ..., Am с вероятностями

Аналогично для игрока B:

,

Теорема Неймана. Каждая конечная игра имеет, по крайней

мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P^* и Q^*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.
Средний выигрыш игрока A определяется математическим ожиданием:

Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной.

Стратегии P^*, Q^* называются оптимальными смешанными стратегиями, если M_A(P, Q^*) ≤ M_A(P^*, Q^*) ≤ M_A(P^*, Q) (1)
В этом случае M_A(P^*, Q^*) называется ценой игры и обозначается через V (V_* ≤ V ≤ V^*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.

 

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

 

 

Полученные задачи являются взаимодвойственными.

 

Запишите уравнения Беллмана для общей задачи динамического программирования. Поясните обозначения. В каком порядке их решают?

Полученные задачи являются взаимодвойственными.

 

Непрерывная задача о распределении средств между предприятиями. Постановка задачи. Уравнения Беллмана.

 

состояние, в котором оказывается система после выбора решения на k-м. шаге, зависит только от данного решения и исходного состояния к началу k-го шага. Данное свойство является основным с точки зрения идеологии динамического программирования и называетсяотсутствием последействия.

 

Постановка задачи выпуклого программирования. Условие регулярности. Теорема Куна-Таккера.

1)Постановка задачи:

Найти экстремумы функции y=F(x) на множестве n M Î R это множество представляет собой

Линейные ограничение и выпуклое  

 

 

 

2) Условие регулярности

 

 

 

3) Теорема Куна Такера

⇐ Предыдущая1234

Поделиться: