1. Определение числа шагов. Число шагов т равно числу предприятий, в которые осуществляется инвестирование.
2. Определение состояний системы. Состояние системы на каждом шаге характеризуется количеством средств s, имеющихся в наличии перед данным шагом s≤D.
3. Выбор шаговых управлений. Управлением на i-ом шаге хi, i= является количество средств, инвестируемых в i-е предприятие.
4. Функция выигрыша на i-ом шаге
φi(хi) (9.8)
– это прибыль, которую приносит i-е предприятие при инвестировании в него средств хi.
, следовательно, данная задача может быть решена методом
динамического программирования.
5. Определение функции перехода в новое состояние
fi(s, x)=s – x. (9.9)
Таким образом, если на i-ом шаге система находилась в состоянии s, а выбрано управление х, то на следующем (i+1)–ом шаге система будет находиться в состоянии s – x. Другими словами, если в наличии имеются средства в размере s усл. ед., и в i-ое предприятие инвестируется х усл. ед., то для дальнейшего инвестирования остается s – x усл. ед.
6. Составление функционального уравнения для i=m.
Wm(s)=φm(s), xm(s)=s.
На последнем шаге, то есть перед инвестированием средств в последнее предприятие, условное оптимальное управление соответствует количеству средств, имеющихся в наличии; то есть, сколько средств осталось надо вложить в последнее предприятие. Условный оптимальный выигрыш равен доходу, приносимому последним предприятием.
7. Составление основного функционального уравнения
Подставив в формулу (9.6) выражения (9.8) и (9.9), получаем следующее функциональное уравнение .
Поясним данное уравнение. Пусть перед i-ым шагом у инвестора остались средства в размере s усл. ед. Тогда х усл. ед. он может вложить в i-ое предприятие, при этом оно принесет доход φi(х), а оставшиеся s – x усл. ед. – в остальные предприятия с (i+1)–го до т-го. Условный оптимальный выигрыш от такого вложения Wi+1(s – x). Оптимальным будет то условное управление х, при котором сумма φi(х) и Wi+1(s – x) максимальна.
Пример
D = 5000, т = 3.
Для простоты будем считать, что вкладываются только суммы, кратные 1 тыс. усл. единиц.
Значения φi(х), i = 1, 2, 3 заданы в таблице 9.3.
Таблица 9.3.
х
тыс. усл. ед.
φ1(х)
тыс. усл. ед.
φ2(х)
тыс. усл. ед.
φ3(х)
тыс. усл. ед.
1,5
1,7
2,1
2,4
2,5
2,3
2,7
3,5
3,2
3,6
3,5
Для х1 > x2φi(х1) ≥ φi(х2), i = .
Проведем условную оптимизацию и по ее результатам постепенно будем заполнять таблицу 9.4.
1. Проведем условную оптимизацию для последнего шага i=3. Функциональное уравнение на последнем шаге имеет вид:
W3(s)=φ3(s), x3(s)=s,
поэтому два столбца в таблице, соответствующие i=3, заполняются по таблице исходных данных.
Таблица 9.4.
s
i=3
i=2
i=1
x3(s)
W3(s)
x2(s)
W2(s)
x1(s)
W1(s)
1,7
2,4
2,7
3,2
3,5
2. Условная оптимизация для i=2. Функциональное уравнение:
.
Для проведения условной оптимизации заполним ряд вспомогательных таблиц (табл. 9.5 – 9.10), соответствующих различным значениям s, то есть различным исходам окончания предыдущего шага.
1) s = 1
Так как s = 1, то s – x =1 – x.
Таблица 9.5.
х
1 – x
φ2(х)
W3(1 – х)
φ2(х) + W3(1 – х)
1,7
1,7
Значения второго столбика получаем путем вычитания из s=1 соответствующего значения х. Третий столбик заполняется на основе таблицы, данной в постановке задачи, в которой для х=1 находим значение φ2(1)=2. Для нулевого аргумента выигрыш равен нулю, так как ничего не инвестировав, невозможно получить прибыль. Данные для четвертого столбика будем брать из таблицы 9.3 для W3(1) получим 1,7, а для W3(0) – ноль.
{1,7; 2}=2, следовательно W2(1)=2 и х2(1)=1, так как максимум в пятом столбце (табл. 9.5) соответствует значению х=1.
2) s=2.
Таблица 9.6.
х
2 – х
φ2(х)
W3(2 – х)
φ2(х) + W3(2 – х)
2,4
2,4
1,7
3,7
2,1
2,1
{2,4; 3,7; 2,1}=3,7, следовательно W2(2)=3,7 и х2(2)=1, так как максимум в пятом столбце (табл. 9.6) соответствует значению х=1.
3) s=3.
Таблица 9.7.
х
3 – х
φ2(х)
W3(3 – х)
φ2(х) + W3(3 – х)
2,7
2,7
2,4
4,4
2,1
1,7
3,8
2,3
2,3
{2,7; 4,4; 3,8; 2,3}=4,4, следовательно W2(3)=4,4 и х2(3)=1, так как максимум в пятом столбце (табл. 9.7) соответствует значению х=1.
4) s=4.
Таблица 9.8.
х
4 – х
φ2(х)
W3(4 – х)
φ2(х) + W3(4 – х)
3,2
3,2
2,7
4,7
2,1
2,4
4,5
2,3
1,7
3,5
3,5
{3,2; 4,7; 4,5; 4; 3,5}=4,7, следовательно W2(4)=4,7 и х2(4)=1, так как максимум в пятом столбце (табл. 9.8) соответствует значению х=1.
5) s=5.
Таблица 9.9.
х
5 – х
φ2(х)
W3(5 – х)
φ2(х) + W3(5 – х)
3,5
3,5
3,2
5,2
2,1
2,7
4,8
2,3
2,4
4,7
3,5
1,7
5,2
{3,5; 5,2; 4,8; 4,7; 5,2; 4}=5,2, следовательно W2(5)=5,2 и х2(5)=1 и х2(5)=4, так как максимум в пятом столбце (табл. 9.9) соответствует значениям х=1 и х=4.
Добавим полученные значения в таблицу 9.4 и получим таблицу 9.4'.
Таблица 9.4'.
s
i=3
i=2
i=1
x3(s)
W3(s)
x2(s)
W2(s)
x1(s)
W1(s)
1,7
2,4
3,7
2,7
4,4
3,2
4,7
3,5
1/4
5,2
6) Условная оптимизация для i=1.
Перед первым шагом состояние системы известно: s=D=5 тыс. усл. ед., значит условную оптимизацию следует проводить только для значения s=5.
s=5.
Таблица 9.10.
х
5 – х
φ1(х)
W2(5 – х)
φ1(х) + W2(5 – х)
5,2
5,2
1,5
4,7
6,2
4,4
6,4
2,5
3,7
6,2
3,6
3,6
{5,2; 6,2; 6,4; 6,2; 5; 3,6}=6,4, следовательно W1(5)=6,4 х1(5)=2, так как максимум в пятом столбце(табл. 9.10) соответствует значениям х=2.
Таблица 9.4".
s
i=3
i=2
i=1
x3(s)
W3(s)
x2(s)
W2(s)
x1(s)
W1(s)
1,7
2,4
3,7
2,7
4,4
3,2
4,7
3,5
1/4
5,2
6,4
Оптимальная прибыль, приносимая тремя предприятиями при инвестировании в них 5 тыс. усл. ед., равна 6,4 тыс. усл. ед. W*=W1(5)=6,4.
Проведем безусловную оптимизацию (табл. 9.4'"). Результаты оптимизации выделены жирным шрифтом.
i=1 s1 = 5 W1(5)=6,4; х1*=х1(5)=2
i=2 s2 = s1 – x1= 5 – 2=3. W2(3)=4,4; х2*=х2(3)=1
i=3 s3 = s2 – x2= 3 – 1=2. W3(2)=2,4; х3*=х3(2)=2
x*=(2; 1; 2).
Таблица 9.4'".
s
i=3
i=2
i=1
x3(s)
W3(s)
x2(s)
W2(s)
x1(s)
W1(s)
1,7
2,4
3,7
2,7
4,4
3,2
4,7
3,5
1/4
5,2
6,4
Таким образом, для получения максимальной прибыли в размере 6400 усл. ед. следует вложить по 2000 усл. ед. в первое и третье предприятия и 1000 усл. ед. – во второе предприятие.
Замечание к задаче: Полученное решение можно улучшить, если взять более мелкий шаг оптимизации, например, вкладывать не по 1000 усл. ед., а по 500 усл. ед.
является количество средств, инвестируемых в i-е предприятие.
, следовательно, данная задача может быть решена методом
.
.
.
{1,7; 2}=2, следовательно W2(1)=2 и х2(1)=1, так как максимум в пятом столбце (табл. 9.5) соответствует значению х=1.
{2,4; 3,7; 2,1}=3,7, следовательно W2(2)=3,7 и х2(2)=1, так как максимум в пятом столбце (табл. 9.6) соответствует значению х=1.
{2,7; 4,4; 3,8; 2,3}=4,4, следовательно W2(3)=4,4 и х2(3)=1, так как максимум в пятом столбце (табл. 9.7) соответствует значению х=1.
{3,2; 4,7; 4,5; 4; 3,5}=4,7, следовательно W2(4)=4,7 и х2(4)=1, так как максимум в пятом столбце (табл. 9.8) соответствует значению х=1.
{3,5; 5,2; 4,8; 4,7; 5,2; 4}=5,2, следовательно W2(5)=5,2 и х2(5)=1 и х2(5)=4, так как максимум в пятом столбце (табл. 9.9) соответствует значениям х=1 и х=4.