21. Динамическое программирование. Принцип оптимальности и принцип вложения.

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

Q = F(U₁,U₂,…U_n) = F[f₁(U₁,…U_n-1),U_n],

т.е. значение ЦФ зависит от одного управления U_n и результата действия всех других управлений.

f₁(U₁,…U_n-1) = f₂[f₁(U₁,…U_n-2),U_n-1] – такие функции называют системами с памятью в один шаг или функциями марковского типа.

Q = F(S_n-1,U_n), где S_n-1 = f₂(U₁,…U_n-1)

S – состояние системы после принятия решения U_n-1.

Функции марковского типа зависят от управления не непосредственно, а через непосредственное состояние системы. Задача с критериями марковского типа рассматриваются как многоэтапная задача, но на каждом шаге оптимизируется только одно управление.

Т.о. ДП дает возможность отыскать глобальный экстремум функции многих переменных, но требует чтобы функция была марковского типа. Метод ДП уменьшает размерность задачи. Он сводит min-,max-цию сложной задачи с многими независимыми переменными к последовательности min-, max-ции только по одной переменной.

Основу ДП составляет принцип оптимальности Беллмана: «Оптимальная стратегия обладает свойством, что какое бы не было начальное состояние и решения, принятые в начальный момент, последующие решения должны составлять оптимальное поведение, относительно состояния, полученного в предыдущем моменте.»

В динамическом программировании используется также принцип вложения, под которым понимается рассмотрение исходной задачи с позиций более широкого класса задач (например, рассматривать не 10, а m состояний). Это позволяет изучить целый класс задач, включая и исходную.

22.-23 Решение задач оптимизации методом динамического программирования. Уравнения Беллмана.

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

Процедура применения метода ДП в общем виде:

Q = f₁(S₀;U₁) + f₂(S₁;U₂) +…+ f_n(S_n-1;U_n) – ЦФ

Пусть мы находимся в состоянии S_m-1. F_m,n(S_m-1) – max прибыль за оставшиеся шаги до S_n.

F_m,n(S_m-1) = max[f_m(S_m-1,U_m) + f_m+1(S_m,U_m+1) +…+ f_n(S_n-1,U_n)]

Разобьем это выражение на 2 части:

F_m,n(S_m-1) = max{f_m(S_m-1,U_m) + max[f_m+1(S_m,U_m+1) +…+ f_n(S_n-1,U_n)]}

F_m,n(S_m-1) = max[f_m(S_m-1,U_m) + F_m+1,n(S_m)] – функциональные уравнения Беллмана, которые описывают переход от одной стадии решения к другой. В общем случае левая часть ≠ правой и только max левой части = правой.

24. Вариационное исчисление. Классы допустимых функций.

Задачей вариационного исчисления (ВИ) является отыскание функций, доставляющих экстремум функционалам этих функций:

Функционал – функция, роль независимой переменной выполняет функция. Задача нахождения функций от y₁(t) до y_n(t), которые давали бы экстремум формулу Q = J[y₁(t),…y_n(t)]. Функция y_i(t) доставляющая формулу экстремальное значение называются экстремалями (минимальи, максимальи).

Классы допустимых функций. Говорят, что функция у(х) принадлежит классу с⁽ⁿ⁾ на сегменте ab, если она непрерывна и имеет непрерывную производные до порядка n на этом сегменте.

1. С⁰ – такой класс непрерывных функций, в котором все кривые близки друг к другу по ординате.

2. С¹ – класс непрерывных функций с непрерывными первыми производными. Это более узкий класс, чем С⁰: С¹ С⁰.

3. С² – класс непрерывных функций с непрерывными производными до 2-го порядка. С² С¹ С⁰.

Различают абсолютный и относительный экстремум. Если экстремум абсолютный, то необходимо проверить все возможные функции; если относительный - то только в каком-то одном классе.