Задача 3 Метод динамічного програмування Беллмана

Короткі теоретичні відомості

У техніці існує клас об’єктів і процесів, керування якими здійснюється на підставі обмеженої кількості рішень, що приймають послідовно у деякі фіксовані моменти часу. Для розв’язування задач оптимізації таких об’єктів американський вчений Р.Беллман запропонував метод, що отримав назву динамічного програмування. Цей термін означає прийняття рішень у часі.

Пояснимо метод динамічного програмування на простому прикладі керування об’єктом, рух якого описується рівнянням (2.1):

Задача 3 Метод динамічного програмування Беллмана - student2.ru

причому на керуючий вплив накладені обмеження u(t) Задача 3 Метод динамічного програмування Беллмана - student2.ru Gu, а також задані початкові умови: y(t0) = y0.

Необхідно мінімізувати функціонал:

Задача 3 Метод динамічного програмування Беллмана - student2.ru (3.1)

де Задача 3 Метод динамічного програмування Беллмана - student2.ru - деякий функціонал, що залежить від значення вихідної координати у кінці інтервалу часу Т, тобто значення критерію при останньому кроці на ділянці dt (без урахування попередніх).

Для розв’язування задачі Беллман застосував прийом, що полягає у просуванні від кінця процесу (t =T) до його початку (t=0).

У результаті було отримане рівняння динамічного програмування у безперервній формі, яке у найпростішому випадку для системи першого порядку з однією керуючою дією має вигляд:

Задача 3 Метод динамічного програмування Беллмана - student2.ru (3.2)

де y0, u0 – початкові значення вихідної координати і керування;

S – мінімальне значення функціоналу (3.1), яке залежить від початкових умов.

Для отримання мінімуму рівняння (3.2) необхідно продиференціювати за керуванням u. Тоді умову мінімуму (3.2) можна замінити системою:

Задача 3 Метод динамічного програмування Беллмана - student2.ru (3.3)

де y, u – поточні значення вихідної координати і керування.

З другого рівняння системи (3.3) визначають dS(y)/dy, а потім з першого рівняння знаходять шукану залежність u=f(y).

У випадку, коли система має n вихідних координат і m керувань, рівняння (3.3) матимуть вигляд:

Задача 3 Метод динамічного програмування Беллмана - student2.ru (3.4)

Наведена система рівнянь є найпоширенішою формою запису рівнянь Беллмана. При цьому функція Задача 3 Метод динамічного програмування Беллмана - student2.ru має бути безперервною й диференційованою за yі, а dS/dyі відіграє ту саму роль, що і множник l у задачі на умовний екстремум. Функція j аналогічна рівнянню зв’язку (2.1).

Завдання до задачі

Задача 3.1Розв’язати задачу 2.2 методом динамічного програмування. Вихідні дані у таблиці 2.2.

Розв’язати задачу (приклад 2.2) методом динамічного програмування.

Маємо рівняння об’єкта: Задача 3 Метод динамічного програмування Беллмана - student2.ru

Функціонал: Задача 3 Метод динамічного програмування Беллмана - student2.ru

Тоді система (3.3) має вигляд:

Задача 3 Метод динамічного програмування Беллмана - student2.ru (3.5)

Звідси знаходимо: dS/dy = - 2u/b;

Задача 3 Метод динамічного програмування Беллмана - student2.ru або Задача 3 Метод динамічного програмування Беллмана - student2.ru

Отримали квадратне рівняння відносно u, корені якого є шуканими керуваннями:

Задача 3 Метод динамічного програмування Беллмана - student2.ru

Другий корінь відкидаємо як такий, що не відповідає умовам стійкості, й остаточно запишемо:

Задача 3 Метод динамічного програмування Беллмана - student2.ru (3.6)

що співпадає з розв’язком (2.19), (2.20).

З рівнянь (3.5) можна виключити u і тоді визначити функцію S.

Задача 3.2Розв’язати методом динамічного програмування задачу з обмеженням.

Рівняння об’єкта: Задача 3 Метод динамічного програмування Беллмана - student2.ru

де x = f(u) – нелінійна функція з обмеженням (рис. 3.1).

Функціонал, що мінімізується, має вигляд:

Задача 3 Метод динамічного програмування Беллмана - student2.ru

Вихідні дані наведені у таблиці 3.1.

Таблиця 3.1

№ вар. q c a b g
-4

Розв’язати задачу з обмеженням: Задача 3 Метод динамічного програмування Беллмана - student2.ru

де x = f(u) – нелінійна функція з обмеженням (рис. 3.1).

Задача 3 Метод динамічного програмування Беллмана - student2.ru Функціонал, що мінімізується, має вигляд: Задача 3 Метод динамічного програмування Беллмана - student2.ru

У даному випадку:

Задача 3 Метод динамічного програмування Беллмана - student2.ru

Тоді рівняння Беллмана матимуть вигляд:

Задача 3 Метод динамічного програмування Беллмана - student2.ru (3.7)

З другого рівняння отримуємо:

Задача 3 Метод динамічного програмування Беллмана - student2.ru Задача 3 Метод динамічного програмування Беллмана - student2.ru

З останнього рівняння: Задача 3 Метод динамічного програмування Беллмана - student2.ru

Тоді перше рівняння системи (3.7) матиме вигляд:

Задача 3 Метод динамічного програмування Беллмана - student2.ru

Задача 3 Метод динамічного програмування Беллмана - student2.ru

Отримали рівняння, аналогічне попередньому прикладу, розв’язок якого має вигляд: Задача 3 Метод динамічного програмування Беллмана - student2.ru , де коефіцієнт k0 той самий, що у виразі (3.6).

Розв’язок рівняння Задача 3 Метод динамічного програмування Беллмана - student2.ru дає константу f(u)=const. З урахуванням обмежень маємо |f(u)| = g.

Отже, закон регулювання (з урахуванням від’ємного зворотного зв’язку) має вигляд:

Задача 3 Метод динамічного програмування Беллмана - student2.ru

При цьому d = g/k0.

Висновок

Задачі оптимального керування об’єктами, рівняння яких відомі, простіше розв’язувати методом динамічного програмування Беллмана. Якщо, крім того, накладено додаткові обмеження на координати і керування, такі задачі не можна розв’язати методами класичного варіаційного числення (методами Ейлера, Лагранжа), необхідно застосування сучасних методів, наприклад методу Беллмана.

Наши рекомендации