1.4. методика вычисления оптимального значения задачи

1.4. методика вычисления оптимального значения задачи

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

Рассмотрим прежде всего простейший из многошаговых процессов, включающий два шага управления, N = 2. В этом случае вектор управляющих переменных (щ,и2) содержит две компоненты, и целевая функция Z является функцией двух переменных щ,и2:

Z = Z(ui,u2) = Zi(x0,Ui) + Z2(xi,U2),

где X = /і(х0,«і)Для определения оптимального значения Z* необходимо вычислить максимум целевой функции по обеим управляющим переменным U, и2:

Z* = max.{z1(xo,u1) + z2(xi,u2)}.

Ul,U2

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

Z* — тах{тах{2і(хо,иі) + z2(xi,u2)}}.

(Конечно, для справедливости такого преобразования необходимо, чтобы множества векторов (щ,и2), учитываемых при одновременном и при последовательном способах вычисления Z*, полностью совпадали). В полученной сумме первое слагаемое 2і(х0,«і) не зависит от переменной и2, по которой вычисляется внутренний максимум. Следовательно, это слагаемое может быть вынесено за знак внутреннего максимума:

maxbi(x0,«i) + z2(xi,u2)} = Zi(z0, т) + max{z2(zi, и2)}-Таким образом, справедливо равенство

Z* = тах{2і(х0,«і) + max{z2(x1,u2)}}.

Ui 1 "2

В результате проведенных преобразований вычисление максимума по двум переменным щ,и2 удалось «разнести» на два последовательных вычисления максимума по переменным и2 и и, т. е. двумерная задача свелась к последовательному решению двух одномерных задач. Как правило, одномерная задача существенно проще двумерной (и тем более многомерной), а проведенные преобразования соответствуют общей закономерности: решить несколько задач низшей размерности проще, чем решить одну задачу высшей размерности.

Структура последнего равенства «подсказывает», что вычисление z* следует разбить на 2 шага —это соответствует структуре многошагового процесса и приводит к более простым выражениям. С этой целью введем новую вспомогательную функцию Bi(xi), принимая в качестве нее внутренний максимум:

Ві(хі) = так{г2(хі,щ)}.

Смысл функции Bi(xi) состоит в том, что она представляет собой максимальное значение частной целевой функции z2 на втором шаге процесса при условии, что перед этим шагом управляемая система находилась в состоянии х. С учетом введенной функции В(х{) можно записать:

Z* = ^{^(ЯО.ИІ) + I x! = fl(x0,m)}.

В данной записи и всюду далее вертикальная черта «|» означает «при условии»: максимум выражения zi(x0,щ) + Ві(хі) по переменной щ вычисляется при условии, что Х не является произвольным, а определяется равенством xi = /і(хо,щ).

Преобразуем два последних выражения к однотипной форме. Для единообразия обозначений введем две новых функции: функцию В2(х2), тождественно равную нулю: В2(х2) = О для всех х2, и функцию В0(х0), определенную только для одного значения х0 и равную оптимальному значению z*, подлежащему вычислению: В0(х0) = z*. С использованием введенных обозначений полученные выше равенства можно записать следующим образом:

= тж{г2(Х1,и2) + В2(х2) | х2 = h(xi,u2)},

В0(х0) = max{zi(a:o,Mi) + Ві(хі) | хг = /і(х0,щ)}.

Важно подчеркнуть, что полученные два равенства полностью совпадают по структуре и отличаются только индексами переменных и функций. Таким образом, проведенные преобразования с использованием введенных вспомогательных функций В0(х0), Ві(хі) и В2(х2) не только позволили упростить вычисления оптимального значения задачи z* путем снижения размерности, но и привели вычисления к однотипной форме, соответствующей структуре процесса. Расчеты проводятся в порядке убывания индексов: В2(х2) =0 по определению; с учетом этого равенства далее вычисляется Bi(xi); наконец, вычисляется Bq(xo) = z*. На вид последних двух равенств следует обратить особое внимание, поскольку он является характерным для записи общего принципа оптимальности.

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

Z = Z{u) = z\{xq,u).

В этом случае решение задачи оптимизации сводится к поиску максимума функции одной переменной:

Z* = max.{zi(x0,ui)},

Ul

причем введение соответствующих вспомогательных функций В0(хо) — Z* и Bi(xi) = 0 позволяет придать последнему соотношению уже полученный выше типовой вид (хотя, конечно, для N = 1 такое преобразование не имеет глубокого смысла и является скорее усложнением, чем упрощением задачи).

Рассмотренная методика вычисления оптимального значения задачи Z* может быть распространена и на общий случай многошаговых процессов. При этом могут быть проведены рассуждения, подобные известному методу математической индукции. Действительно, для N = 1 и N = 2 способ вычисления Z* уже рассмотрен выше. Предположим, что мы умеем вычислять оптимальное значение задачи для любого процесса, включающего N—1 шаг, и рассмотрим ЛГ-шаговый процесс. На первом шаге под действием управления щ система из начального состояния х0 перейдет в состояние х = f(xQ,u), обеспечив экономический эффект zi(x0,ui). При этом для последующего перевода системы из состояния xi в конечное состояние xn остается ровно N-1 шаг. В силу нашего предположения для получаемого «укороченного» на 1 шаг процесса может быть вычислено оптимальное значение задачи — обозначим его через Ві(жі) и назовем условно-оптимальным, поскольку оно относится не ко всему процессу и зависит от выбора состояния xi. В соответствии с аддитивностью критерия для любого фиксированного управления щ наибольшее значение целевой функции Z всего ЛГ-шагового процесса будет равно

z\{xq,ux) + Bi(xi)

(частный экономический эффект на первом шаге плюс максимальный эффект на последующих N 1 шагах). Следовательно, для вычисления оптимального значения Z* всей задачи (обозначим его для единообразия, как и выше, через Bq(xq)) достаточно взять максимум от рассмотренной суммы по всевозможным управлениям и на первом шаге:

Z* = В0(х0) = max.{zi(x0,ui) + Bl(xi) xi = /(х0,щ)}.

Данное соотношение совпадает по форме с типовыми равенствами, полученными выше для случаев N = 2 и iV = 1; конечно, его можно было бы также получить путем строгих аналитических преобразований, аналогичных проведенным выше для случая N = 2. Следуя подобной методике, мы можем вычислить оптимальное значение задачи для любого многошагового процесса.

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

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