Оптимальное планирование капиталовложений на несколько лет

В разделе 2.4.1 мы рассмотрели задачу однократного принятия решений о распределении имеющегося ресурса (капитала). Часто возникают задачи принятия решений о распределении капитала в течение нескольких лет.

Пусть требуется спланировать деятельность двух предприятий П] и П2 в течение п лет. Средства X] и Х2, вложенные в каждое предприятие в начале года, в конце года приносят доход, который каждым предприятием делится на две части. Первые части в предприятия не вкладываются. Будем считать, что это расходы на нужды предприятий, не связанные с дальнейшим производством, и условно назовем их накоплениями. Накопления суммируются по двум предприятиям и по годам. А вторые части дохода от каждого предприятия также суммируются и заново распределяются между предприятиями на их дальнейшую деятельность.

В начале планируемого периода имеется Ki средств, все они вкладываются в предприятия (в том или ином соотношении). В начале второго года распределяется только та часть полученного дохода, которая вкладывается в предприятия, дополнительных средств не поступает, и так в начале каждого следующего года. Доход, полученный после n-го года, также делится на две части по тем же правилам, что и в предыдущие годы. Заданы функции, которые позволяют для каждого предприятия в зависимости от вложенных в него средств (Xj и Х2 соответственно) вычислить и часть дохода, идущего на накопление (d1(X1) и d2(X2) соответственно) и часть дохода, направляемую на распределение в начале следующего года (pi (Х[) и р22) соответственно). Другими словами, Х[ и Х2 — это то, что выдано каждому из предприятий в начале года, dj(Xi) + d2(X2) — это изымаемая часть дохода в конце года (накопления), a Pi(Xi) + р22) — это то, что будет заново распределяться в начале следующего года.

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

Рассмотрим конкретный пример.

Пусть

Итак, планируемый период составляет 5 лет, начальные распределяемые средства равны 10 единиц и в начале каждого следующего года распределяется 0,8Xi + 0,2Х2, где Xi и Х2 соответственно средства, вложенные в предприятия в истекшем году. Накопления за истекший год составляют

и их сумма за пять лет должна быть максимальна.

Задача естественным образом распадается на пять этапов по числу планируемых лет. На каждом этапе достаточно определить только X), т. е. средства вкладываемые в первое предприятие, так как сумма распределяемых средств известна.

«Состоянием системы» на каждом из этапов будем считать количество распределяемых средств. На первом этапе состояние задано и определяется числом 10. Обозначим через Kj средства, распределяемые на i-м шаге, т. е. в начале i-ro года, через Xj средства, вложенные в первое предприятие в i-м году (во второе предприятие вкладывается Kj — Xj), а через Dj накопления, которые получаются от использования К; в i-м году. В наших обозначениях на первом этапе X) = xi, Х2 = 10 — xj, на втором этапе X) = Х2, Х2 = К2 — Х2, ..., на пятом этапе Х = Х5, Х2 = К5 — Х5.

Состояние, в которое перейдет система после первого этапа, определяется как 0,8xi + 0,2(10 — х^, именно столько средств будет распределяться в начале второго года. И управлений х и соответственно состояний бесконечно много. Казалось бы, нужно ввести дискретность по Xi и перейти к конечному числу управлений и состояний, но это не обязательно, и мы этого делать не будем.

Рассмотрим последний пятый год. Накопления D5 зависят от распределяемых средств К5 и от того, как они распределяются, то есть от Х5. Используя (2.16), можно записать D5

Величина К5, характеризующая состояние системы на пятом этапе,неизвестна. Далее, Х5 — любое число на отрезке 0 < Х5 < К5. Выбор Х5 не зависит от того, как было получено состояние К5 (не влияет предыстория), и при заданном К5 Х5 надо выбрать так, чтобы накопления Оз(К5,Х5) были максимальны. Итак, нужен максимум по Х5 функции Х52 + 2(К5 — Х5)2 при условии 0 < Х5 < К5

Максимизируемая функция относительно Х5 при любом К5 представляет собой квадратный трехчлен с положительным первым коэффициентом при Х52. Ее максимум достигается в одной из крайних точек отрезка [0, К5], (а не при равенстве нулю производной по Х5, где функция имеет минимум). При Х5 = 0 значение функции равно 2К52, а при Х5 = К5 только К52. Отсюда следует что надо взять Х5 = 0 для любого состояния К5.

Переходим к четвертому этапу (году). Состояние системы определяется величиной К4 — распределяемыми средствами на четвертом этапе. Из этого состояния нужно дойти до конца и, в частности, перейти на пятый этап по оптимальной траектории, то есть так, чтобы были максимальны суммарные накопления на оставшихся (четвертый + пятый) этапах. Эти накопления составят

так как оптимальную

величину Х5 = 0, не зависящую от Х4, мы знаем. Ей соответствует D5 = 2К52. Переход от четвертого этапа к пятому определяется величиной Х4 — вложениями в первое предприятие на четвертом году. Во второе предприятие будет вложено К4 — Х4, и для величины К5 в соответствии с (2.16) получим

При любом К4 величину Х4 надо искать из условия

Это соответствует принципу оптимальности и представляет собой запись рекуррентного уравнения Р. Веллмана для нашей задачи применительно к четвертому этапу. Максимум этой функции может достигаться только в крайних точках отрезка [О, К4]. При Х4 = 0 имеем 2,08 К42, а при Х4 = К4 соответствующие суммарные накопления на двух последних этапах составят 2,28 К42. Поэтому выбираем Х4 = К4 при любом К4 и переходим к третьему этапу (году). Уравнение Р. Веллмана примет вид

I и, следовательно, Х3

должна быть точкой максимума для

при 0 < Х3 < К3. Аналогично четвертому этапу исследуем только значения Х3 = 0 и Х3 = К3

При Х3 = 0 имеем 2,0912Кз2, а при Х3 = К3 соответственно 2,4592 К32. Выбираем Х3 = К3 и при этом на трех последних этапах суммарные накопления будут составлять 2,4592 К32.

На втором этапе нужно найти Х2 из условия

Здесь и нам нужен

максимум

Максимум достигается при Х2 = К2 и примерно равен 2,57389К22.

Наконец, на первом шаге х надо выбрать из условия максимума

Но К! задано и равно 10. Поэтому нужен максимум

Этот максимум достигается при xi = 10. В результате суммарные накопления при оптимальном управлении ресурсами составят примерно 264,729. При этом первое предприятие получит по годам 10, 8, 6,4, 5.12, 0, а второе предприятие получит 0, 0, 0, 0, 4,096. Точно накопления составят 100 + 64 + 6,42 + 5,122 + + 2(4,096)2.

Полученный результат нельзя считать неожиданным. Действительно, при равных вложениях первое предприятие дает вдвое меньшие накопления, но вчетверо большие распределяемые средства (см. (2.16)). Естественно, что ему отдается приоритет в первые годы деятельности, чтобы обеспечить развитие производства и максимальные суммарные накопления за пять лет. В последний год нас интересуют только накопления, а не дальнейшая деятельность предприятий, поэтому все распределяемые средства отданы второму предприятию. Не случайно функции рДх) и Рг(х) никак не влияют на поиск величины Х5.

Может показаться, что такое распределение сохранится при неизменных функциях dt(x) = х2, d2(x) = 2х2 и при изменении коэффициентов в рДх), рг(х), сохраняющем условие рДх) > рг(х). Однако это не так.

Сохраняя di(x) = х2, d2(x) = 2х2, вместо рДх) = 0,8х, Рг(х) = 0,2х в (2.4) возьмем рДх) = 0,75х, рг(х) = 0,3х и тот же начальный капитал Ki Очевидно, Х5 = 0. Для четвертого этапа имеем теперь

При Х4 = 0 суммарные накопления за два последних года составят 2,18 К42, а при Х4 = К4 только 2,125 К42 и поэтому выбирать нужно Х4 = 0, а не Х4 = К4, как было при коэффициентах 0,8 и 0,2.

Данный пример демонстрирует применение метода динамического программирования не при дискретном, а при непрерывном изменении параметров состояния системы и сведении рекуррентного уравнения Р. Веллмана к задаче поиска максимума квадратичной функции. При более сложных функциях dj(Xj) и d2(X2), Pi(Xi) и Р2(Х2) получаются более сложные уравнения Р. Веллмана и на каждом шаге возникает задача поиска максимума функции более сложной, чем квадратическая. Максимум может быть в точке равенства нулю производной или в одной из крайних точек интервала поиска. Условие равенства нулю производной приводит к уравнению относительно неизвестного управления при заданном начальном состоянии. Так на самом простом пятом шаге нужен max D55, Х5) по Х5 при 0 < Х5 < К5. Если не удается доказать, что максимум достигается в одной из крайних точек (0 или К5) и уравнение 9D5 (К5, Х5)/Эх5 = 0 не удается решить аналитически, то есть получить Х5* как функцию К5, то его приходится решать численно. Затем при поиске Х4* приходится рассматривать различные значения К5, каждому из которых соответствует свое значение накоплений на последнем шаге, которые нам не удалось выразить как функцию К5 и потом перейти к Х4 и т. д. При переходе к численной реализации метода Р. Веллмана приходится решать задачу «от начала к концу», так как интервал значений Кп мы не знаем. Это еще раз опровергает ставшее стереотипным умозаключение: «в любой задаче динамического программирования «начало» и «конец» можно поменять местами» [4, 5].

В рассматриваемой задаче нет необходимости разбивать регулярную сетку состояний на каждом шаге, иначе пришлось бы решать уравнения для определения х, при заданном состоянии, в которое «система переходит под управлением хр>. Вместо этого следует начиная с первого шага рассмотреть с заданным дискретом все значения на отрезке 0 < Xi < Kj, для каждого из них вычислить новое состояние и его оценку, то есть соответственно распределяемые средства по итогам первого года Pi(xi) + P2(Kj — xj) и накопления первого года di(xi) + d2(Kj — Xi). Затем для каждого из полученных состояний перебирать Х2, вычислять новые состояния, их оценки (суммарные накопления за два года) и запоминать связь с состоянием предшествующего шага (откуда пришли и с каким Х2, чтобы не вычислять Х2 в дальнейшем при восстановлении траектории) и т. д. На каждом шаге, начиная со второго, при вычислении нового состояния необходимо проверять, было ли оно уже вычислено, и если да, то запоминать только наилучшую оценку (суммарные накопления) и соответствующую связь в полном соответствии с принципом Р. Веллмана. Характерно, что при нелинейных функциях Pi(x) + рг(х) состояния не располагаются в узлах регулярной сетки и отбраковка путей может происходить крайне редко, а число состояний может быстро расти. В итоге без округлений можно практически придти к почти полному перебору всех путей, что при малом дискрете и большом числе шагов может вызвать вычислительные трудности. К счастью, и в подобного рода задачах эффективным оказывается динамическое программирование на множествах Парето, то есть возможность на каждом шаге исключать не только неэффективные пути достижения некоторого состояния, но и сами неэффективные состояния вместе с их продолжениями.

Продемонстрируем эти возможности на уже решенной задаче с исходными данными: п = 5, К] = 10, ф(х) = х2, Й2(х) = 2х2, Pi(x) = 0,8х, р2(х) = 0,2х.

На первом шаге состояние, зависящее от Х[, определяется как а его оценка

Графики функций Si(xj) и Di (xj) представлены на рис. 2.27

Графики функций первого шага S/(xi) и Dj(xj)

Рис. 2.27. Графики функций первого шага S/(xi) и Dj(xj)

Уже после первого шага выясняется, что все точки (состояния, получаемые при соответствующем выборе Х() для 10/3 < х < 10 могут быть исключены как неэффективные, так как выбор х = 10 дает большие распределяемые средства Si и большие накопления по итогам первого года. Далее следует рассматривать только продолжения состояний, получаемых при 0 < Х) < 10/3 и Х) = 10.

На дальнейших шагах также будет происходить отбраковка состояний и вплоть до последнего шага будет оставаться состояние, порождаемое максимально возможными Х2, хз и Х4, что соответствует передаче всех распределяемых средств первому предприятию. На последнем шаге, когда нет надобности думать о дальнейших распределяемых средствах, окажется выгоднее Х5 = 0.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >