Метод проектов
<<  Проективный метод в психодиагностике Методы экспериментальной оптимизации  >>
Методы оптимизации - II
Методы оптимизации - II
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Динамическое программирование в дискретной форме
Постановка задачи динамической оптимизации
Постановка задачи динамической оптимизации
Методы решения задач динамической оптимизации
Методы решения задач динамической оптимизации
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Уравнение Эйлера для простейшего
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Необходимое условие экстремума
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Классическое вариационное исчисление Решение вариационных задач при
Решение задачи оптимального уравнения классическим вариационным
Решение задачи оптимального уравнения классическим вариационным
Решение задачи оптимального уравнения классическим вариационным
Решение задачи оптимального уравнения классическим вариационным
Принцип максимума
Принцип максимума
Принцип максимума
Принцип максимума
Принцип максимума
Принцип максимума
Формулировка принципа максимума
Формулировка принципа максимума
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Общий алгоритм решения задачи оптимального уравнения с использованием
Пример решения задачи оптимального уравнения с использованием принципа
Пример решения задачи оптимального уравнения с использованием принципа
Пример решения задачи оптимального уравнения с использованием принципа
Пример решения задачи оптимального уравнения с использованием принципа
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Численное решение задачи оптимального уравнения с использованием
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Особенности решения задач на максимальное быстродействие
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Динамическое программирование в непрерывной форме
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического
Алгоритм решения задачи оптимального уравнения методом динамического

Презентация на тему: «Методы оптимизации - II». Автор: dinat. Файл: «Методы оптимизации - II.ppt». Размер zip-архива: 324 КБ.

Методы оптимизации - II

содержание презентации «Методы оптимизации - II.ppt»
СлайдТекст
1 Методы оптимизации - II

Методы оптимизации - II

Проф. В.П. Кривошеев

2 Динамическое программирование в дискретной форме

Динамическое программирование в дискретной форме

В дискретной форме динамическое программирование является декомпозиционным методом решения задач статической оптимизации. Особенность динамического программирования в дискретной форме позволяет свести задачу большой размерности к ряду подзадач меньшой размерности. В динамическом программировании критерий оптимальности Q = Q(u1,…,ur) должен быть функцией Марковского типа, т.е. он может быть представлен в виде функции от состояния S = S (u1,…,ur-1), в которое приходит последний объект в результате воздействия (r-1) управлений, и от оставшегося управления ur, т.е. Q = Q(S, ur). Предполагается, что процесс протекающий в исследуемом объекте, можно рассматривать как многостадийный (N-стадийный, см. рисунок ниже).

3 Динамическое программирование в дискретной форме

Динамическое программирование в дискретной форме

Многостадийный процесс Здесь: Si-1 - состояние перед i-ой стадией; ui - управление на i-ой стадии; qi(Si-1, ui) - составляющая критерия оптимальности, полученная на i-ой стадии. Состояния соседних стадий связаны выражением Si = Si (Si-1, ui), i=1,…,N.

4 Динамическое программирование в дискретной форме

Динамическое программирование в дискретной форме

Рассматривается критерий оптимальности в виде . В основе динамического программирования лежит принцип оптимальности: оптимальная стратегия обладает таким свойством, что для любых значений управлений u1,…,uk, при которых система пришла в состояние Sk = Sk (S0, u1,…,uk), оставшиеся управления uk+1,…,ur должны принимать такие значения, при которых критерий оптимальности принимает наилучшее значения относительно состояния Sk.

5 Динамическое программирование в дискретной форме

Динамическое программирование в дискретной форме

Алгоритм решения задачи оптимизации методом динамического программирования. Принцип оптимальности реализуется по шагам следующим образом: 1. Задаются условно значения вектора состояний Si = (S1i,…, Sin), i=1,…,N-1. Составляющие Sik, i=1,…,N-1; k=1,…,n, есть значения переменных состояния, выбранные в допустимом диапазоне изменения Sikmin? Sik ? Sikmax. 2. На первом шаге оптимизируется N-ая составляющая критерия оптимальности. При решении задачи Q(u)?max получаем FN-1,N(Sn-1)=max[qN(SN-1, uN)]. При этом получается u*N = ?N(SN-1). При этом получается u*N = ?N(sN-1).

6 Динамическое программирование в дискретной форме

Динамическое программирование в дискретной форме

Алгоритм решения задачи оптимизации методом динамического программирования (продолжение): На втором шаге оптимизируется совместное функционирование N-1-ой и N-ой стадий процесса, с учетом результата оптимизации, полученного на 1-ом шаге, в виде FN-2,N(sN-2)=max[qN-1(sN-2, uN-1)+FN-1,N(sN-1)]. При этом получается u*N-1 = ?N-1(sN-2). Заметим, что в состоянии sN-1 приходят в соответствии с sN-1= sN-1(sN-2, uN-1). 3. На последующих шагах оптимизируется совместное функционирование вновь вводимой стадии процесса со стадиями процесса, рассмотренными на предыдущем шаге по функциональному уравнению динамического программирования FN-k-1,N (sN-k-1) = = max[qN-k(sN- k-1, uN- k)+FN-k,N(sN-k)], k=2,3,4,…,N.

7 Динамическое программирование в дискретной форме

Динамическое программирование в дискретной форме

Алгоритм решения задачи оптимизации методом динамического программирования (продолжение): При этом получается u*N-k = ?N-k(sN-k-1) , а в состояние sN-k приходят в соответствии с sN-k= sN-k(sN-k-1, uN-k). 4. На последнем (N-ом) шаге имеем F0,N (s0) = = max[q1(s0, u1)+F1,N(s1)], u*1 = ?1(s0), s1 = s1(s0, u1). 5. Выделяются оптимальные значения управлений u*i, i=1,…,N, следующим образом:

8 Динамическое программирование в дискретной форме

Динамическое программирование в дискретной форме

Алгоритм решения задачи оптимизации методом динамического программирования (окончание): Для заданного состояния s0 после выполнения N-го шага оптимизации при u*1 = ?1(s0) переходят в оптимальное состояние s*1 = s1(s0, u*1). Далее используется выражение u*2 = ?2(s*1). Оптимальные значения остальных управлений u*i, i=3,4,…,N выделяются поочередным использованием выражений s*k = sk(s*k-1, u*k) и u*k+1 = ?k+1(s*k), k=2,3,…N.

9 Постановка задачи динамической оптимизации

Постановка задачи динамической оптимизации

где yi(t), i = 1,…,n, - функции состояния системы управления, uj(t) - функции управления; ? - область допустимых управлений. Требуется найти такие функции управления uj(t), j = 1,…,r, при которых система переходит из одного состояния y0 в другое состояние yk, и при этом выполняются указанные выше условия, а критерий оптимальности принимает минимальное (максимальное) значение.

10 Методы решения задач динамической оптимизации

Методы решения задач динамической оптимизации

Классическое вариационное исчисление. Принцип максимума. Динамическое программирование в непрерывной форме (уравнение Беллмана).

11 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

Рассматривается класс непрерывных функций y(х), имеющих непрерывные первые производные (класс функций C1). Здесь х может быть пространственной координатой (длина e, радиус R) или временем t. Ставится задача где y?(х) = d y(х)/dx, y(a) = A, y(b) = B.

12 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

Пусть в рассматриваемом классе функций, приведенных на рисунке ниже, экстремум функционалу доставляет функция y(х). Необходимые условия экстремума функционала можно получить при вариации функции ?(х) относительно функции y(х) в обе стороны. Заметим, что сравниваемые функции в точках a и b имеют одно и тоже значение. Вариация функции

13 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

Представим процедуру вариации функции y(х) однопараметрическим семейством функций y(?,х) = ??(х)+(1-?)y(х). Здесь полагаем, что экстремум достигается на функции y(х). Используя однопараметрическое семейство функций y(?,х), можно записать Введем обозначение ?y(х) = ?(х) - y(х), тогда d(?y(х))/ dx = ??y(х) = ? ? - y ?(х) = ?y?(х). Заметим, что из однопараметрического семейства функций, функции, доставляющей экстремуму функционалу, соответствует ? = 0.

14 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

Необходимое условие экстремума функционала при однопараметрическом представлении варьируемой функции можно записать как dJ/d? = 0, или Введем обозначения: Fy= ?F/?y, Fy ? = ?F/?y ?.

15 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

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

16 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

и возьмем интеграл по частям Учитывая тот факт, что сравниваемые функции имеют одинаковые значения в граничных точках, т.е. ?(y(a)) = ?y(b)) = 0, имеем

17 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

Оставшуюся часть подставим в функционал и получим Приведем подобные члены

18 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

В соответствии с леммой вариационного исчисления: Если имеет место где H(y(x),y?(x),x) – непрерывная функция, а h(x) - непрерывная функция, на концах интервала обращающаяся в нуль, то H(y(x),y?(x),x) ? 0. Имеем аналогию с H(y(x),y?(x),x) и ?y(x) c h(x).

19 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

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

20 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

Условия Лежандра: Если то Если то Пример. Найти экстремаль функционала: y(0) = 0, y(1) = 1. Уравнение Эйлера: Fy = 12x, Fy? = 12y?(x), d(Fy?)/dx = 2y??.

21 Классическое вариационное исчисление Уравнение Эйлера для простейшего

Классическое вариационное исчисление Уравнение Эйлера для простейшего

функционала

12x - 2y?(x) = 0, y?(x) = 6x, y?(x) = ?6xdx+C1 = 3x2+C1, y(x) = ?(3x2+C1) dx+C2 = x2+C1x+C2. Найдем постоянные интегрирования; используя граничные условия: y(0) = 0+ C1·0+ C2 = 0; C2 = 0; y(1) = 12+ C1·1+ 0·= 1; C1 = 0. Экстремаль: y = x2. Условия Лежандра: Следовательно, на функции y = x2 функционал имеет минимум.

22 Классическое вариационное исчисление Необходимое условие экстремума

Классическое вариационное исчисление Необходимое условие экстремума

функционала, зависящего от n-функций и от их первых производных

Система уравнений Эйлера: где

23 Классическое вариационное исчисление Необходимое условие экстремума

Классическое вариационное исчисление Необходимое условие экстремума

функционала, зависящего от n-функций и от их первых производных

Условия Лежандра: Если то Если то

24 Классическое вариационное исчисление Необходимое условие экстремума

Классическое вариационное исчисление Необходимое условие экстремума

функционала, зависящего от функции и от ее n производных

Уравнение Эйлера-Пуассона:

25 Классическое вариационное исчисление Необходимое условие экстремума

Классическое вариационное исчисление Необходимое условие экстремума

функционала, зависящего от функции и от ее n производных

Условия Лежандра: Если то Если то

26 Классическое вариационное исчисление Необходимое условие экстремума

Классическое вариационное исчисление Необходимое условие экстремума

функционала, зависящего от n функций и от ее m производных для каждой из n функций

27 Классическое вариационное исчисление Необходимое условие экстремума

Классическое вариационное исчисление Необходимое условие экстремума

функционала, зависящего от n функций и от ее m производных для каждой из n функций

В этом случае необходимое условие экстремума функционала представляет собой систему уравнений Эйлера-Пуассона:

28 Классическое вариационное исчисление Решение вариационных задач при

Классическое вариационное исчисление Решение вариационных задач при

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

Интегральная связь: Голономная связь: Неголономная связь:

29 Классическое вариационное исчисление Решение вариационных задач при

Классическое вариационное исчисление Решение вариационных задач при

наличии интегральных связей

Составляется новое подынтегральное выражение Необходимое условие экстремума функционала: Эти уравнения решаются совместно с уравнениями интегральных связей при использовании граничных условий. Здесь ?j, j=1,…,m, - числа.

30 Классическое вариационное исчисление Решение вариационных задач при

Классическое вариационное исчисление Решение вариационных задач при

наличии голономных и неголономных связей

Составляется новое подынтегральное выражение или Необходимое условие экстремума функционала: Эти уравнения решаются совместно с уравнениями голономных и неголономных связей при использовании граничных условий. Здесь ?j(x), j=1,…,m, - функции.

31 Классическое вариационное исчисление Решение вариационных задач при

Классическое вариационное исчисление Решение вариационных задач при

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

Пример Найти экстремали для функционала: Запишем уравнение связи в виде Сформируем новое подынтегральное уравнение

32 Классическое вариационное исчисление Решение вариационных задач при

Классическое вариационное исчисление Решение вариационных задач при

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

Пример (продолжение): Уравнения Эйлера: В развернутом виде имеем: Решим эти уравнения совместно с условием связи или

33 Классическое вариационное исчисление Решение вариационных задач при

Классическое вариационное исчисление Решение вариационных задач при

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

Пример (окончание): Возьмем вторую производную от условия связи и подставим в полученное выражение y?(x) и z? (x): Теперь: Найдем C1 - C4, используя граничные условия: Окончательно имеем

34 Решение задачи оптимального уравнения классическим вариационным

Решение задачи оптимального уравнения классическим вариационным

исчислением

Решается задача: где y(t) = (y1(t),…, yn(t)), u(t) = (u1(t),…, ur(t)). Эта задача является вариационной задачей с неголономными связями. Для функционала: необходимые условия экстремума:

35 Решение задачи оптимального уравнения классическим вариационным

Решение задачи оптимального уравнения классическим вариационным

исчислением

В развернутом виде: Обозначим –1 = ?0, ?i(t) = ?i(t). Теперь необходимые условия в развернутом виде:

36 Принцип максимума

Принцип максимума

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

37 Принцип максимума

Принцип максимума

Игольчатая функция

38 Принцип максимума

Принцип максимума

Содержание принципа максимума: Формируется функция Гамильтона где ?i, i= 0,…,n, подчиняются условиям: Математическое описание процесса, выраженное через функцию Обозначим критерий оптимальности Заметим, что y0(0) = 0, тогда

39 Формулировка принципа максимума

Формулировка принципа максимума

Пусть найдены оптимальные уравнения, минимизирующие функционал. В этом случае система сопряженных уравнений имеет не нулевое решение, и следующие условия при этом выполняются: 1. Функция принимает свое максимальное значение, т.е. 2. ?0 = const ? 0. 3. H* = const.

40 Общий алгоритм решения задачи оптимального уравнения с использованием

Общий алгоритм решения задачи оптимального уравнения с использованием

принципа максимума

1. Максимизируется функция H(y(t),u(t),?(t)) по управлениям u(t). При этом получаются 2. Эти u*j =u*j(y(t),?(t)) подставляются в систему сопряженных уравнений. Заметим, что для получения их решения нужно иметь 2n+2 постоянных интегрирования, определяемых 2n+2 граничными условиями. Из постановки задачи оптимального управления следуют 2n граничных условий и одно граничное условие для функции y0. Нужно еще одно граничное условие.

41 Общий алгоритм решения задачи оптимального уравнения с использованием

Общий алгоритм решения задачи оптимального уравнения с использованием

принципа максимума

Продолжение алгоритма: Однако, в силу линейности функции H относительно ?i, i = 0,…,n, при максимизации функции H(y(t),u(t),?(t)) по u(t) одна из функций ?i(t) может быть представлена с точностью до постоянной интегрирования. Учитывая второе условие принципа максимума, можно принять само значение функции ?0 неположительным числом (принимается ?0 = -1). 3. Теперь решение системы сопряженных уравнений может быть найдено: yi = yi(t), ?i = ?i(t), i = 0,…,n,

42 Общий алгоритм решения задачи оптимального уравнения с использованием

Общий алгоритм решения задачи оптимального уравнения с использованием

принципа максимума

Продолжение алгоритма: 4. Подставляются функции yi = yi(t), i = 0,…,n, и ?i = ?i(t), i = 0,…,n, в функции u*j =u*j(y(t),?(t)), j = 1,…,r, и получаются оптимальные функции управления u*j =u*j(t). Эти функции управления можно получать в виде функций от переменного состояния yi(t), i = 0,…,n, т.е. как u*j =uj(y1(t),…, yn(t)). В этом случае задача оптимального управления называется задачей синтеза оптимального управления.

43 Общий алгоритм решения задачи оптимального уравнения с использованием

Общий алгоритм решения задачи оптимального уравнения с использованием

принципа максимума

Продолжение алгоритма: Запишем в развернутом виде систему уравнений: и необходимое условие максимума функции H(y(t),u(t),?(t)) как

44 Общий алгоритм решения задачи оптимального уравнения с использованием

Общий алгоритм решения задачи оптимального уравнения с использованием

принципа максимума

Окончание алгоритма: Заметим, что выражение для производных d?i/dt соответствует уравнениям Эйлера, записанным для функций yk(t), k = 1,…,n, а условия соответствует уравнениям Эйлера, записанным для функций uj(t), j = 1,…,r, в классическом вариационном исчислении при решении задачи оптимального управления.

45 Пример решения задачи оптимального уравнения с использованием принципа

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

максимума

Пример. Найти управление u(t), при котором функционал принимает минимальное значение. y(0) = 1; y(tk) = 2. Уравнение динамики объекта dy(t)/dt = ay(t)+u(t). Путь на управление не наложено ограничений. Введем dy0/dt = (y2(t)+u2(t))/2, y0(0) = 0. Составим функцию Гамильтона H(y(t),u(t),?(t)) = ?0f0(y(t),u(t))+?(t)f(y(t),u(t)). В развернутом виде H(y(t),u(t),?(t))=?0(y2(t)+u2(t))/2+?(t)(-ay1(t)+u(t)).

46 Пример решения задачи оптимального уравнения с использованием принципа

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

максимума

Продолжение примера: Примем: ?0 = -1. Сопряженное уравнение d?/dt = -?H(y(t),u(t),?(t))/?y(t) = - y(t)+a?(t). Максимизируем функцию H(y(t),u(t),?(t)). Необходимое условие экстремума функции ?H(y(t),u(t),?(t))/?u(t) =0, u(t)-?(t) = 0, т. е. u(t) = ?(t). Подставим u(t) в систему сопряженных уравнений: dy(t)/dt = ay(t)+?(t), d?/dt = -y(t)+a?(t). Решение этих двух уравнений с использованием граничных условий дает y = y(t), ? = ?(t).

47 Численное решение задачи оптимального уравнения с использованием

Численное решение задачи оптимального уравнения с использованием

принципа максимума

В тех случаях, когда система сопряженных уравнений не может быть решена аналитически или аналитическое решение получить трудно, она решается численно. Принимается, что Тогда для системы уравнений: откуда

48 Численное решение задачи оптимального уравнения с использованием

Численное решение задачи оптимального уравнения с использованием

принципа максимума

Для системы уравнений: имеем откуда

49 Численное решение задачи оптимального уравнения с использованием

Численное решение задачи оптимального уравнения с использованием

принципа максимума

Алгоритм решения задачи оптимального уравнения численным методом с использованием принципа максимума: 1. Произвольно задаются ?i(0), i = 0,…,n, и полагается ?0 = -1. 2. Из граничных условий выбираются yi(0), i = 0,…,n. 3. Подставляются выбранные ?0, ?i(0), yi(0), i = 0,…,n, в функцию H, т.е. в H(y(0), ?(0), u(t)),

50 Численное решение задачи оптимального уравнения с использованием

Численное решение задачи оптимального уравнения с использованием

принципа максимума

Продолжение алгоритма: и она максимизируется При этом получается u(0) = (u1(0),…,ur(0). 4. По выше приведенным уравнениям вычисляются yi(?t), ?i(?t), i = 1,…,n, т.е. yi(?t), и ?i(?t) при k = 1. 5. Найденные yi(k?t) и ?i(k?t), i = 1,…,n, подставляются в функцию H, т.е. в H(y(t),?( t),u), и она максимизируется При этом получается u(k?t) = (u1(k?t),…,ur(k?t) при k =1. Пункты 4 и 5 выполняются до k = N, где N соответствует условию N?t = tk.

51 Численное решение задачи оптимального уравнения с использованием

Численное решение задачи оптимального уравнения с использованием

принципа максимума

Окончание алгоритма: 6. Проверяется выполнение условий: или где yip - рассчитанное значение yi, а ?i и ? - требуемая точность вычислений. Если условия пункта 6 не выполняются, то задаются новые значения ?(0) = (?1(0),…,?n(0)) и происходит переход к пункту 2 для последовательного выполнения всех пунктов алгоритма.

52 Особенности решения задач на максимальное быстродействие

Особенности решения задач на максимальное быстродействие

В задаче на максимальное быстродействие функционал имеет вид: т.е. подынтегральное выражение F(y(t),u(t),t) = 1. При этом функция Гамильтона или Функция называется укороченной функцией Гамильтона. Решение задачи выполняется по выше приведенному алгоритму для укороченной функции Гамильтона

53 Особенности решения задач на максимальное быстродействие

Особенности решения задач на максимальное быстродействие

Пример решения задачи на максимальное быстродействие. Решается задача перевода системы из состояния y1(0) = y10 и y2(0) = y20 в состояние y1(tk) = y1k и y2(tk) = y2k за минимальное время. Математическое описание процесса: Составим укороченную функцию Гамильтона: Максимизируем функцию Гамильтона. Учитывая линейность функции H от от u(t), с учетом ограничения -1? u(t) ? 1, имеем u*(t) = Sign(?2(t)).

54 Особенности решения задач на максимальное быстродействие

Особенности решения задач на максимальное быстродействие

Продолжение примера: Сопряженные уравнения Решение этих уравнений дает ?1 = Const = C1; ?2(t) = ??1(t)dt+ C2 = C1t+ C2. Учитывая линейность функции ?2(t), при оптимальном управлении возможно лишь одно переключение u(t) либо с -1 на 1, либо с 1 на -1. Решение системы уравнений математического описания рассмотрим при u = 1 и при u = -1. Пусть u = 1, тогда dy1(t)/dt = y2(t), dy2(t)/dt = 1. Поделим первое уравнение на второе dy1(t)/dy2(t) = y2(t),

55 Особенности решения задач на максимальное быстродействие

Особенности решения задач на максимальное быстродействие

Продолжение примера: dy1(t) = y2(t) dy2(t), y1(t) = ? y2(t) dy2+ C3 = y22(t)/2+C3. Пусть u =-1. Тогда y1(t) = y22(t)/2+C4. Пусть конечное состояние системы определено условиями y1(tk) = 0, y2(tk) = 0. Тогда для t = tk и u = 1 имеем y1(tk) = y22(t)/2+C3; C3 = 0; для u =-1 имеем y1(tk) = y22(t)/2+C4; C4 = 0. Следовательно, через конечную точку проходят траектории движения: при u = 1 y1(tk) = y22(t)/2, а при u =-1 имеем y1(tk) = -y22(t)/2.

56 Особенности решения задач на максимальное быстродействие

Особенности решения задач на максимальное быстродействие

Окончание примера: Чтобы из произвольной точки y(t) = (y1(t), y2(t)) попасть в конечную по оптимальной траектории, нужно из этой точки пойти по траектории, выводящей систему на линию переключения y1(t) = Sign(y2(t))·y2(t)/2. При достижении этой линии знак управляющего воздействия нужно сменить на противоположный. Оптимальное управление соответствует условию u*( t) = Sign((Signy2(t)) y22(t)/2 - y1(t)).

57 Динамическое программирование в непрерывной форме

Динамическое программирование в непрерывной форме

Уравнение Беллмана

Решается задача оптимального управления y(0) = y0, dyi(t)/dt = fi(y(t),u(t),t), i = 1,…,n, y(tk) = yk. В основе динамического программирования лежит принцип оптимальности в соответствии с которым нужно оптимальным образом перевести систему из состояния y(?)в конечное состояние y(tk) не зависимо от того, каким образом система пришла из исходного состояния y(0) в состояние y(?).

58 Динамическое программирование в непрерывной форме

Динамическое программирование в непрерывной форме

Уравнение Беллмана

Вариация функции

59 Динамическое программирование в непрерывной форме

Динамическое программирование в непрерывной форме

Уравнение Беллмана

Математически принцип оптимальности реализуется через выражение: Пусть ? - малая величина. Обозначим Тогда

60 Динамическое программирование в непрерывной форме

Динамическое программирование в непрерывной форме

Уравнение Беллмана

Разложим функцию ?(?, y(?)) в ряд Тейлора относительно состояния t = 0, y(0) = y0 по степеням y(t) и t. Примем, что ?t = ?. Заметим, что или С учетом малости ? можно записать

61 Динамическое программирование в непрерывной форме

Динамическое программирование в непрерывной форме

Уравнение Беллмана

Теперь min(J(y(0),u(t))), с учетом выше приведенных выражений, можно записать в виде

62 Динамическое программирование в непрерывной форме

Динамическое программирование в непрерывной форме

Уравнение Беллмана

Так как ?(0, y(0)) не зависит от u(t), а ? содержится во всех составляющих правой части записанного выше уравнения, то это уравнение приводится к виду Учтем тот факт, что разложение условно оптимальной величины функционала, записанной для условного состояния в какой-то момент времени t (в приведенном случае y(?)),

63 Динамическое программирование в непрерывной форме

Динамическое программирование в непрерывной форме

Уравнение Беллмана

можно разложить в ряд Тейлора относительно оптимального состояния системы в момент времени t = ? при y (t), т.е. Полученное уравнение называется уравнением Беллмана. Оно является уравнением в частных производных. Решение этого уравнения есть функции u*(t), доставляющие экстремум функционалу. Функции состояния системы y*(t) при этом описывают оптимальную траекторию движения из исходного y0 в конечное состояние yk.

64 Алгоритм решения задачи оптимального уравнения методом динамического

Алгоритм решения задачи оптимального уравнения методом динамического

программирования в непрерывной форме

Для решения уравнения Беллмана, кроме условий y(0) = y0 и y (tk) = yk, нужно иметь значение функции ?(t, y(t)) и значения ее производных ??(t, y(t))/?yi, i = 1,…,n, и ??(t,y(t))/?t в один из граничных моментов времени tн = 0 или tk. Заметим, что ?(tk, y(tk)) = 0 по определению. В силу этого имеет место тождество

65 Алгоритм решения задачи оптимального уравнения методом динамического

Алгоритм решения задачи оптимального уравнения методом динамического

программирования в непрерывной форме

Теперь из самого уравнения Беллмана следует Получены все условия для решения уравнения Беллмана. Решение уравнение Беллмана выполняется известными методами решения систем дифференциальных уравнений в частных производных.

66 Алгоритм решения задачи оптимального уравнения методом динамического

Алгоритм решения задачи оптимального уравнения методом динамического

программирования в непрерывной форме

Покажем что уравнение Беллмана при некоторых допущениях может быть приведено к уравнениям Эйлера. Запишем уравнение Беллмана в виде двух видов уравнений: Первый вид: Второй вид:

67 Алгоритм решения задачи оптимального уравнения методом динамического

Алгоритм решения задачи оптимального уравнения методом динамического

программирования в непрерывной форме

Управления, удовлетворяющие уравнениям второго вида, обозначим u*(t). В первом уравнении управления u*(t) удовлетворяют условиям правой части уравнения Беллмана, выраженным уравнениями второго вида. Теперь продифференцируем уравнение первого вида по переменным состояния и введем обозначения: ?k(t) = -??(t, y(t))/?yk, k = 1,…,n, ?0 = -1.

68 Алгоритм решения задачи оптимального уравнения методом динамического

Алгоритм решения задачи оптимального уравнения методом динамического

программирования в непрерывной форме

Принимая допущения, что с учетом принятых выше обозначений, получим

69 Алгоритм решения задачи оптимального уравнения методом динамического

Алгоритм решения задачи оптимального уравнения методом динамического

программирования в непрерывной форме

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

«Методы оптимизации - II»
http://900igr.net/prezentacija/pedagogika/metody-optimizatsii-ii-260636.html
cсылка на страницу

Метод проектов

8 презентаций о методе проектов
Урок

Педагогика

135 тем
Слайды