2.2.4 Оптимальное распределение ресурсов

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

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

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

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

Задача 1. Имеется начальное количество средств , которое необходимо распределить в течение п лет между s предприятиями. Средства (k=1, 2,…,n; i=1,…, s), выделенные в k-м году i-му предприятию, приносят доход в размере и к концу года возвращаются в количестве . В последующем распреелении доход может либо участвовать (частично или полностью), либо не участвовать.

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

Следовательно, в качестве показателя эффективности процесса распределения ресурсов за п лет принимается суммарный доход, полученный от s предприятий:

(4.1)

Количество ресурсов в начале k-го года будем характеризовать величиной (параметр состояния). Управление на k-м шаге состоит в выборе переменных обозначающих ресурсы, выделяемые в k-м году i-му предприятию.

Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид

(4.2)

Если же некоторая часть дохода участвует в дальнейшем распределении в каком-нибудь году, то к правой части равенства (4.2) прибавляется соответствующая величина.

Требуется определить ns неотрицательных переменных , удовлетворяющих условиям (4.2) и максимизирующих функцию (4.1).

Вычислительная процедура ДП начинается с введения функции , обозначающей доход, полученный за п--k+1 лет, начиная с k-го года до конца рассматриваемого периода, при оптимальном распределении средств между s предприятиями, если в k-м году распределялось средств. Функции для k=1, 2, ...n-1 удовлетворяют функциональным уравнениям (2.2), которые запишутся в виде:

(4.3)

При k=n согласно (2.2) получаем

(4.4)

Далее необходимо последовательно решить уравнения (4.4) и (4.3) для всех возможных (k = n--1, п--2, 1). Каждое из этих уравнений представляет собой задачу на оптимизацию функции, зависящей от s переменных. Таким образом, задача с ns переменными сведена к последовательности п задач, каждая из которых содержит s переменных. В этой общей постановке задача по-прежнему сложна (из-за многомерности) и упростить ее, рассматривая как ns-шаговую задачу, в данном случае нельзя. В самом деле, попробуем это сделать. Пронумеруем шаги по номерам предприятий сначала в 1-м году, затем во 2-м и т. д.:

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

В течение k-го года состояние к началу любого шага s(k-1)_+i (i=1,2,…,s) определится по предыдущему состоянию с помощью простого уравнения . Однако по истечении года, т.е. к началу следующего года, к наличным средствам необходимо будет добавить средств и, следовательно, состояние в начале (ks+1)-гo шага будет зависеть не только от предшествующего ks-гo состояния, но и от всех s состояний и управлений за прошлый год. В результате мы получим процесс с последействием. Чтобы исключить последействие, приходится вводить несколько параметров состояний; задача на каждом шаге остается по-прежнему сложной из-за многомерности.

Задача 2. Планируется деятельность двух предприятий (s=2) в течение п лет. Начальные средства составляют . Средства х, вложенные в предприятие I, приносят к концу года доход f₁(x) и возвращаются в размере аналогично, средства х, вложенные в предприятие II, дают доход f₂(x) и возвращаются в размере . По истечении года все оставшиеся средства заново перераспределяются между предприятиями I и II, новых средств не поступает и доход в производство не вкладывается.

Требуется найти оптимальный способ распределения имеющихся средств.

Будем рассматривать процесс распределения средств как n-шаговый, в котором номер шага соответствует номеру года. Управляемая система -- два предприятия с вложенными в них средствами. Система характеризуется одним параметром состояния --количеством средств, которые следует перераспределить в начале k-гo года. Переменных управления на каждом шаге две: -- количество средств, выделенных соответственно предприятию I и II. Так как средства ежегодно перераспределяются полностью, то ). Для каждого шага задача становится одномерной. Обозначим через , тогда

Показатель эффективности k-гo шага равен . Это -- доход, полученный от двух предприятий в течение k-гo года.

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

(4.5)

Уравнение состояния выражает остаток средств после k-гo шага и имеет вид

(4.6)

Пусть --условный оптимальный доход, полученный от распределения средств между двумя предприятиями за n--k+1 лет, начиная с k-гo года до конца рассматриваемого периода. Запишем рекуррентные соотношения для этих функций:

(4.7)

где - определяется из уравнения состояния (4.6).

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

Рассмотрим двумерную задачу, аналогичную предыдущей, в которой строится дискретная модель ДП процесса распределения ресурсов.

Задача 3. Составить оптимальный план ежегодного распределения средств между двумя предприятиями в течение трехлетнего планового периода при следующихусловиях:

1) начальная сумма составляет 400;

2) вложенные средства в размере х приносят на предприятии I доход f₁(x) и возвращаются в размере 60% от х, а на предприятии II -- соответственно f2(x) и 20%;

3) ежегодно распределяются все наличные средства, получаемые из возвращенных средств:

4) функции f₁(x) и f2(x)заданы в табл. 1:

Модель динамического программирования данной задачи аналогична модели, составленной в задаче 1.

Процесс управления является трехшаговым. Параметр -- средства, подлежащие распределению в k-м году (k=l, 2, 3). Переменная управления -- средства, вложенные в предприятие I в k-м году. Средства, вложенные в предприятие II в k-м году, составляют Следовательно, процесс управления на k-м шаге зависит от одного параметра (модель одномерная). Уравнение состояния запишется в виде

(4.8)

А функциональные уравнения в виде

(4.9)

(4.10)

Попытаемся определить максимально возможные значения, для которых необходимо проводить табулирование на k-м шаге (k=l, 2, 3). При =400 из уравнения (4.8) определяем максимально возможное значение имеем = 0,6*400=2400 (все средства вкладываются в предприятие I). Аналогично, для получаем предельное значение 0,6*240 = 144. Пусть интервал изменения совпадает с табличным, т. е. Дх =50. Составим таблицу суммарной прибыли на данном шаге:

Это облегчит дальнейшие расчеты. Так как то клетки, расположенные по диагонали таблицы, отвечают одному и тому же значению , указанному в 1-й строке (в 1-м столбце) табл. 2. Во 2-й строке таблицы записаны значения f₁(x), а во 2-м столбце -- значения f₂(у)взятые из табл. 1.Значения в остальных клетках таблицы получены сложением чисел f₁(x) и f₂(у),стоящих во 2-й строке и во 2-м столбце и соответствующих столбцу и строке, на пересечении которых находится данная клетка. Например, для =150 получаем ряд чисел: 20 --для х = 0, у=150; 18 --для х=50, у=100; 18-- для х--100, у=50; 15 -- для х= 150, у=0.

Проведем условную оптимизацию по обычной схеме. 3-й шаг. Основное уравнение (4.9)

Как указывалось выше, . Просмотрим числа на диагоналях, соответствующих =0; 50; 100; 150 и на каждой диагонали выберем наибольшее. Это и есть В 1-й строке находим соответствующее условное оптимальное управление. Данные оптимизации на 3-м шаге поместим в основную таблицу (табл. 4). В ней введен столбец Дх, который в дальнейшем используется при интерполяции.

Оптимизация 2-го шага проведена в табл. 5 согласно уравнению вида (4.10):

При этом может быть получен максимальный доход, равный Zmax=99,l. Прямой подсчет дохода по табл. 2 для найденного оптимального управления дает 97,2. Расхождение в результатах на 1,9 (около 2%) объясняется ошибкой линейной интерполяции.

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