Ляпидов В.C. Теоретические основы кибернетики. Методы оптимизации

Подождите немного. Документ загружается.

к касательным гиперплоскостям в некоторых точках

гиперповерхности. Условия ортогональности и дают возможность

определить точки

 

на гиперповерхностях и тем самым

определить оптимальный процесс и оптимальную траекторию.

3.6. Динамическое программирование.

Метод динамического программирования разработан

американским математиком Р. Беллманом и его школой. Метод

развивался в процессе решения вариационных задач на

вычислительных машинах, поэтому содержит элементы

дискретности. Постановка основной вариационной задачи в

динамическом программировании такая же, как и в принципе

максимума Понтрягина. При изложении используются материалы

источников [8].

Рассмотрим пример решения вариационной задачи.

Пусть, между пунктами А и В (рис. 3.9) необходимо провести

железную или шоссейную дорогу так, чтобы стоимость строительства

была минимальной. Разобьём путь между А и В на горизонтальные и

вертикальные участки. Обозначим стоимость строительства на

каждом горизонтальном и вертикальном участке в некоторых

условных единицах (стоимость строительства можно заранее

подсчитать по карте). Обозначим узловые точки

Начнём решение задачи с конечного пункта, за который примем

точку В.

В точку В можно попасть за один (последний) шаг или из точки

или из точки С

. Предположим, что каким-либо способом удалось

попасть в С

или С

. Затраты на последний шаг будут 12 или 10 ед.

Поставим величину затрат в кружки и

укажем направление последнего шага стрелками. Сместимся теперь в

точку D

. Опять считаем, что каким то образом эти точки уже

достигнуты. Проследим возможные пути в точку В. Из D

есть один

путь через С

, затраты при этом будут равны 25.

Из D

есть уже два пути: через С

и С

. Один путь даёт затраты

28, а другой 26. Через С

в В путь менее рационален, поэтому его из

дальнейших рассуждений исключаем. Ставим в D

кружок с

затратами 26 и стрелку оптимального управления в сторону С

. Также

анализируем точку D

. Из D

есть только один путь через С

. Ставим в

кружок с затратами 24 и стрелку оптимального управления в

сторону С

. Обратим внимание на то, что неоптимальная траектория

сразу исключается из рассмотрения. В этом и состоит смысл

динамического программирования. Перейдём к точке E

. Точки Е

дают единственно возможные траектории.

Точки Е

и Е

дают по две траектории каждая, из которых

выбираем оптимальные, т.е. дающие минимум затрат. Причём из

точки Е

используем только оптимальную траекторию. Из всех

возможных путей из точек Е

, Е

остаются только четыре

(показаны стрелками). Переход таким же образом к точкам F

, G

и,

наконец, к А, получаем оптимальный путь, который на рисунке

отмечен жирной линией и даёт минимально возможный расход в

условных единицах- 59. Оптимальный путь можно трактовать как

оптимальную траекторию в принятой системе координат. Отметим

ещё раз, что по мере продвижения от В к А последовательно

исключились неоптимальные траектории. Это исключение

значительно упростило нахождение оптимальной траектории. При

Рис. 3.9.

простом переборе пришлось бы рассчитывать все траектории от А до

В, которых всего 25. Заметим ещё особенность, которая заключается

в том, что оптимальная траектория рассматривается не только на

одном шаге, но и учитываются другие шаги. На каждом шаге

траектория может быть и неоптимальной, но вся траектория в целом

оптимальна. Сформулирован принцип оптимальности, который

гласит, что любой отрезок оптимальной траектории также является

оптимальным, а будущее поведение процесса не зависит от его

предыстории, т.е. поведение системы в прошлом до начала

управления.

Следует, однако, сделать оговорку. Для примера был взят очень

простой случай. В реальных ситуациях даже разбиение на шаги и то

представляет большие трудности, причём шагов может быть многие

сотни. Поэтому идея метода динамического программирования в

большинстве случаев реализуется сложным образом. Дадим

математическую запись методу динамического программирования.

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

 

,f

(3.30)

и начальные условия

 

0 xx 

 

0 uu 

. Выбираем критерий

оптимальности:

 

dtuxG ,J







(3.31)

где

- функция управления, которая доставляет минимум

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

Обозначим через

 

minJ

xS

минимальное значение функционала,

которое зависит от начальных условий и вида управления.

Допустим, имеется оптимальная траектория

 



, которая

обеспечивает минимальное значение интегралу J. Разобьем эту

траекторию на два участка: первый от

0t

до



t

, второй от



t

до

t

. Р. Беллманом был сформулирован принцип оптимальности,

согласно которому будущее поведение системы, т.е. при



t

, не

зависит от «предыстории», т.е. поведение системы в прошлом, и

определяется лишь её настоящее состоянием, т.е. в момент времени



t

. Поэтому если траектория от

0t

до



t

, оптимальная, то второй

участок оптимальной траектории также является оптимальным.

Кроме этого, второй участок может рассматриваться и как

самостоятельная траектория с начальными условиями

 





Используя принцип оптимальности, представим интеграл J в виде:

     





















dtuxGdtuxGxS ,,min

(3.32)

Согласно принципу оптимальности Беллмана, если

 

доставляет min интегралу

 





, dtuxG

то она будет доставлять также min интегралу

 







dtuxG ,

Поэтому, учитывая (3.32) получим

     

 



xSdtuxGxS 

















,min

(3.33)

где

 

 



- функция от начального состояния

 



в момент



t

Будем считать τ достаточно малой величиной.

Тогда

 

   

 

 



uxxSxxSxS ,f



(3.34)

Применим к (3.34) формулу конечных приращений

 

 

   



uxxSuxxS ,f,f



(3.35)

Из (3.32) с учётом (3.35) можно записать

       

















uxxSuxGxS

000000

,f,min

(3.36)

Вычтем из обеих частей последнего равенства

 

   

0,f,min

0000

















uxuxG

(3.37)

Для получения минимума по

нужно продифференцировать

(3.37) по

   

,f,



uxd

uxdG

(3.38)

Согласно принципу оптимальности начальные условия

можно заменить на текущие координаты

. Тогда получим

окончательно функциональные уравнения Беллмана:

   













,f,

0,f,

uxd

uxdG

uxuxG

(3.39)

Выражения (3.39) представляют собой нелинейные

дифференциальные уравнения в частных производных. Поэтому

применение этого метода в некоторых случаях требует сложных

расчётов и не всегда возможно в таком виде. Исключив из (3.39)

получим соотношение

 

   

uxd

uxdG

,f,

,f 

(3.40)

Заметим здесь, что функция S должна быть дифференцируемой

по х.

3.7. Способы нахождения фазовых траекторий.

Синтез оптимальных систем обычно проводится в фазовом

пространстве, поэтому необходимо уметь получать фазовые

траектории, т.е. находить их уравнения. При получении уравнений

фазовых траекторий предполагается, что управляющие воздействия

имеют вид единого скачка.

Предположим, что объект управления состоит из двух

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

вид:

















(3.41)

Требуется определить уравнение фазовой траектории, т.е.

функцию

 

f xx 

Первый способ. Разделим почленно уравнения звеньев

212





(3.42)

Проинтегрируем полученное выражение

 

 







 CTxuux

dxx

ln

(3.43)

Постоянную интегрирования С определяем из начальных

условий при

202101

,,0 xxxxt 

 

 

CTxuuxx 

101020

ln

, отсюда

 

101020

ln xuTuTxxC 

(3.44)

Подставляя значение постоянной интегрирования (3.44) в (3.43),

окончательно получим уравнение фазовой траектории.

 

20110

ln xTxx

uTx 





(3.45)

Второй способ. Уравнения для фазовых траекторий не, всегда

интегрируются. Тогда можно получить выражение для фазовой

траектории, исключая время из решений для отдельных координат.

Записываем решение для х

из (3.41)

eCCx





101

(3.46)

Определяем постоянную интегрирования С

из начальных

условий при t=0, x

uxCuC 

1010

; 

Подставим С

в (3.46):

 

euxux



 

101

. (3.47)

Решаем второе уравнение из (3.41), учитывая х

 

euxu



 

;

 

210

2102

CeuxT

utCdteuxudtx











(3.48)

Из начальных условий при t=0, x

находим постоянную C

 

10202

TuxxC 

Подставим значение С

в решение (3.48):

   

1020102

uxTxeuxTutx

 



(3.49)

Из решения для x

определяем:

;ln

;









Подставляем эти значения в решение для х

   

 

.ln

20110

10201

xTxx

uxTxuxT

uTx











 

(3.50)

Естественно, что уравнение (3.50) для фазовой траектории не

отличается от уравнения (3.10), полученного первым способом.

Третий способ. Покажем другой вариант исключения времени из

решений дифференциальных уравнений.

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

уравнений:



















;

212

(3.51)

Запишем решения для х

и х





























;

2102

101

eCeCCx

eCCx

(3.52)

где

uСС 



Определив постоянные интегрирования из начальных условий

при t=0, x

, x

подставив в (3.52), получим:

 

;

110

102

101

uxux

euxux































(3.53)

Из решения (3.53) для x

определяем







(3.54)

Подставляем (3.54) в решение (3.53) для x

 

110

uxux

























 

(3.55)

Из выражения (3.54) определяем время

.ln





(3.56)

Аналогично исключаем



из решения (3.53) для x

 

.ln

112

110

TxuT















(3.57)

Так как фазовая траектория строится при одинаковых моментах

времени, то выражения (3.56) и (3.57) можно приравнять, получив

уравнение фазовой траектории:

.lnln

112

1102

TxuT

















(3.58)

Четвертый способ. Выражение (3.58) довольно сложно и

неудобно для расчетов, так как относительно переменных оно

получилось в неявной форме. Поэтому иногда удобно задавать

уравнения фазовых траекторий в параметрической форме. Примером

такого задания может служить система решений (3.52). Находя при

одинаковых t значения x

и x

, можно построить фазовую траекторию.

Пятый способ. Бывают случаи, когда уравнение для фазовой

траектории не интегрируется, а из решений не исключается время.

Особенно часто встречаются такие случаи, когда объект описывается

системой нелинейных уравнений. Для качественной оценки фазового

портрета применяется метод изоклин.

Рассмотрим объект, который описывается следующей системой

уравнений:

;





(3.59)

Разделим второе уравнение на первое:





(3.60)

Проинтегрировать полученное уравнение фазовой траектории

довольно сложно. Поэтому построим фазовый портрет методом изо-

клин. Сущность метода состоит в следующем. Приравняем произ-

водную

некоторому постоянному числу m. Этому же числу будет

равна и правая часть уравнения (3.60)





(3.61)

Уравнение (3.61) является уравнением некоторой кривой в

плоскости x

, x

. В любой точке этой кривой производная

постоянна и равна m.

Задаемся числами m

=0, m=m

, m=m

,…m=m

. Для этих чисел

решаем уравнение (3.61). В результате получим семейство парабол

(рис.3.10). На каждой параболе

отложим отрезки с наклоном,

соответствующим производной

m

Примем, что начальные условия

нулевые, т. е. при t=0, x

=0. В

нулевой точке производная равна нулю,

так как т

=0. Плавной кривой

соединим отрезки на параболах т

, m

, .

Рис. 3.10 Фазовые траектории,

построенные методом изоклин

. ., т

(см. рис. 3.10, кривая 1). Получим интегральную кривую,

которая является фазовой траекторией. Если взять другие начальные

условия, то найдем другую фазовую траекторию (кривая 2).

Для точного построения фазовой траектории необходимо

построить много изоклин, т.е. линий равных значений производных.

Это связано с большим объемом вычислительной работы. Поэтому

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

стороны некоторого процесса. Обратим внимание на то, что методом

изоклин строятся фазовые портреты только на плоскости, т. е. для

объектов, которые описываются уравнениями не выше второго

порядка.

Шестой способ. Для расчетов процессов весьма полезными могут

быть графо-аналитические приближенные методы решения

дифференциальных уравнений. Наиболее распространен метод А. В.

Башарина, который был успешно использован для анализа и синтеза

нелинейных систем электропривода.

Сущность метода состоит в следующем. Заменим в системе урав-

нений (3.59) дифференциалы приращениями:

;









После несложных

преобразований получим



















;

tux

(3.62)

Построим в координатных осях

, х

статическую характеристику

xx 

(рис. 3.11).

xx 



Рис. 3.11 Графо-аналитический

метод решения нелинейного

уравнения