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

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

Рассмотрим дискретную динамическую модель на примере задачи распределения инвестиций. Требуется распределить имеющиеся В единиц средств среди N предприятий, доход Gi(Xi) от которых в зависимости от количества вложенных средств Xi определяется матрицей , приведенной в табл. 21 так, чтобы суммарный доход со всех предприятий был бы максимальным.

Таблица 21

Gi X	G1	G2	. . .	Gi	. . .	Gn
X1	G1(x1)	G2(x1)	…	Gi(x1)		Gn(x1)
X2	G1(x2)	G2(x2)	…	Gi(x2)		Gn(x2)
Xi	…	…	…	Gi(xi)	…	…
Xn	G1(xn)	G2(xn)	…	Gi(xn)		Gn(Xn)

 Запишем математическую модель задачи.

Определить  удовлетворяющий условиям

   (32), (33)

И обеспечивающий максимум целевой функции

  (34)

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

С этой целью разобьем процесс оптимизации на N шагов и будем на каждом K-том шаге оптимизировать инвестирование не всех предприятий, а только предприятий с K-го по N-е. При этом естественно считать, что в остальные предприятия (с первого по (K – 1)-е) тоже вкладываются средства, и поэтому на инвестирование предприятий с K-го по N-е остаются не все средства, а некоторая меньшая сумма Ck  B. Эта величина и будет являться переменной состояния системы. Переменной управления на K-том шаге назовем величину Xk средств, вкладываемых в K-тое предприятие. В качестве функции Беллмана Fk(Ck) на K-том шаге можно выбрать максимально возможный доход, который можно получить с предприятий с K-го по N-е при условии, что на их инвестирование осталось Ck средств. Очевидно, что при вложении в K-е предприятие Xk средств будет получена прибыль Gk(Xk), а система к (K + 1)-му шагу перейдет в состояние Sk+1 и, следовательно, на инвестирование предприятий с (K + 1)-го до N-го останется Ck+1=(Ck-Xk) средств.

Таким образом, на первом шаге условной оптимизации при K = N функция Беллмана представляет собой прибыль только с N-го предприятия. При этом на его инвестирование может остаться количество средств Cn, . Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е.

На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на K-м шаге для инвестирования предприятий с K-го по N-е осталось Ck средств (). Тогда после вложения в K-ое предприятие Xk средств будет получена прибыль Gk(СK), а на инвестирование остальных предприятий (с K-го по N-е) останется   средств. Максимально возможный доход, который может быть получен с предприятий (с K-го по N-е), будет равен:

  (30)

Максимум выражения (30) достигается на некотором значении , которое является оптимальным управлением на K-ом шаге для состояния системы Sk. Действуя таким образом, можно определить функцию Беллмана и оптимальные управления до шага K = 1.

Значение функции Беллмана F1(C1) представляет собой максимально возможный доход со всех предприятий, а значение , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина  и оптимальным управлением на K-м шаге является то значение Xk, которое обеспечивает максимум дохода при соответствующем состоянии системы Sk.

Пример 73. На развитие трех предприятий выделено 5 млн. р. Известна эффективность капитальных вложений в каждое предприятие, заданная значением нелинейной функции Gi(Xi) представленной в табл. 22. Необходимо распределить выделенные средства между предприятиями таким образом, чтобы получить максимальный суммарный доход.

Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах Xi = {0, 1, 2, 3, 4, 5} млн. р.

 Таблица 22

X	G1	G2	G3
0	0	0	0
1	2.2	2	2.8
2	3	3.2	5.4
3	4.1	4.8	6.4
4	5.2	6.2	6.6
5	5.9	6.4	6.9

Решение. 1 этап. Условная оптимизация.

1-й шаг: K = 3. Предположим, что все средства в количестве X3 = 5 млн. р. отданы третьему предприятию. В этом случае максимальный доход, как это видно из табл. 23, составит G3(X3) = 6.9 тыс. р., следовательно:

F3(C3) = G3(X3).

 Таблица 23

X3 C3	0	1	2	3	4	5	F3(c3)	X3*
0	0	-	-	-	-	-	0	0
1	-	2,8	-	-	-	-	2,8	1
2	-	-	5,4	-	-	-	5,4	2
3	-	-	-	6,4	-	-	6,4	3
4	-	-	-	-	6,6	-	6,6	4
5	-	-	-	-	-	6,9	6,9	5

 2-й шаг: K = 2. Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим предприятиями. При этом соотношение Беллмана имеет вид

На основе которого составлена табл. 24:

Таблица 24

X2 C2	0	1	2	3	4	5	F2(c2)	X2*
0	0+0	-	-	-	-	-	0	0
1	0+2,8	2+0	-	-	-	-	2,8	0
2	0+5,4	2+2,8	3,2+0	-	-	-	5,4	0
3	0+6,4	2+5,4	3,2+2,8	4,8+0	-	-	7,4	1
4	0+6,6	2+6,4	3,2+5,4	4,8+2,8	6,2+0	-	8,6	2
5	0+6,9	2+6,6	3,2+6,4	4,8+5,4	6,2+2,8	6,4+0	10,2	3

  3-й шаг: K = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета суммарного дохода:

На основе которого составлена табл. 25:

Таблица 25

X1 C1	0	1	2	3	4	5	F1(c1)	X1*
0	0+0	-	-	-	-	-	0	0
1	0+2,8	2,2+0	-	-	-	-	2,8	0
2	0+5,4	2,2+2,8	3+0	-	-	-	5,4	0
3	0+7,4	2,2+5,4	3+2,8	4,1+0	-	-	7,6	1
4	0+8,6	2,2+7,4	3+5,4	4,1+2,8	5,2+0	-	9,6	1
5	0+10,2	2,2+8,6	3+7,4	4,1+5,4	5,2+2,8	5,9	10,8	1

  2 этап. Безусловная оптимизация.

Определяем компоненты оптимальной стратегии.

1-й шаг. По данным табл. 25 максимальный доход при распределении 5 млн. р. между тремя предприятиями составляет: С1 = 5, F1(5) = 10.8. При этом первому предприятию нужно выделить Х1* = 1 млн. р.

2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий.

С2 = с1 – х1* = 5 – 1 = 4 млн. р.

По данным табл. 24 находим, что оптимальный вариант распределения денежных средств размером 4 млн. р. между вторым и третьим предприятиями составляет:  F2 (4) = 8.6 при выделении второму предприятию Х2* = 2 млн. р.

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

С3 = с2 – х2* = 4 – 2 = 2 млн. р.

По данным табл. 25 находим:

F3(2)  = 5.4 и х3* = 2 млн. р.

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

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

F(5) = G1(1) + G2(2) + G3(2) = 2.2 + 3.2 + 5.4 = 10.8 млн. р.

< Предыдущая		Следующая >