Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Метод динамического программирования. Принцип оптимальности и уравнение Беллмана.↑ ⇐ ПредыдущаяСтр 2 из 2 Содержание книги
Поиск на нашем сайте
Метод динамического программирования состоит в том что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учётом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Это основное правило динамического программирования, сформулированное Беллманом, называется принципом оптимальности. Так, если система в начале k - шага находится в состоянии и мы выбираем произвольное управление , то она придет в новое состояние в , и последующие управления должны выбираться оптимальными относительно состояния . Последнее, означает, что этих управлениях максимизируется величина , то есть показатель эффективности на последующих до конца процесса шагах . Обозначим через . Выбрав оптимальное управление на оставшихся шагах, получим величину , которая зависит только от , то есть . Назовем величину условным максимумом. Еслимы теперь выберем на k -м шаге некоторое произвольное управление , то система придет в состояние . Согласно принципу оптимальности, необходимо выбирать управление так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему показателю эффективности на шагах, начиная с k -uго и до конца. Это положение в аналитической форме можно записать в виде следующего соотношения: , , (1) получившего название основного функционального уравнения динамического программирования, или основного рекуррентного уравнения Беллмана. Из уравнения (1) может быть получена функция , если известно функция . Аналогично можно получить , если известно и т. д., пока не будет определена величина , представляющая по определению максимальное значение показателя эффективности процесса в целом: . Решая уравнение (1) для определения условного максимума показателя эффективности за шагов, начиная с k -го, мы определяем соответствующее оптимальное управление , при котором этот максимум достигается. Это управление также зависит от ; будем обозначать его через и называть условным оптимальным управлением на k -м шаге. Основное значение уравнения (1), в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения максимума функции n переменных сводится к решению последовательности n задач, задаваемых соотношениями (1), каждое из которых является задачей максимизации функции одной переменной . В результате последовательного решения п частных задач на условный максимум определяют две последовательности функций: - условные максимумы и соответствующие им - условные оптимальные управления. Указанные последовательности функций в дискретных задачах получают в табличной форме, а в непрерывных моделях - аналитически. После выполнения первого этапа (условнойоптимизациии) приступают ко второму этапу - безусловной оптимизации. Если начальное состояние задано , то непосредственно определяют максимум целевой функции , а затем - искомое безусловное оптимальное управление по цепочке . (2) Если задано множество начальных состояний , то дополнительно решают еще одну задачу на максимум , откуда находят , а затем по цепочке (2) - безусловное оптимальное управление. В рассмотренных рекуррентных соотношениях предписывают начинать вычисления с последнего этапа и затем передвигаться назад до этапа 1. Такой метод вычислений известен как алгоритм обратной прогонки. Если расчеты осуществляются в естественном порядке следования этапов, то такой метод вычислений известен как алгоритм прямой прогонки. Приведем рекуррентные соотношения для этого случая. Уравнения состояний для прямого хода удобно записывать в виде . Введем в рассмотрение условные максимумы показателя эффективности за k шагов, от 1-го до k- говключительно, - величину . Повторив приведенные рассуждения, придем к следующей системе уравнений Беллмана: ; . В результате решения этих уравнений получим последовательности ; . Далее определим безусловное оптимальное управление по цепочке .
|
||||
Последнее изменение этой страницы: 2016-09-05; просмотров: 231; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.117.94.77 (0.006 с.) |