Математическая экономика

12.y = x1x2 + x2 x3 при условиях x1 + x2 = 4 , x2 +x3 = 4 .

13.y =3x12 + 2x1 + 2x22 + 4x2 x3 при условиях x12 + 2x22 =19 ,

x1 + 2x2 x3 =11.

14. y = x1x2 x2 при условиях 2x1x2 + x2 x3 =12 , 2x1 − x2 =8.

15.y = x1 − 2x2 + 2x3 при условии x12 + x22 + x33 =9.

16.y = x1x2 при условии x12 + x22 ≤1.

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

−равномерного пассивного поиска;

−метода дихотомии;

−метода золотого сечения;

−метода Ньютона;

−квадратичной аппроксимации.

21.y =1 − xe−x .

22.y = 12 x2 + e−x .

23.y = (x −1)e−x2 .

25.y = 4 −10x + 2x2 − 0,1x3 .

26.y =1−e−x ln x .

27.y = 2 −3x + x3 .

28.y = −1 + e−2x cos x .

161

Указанное выше задание выполнить для следующих функций двух переменных, используя методы [37]:

−Ньютона – Рафсона;

−градиентного спуска с дроблением шага;

−Флетчера – Ривса;

−покоординатной оптимизации (Гаусса – Зайделя);

−Нелдера – Мида;

−Хука – Дживса;

−Давидона – Флетчера – Пауэлла.

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

31.y = (x1 − 4)2 + 14 (x2 − 7)2 .

32.y = 4x12 + 3x22 − 4x1x2 + x1 .

33.y =8x12 + 4x1x2 + 5x22 .

34.y = (x2 − x12 )2 + (1 − x1 )2 .

35.y =100(x2 − x12 )2 + (1 − x1 )2 .

36.y = 2x13 + 4x1x23 −10x1x2 + x22 .

u3 = 2,625 − x1 (1 − x2 )3 .

162

Глава 6. ЗАДАЧИ ОПТИМАЛЬНОГО ДИНАМИЧЕСКОГО

УПРАВЛЕНИЯ И ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

§ 6.1. Понятие об управляемых динамических системах

Рассмотрим некоторую систему любой природы. Это может быть техническая система, например самолет, экономическая система, например производственное предприятие и т.п. Будем считать, что ее поведение можно характеризовать некоторым набором величин и обозначим их s1,... , sm . Они описывают состояние системы, поэтому будем называть их

переменными состояния.

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

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

Система называется статической, если xi , si – постоянные величи-

ны (числа). Если же они изменяются во времени и описываются функциями времени xi = xi (t), si = si (t) , то система называется динамической.

Обычно поведение системы рассматривается на некотором промежутке времени [tн, tк]. Если при этом время непрерывно изменяется от начального момента до конечного, пробегая все возможные значения, то процессы x(t) , s(t) и система называются непрерывными. Существует не-

163

мало систем, в том числе экономических, в которых процессы рассматриваются, контролируются или изменяются в отдельные изолированные моменты времени {t0 =tн, t1, t2,...,tк}. Такие процессы и системы называют

дискретными. Обычно эти моменты следуют друг за другом через одинаковый промежуток времени T , называемый периодом дискретизации, или шагом по времени. Тогда ti =tн +iT , при этом i называют номером такта,

шага или этапа.

Будем рассматривать детерминированные системы, для которых, задав некоторое конкретное управление x(t) и начальное состояние

s (tн) = s (0) , мы получим однозначно определенный закон изменения вектора переменных состояния s = s(t) .

При этом следует иметь в виду, что не все реальные системы, с которыми приходится иметь дело на практике, в том числе в экономике, можно считать детерминированными. Часто на поведение системы помимо целенаправленно формируемых управлений x(t) действуют неподвластные

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

зывают системами с неопределенностями, или стохастическими систе-

мами.

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

§ 6.2. Формулировка классической задачи об оптимальном динамическом управлении

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

164

ных xi = xi (t) , при которых рассматриваемая система переходит из заданного начального состояния в заданное конечное состояние:

Оказывается, эта задача, как правило, имеет не единственное реше-

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

где Y – число, оценивающее эффективность или качество процесса управления, F – правило, по которому оно определяется.

В связи с этим дополнительно к задаче управления (6.1), которую можно считать основной, ставится новая задача, которую можно рассматривать как «сверхзадачу»: из множества возможных управлений x = x(t) , обеспечивающих выполнение условия (6.1), найти такое управление, при котором получается наибольшее (или наименьшее) значение показателя качества (6.2):

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

a j ≤ x j ≤bj .

Обычно они задают ограничения на ресурсы. В общем случае эти ограничения можно представить следующим образом:

где Ωx , Ωs – область допустимых значений в пространстве управлений и пространстве состояний.

Управление заданной системой x(t) = x* (t), обеспечивающее выполнение условий (6.1) – (6.4) называется оптимальным, а показатель качества (6.2) называется критерием оптимальности. Заметим, что соотношение (6.2) функциям x(t), s(t) ставит в соответствие число Y и представляет собой функционал. Это соотношение является аналогом целевой функции y = f (x) в задачах статической оптимизации.

165

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

Ясно, что таких линий существует бесконечное множество. Дополнительно можно потребовать, чтобы сформированная траектория позволя-

выбранного управления x(t) и заданного начального условия s(0) находить переменные состояния:

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

управляющих факторов x(t) = x* (t) , при котором система переходит из за-

данного начального состояния в заданное конечное состояние (6.1), а показатель качества (6.2) принимает наибольшее (наименьшее) значение, при этом соблюдаются ограничения (6.4).

Следует отметить, что задача об отыскании функций x(t) , при кото-

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

166

и др. В их трудах были заложены основы специального раздела математики, который называется вариационным исчислением [4, 17, 30, 34].

Специфика задач управления оказалась довольно существенной и потребовала использования специального математического аппарата, который был разработан во второй половине ХХ в. в СССР (принцип максимума Л.С. Понтрягина [4]) и в США (динамическое программирование Р. Беллмана [6, 30, 32]). Впоследствии оказалось, что они во многом близки. Однако детальное их изучение и опыт их использования показали, что принцип максимума (ПМ) лучше приспособлен для решения задач непрерывного динамического управления, а динамическим программированием (ДП) целесообразнее пользоваться для решения задач управления дискретными системами.

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

§ 6.3. Формулировка классической задачи динамического программирования (ДП)

Рассмотрим задачу (6.1) – (6.5) об оптимальном управлении некоторой, например экономической, системой, предполагая, что она является детерминированной, динамической и дискретной, т.е. процессы в ней изменяются во времени и эти изменения происходят по шагам.

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

1. Система описывается m переменными состояния ( s1,..., sm ), и ее

функционирование осуществляется по этапам. Будем считать, что управление состоит из n шагов, причем на i -м шаге система под действием управления u (i) переходит из состояния s(i −1) в следующее состояние

s(i) (рис. 6.3).

Рис. 6.3

2. Свойства системы таковы, что для выбранных переменных состояния ее математическая модель (6.5) может быть представлена в виде

167

где Gi – некоторый оператор.

Это соотношение отражает принципиально важное для ДП свойство системы – ее новое состояние s(i) зависит от текущего управления, реали-

зуемого на текущем этапе, и предшествующего состояния s(i −1) и не за-

висит от того, каким образом система пришла в это состояние. Это свойство называется отсутствием последействия [13].

3. Показатель качества управления Y , например доход предприятия, полученный на всем промежутке времени за все n этапов, складывается из оценок качества управления yi на отдельных этапах:

где fi – функция, определяющая показатель качества, например доход, на i -м этапе по состоянию системы s(i −1) в начале этапа и реализованному на этом этапе управлению x(i) . Это свойство называется аддитивностью

критерия качества.

Задача ДП состоит в том, чтобы для каждого этапа (шага) найти значения управляющих факторов x(1),..., x(n) , при которых система из задан-

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

Эта задача – классическая (стандартная) задача динамического программирования, хотя лучше было бы назвать ее задачей многоэтапного планирования, поскольку, как уже отмечалось ранее, термин «программирование» известен в ином более употребительном значении.

§ 6.4. Принцип оптимальности Р. Беллмана

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

168

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

Эту же идею можно сформулировать несколько иначе – каково бы ни было состояние s системы в результате какого-то числа шагов, необходимо выбирать управление на ближайшем шаге так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному эффекту на всех оставшихся шагах, включая данный [6].

Этот принцип может показаться довольно простым и даже очевидным. Хотя это вовсе не так. Проиллюстрируем эту ситуацию на примере [13]. Дана транспортная сеть (рис. 6.4) с начальным пунктом А, конечным пунктом В и промежуточными пунктами А1, А2, …, которые соединены транспортными магистралями, длины которых заданы и отмечены. Требуется выбрать оптимальный (наикратчайший) путь из А в В. Эту задачу можно представить как задачу поэтапного выбора 1-го, 2-го, … участков искомого маршрута. Эта задача рассматривалась в § 4.2, там же был изложен метод отыскания кратчайшего пути.

Рис. 6.4

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

169

следующую соседнюю (смежную) точку, не заглядывая вперед, то получится маршрут A0 , A1, A3 , A2 , A4 , B , имеющий длину 34 ед. Этот маршрут не

является оптимальным. Нетрудно найти путь с меньшей длиной, например A0 , A3 , A4 , B с длиной 25, хотя и он не является кратчайшим.

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

Может показаться, что изложенный выше принцип оптимальности носит слишком общий, быть может, философский характер, и исходя из него вряд ли удастся сформулировать вычислительный алгоритм. Однако это не так. Как отмечается в [12], заслуга Р. Беллмана состоит не только в том, что он в своих основополагающих работах сформулировал этот принцип. Главное состоит в том, что Р. Беллман разработал концепцию практического использования принципа оптимальности для организации вычислительного процесса и «с удивительной изобретательностью стал применять его буквально к сотням оптимизационных задач, возникающих в математике, технике, экономике, исследовании операций и других областях знаний» [12].

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

§ 6.5. Сущность метода ДП

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

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

170