Теория автоматического управления. Часть 2

x2

x(t f )

x(t′)

x(t0 )

x1

x3

Рис. 4.4. К принципу оптимальности.

Принцип оптимальности гласит, что любая конечная часть оптимальной траектории является, в свою очередь, оптимальной траекторией. Это означает, что траектория от некоторой промежуточной точки x(t′) до конечной точки x(t f ) является оптимальной, то есть обеспечивает мак-

симум критерия R′ = t∫f r(x,u,t)dt . Действительно, предположим, что это

t'

не так, а, следовательно, есть какая-то другая траектория (на рис. 4.4 показана штриховой линией), доставляющая максимум функционала R′ . Но тогда и первоначальная траектория вопреки предположению не являлась оптимальной, поскольку критерий оптимальности, состоящий из суммы двух частей – максимальной на отрезке траектории от точки x(t0 ) до точки x(t′) и не максимальной – от точки x(t′) до точки x(t f ), принимал бы не максимальное значение.

Изложенное выше справедливо, конечно, и для систем, в которых время разбито на дискретные шаги (этапы).

251

Таким образом, оптимальная стратегия зависит только от состояния объекта в рассматриваемый момент времени и не зависит от того как объект попал в это состояние, то есть не зависит от его предыстории.

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

Если речь идёт о многошаговых процессах оптимизации, то такой подход сводит исходную задачу к последовательному решению одношаговых процессов оптимизации. В многошаговом процессе оптимизации полных выигрыш для N шагов, согласно принципу оптимальности, можно представить в виде

RN = r(x1,u1 )+ RN−1(x1,u1 ).

Первое слагаемое в этом выражении – начальный выигрыш, второе слагаемое – максимальный выигрыш от последующих N-1 шагов.

Максимальный выигрыш запишется как

Таким образом, принцип оптимальности позволяет исходный N шаговый процесс заменить последовательностью одношаговых процессов и на каждом шаге использовать одно и то же рекуррентное соотношение (4.4.1).

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

Обозначим через Rn (c) максимальное значение произведения, x –

первая часть, (c − x) – оставшаяся часть. Тогда, используя соотношение

(4.4.1), можно составить функциональное уравнение

Очевидно, что при n=1

R1 (c)= c и R1 (c − x)= c − x .

Положим в уравнении (4.4.2) n=2:

Максимум найти нетрудно, приравняв нулю производную по x от вы-

ражения в фигурных скобках. Этот максимум будет при x = c2 . Таким

образом, оптимальная стратегия деления на две части – это деление на две равные части

253

{ }= c , c , ui 2 2

Положим n=3. Максимальное произведение найдем из соотношения

Взяв производную и приравняв её нулю, получим x = 3c . Оставшаяся

часть в 23 c , согласно предыдущему рассуждению, оптимально будет

разделена на две равные части, то есть на 3c и 3c .

Оптимальное деление на три части будет, таким образом

Продолжая подобные рассуждения, приходим к выводу, что при n=k оптимальным делением будет деление на k равных частей

254

а максимальное произведение будет

( )= c k .

Rk c k

Методом математической индукции можно доказать, что оптимальным делением будет деление на равные части и при n=k+1. Действительно, полагая n=k+1, из соотношения (4.4.2) получим

и максимальное произведение равно

255

( )= c n .

Rn c n

Задача, рассмотренная в данном примере, очень простая и она могла быть решена обычными методами. Но этот пример имел целью показать, каким образом данная задача может быть сформулирована как многошаговый процесс оптимизации. Во многих более сложных задачах подобная формулировка часто является ключом к их решению при применении метода динамического программирования.

4 . 4 . 3 . Дискр етный вар иант м ето да динам ическо го про гр амм иро вания

Начать рассмотрение метода динамического программирования про-

то есть найти оптимальную траекторию, соединяющую точку x(k0 ) и точку x(k f ).

256

В критерии (4.4.3) r(x(k),u(k)) – потери от сделанного k-го шага. Например, это могут быть затраты энергии или штраф на k-м шаге.

Поскольку на каждом шаге (а таких шагов N = k f − k0 ) состояние объекта принимает только одно из l значений, то число возможных траекторий конечно и равно lN , и, в принципе, оптимальную траекторию можно было бы найти простым перебором. Однако в реальных случаях это потребовало бы непомерно большого объема вычислений. Метод динамического программирования позволяет резко сократить объем вычислительной работы.

Возьмём некоторую промежуточную точку k j . Показатель качества R

на интервале от k j до k f определяется состоянием объекта x(k j ) и управляющими воздействиями u(k) при k j ≤ k ≤ kf :

Принцип оптимальности означает, что если выражение (4.4.3) минимально, то часть (4.4.4) также должна быть минимальной. Более того, оптимальная стратегия управления u (k) на интервале (kj ,kf ) является только функцией состояния x(k j ), то есть u (k)= gk (x(k j )). Поэтому оптимальное значение критерия (4.4.4) является лишь функцией состояния x(k j ) и самого k j :

Очевидно, что при k j = k f R (x(k f ),k f )= 0 . Приняв это граничное

условие за исходное, можно воспользоваться уравнением (4.4.5) для вычисления u (k) при попятном движении от k = k f до k = k0 .

Действительно, на шаге k f −1 находим управление u (kf −1), соот-

ветствующее минимальному значению R, то есть, определяем и запоминаем R (x(k f −1),k f −1), которое будет являться функцией значения x в

начале последнего шага. Поиск минимума при этом ведётся только по одной переменной u(k f −1)

Минимизировать приходится всё выражение в фигурных скобках, по-

{u (kf − 2),u (kf −1)}, значение x(k f −1) в конце предпоследнего шага и величину R (x(k f − 2),kf − 2) как функцию x(kf − 2). Заносим её в память

вместо R (x(k f −1),k f −1).

Далее процесс повторяется до тех пор, пока мы не придём в точку, соответствующую k = k0 . А значения x(k0 ) нам известно! Таким образом, определится стратегия оптимального управления

{u (k0 ),u (k0 +1),...,u (kf − 2),u (k f −1)}.