32231

Метод динамического программирования Р. Беллмана

Лекция

Информатика, кибернетика и программирование

6 величина определяется в соответствии с уравнениями 7.10 При условиях ; Оптимальное уравнение определяется в результате решения уравнения 7.10 можно заменить уравнениями в частных производных 7.4 получим Из уравнения получим П 7.

Русский

2013-09-04

1.14 MB

34 чел.

Лекция №7

Метод динамического программирования Р. Беллмана

В основу динамического программирования положен принцип оптимальности. Согласно этому принципу оптимальное уравнение определяется конечной целью управления и состоянием системы в рассматриваемый момент времени не зависимо от предыстории системы (как она попала в рассматриваемую точку). Это означает что для оптимальных траекторий каждый участок, связывающий любую промежуточную точку этой траектории с конечной точкой, также является оптимальной траекторией.

Задача оптимизации состоит в том, чтобы определить оптимальное управление  и оптимальную траекторию (экстремаль) из условия выполнения минимума (или максимума) функция …. (критерия)

     (7.1)

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

      (7.2)

или        (7.3)

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

В данном методе вводится вспомогательная функция S, называемая функцией Беллмана

     (7.4)

Дадим приращение по времени Δt. Тогда

     (7.5)

где ,  - вектор переменных (координат) объекта в момент .

Пусть 0, тогда с учетом выражения (7.5) получим

     (7.6)

Получаемая из (7.6) величина  определяется в соответствии с уравнениями (7.2) или (7.3) оптимальную траекторию .

Первое слагаемое в первой части выражения (7.6) с точностью до малых величин   …. Порядка  можно заменить приближенным выражением

   (7.7)

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

  (7.8)

В соответствии с (7.2) точность для любых малых более высокого порядка

С учетом этого выражение (7.8) примет вид:

 (7.9)

На основании (7.6), (7.7) и (7.8) запишем

После деления всех членов на  и переходя к пределу 0 получим нелинейное уравнение Беллмана в частных производных

  (7.10)

При условиях ; ,

Оптимальное уравнение  определяется в результате решения уравнения (7.10), что в общем случае сделать достаточно сложно. Для внутренней области  условие (7.10) можно заменить уравнениями в частных производных

   (7.11)

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

Для стационарного объекта управления в (7.11) можно представить в виде

   (7.12)

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

    (П 7.1)

    (П 7.2)

или       (П 7.3)

где ; ; .

В соответствии с (7.12) для нашего случая будет:

   (П 7.4)

И условие минимума не управляющему воздействию (второе уравнение (7.11)) дает следующее уравнение:

    (П 7.5)

Из (П 7.5) следует

     (П 7.6)

После подстановки (П 7.6) в (П 7.4) получим

Из уравнения получим

   (П 7.7)

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

   (П 7.8)

где   – коэффициент обратной связи будет определятся, как

  (П 7.9)

Что совпадает с результатами, полученными в предыдущих примерах.

Наиболее эффективное применение динамического программирования при численном решении уравнения Беллмана. Для этого заменяем дифференциальные уравнения объекта управления (7.3) уравнениям в конечных разностях, т.е. дифференциальные уравнения  заменяем на разность  

    (П 7.9)

, k=1,2,…N – число временных …

Функционал (критерий оптимальности) примет вид

   (П 7.9)

На каждом интервале  считаем  - непостоянной величиной. Таким образом решая рекуррентные уравнения (7.13) находится значения оптимального уравнения на каждом значения оптимального уравнения на каждом интервале : , ,…,, также что  ,  и которые обеспечивают минимум функционала (7.14). при численном решении задача оптимизации на каждом участке решается в обратном порядке -  от конца к началу.

Графически вычислительную процедуру можно в виде пути, который проходит через точку, минимальных значений критерия (7.14) на рис 7.1 представлена оптимальная траектория (экстремаль) x(t). Величина x разбита на интервалы Δx и время t на интервалы Δt. В точках пересечения показаны численные значения приращения функционала ΔJ.

Рис. 7.1. Расчет оптимальной траектории x(t) по минимому приращения функционала.

Минимальное значение функционала достигается при движении по траектории, обозначается при движении по траектории, обозначенной сплошной строкой.


x

1,5

1,3

1,1

0,7

1,8

1,6

1,5

1,2

2,7

2,4

2,1

1,8

 0

 0

1,1

0,8

0,6

0,3

3,5

3,2

2,8

2,3

1,6

1,2

0,8

0,6

X5

Δx

X4

Δx

X3

Δx

X2

Δx

X1

Δx

t1

Δt

t2

Δt

t3

Δt

t4

Δt

t5


 

А также другие работы, которые могут Вас заинтересовать

33646. Атаки на протокол ARP 38 KB
  Атаки на протокол RP Протокол разрешения адресов – RP. Функционально протокол RP состоит из двух частей. Одна часть протокола определяет физические адреса другая отвечает на запросы при определении физических адресов. Протокол RP работает различным образом в зависимости от того какой протокол канального уровня работает в данной сети протокол локальной сети Ethernet Token Ring FDDI с возможностью широковещательного доступа одновременно ко всем узлам сети или же протокол глобальной сети Х.
33647. ПРОТОКОЛ ICMP. ФОРМАТЫ СООБЩЕНИЙ ICMP 35 KB
  Если маршрутизатор обнаруживает ошибку он уничтожает дейтаграмму но одновременно с помощью ICMP отсылает сообщение об ошибке отправителю для принятия мер по ее устранению. 8бит – тип сообщение 8 бит – поле кода конкретизирует назначение сообщения 16 бит – контрольная сумма. Сообщение Получатель недостижим посылается маршрутизатором если он не может доставить IPдейтаграмму по назначению. В это сообщение включается IPзаголовок отвергнутой IPдейтаграммы и ее первые 64 бита.
33648. Атаки сетевого уровня на протокол IP и его защита 119 KB
  В качестве примера можно привести известную утилиту Nmp некоторые режимы которой позволяют задать поддельные адреса отправителя пакетов. Посылка специфических пакетов где определённым образом заполнены поля заголовка отвечающие за фрагментацию может приводить к зависанию или понижению производительности узла. Исправление этих ошибок – это установка пакетов обновления программного обеспечения. Большое число одинаковых фрагментированных пакетов вызывают замораживание машины на время атаки.
33649. Атаки на протокол ICMP и его защита 27.5 KB
  Атаки на протокол ICMP и его защита Поскольку протокол ICMP служит для передачи различных управляющих служебных сообщений поэтому всегда был популярной мишенью для атаки. Атака Sping Jolt Атака состоит в посылке нескольких дефрагментированных пакетов ICMP IСМР_ЕСНО больших размеров по частям. Для устранения уязвимости необходимо применить патч icmpfix который зависит от версии Windows NT и установленного пакета обновления. Атака ICMP Request Атака заключается в посылке пакета ICMP Subnet Msk ddress Request по адресу сетевого интерфейса...
33650. Протокол IPSec 43.5 KB
  Протокол IPSec Шифрование данных на сетевом уровне представлено группой протоколов IPSec основанных на современных технологиях электронной цифровой подписи и шифрования данных. Протокол IPSec включает в себя: протокол аутентификации uthentiction Heder АН который привязывает данные в составе пакета к своеобразной подписи позволяющей удостовериться как в подлинности отправителя так и в целостности принятых от него данных; протокол Encpsulted Security Pylod ESP отвечающий за шифрование содержимого отдельных пакетов и даже...
33651. Протокол ESP 42 KB
  Протокол IKE Протокол IKE обеспечивает распределение ключей и согласование протоколов между участниками обмена. Протокол IKE решает три задачи: согласование алгоритмов шифрования и характеристик ключей которые будут использоваться в защищенном сеансе; непосредственный обмен ключами в том числе возможность их частой смены; контроль выполнения всех достигнутых соглашений. Протокол IKE функционирует в два этапа: Установление защищенного соединения для процедуры обмена IKE S. Два из них основной и агрессивный относятся к первому...
33652. Режимы работы IPSec 30 KB
  Каждое из них определяет различные параметры IPSecсоединения такие как алгоритмы шифрования и аутентификации которые будут использованы при обмене информацией между системами сеансовые ключи шифрования и т. Алгоритмы шифрования IPSec это набор протоколов в которых используются алгоритмы аутентификации и шифрования. На сегодня определены два алгоритма аутентификации и семь алгоритмов шифрования. Алгоритм шифрования DES Dt Encryption Stndrd с явно заданным вектором инициализации Initiliztion Vector IV применяют в протоколе ESP по...
33653. Виртуальные частные сети 30.5 KB
  Виртуальные частные сети Виртуальная частная сеть VPN это технология обеспечивающая безопасную связь по открытой общей сети. Истинная частная сеть принадлежность оборудования сети предприятия и гарантия конфиденциальности информации передаваемой по этой сети. Такие сети не очень распространены. Корпоративные данные практически не доступны для абонентов не являющихся пользователями корпоративной сети или сотрудниками провайдера.
33654. Типы VPN-устройств 31 KB
  Типы VPNустройств Существует несколько основных типов VPNустройств: отдельное аппаратное устройство VPN на основе специализированной ОС реального времени имеющее 2 или более сетевых интерфейса и аппаратную криптографическую поддержку так называемый черный ящик; отдельное программное решение которое дополняет стандартную операционную систему функциями VPN; расширение межсетевого экрана за счет дополнительных функций защищенного канала; средства VPN встроенные в маршрутизатор. Устройства VPN могут играть роль шлюза или клиента...