[МУЗЫКА] Здравствуйте. Сегодняшнее занятие посвящено дифференциальным играм. В первой части мы рассмотрим некоторые предварительные сведения, которые позволят нам находить решения в дифференциальных играх. Вторая часть посвящена неантагонистическим дифференциальным играм n лиц. И третья часть посвящена кооперативным дифференциальным играм. Начнем с примера оптимизации затрат на рекламу. Предположим, существует некоторая фирма, доход которой зависит от ее доли на рынке, и единственным способом увеличения этой доли является увеличение затрат на рекламу или управление затратами на рекламу. Вопрос: каким же образом фирме выбрать это управление? Каким же образом выбрать затраты на рекламу на некотором замкнутом временном интервале от t0 до T? Предположим, что фирма хочет спланировать свою деятельность на один год вперед. Что же такое задача оптимального управления? Рассмотрим некоторую динамическую систему. В нашем случае это некоторая фирма. Движение динамической системы описывается с помощью системы дифференциальных уравнений 2. Решением данной системы дифференциальных уравнений является некоторая функция x(t), а именно — траектория, вдоль которой будет двигаться динамическая система. В нашем случае нас интересует отрезок времени от t0 до T. Интерпретацией x(t) в случае задачи оптимального управления рекламой является доля фирмы на рынке. Правая часть данной системы дифференциальных уравнений зависит от некоторого внешнего параметра u, а именно управления, которое может использовать система. Управление мы будем искать в классе функций вида u (t, x). То есть мы будем предполагать, что управление задано для любого момента времени t и для любого состояния x. В одном из предыдущих разделов, посвященных многошаговым играм с полной информацией, мы определяли стратегию игроков для каждого шага многошаговой игры и для каждой позиции на графе. В случае дифференциальных игр функция u (t, x) является аналогом того самого управления. Вернемся к задаче оптимального управления. Таким образом, для любого выбранного управления система 2 имеет некоторое решение, то есть некоторую реализацию процесса. В свою очередь целевой функционал, или выигрыш, зависит от траектории, по которой двигается динамическая система, то есть x(t), и управления, которое было выбрано. И задачей оптимального управления как раз является и максимизация целевого функционала 1. То есть выбора такой функции u, которая доставляет ему максимальное значение. Управление, доставляющее максимальное значение функционалу 1, будем называть оптимальным управлением. А траекторию, соответствующую этому управлению, а именно решение системы 2, соответствующее этому управлению, будем называть оптимальной траекторией. Задача оптимального управления для модели управления рекламой имеет вид, представленный на слайде. Целевой функционал 3 описывает прибыль фирмы в зависимости от доли, которую она занимает на рынке на интервале от t0 до T, и затрат на рекламу, которую она производит. Уравнение движения 4 может быть интерпретировано как доля фирмы на рынке, а именно функция x(t), которая является решением заданной системы, при заданных управлениях может быть интерпретирована как доля фирмы на рынке. Вопрос: как же нам найти это оптимальное управление? Существует два классических метода для нахождения оптимального управления. Первый — это динамическое программирование, или уравнение Беллмана, или принцип максимума Понтрягина. Динамическое программирование чаще всего используется в теории дифференциальных игр, потому что она позволяет найти оптимальное управление, так как это является достаточным условием оптимальности. Принцип максимума Понтрягина может быть применен к более широкому классу задач, однако он является только необходимым условием. У принципа динамического программирования, или уравнения Беллмана, существует ряд минусов, о которых мы поговорим позже. Все-таки что же такое принцип динамического программирования? О чем же нам говорит принцип динамического программирования? Предположим, что мы знаем некоторое оптимальное управление в задаче, заданной на интервале от t0 до T, и конечно, соответствующую оптимальную траекторию. Тогда принцип динамического программирования говорит нам о том, что любое сужение оптимального управления u*(t) на некоторую подзадачу, заданную в интервале от t до T, начинающуюся в позиции x*(t), то есть в позиции на оптимальной траектории, также является оптимальной в подзадаче, заданной на интервале от t до T. В случае задач дискретного управления это означает следующее. Это означает, что оптимальные управления, заданные во всех подзадачах длиной 1, могут быть использованы для нахождения всех подзадач длиной 2. И так далее и так далее до начальной вершины. Мы использовали этот подход, не зная о принципе динамического программирования, в разделе, посвященном многошаговым играм с полной информацией. Там, когда мы находили абсолютное равновесие по Нэшу, мы находили решение оптимальной задачи во всех подыграх длиной 1, потом во всех подыграх длиной 2, во всех подыграх длиной 3 и так далее. Это и было применение принципа динамического программирования. Как же его применить для модели дифференциальной игры, когда мы не можем рассмотреть некоторые подыгры длиной 1? Необходимо определить так называемую функцию Беллмана, или значение оптимизационной задачи в подыгре или в подзадаче, которая начинается в момент времени t и в позиции x. Она представлена на слайде. Что такое подзадача, начинающаяся в момент времени t и в позиции x? Нам необходимо рассмотреть всю ту же оптимизационную задачу, но где интегральный функционал определен на интервале от t до T, не от t0 до T. И начальным условием системы дифференциальных уравнений является не x0, а некоторое произвольное x. Предположим, что мы знаем эту функцию Беллмана. Или обозначим оптимальное значение функционала через вот такую функцию Беллмана в V(t, x). Важно заметить, что функция Беллмана не зависит от управления, потому что мы уже предполагаем, что мы выбрали оптимальное управление в каждой подзадаче. Тогда верна следующая теорема. Оказывается, что если существует решение уравнения, представленного ниже, а именно уравнения Беллмана, то есть существует такая непрерывная дифференцируемая функция V(t, x), удовлетворяющая этому уравнению, то тогда управления, получаемые в рамках оптимизации правой части, являются оптимальными управлениями в исходной задаче оптимизации 1, 2. И данное уравнение является достаточным условием оптимальности. Уравнение Беллмана является уравнением в частных производных. В левой части мы видим частную производную функцию Беллмана по t, а справа видим частную производную функцию Беллмана по x. Решением этого уравнения является некоторая функция Беллмана и в том числе оптимальное управление, которое соответствует этой функции Беллмана. Вопрос, конечно, заключается в том, чтобы найти эту функцию Беллмана. Понятно, что в общем виде решить это уравнение невозможно, однако можно использовать подход, который мы сейчас продемонстрируем для задачи оптимального управления рекламой. Можно предположить, что функция Беллмана некоторым образом зависит от компоненты x. Уравнение Беллмана для задачи управления рекламы представлено на слайде сверху, а функцию Беллмана мы будем искать в виде exp[−rt] на некоторую функцию A, зависящую от t * x, то есть на состояние, + некоторую функцию B, зависящую от t. Важно заметить, что начальное условие для функции Беллмана определено на правом конце интервала, то есть в точке t. И для любого некоторого состояния x в этот момент времени. Итак, вернемся к решению оптимизационной задачи. Предположим, что функция Беллмана имеет такой вид. Или: будем искать функцию Беллмана в таком виде. Тогда мы можем подставить эту функцию Беллмана в исходное дифференциальное уравнение частных производных, найти частные производные, потому что мы можем теперь взять частную производную по t и частную производную по x. Мы можем найти управление, которое максимизирует правую часть уравнения Беллмана и получить в управление функцию φ(t, x), которая представлена на слайде. Дальше, конечно, стоит вопрос, что же такое функции A(t) и B(t) и каким образом мы можем их найти. Итак, оказывается в некоторых случаях возможно привести уравнение в частных производных к системе дифференциальных уравнений. Для этого необходимо упростить уравнение и получить слева следующее выражение. Производное от функции A умножить на x + производное от функции B, а справа получить некоторый множитель, некоторое выражение, умноженное на x, плюс свободные члены. И тогда можно разделить это уравнение на систему уравнений, где слева будет производное от функции A, справа будут элементы из выражения, которые умножались на x. И второе уравнение будет состоять из производной функции B и свободных членов, которые находились ранее справа. Таким образом, если дифференциальное уравнение относительно функции A(t) мы домножим слева и справа на x и сложим с дифференциальным уравнением для функции B(t), то мы получим как раз исходное уравнение Беллмана. Начальное условие для системы дифференциальных уравнений для функции A и B(t) у нас находится аналогичным образом. После того как мы построили эту систему дифференциальных уравнений, мы можем определить функции A(t) и B(t) и подставить в оптимальное управление и в функцию Беллмана. Мы таким образом получаем два результата. Первый результат — это оптимальное управление. И второй результат — это оптимальное значение функционала для любой подзадачи в начальной позиции t и x. Если мы хотим знать значение функционала в задаче, начинающейся в момент t0 x0, все, что мы должны сделать, это вместо t подставить t0, и вместо x подставить x0. Однако в явном виде мы не всегда можем решить систему дифференциальных уравнений для функции A и B. Но в этом случае мы можем использовать численные методы. Также иногда не существует решения данной системы. Иногда мы не можем подобрать такой вид функций Беллмана, чтобы найти решение уравнения Беллмана. Однако в нашем конкретном случае мы смогли это сделать, и после этого мы находим численное решение системы дифференциальных уравнений для A и B(t). После этого мы подставляем это решение в соответствующее управление, после этого оптимальное управление мы подставляем в уравнение движений или в систему дифференциальных уравнений 2 и получаем оптимальную траекторию. Потом и оптимальную траекторию и управление можем подставить в целевой функционал. На данном слайде представлен график оптимального управления вдоль оптимальной траектории, то есть уже функции от t, и график оптимальной траектории. На данном слайде представлен список источников, который поможет вам детальнее разобраться в принципе динамического программирования, в принципе максимума Понтрягина и рассмотреть другие примеры.
