Динамическое программирование при математическом моделировании социально-экономических процессов.
Постановка задачи динамического программирования не имеет существенных отличий от общей постановки задачи математического программирования и выглядит следующим образом.
Пусть задан детерминированный процесс с конечной длительностью. Процесс (система) называется детерминированным, если значение состояния, в котором он находится в настоящем, достаточно для определения любого ее будущего состояния.
И пусть состояние системы в любой момент времени определяется вектором в фазовом пространстве системы. Преобразование состояния системы осуществляется
вектором управления , который определяется управляемой частью обобщенных координат.
Для любого состояния системы существует лишь ограниченное число векторов управления, которые будем называть допустимыми управлениями, или просто управлениями, если не будет надобности подчеркивать наличие ограничений.
Выбором соответствующего вектора управления мы преобразуем вектор
в нужном нам направлении, то есть меняем состояние системы. Годограф вектора состояния в пространстве состояний будем называть траекторией системы, а годограф вектора управления в пространстве управлений - программой управления.
Множество всех векторов состояний, образующих одну траекторию системы, когда система переходит из состояния
в состояние
будем обозначать через
. Подобным же образцом множества всех векторов управления, образующих одну программу управления, переводящую систему из состояния
, в состояние
будем обозначать через
. Обозначим также векторы начального и конечного состояний системы соответственно через
и
, а множество всех этих векторов через М(
) и М(
). Через букву М будем вообще обозначать любые допустимые множества. Допустимым состоянием будем считать состояние, в котором окажется система после выбора допустимого управления. Допустимая траектория - траектория, состоящая из допустимых состояний. Имея закон преобразования состояния системы
, можем записать:
=
(
;
), (4.1)
где - вектор функций
,
- начальный и конечный вектор управления.
Пусть задан критерий оценки процесса Ф, который представляет собой скаляр-
функцию, определенную на всем множестве траекторий системы M( ),
Ф=Ф[ ] (4.2)
Требуется, начиная процесс из какого-нибудь начального состояния системы
М(
), провести его так, чтобы заканчивать его некотором состоянии
М(
) и при этом достичь максимум (или минимум) значения Ф, определяемого выражением
М(
)
Ф=Ф[L{ ;
}] (4.3)
Траектория системы L{ ;
} при этом называется оптимальной траекторией.
Программа управления, реализующая оптимальную траекторию, называется оптимальной программой управления . В общем случае возможны несколько оптимальных траекторий и соответственно программ управления. Однако оптимальное значение критерия оценки всегда будет единственным.
По своей сути эти задачи принадлежат к классу вариационных. Но из-за наличия большого количества ограничений решение вариационным методом становится невозможным.
Для некоторого класса классических вариационных задач современного анализа Понтрягиым Л.С. и его учениками разработан специальный метод решения. Однако, преследуя цель показать идеи динамического программирования, не будем останавливаться на этом методе, называемом "принципом максимума".
Ограничимся дискретным вариантом метода.
Итак, будем предполагать, что параметры нашей системы дискретны и находятся в определенных пределах, т.е. множество всех состояний системы М( ) - конечно. Это касается и множества всех управлений.
Далее для удобства будем предполагать. Что система свое движение начинает всегда из единственного начального состояния ( ), т.е. М(
) состоит из одного элемента. Мы увидим в дальнейшем, что это ограничение не будет влиять на общность полученных результатов.
Как уже было сказано, из любого состояния выбранное управление переводит систему в новое состояние. Для нашего дискретного случая, это преобразование состояний происходит дискретно. Будем говорить, что из каждого состояния выбором управления система переходит в новое состояние на следующем этапе. Этапы будем нумеровать по количеству выбранных до этого состояния управлений. Иначе говоря, номер этапа совпадает с количеством элементов содержащихся во множестве . Здесь
- множество векторов управлений, переводящих систему из начального состояния
в состояние
по одной из допустимых траекторий. Из принятого определения этапа следует, что система во время одного цикла работы не может дважды оказаться на одном и том же этапе. Таким образом, из состояния
выбором какого-нибудь управления
система переходит в новое состояние
на первом этапе. Из этого состояния выбором управления
2 система переходит в состояние
на втором этапе. Или, в общем случае, выбором управления
i система переходит из состояния
i-1 в состояние
на i-ом этапе*
Если система двухмерная, то ее траектория может быть изображена графически, для 3-хмерных - трудно, больше трех - вообще невозможно.
На рис. 1 каждому этапу работы системы соответствуют вертикальные линии, которые рассматриваются по порядку возрастания номеров этапов, а каждому состоянию точки на этих линиях. Точки на каждой вертикали исчерпывают все возможные состояния системы на данном этапе. Это всегда возможно, ибо множество состояний М (Е) конечно.
![]() | ![]() | ||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | |||||||||||||||||||||
![]() | ![]() | ||||||||||||||||||||
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-82.gif)
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-83.gif)
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-84.gif)
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-85.gif)
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-86.gif)
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-87.gif)
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-88.gif)
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-89.gif)
Рисунок 1 - Фазовый портрет системы
Будем различать четыре вида состояний системы:
1. Начальное состояние - .
2. Промежуточное состояние системы - состояния, в которые система переходит из предыдущего этапа и из которого обязательно переходит в состояние следующего этапа.-
3. Конечное состояние - состояния, в которых система всегда заканчивает свою работу.
4. Переходные состояния - состояния, которые одновременно являются и промежуточными и начальными. Находясь в этом состоянии, система может продолжить работу (выбрать новый вектор управления) или закончить ее. На рис. 1 соединениям справа соответствуют допустимые управления, переводящие систему в состояние следующего этапа. Соединения слева - это пути (управления), которым можно попасть из предыдущего этапа в данное состояние.
Очевидно, что конечное состояние системы связано только слева, а начальное - только справа. В дальнейшем эти соединения будем называть периодами.
Процесс будет называться n-этапным, если максимальное количество этапов работы -n. На последнем этапе все состояния системы конечны. На остальных этапах возможны и конечные, и промежуточные, и переходные состояния системы.
Каждой траектории системы на фазовом портрете соответствует определенная ломаная линия. Эта ломаная линия состоит из, периодов и не может иметь петель.
Состояниям системы на фазовом портрете иногда будем приписывать двойные индексы вида, где i - номер этапа, a j -номер состояния этом этапе. В общем случае количество состояний на этапах не равны. Общее количество состояний определяется как
(4.4)
где mi - число состояний на i-ом этапе
n - число этапов.
При обозначении конкретного управления будем пользоваться тройной индексацией.
Так - управление, приводящее систему из j-ого состояния i-1 этапа в k-ое состояние i-го этапа, т.е.
.
Обозначим множество допустимых состояний i-го этапа через M(Ei). Множество допустимых управлений из состояния Ei через M( )
Далее нам понадобится одно важное допущение, а именно: система не обладает наследственностью, т.е. предыстория не влияет на будущее. Тогда, если , где
- закон преобразований состояний, то можно записать
, где
- двукратное применение преобразования. И вообще, несмотря на то, что система всегда начинает работу из состояния
, можно определить любое будущее состояние
, относительно некоторого состояние
, r - i - кратным применением преобразования
,
(4.5)
Кроме того, критерий оценки Ф тактов, что его приращение на переходах не зависит от предыдущих траекторий системы. Если обозначим приращение Ф через Ф, то можно записать:
Ф=Фi – Фi-1 (4.6)
, Фi-1 =
,
Согласно определению функция Ф такова, что не зависит от траектории
, а зависит лишь от
и
т.е.
(4.7)
Легко убедиться, что все аддитивные функции удовлетворяют этому требованию. В случае, когда функция ф для различных этапов не одинакова, выражение (4.7) примет вид:
(4.8)
В дальнейшем основные идеи динамического программирования будут проиллюстрированы на ряде специально подобранных типовых задачах.
Пусть дана система с начальным состоянием . Система дискретна с конечным множеством состояний М(
) . Все состояния системы , кроме состояний последнего этапа - промежуточные.
Максимальное число этапов - п (рис 1). Требуется найти оптимальную траекторию системы. Пусть критерий оценки системы Ф. Здесь и в дальнейших задачах для определенности будем предполагать, что оптимизация требует максимизации Ф. Обозначая оптимальные значения Ф через Фоп можно записать:
(4.9)
Это уравнение означает, что необходимо найти траекторию , максимизирующую Ф.
Дальнейшие рассуждения будут исходить из принципа оптимальности, который сформулирован Р. Беллманом, следующим образом:
"Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояние и решение в начальный момент, последующие решения должны составить оптимальное поведение относительно состояния, получающегося в результате первого решения ".
На рис. 4.2 показано поэтапное изменение дискретной функции Ф для трех различных траекторий системы.
|
|
|
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-125.gif)
Рис. 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(
) содержит т элементов, а множество
- mn-i элементов.
Пусть п=20; m=1O. Если для этого случая оптимизацию произвести простым перебором вариантов, то при отыскании оптимальной траектории из начального состояния системы (i=0) потребуется перебрать mn-1020 элементов множества , а с использованием уравнения (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), будем называть оцененным фазовым портретом.
|
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![Динамическое программирование при математическом моделировании социально-экономических процессов. Динамическое программирование при математическом моделировании социально-экономических процессов. - student2.ru](/images/matematika/dinamicheskoe-programmirovanie-pri-matematicheskom-modelirovanii-socialno-yekonomicheskikh-processov-400017-226.gif)
|
|
|
|
|
|
Рис. 4.4 Элемент оценного фазового портрета Рис. 4.5 Элемент полного фазового портрета
Если же для такого портрета определены также все значения функции Фоп(Е), то портрет будем называть полным фазовым портретом (рис. 4.5). При наличии полного фазового портрета уравнением (4.20) можно пользоваться как алгоритмом выбора оптимального управления из всех допустимых управлений.
Во всех вышеприведенных примерах предполагалось, что система начинает движение из единственного начального состояния. Когда система имеет несколько начальных состояний, необходимо все начальные состояния рассматривать как состояние первого этапа, на которые система может перейти из некоторого искусственного начального состояния с нулевыми переходами, т.е. с переходами, имеющими нулевые приращения критерия оценки. Однако, это лишь упрощает выкладки и на практике не обязательно применение искусственного начального состояния.
Можно руководствоваться простым правилом выбора того начального состояния, для которого функция Ф(Е) имеет наибольшее (наименьшее значение).
Рассмотрим некоторые примеры оптимизации с использованием динамического программирования. Пример 1.
Дан оцененный фазовый портрет системы (рис. 4.6). Требуется найти оптимальную траекторию системы. Задача заключается в максимизации некоторой функции Ф, значения приращений которой на переходах приведены на фазовом портрете. Если эта функция удовлетворяет требованию независимости приращений, то значения ее на любой траектории системы можно определить через приращения как Ф(
)=
.
Задача требует выбрать такую , при которой имело бы место:
где
Рис. 4.6 Оцененный фазовый портрет, к примеру, 1 (без цифр в кружочках)
Составим полный фазовый портрет системы. Пользуясь уравнением (4.21) находим значения функции Фоп для состояний предпоследнего - третьего этапа. Для состояния .
| |||||
![]() | ![]() | ||||
=9
Для состояний и
соответственно получим
Фоп( 23)=-4;Фоп(
33)=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