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

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

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

У основі методу лежить принцип оптимальності. Відповідно до цього принципу оптимальне керування визначається кінцевою метою керування і станом системи у даний момент часу незалежно від того, яким чином система дійшла до цього стану, тобто від “передісторії” системи. Це означає, що для будь-якої оптимальної траєкторії кожна ділянка, яка зв’язує будь-яку проміжну точку цієї траєкторії з кінцевою, також є оптимальною траєкторією. Іншими словами, друга ділянка оптимальної траєкторії є оптимальною траєкторією.

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

причому на керуючий вплив накладені обмеження u (t) G_u, а також задані початкові умови: y(t₀) = y₀.

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

(10.35)

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

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

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

(10.36)

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

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

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

(10.37)

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

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

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

(10.38)

Наведена система рівнянь є найпоширенішою формою запису рівнянь Беллмана. При цьому функція має бути безперервною й диференціюваною за y_і, а dS/dy_і відіграє ту саму роль, що і множник l у задачі на умовний екстремум. Функція j аналогічна рівнянню зв’язку (10.21).

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

Маємо рівняння об’єкта:

Функціонал:

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

(10.39)

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

або

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

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

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

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

Приклад 10.4 Розв’язати задачу з обмеженням:

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

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

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

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

(10.40)

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

Тоді: ;

Отримали рівняння, аналогічне попередньому прикладу, розв’язок якого має вигляд:

Розв’язок рівняння дає константу f(u)=const. З урахуванням обмежень маємо |f(u)| = C.