Курсовая работа: Градиентный метод первого порядка

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

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

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

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

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

Каждая стадия характеризуется входными x^{i -1} и выходными xⁱ параметрами, а также параметрами управления uⁱ . При помощи управляющих воздействий оптимизируется результирующая оценка эффективности многостадийного процесса, определяемая как аддитивная функция результатов, получаемых на каждой стадии ui(x₁ ^{i -1} , uⁱ ):

(1)

Значение критерия оптимальности R_N зависит от совокупности u_N управляющих воздействий на всех стадиях. Совокупность управлений называется стратегией управления многостадийным процессом.

Основным уравнением динамического программирования является функциональное уравнение вида:

, (2)

где - оптимизируемая функция N-стадийного процесса, максимальное значение критерия R_N .

Максимизация первого слагаемого r₁ (x⁰ ,u¹ ), представляющего собой частный критерий, характеризующий первую стадию, проводится только по управлению u¹ .

Член есть значение оптимизируемой функции на последующих N-1 стадиях и максимизируется выбором управлений на всех стадиях, uⁱ (I = 1,…,N), поскольку значение x¹ зависит от управления u¹ .

Выражение (2) представляет собой рекуррентное соотношение, характеризующее последовательность функций последняя из которых отвечает искомому решению оптимальной задачи. Стратегия решения выражается системой выбранных значений u_i – членов уравнения (2), где i = 1, 2, ..., N; система дает решение функционального уравнения. Оптимальная стратегия выражается системой функций u_i , которые максимизируют правую часть уравнения (2), а именно: для i = 1, 2, ..., N.

Часто важно знать сам характер оптимальной стратегии, нежели значение оптимизируемой функции. В ходе определения функции f_N (x) получают одновременно последовательность решений u_i или стратегию также в виде функции номера стадии i.

Решение рекуррентных уравнений обычно выполняется численными методами. Часто используется следующая последовательность расчета с применением вычислительной машины: сначала находят f₁ (x), затем по найденному значению функции f₁ (x) по уравнению ( 1 ) определяют функцию f₂ (x); далее последовательно определяют f₃ (x) из f₂ (x) и т.д.

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

А) оптимизируемый процесс должен быть дискретно-распределенным во времени или пространстве (многостадийный процесс);

Б) отдельные стадии процесса должны обладать относительной независимостью, т.е. вектор выходных параметров любой стадии должен зависеть только от вектора входных параметров на эту стадию и управления на ней;

В) критерий оптимальности всего процесса должен быть сформулирован как аддитивная функция критериев оптимальности каждой стадии.

Если выполняются эти условия, необходимо правильно сформулировать задачу оптимизации. При формулировке задачи оптимизации и моделирования должны быть выявлены: 1) параметры, характеризующие состояние каждой стадии; 2) управляющие параметры на каждой стадии; 3) ограничения, которые накладываются на параметры состояния процесса и управляющие параметры. Кроме того, должно быть составлено математическое описание для каждой стадии и определен критерий оптимальности.

Градиентные методы оптимизации

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

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

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

Если критерий задан уравнением

, (3)

то его градиент в точке (x₁ , x₂ ,…, x_n ) определяется вектором:

. (4)

Частная производная пропорциональна косинусу угла, образуемого вектором градиента с i-й осью координат. При этом