Имя материала: Динамическое программирование в экономических задачах

Автор: Лежнёв А. В.

1.3.    замечания по оптимизации многошаговых процессов

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

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

1J Термин «аддитивность» латинского происхождения означает свойство, имеющее отношение к операции сложения.

Наглядным примером может служить бег на длинную дистанцию, который никоим образом не сводится к многократному повторению бега на короткую дистанцию на максимальной скорости. Целевой функцией в данном примере является время пробегания всей дистанции, допустимым решением — тактика, позволяющая просто «добежать» до конца дистанции, оптимальным решением — тактика, позволяющая пробежать дистанцию за минимальное время.

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

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

m&x{a(t) + b(t)} < max{a(t)}.+ max{6(f)},

причем, вообще говоря, равенство может не иметь места. В качестве примера можно рассмотреть функции a(t) = t и b(t) = l — t, заданные при 0 з$ t < 1. При этом

a(t) + b(t) = 1,    max {a(t)} = 1,    max {b(t) = 1,

так что

max{o(t) + b{t)} = 1^2 = max{a(t)} + max{b(t)}.

Таким образом, максимум суммы двух или большего числа слагаемых нельзя вычислять по отдельности, а соответствующая задача максимизации является более сложной и требует более взвешенного подхода к ее решению. В то же время, если одна из функций является постоянной, например, a(t) = А, где А — некоторое число, то соответствующее равенство все-таки имеет место:

тах{А + b(t)} = А + max{b(t)};

t

иными словами, постоянное слагаемое можно выносить за знак максимума.

Аналогичное замечание можно сделать и относительно вычисления минимума:

min{a(i) + b(t)} ^ min{o(t)} + mm{b(t)}, тіп{А + b(t)} = A + mm{b(t)}.

Здесь уместно отметить связь между задачами на максимум и минимум: минимум функции F(t), заданной на некотором множестве Т, достигается в тех же точках, что и максимум функции —F(t), причем имеет место равенство

min{F(m = -max{-F(m.

Следовательно, задачу оптимизации многошагового процесса с поиском минимума целевой функции Z можно свести к подобной задаче оптимизации с поиском максимума целевой функции — Z; оптимальные решения при этом не изменятся, а оптимальное значение задачи изменит знак на противоположный.

Рассмотрим подробнее целевую функцию

Z = 2l(x0,Ul) + z2{xi,u2) + ... + ZN(XN-1,UN)

всего процесса и покажем, что она является функцией начального состояния xq и управляющих переменных ui, «2, • • • і ^iv- Действительно, в силу соотношения Х = fi{xQ,u) состояние х зависит ОТ Жо и щ. Далее, в силу соотношения х2 = /2(^1,^2) состояние х2 зависит от и2 и косвенно через посредство xi зависит ОТ xq И U, т. е.

Х2 = f2{fl(X0,U1),U2).

Рассуждая аналогично, получим наконец, что в силу соотношения xN — /лг(жлг-1,«лг) конечное состояние хдг системы зависит ОТ UN

и   КОСВеННО  Через  ПОСредСТВО  XN-1   ЗавИСИТ  ОТ  Х0   и  Itl, U2, . . . , UN-1-

Соответственно и целевая -функция Z зависит от хо и всех управляющих переменных:

Z = Z(Xq,Ui,U2, ... ,UN).

Если же в некоторых задачах начальное состояние х0 является фиксированным, то целевая функция зависит только от управляющих переменных.

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

вычислить частные производные целевой функции по всем переменным;

составить и решить систему уравнений для поиска тех точек, в которых возможен экстремум (они называются критическими точками);

проверить, в каких из найденных критических точек экстремум действительно существует, и вычислить его значение.

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

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

получаемые системы уравнений для поиска критических точек являются, как правило, нелинейными, и для их решения не существует универсальных методов;

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

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

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |