logo search
ОИТ_Учебник

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

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

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

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

. (7.75)

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

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

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

J1 {j¦hj 0, j 1, …, m} (7.76)

J2 {j¦hj 0, j 1, …, m} (7.77)

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

, (7.78)

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

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

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

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

xk(i) k(i)(x1(i-1), …, xm(i-1), u1(i), …, ur(i)), (7.79)

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

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

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

x(i) (i)(x(i-1), u(i)), (7.80)

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

x(i) (x1(i), x2(i), …, xm(i)), (7.81)

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

u(i) (u1(i), u2(i), …, ur(i)). (7.82)

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

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

Fj(x(1), …, x(N), u(1), …, u(N)), (7.83)

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

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

, (7.84)

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

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

ri ri*(x(i), u(i)). (7.85)

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

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

ri ri(x(i-1), u(i)). (7.86)

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

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

(7.87)

Естественно, что значение критерия оптимальности RN зависит от совокупности u(i)N управляющих воздействий на всех стадиях процесса, которые представляет собой набор значений векторов u(i) для всех стадий:

uN (u(1), u(2), …, u(N)). (7.88)

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

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

(uопт(1), uопт(2), …, uопт(N)), (7.89)

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

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

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

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

(7.90)

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

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

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

иN-1 иN-1 (x(1)). (7.91)

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

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