Комбинированные алгоритмы штрафных функций

Для задач нелинейного программирования с ограничениями-равенствами методы внутренних штрафных функций неприменимы. Однако при практических расчетах в ряде случаев необходимо выполнение некоторых ограничений-неравенств в течение всего процесса оптимизации. В подобных обстоятельствах используют комбинированные алгоритмы, учитывающие особенности внутренних и внешних штрафных функций. Вспомогательная функция F(x, a) включает в себя слагаемые в виде внутренних штрафных функций j (х, а) для ограничений-неравенств и внешних штрафных функций f (х, а) для ограничений-равенств:

F(x, а) f(х) + Ф(х, а) + f (х, а) . (7.74)

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

. (7.75)

В качестве начальной точки выбирается вектор х[0] , удовлетворяющий условиям h_j(х) 0, j 1 ,..., m. Последовательность {a_k} , k 1, 2,..., положительных чисел является монотонно убывающей и сходящейся к нулю.

Выбор начальной точки допустимой области

В данном случае задача состоит в поиске точки, удовлетворяющей строгим неравенствам h_i(х) 0, j 1, ..., т. Рассмотрим два множества индексов:

J₁ {j¦h_j 0, j 1, …, m}(7.76)

J₂ {j¦h_j 0, j 1, …, m}(7.77)

Поиск внутренней точки должен состоять в том, чтобы перейти от точки к новой точке , в которой удовлетворяются некоторые из ограничений множества J₂. При этом ни одно из условий множества J₁ не должно нарушаться. Затем необходимо перейти от точки к другой точке, и так далее до тех пор, пока не будут удовлетворены все ограничения. Эта процедура реализуется минимизацией функции

, (7.78)

где V(x) - внутренняя штрафная функция одного из видов, представленных выше, относительно ограничений из множества J₁. Последовательность {а_k}, k 1, 2, ..., сходится к нулю. В процессе минимизации производится проверка знаков функций h_j, j J₂. Как только какое-либо из этих ограничений удовлетворяется, оно переводится во второе слагаемое, т.е. формируется соответствующая штрафная функция V(х). Минимизация полученной в результате новой функции W(x, а.) осуществляется из последней найденной точки х[k].

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

Рис. 7.14 ‑ Многостадийный процесс

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

x_k⁽ⁱ⁾ j _k⁽ⁱ⁾(x₁^(i-1), …, x_m^(i-1), u₁⁽ⁱ⁾, …, u_r⁽ⁱ⁾), (7.79)

k 1, ..., m; i 1, ..., N,

связывающей выходные параметры i-й стадии x_k⁽ⁱ⁾ с выходными параметрами предыдущей стадии x_k^(i-1) и управлением и_l⁽ⁱ⁾ (l 1, ..., r), используемым на i-й стадии.

Систему уравнений удобно также представить в векторной форме

x⁽ⁱ⁾ j ⁽ⁱ⁾(x^(i-1)_, u⁽ⁱ⁾), (7.80)

причем x⁽ⁱ⁾ вектор совокупности переменных состояния (или выход) i-й стадии;

x⁽ⁱ⁾ (x₁⁽ⁱ⁾, x₂⁽ⁱ⁾, …, x_m⁽ⁱ⁾), (7.81)

a u⁽ⁱ⁾ - вектор совокупности управляющих воздействий (управление) на i-й стадии:

u⁽ⁱ⁾ (u₁⁽ⁱ⁾, u₂⁽ⁱ⁾, …, u_r⁽ⁱ⁾). (7.82)

Размерности векторов состояния x⁽ⁱ⁾ и управления и u⁽ⁱ⁾ в общем случае могут быть различными для разных стадий процесса. Однако далее, не нарушая общности, можно принять, что размерности m и r векторов состояния и управления для всех стадий процесса одинаковы.

В реальных процессах на значения переменных состояния x⁽ⁱ⁾ и управляющих воздействий u⁽ⁱ⁾ могут быть наложены ограничения, определяющие диапазон изменения или взаимосвязь указанных переменных. Математически это находит выражение в появлении дополнительных условий в виде равенств или неравенств

F_j(x⁽¹⁾, …, x^(N), u⁽¹⁾, …, u^(N)), (7.83)

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

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

, (7.84)

Смысл записи заключается в том, что значения переменных x⁽ⁱ⁾ и u⁽ⁱ⁾ принадлежат к допустимым областям их изменения Х и U, ограниченным соответствующими соотношениями.

Предполагается, что эффективность каждой стадии процесса оценивается некоторой скалярной величиной

r_i r_i^*(x⁽ⁱ⁾, u⁽ⁱ⁾). (7.85)

заданной в виде функции от переменных состояния стадии x⁽ⁱ⁾ и принятого на ней управления u⁽ⁱ⁾.

С учетом математического описания стадии функциональная зависимость эффективности может быть представлена также как

r_i r_i(x^(i-1), u⁽ⁱ⁾). (7.86)

т. е. как функция состояния входа x^(i-1) на i-й стадии и используемого на ней управления u⁽ⁱ⁾

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

(7.87)

Естественно, что значение критерия оптимальности R_N зависит от совокупности u⁽ⁱ⁾_N управляющих воздействий на всех стадиях процесса, которые представляет собой набор значений векторов u⁽ⁱ⁾ для всех стадий:

u_N (u⁽¹⁾, u⁽²⁾, …, u^(N)). (7.88)

Совокупность управлений для всех стадий процесса u_N будем называть в дальнейшем стратегией управления многостадийным. процессом или просто стратегией управления.

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

(u_опт⁽¹⁾, u_опт⁽²⁾, …, u_опт^(N)), (7.89)

для которой критерий оптимальности r_n принимает в зависимости от постановки оптимальной задачи максимальное или минимальное значение.

Принцип оптимальности

В основу метода динамического программирования положен принцип оптимальности, который в переложении для много-, стадийного процесса может быть сформулирован следующим образом. Оптимальная стратегия обладает тем свойством, что каковы бы ни были начальное состояние x⁽⁰⁾ многостадийного процесса и управление на первой стадии u⁽¹⁾, последующие управления на всех стадиях u⁽ⁱ⁾ (i 2, ..., N) должны составлять оптимальную стратегию и_N-1 относительно состояния x⁽¹⁾ первой стадии, определяемого начальным состоянием процесса x⁽⁰⁾ и управлением на первой стадии u⁽¹⁾.

В приведенной формулировке принципа оптимальности под оптимальной стратегией и_N-1 понимается стратегия управления многостадийным процессом, включающим N-1 последних стадий исходного процесса, придающая критерию

(7.90)

оптимальное значение.

Другими словами, оптимальная стратегия и_N-1 находится для (N-1)-стадийного процесса, для которого величина является начальным состоянием.

Таким образом, если известна оптимальная стратегия управления и_N-1 для любого возможного состояния x⁽¹⁾ первой стадии N-стадийного процесса, то уже не составляет труда выбрать оптимальное управление и на первой стадии u_опт⁽¹⁾, поскольку на последующих стадиях оно определяется только состоянием выхода первой стадии:

и_N-1 и_N-1 (x⁽¹⁾). (7.91)

Процедура применения принципа оптимальности для оптимизации N-стадийного процесса, очевидно, должна начинаться с последней стадии процесса, для которой не существует последующих стадий, могущих повлиять согласно принципу оптимальности на выбор управления u_опт^(N) на этой стадии. После того как оптимальное управление u_опт^(N) найдено для всех возможных состояний входа последней стадии x^(N-1) X, можно приступить к определению оптимального управления для предыдущей (N-1)-стадии, для которой оптимальная стратегия управления на последующих стадиях (т. е. на последней N-й стадии) известна, и т. д.

В результате может быть найдена оптимальная стратегия управления для всего многостадийного процесса, являющаяся функцией начального состояния процесса u_N^(x(0)). Если начальное состояние x⁽⁰⁾ известно (задано или выбрано из условия оптимума критерия R), то его значение определяет оптимальные управления для всех стадий процесса.