182169 (629343), страница 3

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

Текст из файла (страница 3)

где - управление на k-м шаге, переводящее систему из состояния в состояние (рис.1). Управление на k-м шаге заключается в выборе значений определенных управляющих переменных .

Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы и управления на данном шаге (рис.1). Такое свойство получило название отсутствия последствия. Обозначим эту зависимость в виде

(1.1)

Равенства (1.1) получили название уравнений состояний. Функции полагаем заданными.

Варьируя управления U, получим различную «эффективность» процесса, которую будем оценивать количественно целевой функцией Z, зависящей от начального состояния системы и от выбранного управления U:

(1.2)

Показатель эффективности k-го шага процесса управления, который зависит от состояния вначале этого шага и управления , выбранного на этом шаге, обозначим через (рис. 1). В рассматриваемой задаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т.е.

(1.3)

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

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

Для единообразия формулировок (но не вычислительных процедур!) в дальнейшем будем говорить только о задаче максимизации, имея в виду, что если необходимо минимизировать Z, то заменив Z на Z’=-Z перейдем к максимизации Z’.

Начальное состояние и конечное состояние могут быть заданы однозначно или могут быть указаны множество начальных состояний и множество конечных состояний так, что . В последнем случае в задаче пошаговой оптимизации требуется определить совокупность допустимых управлений, переводящих систему из начального состояния в конечное и максимизирующих целевую функцию (1.3). Управление, при котором достигается максимум целевой функции (1.3) называется оптимальным управлением и обозначается через U*=

.

Если переменные управления принимают дискретные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерные модели ДП. Число шагов в задаче может быть либо конечным, либо бесконечным.

ДП применяется при оптимизации как детерминированных, так и стохастических процессов.

В некоторых задачах, решаемых методом ДП, процесс управления естественно разбивается на шаги. Например, при распределении на несколько лет ресурсов деятельности предприятия шагом естественно считать временной период; при распределении средств между n предприятиями номером шага естественно шага номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на некоторые временные отрезки – шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.

2.2.2 Принцип оптимальности и уравнение Беллмана

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

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

С точки зрения интересов оптимизации только каждого ближайшего шага – выбора кратчайшего пути из данной точки в соседнюю – следует двигаться по маршруту, проходящему через точки А, А₁, А₃, А₂, А₄, В. Длина этого маршрута равна 34. Такой путь из А в В не является кратчайшим. Например, маршрут, проходящий через точки А, А₃, А₄, В имеет меньшую длину, равную 25. Решив эту задачу, мы убедимся, что второй путь также не является оптимальным.

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

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

Использование этого принципа гарантирует, что управление, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения процесса в целом.

Так, если система в начале k-го шага находится в состоянии и мы выбираем произвольное управление , то система придет в новое состояние , и дальнейшие управления должны выбираться оптимальными относительно состояния

. Последнее означает, что при этих управлениях максимизируется показатель эффективности на последующих до конца процесса шагах k+1,…,n, т.е. величина Показатель, характеризующий суммарную эффективность от данного k-го до последнего n-го шага, будем обозначать через Z_k, т.е. Задача оптимизации процесса, начиная с k-го до последнего n-го шага (рис.3), похожа на исходную при начальном состоянии системы

, управлении и показателе эффективности (аналогично (2)). Выбрав оптимальное управление U_k* на оставшихся n-k+1 шагах, получим величину , которая зависит только от

, т.е.

(2.1)

Назовем величину условным максимумом. Если теперь мы выберем на k-м шаге некоторое произвольное управление

, то система придет в состояние . Согласно принципу оптимальности, какое бы мы не выбрали, на последующих шагах управление должно выбрать так, чтобы показатель эффективности Z_k+1 достигал максимального значения, равного . Остается выбрать управление

. Его нельзя выбирать из условия локальной максимизации показателя эффективности на данном k-м шаге, лишь бы получить . Такой подход был бы недальновидным, поскольку от выбора

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

так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1) – го) приводило бы к общему максимуму показателя эффективности на n-k+1 шагах, начиная с k-го до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:

(2.2)

Получившего название основного функционального уравнения ДП, или уравнения Беллмана.

Из уравнения (5) может быть получена функция , если известна функция ; аналогично можно получить , если найдена , и т.д., пока не будет определена величина , представляющая по определению максимальное значение показателя эффективности процесса в целом:

Соотношения (5) для определения последовательности функций через (k=n, n-1,…,1) получили название основных рекуррентных уравнений Беллмана.

Решая уравнения (2.2) для определения условного максимума показателя эффективности за n-k+1 шагов, начиная с k-го шага, определяем соответствующее оптимальное управление , при котором этот максимум достигается. Это управление также зависит от . Будем обозначать такое управление через и называть условным оптимальным управлением на k-м шаге.

Основное значение уравнения (2.2, в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения максимума функции (1.2) n переменных сводится к решению последовательности n задач, задаваемых соотношениями (2.2), каждое из которых является задачей максимизации функции одной переменной . Эти задачи оказываются взаимосвязанными, так как в соотношении (2.2) при определении учитывается найденная при решении предыдущей задачи функция .

2.2.3 Общее описание процесса моделирования и построения вычислительной схемы динамического программирования

Общая задача оптимизации, чтобы ее можно было описать моделью ДП должна удовлетворять следующим условиям :

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

2. Структура задачи инвариантна относительно числа шагов п, т. е. должна быть определена для любого n и не зависеть от этого числа.

3. На каждом шаге состояние системы определяется конечным числом s параметров состояния и управляется конечным числом r переменных управления, причем s и r не зависят от числа шагов п.

4. Выбор управления на k-м шаге не влияет на предшествующие шаги, а состояние в начале этого шага есть функция только предшествующего состояния и выбранного на нем управления (отсутствие последействия).

Построение модели ДП сводится к следующим основным моментам:

1) выбирают способ деления процесса на шаги;

2) вводят параметры состояния и переменные управления на каждом шаге процесса;

Характеристики

Список файлов курсовой работы