7. РАСПРЕДЕЛЕНИЕ РЕСУРСОВ СО ВЛОЖЕНИЕМ ДОХОДОВ В ПРОИЗВОДСТВО

До сих пор в задачах о распределении ресурсов мы рассматривали «доход», приносимый предприятиями, совершенно независимо от распределяемых средств; он даже мог выражаться в других единицах (например, ресурсы — в человеко-часах, а доход — в рублях). Теперь мы рассмотрим случай, когда доход вкладывается в производство (полностью или частично). Разумеется, для этого доход и средства должны быть приведены к единому (денежному) эквиваленту.

Задача о распределении ресурсов со вложением доходов в производство может ставиться по-разному, в зависимости от того, вкладывается доход полностью или частично и какая величина максимизируется.

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

1. Доход вкладывается в производство полностью, максимизируется сумма всех средств (основные плюс доход) после этапа.

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

если считать, что выигрыши на всех этапах, кроме последнего, равны нулю

Так как вече средства (и основные и ) вкладываются в производство на равных основаниях, нет надобности рассматривать отдельно «функции дохода» и «функции траты», а достаточно ввести для каждой отрасли только по одной функции: для отрасли I — функцию показывающую, сколько средств (включая и доход) получится в конце шага в отрасли I при вложении в нее средств X в начале этого шага. Аналогичная функция для отрасли II будет . Назовем функции

«функциями изменения средств» на этапе. Заметим, что вообще возможно любое из соотношений:

(аналогично для ).

Рис. 3.35

Рассмотрим фазовое пространство, соответствующее данной задаче (рис. 3.35). Таким пространством будет уже не треугольник AQB (как в задачах без вложения доходов), а весь первый квадрант ХОК (средства могут не только уменьшаться, но и расти). Траектория по-прежнему состоит из ряда звеньев, распадающихся на полузвенья; первое полузвено (для всех этапов, кроме первого) изображает перераспределение средств (точка S движется параллельно АВ), второе — трату и приобретена средств (точка S может двигаться в любом направлении). В отличие от ранее рассмотренных задач, здесь доход приносит только одно, последнее, звено, которое на рис. 3.35 выделено жирной стрелкой.

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

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

Выигрыш на всех шагах, кроме последнего, равен нулю, поэтому не будем его записывать.

На последнем же шаге он выражается формулой:

где К — средства, с которыми мы подошли к последнему шагу.

Основное функциональное уравнение динамического программирования будет:

где К — средства, с которыми мы подошли к шагу.

На последнем шаге получаем условный оптимальный выигрыш, равный

и условное оптимальное управление, при котором этот выигрыш до стигается:

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

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

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

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

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

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

есть неубывающая функция своего аргумента (суммы средств в конце шага). Докажем, что тогда неубывающей функцией будег и (7.4).

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

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

Зафиксируем какое-то значение Пусть для этого значения выражение (7.6) достигает максимума по равного при определенном управлении Придадим теперь величине некоторое положительное приращение . У нас образовался некоторый избыток средств, который мы можем вложить дополнительно либо в отрасль I, либо в отрасль II, либо в обе сразу. Так как функции неубывающие, то от такого «добавления» средств каждое слагаемое под знаком функции (7.6) может только увеличиться, а значит, и их сумма может только увеличиться, а не стать меньше. Что при этом станет с функцией Согласно нашему допущению, функция 1 — неубывающая, значит, при увеличении выражение (7.6) уменьшиться не может. Итак, переход от к i доказан.

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

и, естественно, является неубывающей функцией от (это только что было доказано для любого i, а значит, и для Таким образом, есть неубывающая функция а значит, согласно принципу полной индукции, и любой из выгрышей — неубывающая функция, что и требовалось доказать.

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

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

На втором — то управление, при котором обращается в максимум величина

до . Максимальный выигрыш на шаге будет равен: шах

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

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

2. Доход вкладывается в производство полностью на всех этапах, кроме последнего; максимизируется доход на последнем шаге.

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

Для того, чтобы отделить сумму оставшихся средств от дохода, нужно для последнего шага задать не функции изменения средств, а по отдельности «функции дохода» и «функции траты»

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

получаем условия п. 1. Естественно, что если все функции — неубывающие, данная задача, как и предыдущая, будет вырожденной.

3. Доход вкладывается в производство не полностью, а какая-то часть его отчисляется; максимизируется полный отчисленный доход на всех этапах плюс остаток средств после этапа.

Для решения этой задачи должны быть заданы «функции дохода»:

«функции траты»:

и еще, дополнительно, «функции отчислений»:

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

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

Выигрыш на шаге будет

Управление на шаге (вложение средств в отрасль I, а остальных средств — в отрасль II) переводит систему из состояния К в новое состояние:

Основное функциональное уравнение:

Условный оптимальный выигрыш на шаге:

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

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

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

5. Доход вкладывается в производство не полностью, а частично; максимизируется суммарное количество средств (основные плюс доход) после шага, без учета ранее отчисленных сумм.

Не будет ли какая-нибудь из этих задач при некоторых условиях вырожденной?