2. Аналитическое решение задачи

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

Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств X у.е. приносит прибыль Pi (x) у.е. (i = l, 2 и 3) последующим данным, приведённым в таблице 1.

Таблица 1 – Исходные данные.

Инвестируемые средства (у.е.)	Общая прибыль (у.е.)
Х	P1(x)	P2(x)	P3(x)
1	3,22	3,33	4,27
2	3,57	4,87	7,64
3	4	5,26	10,25
4	4,12	7,34	15,93
5	4,85	9,49	16,12

Составим математическую модель задачи:

а) Число шагов в данной задаче равно 3.

б) Пусть S - количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге.

в) Управление на i -ом шаге (i = l,2,3) выберем X, - количество средств, инвестируемых в i -ое предприятие.

д) Выигрыш Pi (Xi) на i -ом шаге - это прибыль, которую приносит I -oe предприятие при инвестировании в него средств Xi. Если через выигрыш в целом обозначить общую прибыль W, то

W = P₁ (x₁) + P₂ (x₂) + P₃(x₃).

е) Если в наличии имеются средства в количестве S у.е. и в i -oe предприятие инвестируется X у.е., то для дальнейшего инвестирования остается (S-X) у.е.. Таким образом, если на i -ом шаге система находилась в состоянии S и выбрано управление X, то на (i +1) -ом шаге система будет находиться в состоянии (S-X), и, следовательно, функция перехода в новое состояние имеет вид: F_i (S-X) = S-X.

ж) На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием:

X_i (S) = S. W_i (S) = P_i (S).

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

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

W_i (S) = max_x<=s {P_i (X) + W_i+1 (S - X)}

Проведём пошаговую оптимизацию, по результатам которой заполним таблицу 2.

Таблица 2 – Итоговые данные.

S	i = 3		i = 2		i = 1
	X3 (s)	W3 (s)	X2 (s)	W2 (s)	X1 (s)	W1 (s)
1	1	4,27	0	3,33	-	-
2	2	7,64	0	4,87	-	-
3	3	10,25	1	10,97	-	-
4	4	15,93	0	15,93	-	-
5	5	16,12	1	19,26	0	19,26

В первой колонке таблицы записываются возможные состояния системы, в верхней строке - номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего. Так как для последнего шага i = 3 функциональное уравнение имеет вид:

X₃ (S) = S,

W₃ (S) = P₃ (S),

то две колонки таблицы, соответствующие i = 3, заполняются автоматически по таблице исходных данных.

На шаге i = 2 основное функциональное управление примет вид:

W₂ (S) = max_x<=s {P₂ (X) + W₃ (S - X)}

Поэтому для проведения оптимизации на этом шаге заполним таблицу 3 для различных состояний S при шаге i = 3.

Таблица 3 – Второй шаг обработки.

S	X	S-X	P2 (x)	W3 (s-x)	P2 (x) + W3 (s-x)	W2 (s)
1	0	1	0	4,27	4,27	4,27
	1	0	3,33	0	3,33
2	0	2	0	7,64	7,64	7,64
	1	1	3,33	4,27	7,6
	2	0	4,87	0	4,87
3	0	3	0	10,25	10,25	10,97
	1	2	3,33	7,64	10,97
	2	1	4,87	4,27	9,14
	3	0	5,26	0	5,26
4	0	4	0	15,93	15,93	15,93
	1	3	3,33	10,25	13,58
	2	2	4,87	7,64	12,51
	3	1	5,26	4,27	9,53
	4	0	7,34	0	7,34
5	0	5	0	16,12	16,12	19,26
	1	4	3,33	15,93	19,26
	2	3	4,87	10,25	15,12
	3	2	5,26	7,64	12,9
	4	1	7,34	4,27	11,61
	5	0	9,49	0	9,49

На шаге i = 1 основное функциональное управление примет вид:

W₁ (S) = max_x<=s {P₁ (X) + W₂ (S - X)},

а состояние системы перед первым шагом S = 5, поэтому для проведения оптимизации на этом шаге заполним таблицу 4.

Таблица 4 – Первый шаг обработки.

S	X	S-X	P1 (x)	W2 (s-x)	P1 (x) + W2 (s-x)	W1 (s)
5	0	5	0	19,26	19,26	19,26
	1	4	3,22	15,93	19,15
	2	3	3,57	10,97	14,54
	3	2	4	7,64	11,76
	4	1	4,12	4,27	8,27
	5	0	4,85	0	4,85

Видно, что наибольшее значение выигрыша составляет 19,26. При этом оптимальное управление на первом шаге составляет X₁ (S₁)=0 при этом S₁=5, на втором шаге X₂ (S₂)=1 при этом S₂=S₁–X₁=5 и на третьем шаге X₃(S₃)=4 при этом S₃=S₂–X₂=4. Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.

Таким образом, для получения наибольшей обшей прибыли в размере 19,26 у.е., необходимо вложить 1 у.е. во второе предприятие и 4 у.е. в третье предприятие.