Задачи распределения ресурсов

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

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

Задача ставится следующим образом.

Имеется определенное начальное количество средств (необязательно в денежной форме), которые мы должны распределять в течение лет между двумя отраслями производства I и II.

Средства, вложенные в каждую отрасль, приносят за год определенный доход, зависящий от объема вложений. Если мы вложим средства X в отрасль 1, то за год получим доход, равный при этом вложенные средства частично уменьшаются (амортизируются, тратятся), так что к концу года от них остается какая-то часть:

Аналогично, средства Y, вложенные в отрасль II, приносят за год доход и уменьшаются до

По истечении года, оставшиеся от средства заново распределяются между отраслями I и II. Новых средств извне не поступает, и в производство вкладываются все оставшиеся в наличии средства; доход в производство не вкладывается, а накапливается отдельно. Требуется найти такой способ управления ресурсами (какие средства, в какие годы и в какую отрасль вкладывать), при котором суммарный доход от обеих отраслей за лет будет максимальным.

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

1. Система S в данном случае — две отрасли со вложенными в них средствами. Она характеризуется двумя параметрами X и Y, выражающими количества средств в отраслях I и II соответственно. Естественным «шагом» (этапом) процесса является хозяйственный год. В процессе управления величины X и Y меняются в зависимости от двух причин:

— перераспределение средств между отраслями в начале каждого года;

— уменьшение (трата) средств за год, сказывающееся в конце каждого года.

Управлением на шаге будут количества средств вкладываемые в отрасли I и II на этом шаге. Управление операцией U состоит из совокупности всех шаговых управлений:

Нам нужно найти такое (оптимальное) управление

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

2. Состояние системы перед шагом характеризуется одним параметром К — количеством средств, сохранившихся после предыдущих шагов.

Управление на шаге будет состоять в том, что мы выделим в отрасль I средства Х; величина определится автоматически; она будет равна оставшимся средствам:

Выигрыш (доход) на шаге будет:

3. Под влиянием этого управления на шаге система перейдет из состояния К в состояние

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

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

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

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

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

6. Зная функцию находим по формуле (4.6) условные оптимальные выигрыши на двух последних, на трех последних и т. д. шагах:

и соответствующие им условные оптимальные управления:

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

Оптимальное управление на первом шаг будет:

Состояние системы после первого шага:

Оптимальное управление на втором шаге:

и т. д. по цепочке. Состояние системы после i шагов:

Оптимальное управление на шаге:

и т. д., вплоть до последнего шага, по цепочке:

Величина будет представлять собой количество средств, оставшихся (при оптимальном управлении) после последнего шага. Совокупность средств, вложенных по годам в отрасль I:

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

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

Дадим процессу распределения ресурсов геометрическую интерпретацию. Из соображений наглядности сделаем фазовое пространство двумерным, хотя можно было бы ограничиться и одномерным. Будем откладывать по оси ОХ средства X, вкладываемые в отрасль I, по оси — средства Y, вкладываемые в отрасль II. Сумма этих средств не может быть больше, чем количество начальных средств поэтому фазовое пространство — это часть плоскости заключенная внутри равнобедренного прямоугольного треугольника с катетами (рис.).

Так как в начале процесса распределения сумма средств в обеих отраслях равна то область начальных состояний есть не что иное, как гипотенуза треугольника АВ. На количество средств в конце периода лет никаких ограничений, кроме не накладывается; поэтому областью S конечных состояний системы является весь треугольник ЛОВ (кроме гипотенузы).

Изобразим траекторию точки 5 в фазовом пространстве (рис. 3.18).

Представим себе, что в начале каждого года происходит распределение (или перераспределение) средств по отраслям, а в течение года вложенные средства тратятся и образуется доход. Тогда каждое звено траектории точки S в фазовом пространстве будет состоять из двух полузвеньев: на первом происходит только перераспределение средств и точка S перемещается параллельно АВ, на втором — средства тратятся и точка S перемещается вниз и налево, ближе к началу координат.

Рис. 3.17

Рис. 3.18

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