4. Модели динамического программирования. Задача распределения капиталовложений

Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме С^*=10 (усл. ед.). Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами x_i (в усл. ед.) суммарных затрат и доходов g_i(x_i) (g_i(x_i) – неубывающие функции), связанных с реализацией каждого из проектов. Соответствующие данные приведены в табл. 4.1, в которую включены также проекты с нулевыми затратами. Это позволяет учесть возможность отказа от расширения какого-либо предприятия. Цель фирмы состоит в получении максимального дохода от инвестиций в объеме С^* усл. ед.

Таблица 4.1

m	0	1	2	3	4	5	6	7	8	9	10
xi=m·h	0	1	2	3	4	5	6	7	8	9	10
g1(xi)	0	1	2	2	2	2	2	2	2	2	2
g2(xi)	0	0.5	1	1.5	2	2.5	3	3	3	3	3
g3(xi)	0	0	0	0	0	0.5	1	3	5	6	6.5

Графики функций g_i(x_i) приведены на рис 4.1.

Рис. 4.1

Таким образом, задача динамического программирования в данном конкретном случае формулируется следующим образом:

W(x₁,x₂,х₃)= g₁(x₁)+ g₂(x₂)+ g₁(x₃)→max, (4.1)

x₁+ x₂+ x₃= С^*,

x₁, x₂, x₃ ≥ 0.

Вместо данной задачи об оптимальном разбиении какой-то одной конкретной суммы С^*, предполагается решить целый спектр задач о разбиении всех других возможных значений этой суммы X, меньших по сравнению с С^* (с точностью до шага h), начиная от X=0 и заканчивая С^*, или, что одно и то же, начиная от x=0 и заканчивая m (в нашем случае m=10). Мы рассчитываем построить поле оптимальных решений для различных значений X и уже на этом поле искомое нами оптимальное разбиение конкретной суммы С^* легко определится как некоторый частный случай – равно как и другие частные случаи, ему подобные, с другими значениями X≤С^*. Оказывается, целое поле оптимальных решений в данных условиях строить легче, нежели находить одно-единственное оптимальное решение для какого-то фиксированного значения суммы С^*. Логика построения поля решений следующая. В рассмотрение вводится последовательность функций f₁(x), f₂(x),…, f_i(x),…, f_n(x). Эти функции принято называть функциями Беллмана. Рассмотрим произвольную промежуточную функцию f_i(x). Она характеризует величину суммарного дохода от i предприятий (1≤i≤n) при условии, что инвестируемая сумма x между этими i предприятиями поделена оптимально. Иными словами, мы рассматриваем только первые по списку i предприятий, не обращая (временно) внимания на остальные, и ставим задачей оптимальное распределение суммы x только между этими предприятиями. Величина f_i(x) характеризует максимально достижимый при этом доход. Мы будем последовательно строить все n функций Беллмана одну за другой, начиная от i=1 и заканчивая на i=n. Параллельно с построением f_i(x) будем строить еще одну последовательность – функций оптимальных инвестиций x₁(x), x₂(x),…, x_i(x),…, x_n(x). Смысл этих функций таков: если рассматривается только i первых предприятий(1≤i≤n), то какая часть от выделенной суммы x, при оптимальном ее разбиении инвестируется сугубо на i-ю отрасль.

В нашем конкретном примере n=3 и, значит, индекс i будет пробегать значения 1, 2, 3. Заготовим табл.4.2 для систематизированной записи возможных значений функций f₁(x), f₂(x), f₃(x), x₁(x), x₂(x), и x₃(x). Начнем с i=1.

Таблица 4.2

x	f1(x)	f2(x)	f3(x)	x1(x)	x2(x)	x3(x)
0	0	0	0	0	0	0
1	1	1	1	1	0	0
2	2	2	2	2	0	0
3	2	2.5	2.5	3	1	0
4	2	3	3	4	2	0
5	2	3.5	3.5	5	3	0
6	2	4	4	6	4	0
7	2	4,5	4.5	7	5	0
8	2	5	5	8	6	0
9	2	5	6	9	6	0
10	2	5	7	10	6	0

Как оптимально делить ресурсы x при i=1? Никак! Все, что имеется, надо вкладывать только в первое предприятие, ибо оно в данном случае – монополист. Это сразу определяет соответствующие столбцы таблицы: f₁(x)= g₁(x), x₁(x)= x.

Переходим к i=2. Для x=0 все ясно: f₂(0)=0, x₂(0)= x₁(0)=0. А вот уже для x=1 возможны два варианта деления этой суммы между 1-м и 2-м предприятиями: x₁=1, x₂=0 или x₁=0, x₂=1. Первому варианту соответствует суммарный доход

f = g₁(1)+ g₂(0)= f₁(1)+ g₂(0)=1,

второму – доход

g₁(0)+ g₂(1)=1/2.

Очевидно, первый вариант лучше, поэтому f₂(1)=1 и, следовательно, x₂(1)=0. Перейдем последовательно к значениям x= 2, 3 и 4. Для компактности будем сводить получаемые результаты в таблицы 4.3 а), б), в).

Таблица 4.3

а)

х=2
x1	x2	f1(x1)+ g2(x2)	f2(2)	x(2)
2	0	2+0=2	2	0
1	1	1+0.5=1.5
0	2	0+1=1

б)

х=3
x1	x2	f1(x1)+ g2(x2)	f2(3)	x2(3)
3	0	2+0=2	2	0
2	1	2+0.5=2.5	2.5	1
1	2	1+1=2
0	3	0+1.5=1.5

в)

х=4
x1	x2	f1(x1)+ g2(x2)	f2(4)	x2(4)
4	0	2+0=2
3	1	2+0.5=2.5
2	2	2+1=3	3	2
1	3	1+1.5=2.5
0	4	0+2=2

Заполним целиком подобным образом столбцы, относящиеся к f₂(х) и х₂(х). Обратим внимание на то, что f₂(х) ≥ g₁(x) и f₂(х) ≥ g₂(x). Этого в общем и следовало ожидать, ибо при увеличении числа предприятий возрастает «свобода маневра» в распределении ресурсов, что позволяет в зависимости от условий инвестиций x использовать наиболее «выгодные» свойства функций g₁(x) и g₂(x). Такая тенденция еще более отчетливо будет проявляться и в дальнейшем по мере роста i. В случае «размытости» максимума функции f₁(x)+ g₂(x) возможен произвол в выборе величины х₂(х), что иногда будет иметь место и в дальнейшем.

При переходе к i=3 мы сталкиваемся с качественно новой ситуацией: «против» третьего нового предприятия теперь «играет» не первое и второе в отдельности, каждое само по себе, но их «объединенная команда»: если из общей суммы Х в третье предприятие инвестируется сумма х₃, то оставшаяся сумма (X–х₃) делится между 1-м и 2-м предприятиями не произвольно, а оптимально. Поэтому вклад в значение целевой функции, вносимый совместно первым и вторым предприятиями, будет равняться величине f₂(X-х₃).

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

Таблица 4.4

х=9
x-x3	x2	f2(x-x3)+ g3(x3)	f3(9)	x2(9)
9	0	5+0=5
8	1	5+0=5
7	2	4.5+0=4.5
6	3	4+0=4
5	4	3.5+0=3.5
4	5	3+0.5=3.5
3	6	2.5+1=3.5
2	7	2+3=5
1	8	1+5=6	6	8
0	9	0+6=6

Нетрудно построить заключительную для нашего примера функцию f₃(x) и соответствующую ей функцию x₃(x). В качестве характерного примера рассмотрим табл.4.4 расчета только по одному из значений. Мы остановились на значении x₃=8, хотя вполне возможно было также и x₃=9. Построение поля оптимальных решений завершено. Семейство функций f₁(x), f₂(x), f₃(x) графически изображено на рис.4.2. Рекомендуем сравнить его с функциями g ₁(x), g ₂(x), g ₃(x) (рис.4.1).

Рис.4.2

Как решить исходную задачу об оптимальном распределении вполне конкретной суммы С^*? Пусть, например, С^*=7. Это значит, x₃=0, что явствует из последнего столбца табл.4.2. Следовательно, на первое и второе предприятия совместно остается С^*–х₃(7)=7–0=7. В предпоследнем столбце находим х₂(7)=5. Следовательно, на первое предприятие остается х₁=7–5=2. Поэтому оптимальным решением будет вектор X=(2;5;0). Ему будет соответствовать оптимальный доход, равный f₃(2;5;0)=4.5. Для заданного значения С^*=10 мы получим x₃=8, далее x₂=0 и x₁=2, при оптимальном доходе f₃(2;0;8)=W(2;0;8)=7.

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