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

Мы уже отметили, что аналитическое решение уравнений Беллмана удается найти лишь в сравнительно несложных случаях. Основное же назначение метода динамического программирования состоит в том, чтобы он позволил строить вычислительные алгоритмы для решения задач на ЦВМ. Для этого задача формируется с помощью разностных уравнений.

Любую систему обыкновенных дифференциальных уравнений в принципе можно заменить системой уравнений в конечных разностях.

Пусть объект управления описывается дифференциальным уравнением в векторной форме:

(2.17)

Зададим функционал:

, (2.18)

где Т – фиксированная величина.

Разобъем Т на N интервалов с шагом дискретности t, т.е. Т = Nt.

Осуществляем дискретизацию непрерывного процесса x(t)=x(nT).

Дифференциальное уравнение (2.17) заменим уравнением в конечных разностях:

или:

, (2.19)

где .

Функционал (2.18) также приближенно заменим суммой:

. (2.20)

Уравнения (2.19) и (2.20) записаны в векторной форме. Для простоты изложения метода динамического программирования с целью построения вычислительного алгоритма рассмотрим x и U как скалярные функции и примем значение t равным единице. Тогда математическая постановка задачи управления запишется в следующем виде:

(2.21)

 разностные уравнения, которые описывают поведение объекта управления и критерий оптимальности

. (2.22)

Начальное состояние системы задано условием x(0) = x⁰.

Требуется найти управление, удовлетворяющее ограничению и доставляющее минимум сумме (2.22).

Решение задачи начинается с конца траектории управления, т.е. с последующего интервала , считая состояние x(N-1) известным. Значение I_N-1 на этом интервале равно:

Учитывая соотношение (2.21) выразим x(N) через x(N-1) и U(N-1).

Тогда

. (2.23)

получаем функцию (2.23) одной переменной U(N-1).

С помощью известных правил можно найти оптимальное значение U^*(N-1), которое доставляет минимум I_N-1. Обозначим минимальное значение I_N-1 через S_N-1.

Запоминаем значения S_N-1 и U^*(N-1).

Далее рассмотрим интервал [N-2,N], состоящий из двух интервалов: последнего и предпоследнего. Для него

.

В соответствии с принципом оптимальности состояния x(N-2) полностью определяет оптимальное управление на данном интервале.

Тогда

.

полученное функциональное уравнение содержит также одну только переменную U(N-2). Из него находим оптимальное значение

U^*(N-2). Запоминаем значения U^*(N-2) и S_N-2.

Аналогично, продолжая «попятное» движение, можно получить общую рекуррентную формулу:

(2.24)

В результате минимизации по переменной U (N-k) находим оптимальное значение U^*(N-k). Причем значения x(N-k), x(N-k+1),…,

x(N-2) считаются условно известными. Эти значения определяются в процессе вычислений.

Поступаем следующим образом. Так как в последнем соотношении x(0) задано, находим U^*(0) и по формуле:

вычисляем x^*(1) и затем по формуле (12) находим U^*(1) и так далее до x^*(k), U^*(k).

В случае, когда `x(k) и`U(k) – векторы, то вид рекуррентной формулы (2.24) сохраняется, только в ней x, U, f – векторы и минимум S_N-K ищется по m-скалярным аргументам U₁(N-k),…,U_m(N-k).

Пример 2.3. Минимизация времени переправы лодки через реку.

Математическое описание процесса переправы лодки через реку.

Введем обозначения:

V_л – скорость лодки в стоячей воде; V_т – скорость течения воды; x – ось направления к противоположному берегу; y – ось направления по течению; φ – угол между вектором и осью x;  скорость лодки по оси x.

Изобразим на рисунке 2.3 прямоугольную систему координат x0y с началом в точках старта лодки.

Рис. 2.3. Схема движения лодки.

Для простоты описания задачи примем:

V_л=1; V_т=0,1;

 начальное состояние лодки;

 конечное состояние лодки.

Задачи минимизации процесса переправы лодки имеет следующее математическое описание (в соответствии с рис. 2.3).

Тогда

и .

Управление и преобразуем исходную задачу.

Проведем подстановки и упрощения, с учетом, что :

, .

Тогда, исключив время

,

получаем

.

Критерием оптимальности является

I = T → min (2.25)

и функционал имеет вид:

.

Из начальных состояний лодки

0 ≤ x ≤ 4, y(0) = y(4) = 0,

и значений скоростей:

, при V_л=1 и V_т=0,1

(2.26)

Тогда получаем:

и

.

Введем дискретизацию по x с шагом ∆x = 1:

; (2.27)

;

где ; ; .

Подготовим задачу для использования метода динамического программирования. Для этого построим элементарную операцию, которая бы позволяла найти управление U_i для перевода лодки из точки y_i в точку y_i+1.

Преобразуем исходное разностное уравнение (2.27):

и решим его относительно U_i:

.

На основе простых рассуждений можно убедиться, что исходному разностному уравнению удовлетворяет

.

Последнее выражение и является основным для нахождения оптимального варианта движения лодки.

Примем шаг дискретности по переменной y равным ∆y = 1. Тогда множество допустимых значений переменной y_i при каждом фиксированном i составят числа -1, 0, 1.

Метод динамического программирования заключается в том, что на каждом шаге, начиная с последнего, вычисляют условное оптимальное управление U_i^* (y_i) и условное минимальное значение S_i(y_i).

Для простоты имеется по оси x рассмотрим четыре шага, так как конечное состояние лодки принято (рис.2.4).

Рис. 2.4. Граф движения лодки.

Начнем с предпоследнего шага, т.е. с третьего. Алгоритм расчета будет следующим. Для каждого допустимого значения y₃ вычисляют:

 разность ∆y₃ = y₄ - y₃ = -y₃;

 управление ;

 функционал .

На этом шаге отсутствует процесс минимизации, т.к. управление U₃(y₃) однозначно определяется из граничного условия y₄ = 0, т.е. для каждой точки y₃ существует только одна траектория, приводящая лодку в точку y₄ = 0 (рис. 2.4).

Результаты расчета на третьем шаге сведены в таблицу 2.1.

Таблица 2.1.

Третий шаг

y4	0
y3	-1	0	1
∆y3	1	0	-1
U3	-0,755	-0,1	0,655
S3	1,526	1,005	1,324
S3		1,005
U3*		-0,1

Из результатов (табл. 2.1) видим, что условное минимальное значение функционала и оптимальное управление .

На втором шаге алгоритм расчета несколько отличается. Здесь уже производят вычисления для каждого допустимого значения y₂ и всех допустимых значений y₃:

 разности ∆y₂ = y₃ – y₂;

 управления ;

 приращения функционала на втором шаге;

 функционал ;

 минимум ;

 условное оптимальное управление U₂^*(y₂) путем перебора.

На первом и нулевом шагах алгоритм расчета такой же, как и на втором. Результаты расчета на втором шаге сведены в таблицу 2.2, на первом шаге  в таблицу 2.3 и на начальном шаге  в таблицу 2.4.

Таблица 2.2.

Второй шаг.

y2	-1			0			1
y3	-1	0	1	-1	0 *	1	-1	0	1
∆y2	0	1	2	-1	0	1	-2	-1	0
U2	-0,1	0,655	0,874	-0,75	-0,1	0,655	-0,91	-0,75	-0,1
∆I2	1,005	1,324	2,054	1,526	1,005	1,324	2,458	1,526	1,005
I2	2,01	2,329	3,059	2,531	2,01	2,329	3,463	2,531	2,01
S2	2,01				2,01				2,01
U2*	-0,1				-0,1				-0,1

Таблица 2.3.

Первый шаг.

y1	-1			0			1
y2	-1	0	1	-1	0 *	1	-1	0	1
∆y1	0	1	2	-1	0	1	-2	-1	0
U1	-0,1	0,655	0,874	-0,75	-0,1	0,655	-0,91	-0,75	-0,1
∆I1	1,005	1,324	2,054	1,526	1,005	1,324	2,458	1,526	1,005
I1	3,015	3,334	4,064	3,536	3,015	3,334	4,468	3,536	3,015
S1	3,015				3,015				3,015
U1*	-0,1				-0,1				-0,1

Таблица 2.4.

Начальный шаг.

y0	0
y1	-1	0 *	1
∆y0	-1	0	1
U0	-0,755	-0,1	0,655
∆I0	1,526	1,005	1,324
I0	4,541	4,02	4,339
S0		4,02
U0*		-0,1

Из таблицы 2.4 видно, что в начальный момент при y₀ = 0 и x₀=0 оптимальное управления будет U₀^*= -0,1 и y₁^*= 0. Далее находим из таблицы 2.3 при y₁^*= 0 значения оптимального управления U₁^*= -0,1 и y₂^*=0, из таблицы 2.2 при y₂^*=0 оптимальное управление будет

U₂^*=-0,1 и y₃^*=0 и из таблицы 2.1 имеем: U₃^*= -0,1 и y₄^*=0.

2. Метод динамического программирования 29

2.1. Геометрическая интерпретация метода динамического программирования 30

2.2. Уравнение Беллмана для непрерывных систем 31

2.3. Применение ЦВМ для определения алгоритма оптимального управления методом динамического программирования 35

41