Динамическое программирование при математическом моделировании социально-экономических процессов.

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

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

И пусть состояние системы в любой момент времени определяется вектором в фазовом пространстве системы. Преобразование состояния системы осуществляется

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

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

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

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

= ( ; ), (4.1)

где - вектор функций

, - начальный и конечный вектор управления.

Пусть задан критерий оценки процесса Ф, который представляет собой скаляр-

функцию, определенную на всем множестве траекторий системы M( ),

Ф=Ф[ ] (4.2)

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

М( ), провести его так, чтобы заканчивать его некотором состоянии М( ) и при этом достичь максимум (или минимум) значения Ф, определяемого выражением М( )

Ф=Ф[L{ ; }] (4.3)

Траектория системы L{ ; } при этом называется оптимальной траекторией.

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

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

Для некоторого класса классических вариационных задач современного анализа Понтрягиым Л.С. и его учениками разработан специальный метод решения. Однако, преследуя цель показать идеи динамического программирования, не будем останавливаться на этом методе, назы­ваемом "принципом максимума".

Ограничимся дискретным вариантом метода.

Итак, будем предполагать, что параметры нашей системы дискретны и находятся в определенных пределах, т.е. множество всех состояний системы М( ) - конечно. Это касается и множества всех управлений.

Далее для удобства будем предполагать. Что система свое движение начинает все­гда из единственного начального состояния ( ), т.е. М( ) состоит из одного элемента. Мы увидим в дальнейшем, что это ограничение не будет влиять на общность полученных результатов.

Как уже было сказано, из любого состояния выбранное управление переводит систему в новое состояние. Для нашего дискретного случая, это преобразование состояний происхо­дит дискретно. Будем говорить, что из каждого состояния выбором управления система переходит в новое состояние на следующем этапе. Этапы будем нумеровать по количеству выбранных до этого состояния управлений. Иначе говоря, номер этапа совпадает с количе­ством элементов содержащихся во множестве . Здесь - множество векторов управлений, переводящих систему из начального состояния в состояние по одной из допустимых траекторий. Из принятого определения этапа следует, что система во время одного цикла работы не может дважды оказаться на одном и том же этапе. Та­ким образом, из состояния выбором какого-нибудь управления система переходит в новое состояние на первом этапе. Из этого состояния выбором управления ₂ система переходит в состояние на втором этапе. Или, в общем случае, выбором управления _i система переходит из состояния _i-1 в состояние на i-ом этапе*

Если система двухмерная, то ее траектория может быть изображена графически, для 3-хмерных - трудно, больше трех - вообще невозможно.

На рис. 1 каждому этапу работы системы соответствуют вертикальные линии, которые рассматриваются по порядку возрастания номеров этапов, а каждому состоянию точки на этих линиях. Точки на каждой вертикали исчерпывают все возможные состояния системы на данном этапе. Это всегда возможно, ибо множество состояний М (Е) конеч­но.

Рисунок 1 - Фазовый портрет системы

Будем различать четыре вида состояний системы:

1. Начальное состояние - .

2. Промежуточное состояние системы - состояния, в которые система переходит из пре­дыдущего этапа и из которого обязательно переходит в состояние следующего этапа.-

3. Конечное состояние - состояния, в которых система всегда заканчивает свою рабо­ту.

4. Переходные состояния - состояния, которые одновременно являются и промежуточны­ми и начальными. Находясь в этом состоянии, система может продолжить работу (выбрать новый вектор управления) или закончить ее. На рис. 1 соединениям справа со­ответствуют допустимые управления, переводящие систему в состояние следующего этапа. Соединения слева - это пути (управления), которым можно попасть из предыду­щего этапа в данное состояние.

Очевидно, что конечное состояние системы связано только слева, а начальное - только справа. В дальнейшем эти соединения будем называть периодами.

Процесс будет называться n-этапным, если максимальное количество этапов рабо­ты -n. На последнем этапе все состояния системы конечны. На остальных этапах возможны и конечные, и промежуточ­ные, и переходные состояния системы.

Каждой траектории системы на фазовом портрете соответствует определенная ломаная линия. Эта ломаная линия состоит из, периодов и не может иметь петель.

Состояниям системы на фазовом портрете иногда будем приписывать двойные ин­дексы вида, где i - номер этапа, a j -номер состояния этом этапе. В общем случае ко­личество состояний на этапах не равны. Общее количество состояний определяется как

(4.4)

где m_i - число состояний на i-ом этапе

n - число этапов.

При обозначении конкретного управления будем пользоваться тройной индексацией.

Так - управление, приводящее систему из j-ого состояния i-1 этапа в k-ое состояние i-го этапа, т.е. .

Обозначим множество допустимых состояний i-го этапа через M(E_i). Множество допустимых управлений из состояния E_i через M( )

Далее нам понадобится одно важное допущение, а именно: система не обладает на­следственностью, т.е. предыстория не влияет на будущее. Тогда, если , где - закон преобразований состояний, то можно записать , где - двукратное применение преоб­разования. И вообще, несмотря на то, что система всегда начинает работу из состоя­ния , можно определить любое будущее состояние , относительно некоторого состояние , r - i - кратным применением преобразования ,

(4.5)

Кроме того, критерий оценки Ф тактов, что его приращение на переходах не зави­сит от предыдущих траекторий системы. Если обозначим приращение Ф через Ф, то можно записать:

Ф=Ф_i – Ф_i-1 (4.6)

, Ф_i-1 = _,

Согласно определению функция Ф такова, что не зависит от траектории

, а зависит лишь от и т.е.

(4.7)

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

(4.8)

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

Пусть дана система с начальным состоянием . Система дискретна с конечным множеством состояний М( ) . Все состояния системы , кроме состояний последнего эта­па - промежуточные.

Максимальное число этапов - п (рис 1). Требуется найти оптимальную траекторию сис­темы. Пусть критерий оценки системы Ф. Здесь и в дальнейших задачах для определенно­сти будем предполагать, что оптимизация требует максимизации Ф. Обозначая опти­мальные значения Ф через Ф_оп можно записать:

(4.9)

Это уравнение означает, что необходимо найти траекторию , максимизирующую Ф.

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

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

На рис. 4.2 показано поэтапное изменение дискретной функции Ф для трех различ­ных траекторий системы.

Рис. 4.2 График поэтапного изменения критерия оценки Ф.

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

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

(4.10)

где

Предположим далее, что система находится в состоянии и уже выработано зна­чение критерия оценки, равное Ф=Ф[ ]

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

(4.11)

Но так как в состоянии , не зависит от , то максимиза­ция правой части (4.11) по всем равносильна максимизации только по можно представить так:

= (4.12)

Эта задана аналогична задаче (4.9), лиши с тои ризницей, что исходным состоянием является состояние , а число этапов n-i. Такая идентичность ситуаций позволяет пред­положить, что закон нахождения оптимальных управлений из каждого состояния не дол­жен зависеть от состояния, в котором система находится. Следовательно, можно продолжить рассуждения для выбранного произвольного состояния . Значение можно представить как сумму приращений критерия оценки на переходе из состояния . и дальнейшего роста критерия оценки (рис. 4.1)

(4.13)

Для максимизации (4.13) нельзя руководствоваться стремлением вы­брать такое управление при котором приращение принимает наибольшее зна­чение, т.к. второе слагаемое в выражении (4.13) есть значение критерия оценки на траектории , начало которой состояние - результат этого управления. Однако, в какое бы состояние не пребыла система выбором управления дальнейшее управление также должно быть оптимальным. Следовательно, каждому состоянию , в которое может прийти система из состояния соответствует одно единственное значение кри­терия оценки Ф, определенном на оптимальном продолжении траектории, а именно,

= (4.14)

Отметим, что значение при неизменном фазовом портрете зависит только от состояния, в котором система находится. Это очень важное обстоятельство и оно выте­кает из принципа оптимальности, являющимся прямым следствием того, что система не обладает наследственностью, а критерий оценки имеет независимые приращения на пе­риодах. Значит, предполагая, что система находится в состоянии и что из любого со­стояния следующего этапа управление будет оптимальным, выражение (4.13) с учетом (4.7) можно представить в виде:

(4.15)

В уравнении (4.15) для состояния зависит только от управления , а Ф - только от состояния , в которое система перейдет из состояния выбором управле­ния . Выражая через и из (4.15), получим:

(4.16)

Здесь является единственным переменным и максимум можно искать не по всем , а только по всем .

Следовательно, требование (4.14) можно переписать в виде:

(4.17)

M( )

Преимущество (4.17) относительно (4.14) заключается в том, что количество эле­ментов во множестве M( ) намного меньше, чем во множестве , и эта разница тем больше, чем меньше номер этапа, на котором находится система. Например, если на каждом этапе система имеет т состояний и из всех состояний этапа можно пе­рейти в любое состояние следующего этапа, то на i-ом этапе системе предстоит пройти еще n-i этапов и множество M( ) содержит т элементов, а множество - m^n-i элементов.

Пусть п=20; m=1O. Если для этого случая оптимизацию произвести простым пере­бором вариантов, то при отыскании оптимальной траектории из начального состояния системы (i=0) потребуется перебрать mⁿ-10²⁰ элементов множества , а с использованием уравнения (4.17) всего лишь m(N-m)=m(mn+I- т)=1910 10^го. Здесь N=m-n+1 - ко­личество элементов во множестве М(Е). Это огромная количественная разница и превращается в качественное достоинство метод динамического программирования.

Уравнение (4.17) является основным уравнением динамического программирования. Оно позволяет из произвольного состояния любого этапа найти оптимальное управление системой.

Для начального состояния будем иметь:

(4.18)

или иначе

(4.19)

Предполагая известными значения Ф_оп( ) для всех ( ), не трудно хотя бы

простым перебором найти M( ), при котором имеет место Ф_оп( ). Результат этого выбора будет оптимальным согласно принципу оптимальности. Но он обеспечит достижение максимума критерия оценки , если траектория из состояния , в котором

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

Естественно, возникает вопрос: как определить значение Ф_оп( ). Действительно в уравнении (4.19) определение Ф_оп( ) задача такай же трудности, как и определение самой Ф_оп( ). Однако, как мы увидим ниже, эта трудность лишь кажущаяся. Предположим, что известны значения Ф_оп( ) для всех состояний i+1-го этапа системы. Тогда при по­мощи уравнения (4.17), которое удобно представить в виде:

(4.20)

можно определить значение Ф( ) для всех состояний i-го этапа аналогично можно определить Зисл значил дал всех и т.д. вплоть до состояния . Для того, чтобы начать эту процедуру с п-1-ого этапа необходимы зна­чения , которые для системы заведомо известны: =0 для всех . Следовательно, уравнения последнего этапа будет иметь вид:

(4.21)

т.е. на последнем этапе следует выбрать управление, при котором приращение имеет наибольшее значение. Каждому переходу на фазовом портрете системы (рис 4.1) удобно приписывать соответствующие значения приращения критерия оценки, а каждой точке соответствующие значения функции Ф_оп

Фазовый портрет, на котором написаны значения приращений критерия оценки (рис. 4.4), будем называть оцененным фазовым портретом.

k(i+1)

ji

k(i+1)

ji

Рис. 4.4 Элемент оценного фазового портрета Рис. 4.5 Элемент полного фазового портрета

Если же для такого портрета определены также все значения функции Ф_оп(Е), то портрет будем называть полным фазовым портретом (рис. 4.5). При наличии полного фа­зового портрета уравнением (4.20) можно пользоваться как алгоритмом выбора опти­мального управления из всех допустимых управлений.

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

Можно руководствоваться простым правилом выбора того начального состояния, для которого функция Ф(Е) имеет наибольшее (наименьшее значение).

Рассмотрим некоторые примеры оптимизации с использованием динамического про­граммирования. Пример 1.

Дан оцененный фазовый портрет системы (рис. 4.6). Требуется найти оптимальную траекторию системы. Задача заключается в максимизации некоторой функции Ф, значения приращений которой на переходах приведены на фазовом портрете. Если эта функция удовлетворяет требованию независимости приращений, то значения ее на любой траектории системы можно определить через приращения как Ф( )= .

Задача требует выбрать такую , при которой имело бы место:

где

Рис. 4.6 Оцененный фазовый портрет, к примеру, 1 (без цифр в кружочках)

Составим полный фазовый портрет системы. Пользуясь уравнением (4.21) находим значения функции Ф_оп для состояний предпоследнего - третьего этапа. Для состояния .

		-12

=9

Для состояний и соответственно получим

Ф_оп( ₂₃)=-4;Ф_оп( ₃₃)=14.

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

Ф_оп( )=12+9=21

Для состояний , и имеем:

=2

Здесь Ф( )=17 соответствует как переходу в состояние , так и в состоянии

. Находясь в состоянии с точки зрения выбранного критерия оптимальности без­различно, каким из этих двух переходов осуществлено движение системы. Любое из них по отношению к состоянию будет оптимальным. Таким образом, система будет иметь две оптимальные траектории. Возможно и большее число оптимальных траекторий сис­темы. В таких случаях можно ориентироваться дополнительными условиями, которые не учтены в задаче. Например, желательно, чтобы какой-нибудь параметр системы находился как можно ближе к своему низшему пределу. В таком случае из эквивалентных оп­тимальных переходов выбирается тот, который удовлетворяет этому дополнительному требованию.

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

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

Оптимальная траектории из состояния будет L{ ; ; ; ; }, а мак­симальное значение функции Ф при этом движении будет Ф_оп( )=mах Ф[L{ ; }]=max

Если система каким-либо образом оказалась в состоянии, находящемся не на оптимальной траектории, например в , то дальнейшее предложение траектории также находится из уравнения (4.20).

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

В этих случаях выбор нового управления также осуществляется с помощью уравне­ний (4.20) или (4.17).

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

Пусть такие данные имеются по четырем фондам и представлены следующей таб­лицей 4.1.

Таблица 1

Вложения (в млн. д.е.)	Прибыль
I	I I	I I I	Iv
	0,28	0,25	0,15	0,2
	0,45	0,41	0,25	0,33
	0,65	0,55	0,4	0,42
	0,78	0,65	0,5	0,48
	0,9	0,75	0,62	0,53
	1,02	0,8	0,73	0,56
	1,13	0,85	0,82	0,58
	1,23	0,88	0,9	0,6
	1,32	0,9	0,96	0,6
	1,38	0,9	1,00	0,6

Следует подчеркнуть, что нахождение таких данных является не очень простой зада­чей.

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

(10, 0, 0, 0); (9, 1, 0, 0); (9, 0, 1, 0);...;

(8, 1, 1, 0); (8, 1, 0, 1); (8, 0, 1, 1);...;

(8, 0, 2, 0); (8, 0, 0, 2); (7, 1, 1, 1);...;

(4, 3,2, 1);...(4, 2, 2, 2);...

Всего надо вычислить 286 чисел!

Это еще вполне терпимо; но так как группа, распределяющая финансы, обнаруживается также желание знать оптимальное решение в спросе, когда капиталовложения в целом составили бы 9, 8, 7, ... ,2 или 1 миллион денежных единиц, то перед нами оказывается вычислительная работа большого объема, на которую потребовалось бы много рабочих дней.

Рассмотрим решение этой задачи методом динамического программирования.

Введем следующие обозначения.

f1 (х) - функция соответствующая I фонду,

f2 (х) - функция соответствующая II фонду,

f3 (х) - функция соответствующая III фонду,

f4 (х) - функция соответствующая IV фонду;

Далее:

F1,2 (А ) - оптимальное распределение, когда А млн. д. ед. вкладываются в I и II фонды

вместе:

F1,2,3 (А) - оптимальное распределение, когда А млн. д. ед. вкладываются в l, II и

III фонды вместе

F1,2,3,4 (А) - оптимальное распределение, когда А млн. д. ед. вкладываются в I, II,

III и IV фонды вместе.

Таким образом, чтобы определить F1,2(2), надо вычислить

f1 (0) + f2 (2) = 0,00 + 0,41 = 0,41

f1 (1) +f2 (1) = 0,28+0,25 = 0,53

f1 (2) +f2 (0) = 0,45 + 0,00 = 0,45

Тогда оптимальное значение будет

F1,2 = 0,53

Вычислим таким способом значения

F1,2 (0), F1,2(1), F1,2 (2), ... ,F1,2 (9), F1,2(10)

Вычислим, используя формулу Беллмана

F1,2 (А) = тах(f1(х) +f(A-х)) Получим следующую таблицу 4.2.

Оптимальная политика вложения денежных средств в I и II фонды.

Таблица 2

Вложения (в млн. д.е.)	f1(x)	f2(x)	F1,2(A)	оптимизационная политика предприятий при вложении в фондыIиII
				(0, 0)
	0,28	0,25	0,28	(1, 0)
	0,45	0,41	0,53	(1, 1)
	0,65	0,55	0,7	(2, 1)
	0,78	0,65	0,9	(3, 1)
	0,9	0,75	1,06	(3, 2)
	1,02	0,8	1,2	(3, 3)
	1,13	0,85	1,33	(4, 3)
	1,23	0,88	1,45	(5, 3)
	1,32	0,9	1,57	(6, 3)
	1,38	0,9	1,68	(7, 3)

Таблица (4.2) позволяет отразить политики, соответствующие оптимальному доходу при данном капиталовложении. Например, если в I и II фонды вложены 4млн. д. ед., то в фонд I надо вложить 3 млн. д. ед., а в фонд II - 1 млн. д. ед.: именно это и обозначает символ ( 3, 1) в пятом столбце; прибыль в этом случае ровно 0,9 млн. д.е. Аналогичное исследование можно продолжить вычислением F1,2,3 (А ), т.е. поиском оптимальной комбинации, когда капитал А вкладывают в фонды I, II и III, используя рекуррентное соотношение: F1,2,3 (А) = тах(F1,2 (х) +f3(А-х))

Таблица 3

Вложения (в млн. д.е.)	F1,2(A)	f3(x)	F1,2,3(A)	оптимизационная политика вложения в фонды
				(0, 0)	(0, 0, 0)
	0,28	0,15	0,28	(1, 0)	(1, 0, 0)
	0,53	0,25	0,53	(1, 1)	(1, 1, 0)
	0,7	0,4	0,7	(2, 1)	(2, 1, 0)
	0,9	0,5	0,9	(3, 1)	(3, 1, 0)
	1,06	0,62	1,06	(3, 2)	(3, 2, 0)
	1,2	0,73	1,21	(3, 3)	(3, 2, 1)
	1,33	0,82	1,35	(4, 3)	(3, 3, 1)
	1,45	0,9	1,48	(5, 3)	(4, 3, 1)
	1,57	0,96	1,6	(6, 3)	(5, 3, 1) или (3, 3, 3)
	1,68		1,73	(7, 3)	(4, 3, 3)

Из таблицы 3 видим, что, вложив 10 млн. д. ед., следуя политике (4, 3, 3) при­быль будет оптимальной и составит 1,73 млн. д. ед. Продолжая вычисления, можем определить. F1,2,3,4 (A)=max (F1,2,3 (x)+f4(A-x), а результаты представим таблицей (4.5)

Таблица 4