.RU
Карта сайта

2.3 Теория применения динамического программирования - Список сокращений и обозначений дп


2.3 Теория применения динамического программирования


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

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


В динамическом программировании рассматриваются многостадийные процессы принятия решения.
Многостадийные процессы – это такие процессы, в которых решения принимаются на каждой из последовательных стадий.
Динамическое программирование является средством оптимизации математически описанных процессов.
При постановке и решении задачи динамического программирования формулируется некоторый критерий, подлежащий удовлетворению, рассматриваемый процесс разбивается на стадии во времени или в пространстве и на каждой стадии принимаются решения, при которых достигается поставленная цель.
При рассмотрении вопросов динамического программирования принята следующая терминология:
а) стадия – единичный элемент, на которые делится весь процесс во времени или в пространстве; ступень – часть стадии. В любом случае стадия и ступень – это математические конструкции, применяемые для представления в дискретном виде непрерывной переменной;
б) состояние системы характеризуется совокупностью переменных, последние описывают состояние системы на любой стадии процесса;
в) переход от стадии к стадии и от состояния к состоянию описывается функциональными уравнениями;
г) стратегия определяется системой решений функционального уравнения; оптимальная стратегия выражается системой функций, максимизирующих правую часть уравнения.
Стадии процесса могут быть однородными и неоднородными. Процесс с однородными стадиями
представляет собой последовательное изменение состояния объекта во времени, он состоит из последовательности однотипных стадий.
Процесс с неоднородными стадиями состоит из разнородных стадий. Состояние отдельной стадии характеризуется совокупностью величин, которые называются выходом или переменными состояния стадии. Если выход стадии является входом для следующей стадии, то для последней совокупность выходных переменных предыдущей стадии определяет состояние входа.
Кроме входных и выходных переменных на каждой стадии определяется группа управляющих переменных (управление), а также предполагается известным математическое описание каждой стадии. Рассматриваемый многостадийный процесс условно изображается схемой, изображенной на рис. 2.3.1.1.
Рис. 2.3.1.1 Многостадийный процесс
Краеугольным камнем метода динамического программирования является принцип оптимальности: оптимальная стратегия обладает таким свойством, что, каково бы ни было начальное состояние и начальные решения, последующие решения должны приниматься, исходя из оптимальной стратегии с учетом состояния, вытекающего из первого решения.
Использование принципа оптимальности является гарантией того, что решение, принимаемое на каждой стадии, является наилучшим с точки зрения всего процесса в целом.
В динамическом программировании используется также принцип вложения, под которым понимается рассмотрение исходной задачи с позиций более широкого класса задач (например, рассматривать не 10, а m стадий). Это позволяет изучить целый класс задач, включая и исходную. Исходя из принципа вложения, представляется возможным изучить как структуру, так и "чувствительность" решения.

^ 2.3.2 Математическое описание. Функциональное управление Беллмана.


Как уже говорилось, математическое описание процесса известно.
Пусть состояние системы на каждой стадии описывается уравнением
2.3.2.1
где , – переменные состояния v – 1 и v стадий соответственно, – управление на v-й стадии.
Уравнение (2.3.2.1) связывает выходные переменные ν стадии с выходными переменными предыдущей стадии -1 и управлением , используемым на этой ν стадии.
На переменные состояния и управляющие воздействия могут быть наложены ограничения, выражающиеся в виде равенств или неравенств
, . 2.3.2.2
Кроме того, используется запись
2.3.2.3
смысл которой заключается в том, что переменные принадлежат к допустимым областям, ограниченным соотношениями (2.3.2.2).
Эффективность каждой стадии процесса оценивается скалярной величиной , которая называется функцией полезности – критерием оптимальности
2.3.2.4,а
с учетом (2.3.2.1) функциональная зависимость (2.3.2.4,а) может быть представлена как
2.3.2.4,б
Результирующая оценка эффективности многостадийного процесса в целом определяется как аддитивная функция результатов, получаемых на каждой стадии
2.3.2.5
Естественно, что критерий оптимальности Q зависит от совокупности управляющих воздействий на всех стадиях процесса .
Таким образом, задачу оптимизации многостадийного процесса можно сформулировать как задачу отыскания оптимальной стратегии , для которой критерий оптимальности Q принимает максимальное или минимальное значение.
Процедура применения принципа оптимальности для оптимизации m-стадийного процесса должна начинаться с последней стадии, для которой не существует последующих стадий, могущих повлиять на выбор управления на этой стадии. После этого приступают к определению оптимального управления для предыдущей m – 1 стадии, для которой оптимальная стратегия на последующих стадиях, т.е. на последней m-й известна и т.д. В результате может быть найдена оптимальная стратегия управления для всего многостадийного процесса, являющаяся функцией начального состояния процесса .
При применении любой стратегии управления величина критерия оптимальности Q зависит только от состояния входа первой стадии .
Пусть оптимальное значение целевой функции (для определенности минимальное) на участке от ν до m будет , и оно зависит от состояния на ν – 1 стадии
. 2.3.2.6
Соответственно
, 2.3.2.7
здесь оптимизация проводится по всем возможным управлениям, принадлежащим области допустимых значений U, на всех стадиях процесса. Соотношение (2.3.2.7) по существу является математической формулировкой задачи оптимизации m-стадийного процесса, но не содержит указаний как нужно минимизировать критерий Q, чтобы получить оптимальную стратегию .
Так как Q является аддитивной функцией критериев оптимальности отдельных стадий, то его можно представить в виде
, 2.3.2.8
тогда (2.3.2.7) перепишется в виде
, 2.3.2.9
Выражение (2.3.2.9) может быть также переписано в виде
, 2.3.2.10
где минимизация первого слагаемого проводится только по управлению , а второе минимизируется выбором управлений на всех стадиях, причем каждое слагаемое в (2.3.2.10) нельзя минимизировать в отдельности, так как они оба зависят от .
Минимизацию второго слагаемого в (2.3.2.10) можно рассматривать как задачу оптимизации (m – 1) стадийного процесса с критерием оптимальности и оптимальной стратегией . Таким образом, можно записать, что
, 2.3.2.11
Выражение (2.3.2.9) с учетом (2.3.2.11) может быть представлено в виде
, 2.3.2.12
Если математическое описание первой стадии , то
. 2.3.2.13
Последнее уравнение является математической формулировкой принципа оптимальности и называется рекуррентным соотношением Беллмана.
Для начала расчетов необходимо задать начальную функцию , которая может быть принята равной нулю, что естественным образом соответствует отсутствию процесса за пределами последней стадии.
Уравнение (2.3.2.13) можно трактовать как оптимальные потери, причем – потери на первом участке, а – оптимальные потери на всех последующих участках. Минимизируя сумму этих потерь, необходимо найти правильное соотношение между ними.

^ 2.4 Процедура решения задачи методом динамического программирования


Согласно общему подходу к решению задач методом динамического программирования определение оптимальных управлений начинается с последней стадии процесса, для которой рекуррентное соотношение Беллмана с учетом, что , записывается в виде
2.4.1
Для этой стадии можно построить зависимость целевой функции от управления для различных значений переменной состояния (рис. 2.4.1).
Эта зависимость позволяет найти зависимость оптимального управления на последней стадии от входной переменной этой стадии (рис. 2.4.2).
Рис. 2.4.1 Зависимость от


Рис. 2.4.2 Зависимость оптимального управления
от входной переменной
Одновременно определяется минимальное значение целевой функции данной стадии от ее входа, т.е. (рис. 2.4.3).
Таким образом можно получить зависимости оптимального управления на m-й стадии от входной переменной этой стадии , а также критерия оптимальности на этой m-й стадии от ее входа . Кроме того, можно определить зависимость выходной переменной при оптимальном управлении от входной переменной (рис. 2.4.4).
Рис. 2.4.3 Зависимость от
Рис. 2.4.4 Зависимость от
Для определения оптимального управления на (m – 1)-й стадии из всех полученных результатов необходима зависимость , с учетом которой рекуррентное соотношение для (m – 1)-й стадии записывается как
, 2.4.2
Далее необходимо построить зависимость от управления для различных значений переменных состояний входа (m – 1) стадии (рис. 2.4.5).
Рис. 2.4.5 Зависимость от

Рис. 2.4.6 Зависимость оптимального управления
от входа на (m – 1) стадии
Также как и для m-й стадии в результате минимального значения выражения (2.4.2) находятся зависимости , , а также , которые представлены соответственно на рис. 2.4.6, 2.4.7, 2.4.8.
Рис. 2.4.7 Зависимость от
Рис. 2.4.8 Зависимость от
Далее появляется возможность записать рекуррентные соотношения на (m – 2) стадии, и т.д. Продолжая процесс вычислений можно дойти до первой стадии, для которой также будут получены соотношения ,, . Возможный вид кривых для них представлен на рис. 2.4.9 –2.4.12.
Рис. 2.4.9 Зависимость от
Рис. 2.4.10 Зависимость оптимального управления от входа на 1-й стадии
На этом первый этап решения задачи оптимизации многостадийного процесса заканчивается. Полученные соотношения определяют оптимальную стратегию управления m-стадийного процесса для любого возможного состояния входа первой стадии.

Рис. 2.4.11 Зависимость от
На втором этапе решения оптимальной задачи находятся оптимальные управления всех стадий , , для чего необходимо принять соответствующее значение состояния входа. В том случае, если оно в постановке задачи не задано, его можно определить из условия минимума величины как функции значения (рис. 2.4.11). В рассмотренном случае зависимость от имеет минимум, что позволяет найти оптимальное значение состояния входа . Минимальное значение может достигаться и на концах.
После определения переменной состояния входа из условия минимума функции , преступают к определению оптимальных управлений для всех стадий процесса, соответствующих выбранной величине (рис. 2.4.11). Вторым этапом решения задачи оптимального управления методом динамического программирования является определение оптимальных управлений для всех стадий. Здесь порядок расчета следующий.
Определяется оптимальное управление на первой стадии (рис. 2.4.10) и значение выходной переменной этой стадии (рис. 2.4.12), отвечающее оптимальному управлению. После этого переходят ко второй стадии, и вся процедура повторяется и т.д. В результате решения задачи доходят до последней m-й стадии и имеют значения для всей рассматриваемой задачи по стадиям.
Рис. 2.4.12 Зависимость от 2014-07-19 18:44
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • © sanaalar.ru
    Образовательные документы для студентов.