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

 

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

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

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

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

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

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

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

(3.1)

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

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

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

(3.2)

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

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

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

(3.3)

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

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

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

(3.4)

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

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

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

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

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

Функціонал:

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

(3.5)

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

або

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

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

(3.6)

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

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

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

Рівняння об’єкта:

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

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

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

 

 

Таблиця 3.1

№ вар.	q	c	a	b	g	№ вар.	q	c	a	b	g
			-1						-1
			-2						-5
			-4						-3
			-6						-5
			-1						-6
			-3						-3
			-9						-2
			-1						-6
			-5						-1
			-8						-4
			-2						-7
			-3						-9
			-1						-5
			-4						-3
			-7						-1

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

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

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

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

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

(3.7)

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

З останнього рівняння:

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

Отримали рівняння, аналогічне попередньому прикладу, розв’язок якого має вигляд: , де коефіцієнт k₀ той самий, що у виразі (3.6).

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

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

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

Висновок

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

 

Контрольні запитання

1. У чому полягає перевага сучасних методів варіаційного числення порівняно з класичними методами?

2. Поясніть суть методу динамічного програмування.

3. Який принцип лежить в основі методу динамічного програмування?

4. Поясніть сутність принципу оптимальності.

5. Наведіть систему рівнянь Беллмана для системи першого порядку з однією керуючою дією.

 

Література: [3, с. 60-70], [6, с. 72-75].