Пример решения задачи распределения ресурсов

Пример. Планируется деятельность двух отраслей производства 1 и II сроком на 5 лет Заданы «функции дохода»:

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

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

Решение. В соответствии с общей схемой, приведенной в § 4, получаем:

1. Как в п. 1 общей схемы.

2. Выигрыш на шаге:

3. Под Влиянием управления (вложения средств в отрасль в отрасль II система на шаге перейдет из состояния К в

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

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

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

Найдем этот максимум.

При фиксированном К выражение, стоящее в фигурных скобках, есть функция аргумента выпуклая вверх. В зависимости от значения К максимум этой функции может достигаться либо внутри отрезка (0, К) (рис. 3.19), либо на левом его конце (рис. 3.20).

Рис. 3.19

Рис. 3.20

Чтобы найти этот максимум, продифференцируем выражение

при фиксированном К по и приравняем производную нулю

На данном (пятом) шаге нам еще удастся решить уравнение (5.1) в буквенном виде, на дальнейших шагах такие задачи придется решать численно (графически). Из (5.1) имеем:

Отсюда следует, что если то максимум достигается внутри отрезка (0, К) в точке если же да 0,347, то максимум достигается в конце отрезка

Таким образом, условное оптимальное управление на последнем (пятом) шаге найдено: если мы подошли к этому шагу с запасом средств то из этих средств следует выделить в отрасль I долю (5.3); если же мы подошли к пятому шагу с запасом средств, меньшим, чем то все эти средства надо отдать в отрасль II. Как же быть, если мы подойдем к пятому шагу с запасом средств, в точности равным Очевидно, в этом случае оба управления указывают одно и то же, а именно: выделять средств в отрасль I не нужно. Запишем найденное условное оптимальное управление на пятом шаге в виде формулы

Найдем теперь условный оптимальный выигрыш (доход) на пятом шаге, который получится при таком управлении:

или, подставляя сюда выражения (5.4):

Так как нам в дальнейшем придется вычислять величину для разных значений аргумента, построим ее график в зависимости от К (рис. 3.21).

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

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

6. Переходим к предпоследнему (четвертому) шагу. Задачу его условной оптимизации будем решать численно, задаваясь рядом значений К (количества средств, Оставшихся после третьего шага). Чтобы не делать лишней работы, выясним, в каких пределах может находиться К. Найдем самое большое из возможных значений К.

Оно будет получено, если на первых трех шагах все средства будут вложены в отрасль 1, где траты минимальны; тогда после трех лет получим:

Наименьшее значение К получится, если на первых трех шагах все средства будут вложены в отрасль II:

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

Рис. 3.21

Рис. 3.22

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

где первое слагаемое а второе слагаемое определяется по графику рис. 5.3, для чего нужно войти в него вместо К с аргументом

Кривые зависимости от (при заданном К) для шестого шага представлены на рис. 3.22.

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

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

Рис. 3.23

Затем прибавим к нему уже оптимизированный доход на двух последних шагах который мы определим по графику рис. 3.21, входя в него вместо К аргументом и получим «полуоптимальный» выигрыш на трех последних шагах (при оптимальном управлении на двух последних и любом управлении — на третьем шаге)

Рис. 3.24

Рис. 3.25

Для этой функции опять построим графики зависимостей от при фиксированном К? На каждой из кривых снова отметим максимум (рис. 3.24). После этого построим на одном графике (рис. 3.25) две кривые: условное оптимальное управление и условный оптимальный выигрыш

Совершенно аналогично решается задача оптимизации второго шага. Варьируются значения К от до. Определяется доход на втором шаге:

К нему прибавляется условный максимальный доход определяемый по графику рис. 3.25 со входом

Получается величина для которой снова строятся графики (рис. 3.26). На каждой кривой находится максимум и строятся две кривые: (рис. 3.27).

Рис. 3.26

Рис. 3.27

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

а последний член находится по графику рис. 3.27 при входе в него с аргументом где

Определяя на единственной кривой (см. рис. 3.28) максимум, найдем окончательное (уже не условное) значение максимального дохода за все пять лет:

и соответствующее ему безусловное оптимальное управление на первом шаге:

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

Зная находим запас средств после первого шага:

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

Рис. 3.28

Остаток средств после второго шага будет:

С этим значением входим в график (см. рис. 3.25) и находим оптимальное управление на третьем шаге

Остаток средств после третьего шага:

По графику рис. 3.23 находим оптимальное управление на четвертом шаге

Остаток средств после четвертого шага:

С этим значением входим в график (см. рис. 3.21) и находим оптимальное управление на последнем шаге

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

Учитывая, что наличные средства перед началом каждого года известны и равны:

сразу же находим и количества средств, вкладываемых в отрасль II по годам:

Таким образом, можно сформулировать следующие рекомендации по вложению средств.

Из имеющегося в начале запаса и остающихся средств в конце каждого годя нужно вкладывать по годам в отрасли I и II следующие суммы:

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

Остаток средств в конце периода будет равен:

Рис. 3.29

На рис. 3.29 изображена оптимальная траектория в фазовом пространстве (каждый этап, кроме первого, разделен на полуэтапы).

Из рассмотренного примера видно, насколько сложной и кропотливой является пошаговая оптимизация «вручную», даже для наиболее элементарных задач (только две отрасли производства; простейшие «функции дохода» и «функции трат»). При сколько-нибудь более сложных условиях разработка оптимального плана методом динамического программирования практически невозможна без привлечения быстродействующих ЭЦВМ,