4.2.1. Инвестор располагает финансовыми средствами в объеме 5 млн. $., которые он может использовать на инновации четырех предприятий, приросты прибыли которых описываются нижеследующей таблицей:
Таблица 4.2.1
Варианты
капиталовложений
x (млн. $.)
Годовой прирост прибыли yi(x) (млн. $.)
на i- м предприятии при капиталовложении
в него в размере x млн. $
y1 (x)
y2 (x)
y3(x)
y4(x)
0, 25
0, 41
0, 55
0,65
0,75
0, 28
0, 45
0, 65
0, 78
0, 9
0, 2
0, 33
0, 42
0, 48
0, 53
0, 15
0, 25
0, 4
0, 5
0, 62
Требуется так распределить капиталовложения между предприятиями, чтобы увеличение прибыли по четырем предприятиям было наибольшим.
Решение
Обозначим yk(xk) – годовой прирост прибыли, полученный на k- м предприятии при величине капиталовложений xk.
Целевая функция z(x1, x2, x3, x4) выражает общий (суммарный) ежегодный прирост прибыли, соответствующий распределению x = (х1, х2, х3, х4) капиталовложений между четырьмя предприятиями.
Обозначим
f1(S) = max y1(x1)
0 x1 S
– максимальный прирост прибыли,
который может быть получен на первом предприятии
в случае выделения ему S единиц капиталовложений.
Так как все функции yk(xk) монотонно возрастающие, то прирост прибыли будет наибольшим, если предприятие освоит все выделенные ему капиталовложения.
Поэтому можно записать, что
f1(S) = max y1 (x1)= y1 (S) (4.2.1)
0£ x1 £ S
Пусть теперь S млн. $. капиталовложений распределяются между первым и вторым предприятиями, т. е. капиталовложения должны быть разделены на две части (x2; S- x2),
где х2 – это капиталовложения, выделяемые второму предприятию,
(S- х2 ) – остающаяся часть для первого предприятия.
В результате такого распределения прирост прибыли на первом предприятии составит величину f1(S- x2), на втором – y2(x2), общий прирост будет равен f1 (S- x2) + y2 (x2).
Будем выбирать величину х2 таким образом, чтобы общий (суммарный) прирост прибыли на 1-м и 2-м предприятиях был наибольшим.
Обозначим как f2 (S) максимальную суммарную прибыль на обоих предприятиях, т. е.
f2 (S) = max { y2 (x2) + f1 (S- x2)}. (4.2.2)
0£ x2 £ S
Отметим, что задача (4.2.2) является однопараметрической задачей (задачей максимизации зависящей только от одной искомой переменной).
Если обозначить через х2*(S) – величину капитальных вложений, выделяемых 2-му предприятию, обеспечивающую максимальный суммарный прирост прибыли первого и второго предприятий (т.е. х2*(S) – это решение задачи (4.2.2)), то можно записать
f2 (S) = y2 (x2*(S))+ f1(S- x2*(S)).
Управление (решение) х2*(S) называется условно-оптимальным, так как оно является оптимальным для второго и первого предприятий при условии, если им выделяются капиталовложения в объеме S единиц.
Далее следует построить еще функции f3(S) и f4(S).
Функция f3(S) выражает максимальный прирост прибыли, который может быть получен на трех предприятиях (первом, втором и третьем) в случае распределения между ними S млн. $. капиталовложений. Эта функция строится по такому же принципу, как и функция
f2 (S), а именно:
f3(S) = max {y3(x3)+ f2(S- x3)} (4.2.3)
0£ x3 £ S
Задача (4.2.3) – это задача принятия решения на 3 -м шаге, т. е. задача определения капиталовложений третьему предприятию. Эта задача решается для каждого значения S=1,..., 5. В результате решения определяются две величины: величина x3*(S) – условно-оптимальный объем капвложений, выделяемый 3 -му предприятию и f3(S) – суммарная прибыль на трех предприятиях в случае наилучшего распределения между ними S млн. $. капиталовложений.
Последней задачей в нашем примере будет задача поиска условно-оптимальных решений x4(S) для четвертого предприятия, т. е. следующая задача максимизации
f4 (S) = max{y4(x4)+ f3(S-x4)} (4.2.4)
0£ x4 £ S
Уравнения (4.2.1 – 4.2.4) называются рекуррентными уравнениями Беллмана. Они решаются последовательно, результаты их решения
(xk*(S), fk(S)), k = 1,...,4,
можно представить в виде нижеследующей итоговой таблицы. В ней на первом этапе проставляются только данные при k = 1, остальные же по мере решения этапов задачи, то есть по мере решения соотношений (4.2.2 – 4.2.4).
Таблица 4.2.2
Условно-оптимальные решения
Кап. вложения
k= 1
k= 2
k= 3
k= 4
S
x1*(S) f1(S)
x2*(S) f2(S)
x3*(S) f3(S)
x4*(S) f4(S)
0 0,25 0,41 0,55 0,65 0,75
0 0,28 0,53 0,70 0,90 1,06
1
0 0,28 0,53 0,73 0,90 1,1
0
0 0,28 0,53 0,73 0,90 1,10
В столбце k =1 представлены результаты решения задачи (4.2.1). Здесь f1(S) = y1(S) и x1*(S) = S, так что фактически каких-либо расчетов при решении задачи (4.2.1) делать не нужно.
Приведем вычислительную схему для решения задачи (4.2.2). Эта схема представлена в следующей таблице:
Таблица 4.2.3
Решение задачи (4.2.2)
Лучший результат
Лучшее управление
S
x2
y2 (x2)
f1(S- x2)
y2(x2)+ f1(S- x2)
f2(S)
x2*(S)
0,28
0,25
0,25
0,28
—
0,28
—
0,28
0,45
0,41
0,25
0,41
0,53
0,45
—
0,53
—
—
—
0,28
0,45
0,65
0,55
0,41
0,25
0,55
0,69
0,7
0,65
—
—
0,70
—
—
—
—
0,28
0,45
0,65
0,78
0,65
0,55
0,41
0,25
0,65
0,83
0,86
0,9
0,78
—
—
—
0,90
—
—
—
—
—
0,28
0,45
0,65
0,78
0,9
0,75
0,65
0,55
0,41
0,25
0,75
0,93
1,0
1,06
1,03
0,9
—
—
—
1,06
—
—
—
—
—
—
—
Таким образом, согласно приведенной таблице, при решении задачи (4.2.2) поиск условно-оптимальных решений x2*(S) производился только среди целых чисел, то есть решалась следующая задача
f2(S) = max { y2 (x2) + f1(S- x2)}
0£ x2 £ S
Это означает, что оптимальное распределение находится среди целых чисел (с точностью до 1 млн. $). Если такая точность не устраивает, то следует расширить область допустимых значений для х2 (с шагом 100 тыс. $., например).
В столбце “х2” таблицы показаны возможные значения х2. Например, при k=3 возможны четыре значения х2 : х2 = 0, 1, 2, 3, то есть, при распределении 3 млн. $. между первым и вторым предприятиями возможны следующие четыре варианта распределения (x2, S- x2) :
(0, 3) – второму предприятию не давать ничего, а отдать все первому;
(1, 2) – второму дать 1 млн. $., первому – 2 млн. $.;
(2, 1) – второму дать 2 млн. $., первому – 1 млн. $.;
(3, 0) – отдать все 3 млн. $. второму предприятию.
В столбце “y2(x2)” записываются значения функции y2 (x2), взятые из начальной таблицы, а в столбце f1 (S- x2) – значения вычисленной на предыдущем шаге функции f1(S). Эти значения берутся из итоговой таблицы, в которой должен быть заполнен столбец “k=1” к моменту вычисления функции f2(S).
Далее производится сложение столбцов y2(x2) и f1(S- x2) и выбор максимального элемента в столбце y2(x2) + f1(S- x2) для каждого значения S.
Жирным шрифтом выделены найденные условно-оптимальные решения x2*(S). В предпоследнем столбце находятся значения функции f2(S), они вместе с x2*(S) записываются в итоговую таблицу в столбец “k=2”.
После решения задачи (2) и заполнения в итоговой таблице столбца “k=2”, решается задача (3) по аналогичной схеме.
Изменяется “шапка” в вычислительной схеме, она при решении будет такой:
Таблица 4.2.4
Решение задачи (4.2.3)
Лучший результат
Лучшее управление
S
x3
y3 (x3)
f2(S-x3)
y3(x3) + f2(S-x3)
f3(S)= max (y3 (x3)+ f2(S- x3))
x3*(S)
Результаты расчетов третьей задачи записаны в столбце “k=3” итоговой таблицы.
Последнюю четвертую задачу достаточно решить при одном значении S= 5 млн. $., чтобы ответить на вопрос об оптимальном распределении 5 млн. $. между четырьмя предприятиями.
Приведем решение задачи (4.2.4) при S = 5, то есть задачи
f4(S) = max {y4(x4) + f3(S- x4)}.
0£ x4 £ S
Таблица 4.2.5
Решение задачи (4)
Лучший результат
Лучшее управление
S= 5
x4
y4(x4)
f3(5-x4)
y4(x4) + f3(5- x4)
f4(5)
x4*(S)
0,15
0,25
0,4
0,5
0,62
1,1
0,90
0,73
0,53
0,28
1,1
1,05
0,98
0,93
0,78
0,62
1,1
—
—
—
—
—
Результат решения этой задачи записан в последней строке в столбце k = 4 итоговой таблицы.
После заполнения сводной таблицы условно-оптимальных решений находится безусловное (окончательное) распределение капиталовложений между четырьмя предприятиями с помощью итоговой таблицы обратным ходом.
В начале определяется оптимальная величина капиталовложений, выделяемая четвертому предприятию.
Она находится из последней строки итоговой таблицы и равна х4(5) = 0 млн. $.
Вычитая из 5 млн. $. величину х4(5) = 0 млн. $, получим остаток, равный 5 млн. $.– величину вложений для первых трех предприятий. В столбце “k=3” находим х3(5) = 1.
Вычитая из суммы, выделявшейся первым трем предприятиям (5 млн. $), величину х3 = 1 млн. $, получим остаток, равный 4 млн. $.– величину вложений для первых двух предприятий. В столбце “k=2” находим х2(4) = 3.
Вычитая из суммы, выделявшейся первым двум предприятиям (4 млн. $), величину х2 = 3 млн. $, получим остаток, равный 1 млн. $.– величину вложений для первого предприятия.
В результате найдено оптимальное распределение капвложений х*= (1, 3, 1, 0), которому соответствует наибольший ежегодный прирост прибыли по объединению, равный f4(5) = 1,1 млн. $.
Ниже приводится решение данной задачи с использованием табличного процессора Excel.
В отличие от «ручного» счета, как это видно в таблицах Excel, отдельная итоговая таблица не строится, но ее отдельные столбцы приведены рядом с основными расчетными.
Вторая таблица строится копированием первой вместе с таблицей исходных данных. После этого вектор y(x2) копии исходных данных заменяется вектором y(x3), а f1 вручную заменяется значениями f2 из предыдущей таблицы. Этим ускоряется построение второй таблицы таким образом, что на решение всей задачи достаточно 20 минут.
Третья таблица строится по аналогии с предыдущей, только на место, где в первой стоял вектор y(x2), замененный во второй вектором y(x3), в третьей ставится y(x4). А на место f2 ставится f3.
Итоги собираются обратным ходом согласно логике метода.
Решение упражнения 4.2.1 в Excel
x
y(x1)
y(x2)
y(x3)
y(x4)
x1**
x2**
0,25
0,28
0,2
0,15
x3**
0,41
0,45
0,33
0,25
x4**
0,55
0,65
0,42
0,4
0,65
0,78
0,48
0,5
f4=
1,1
0,75
0,9
0,53
0,62
В рамках
копировать
f1
x
y(x2)
s
x2
y(x2)
f1(s-x2)
sum
прямым
ходом и
0,25
0,28
0,25
0,25
восстановить
0,41
0,45
0,28
0,28
связи
0,55
0,65
0,41
0,41
0,65
0,78
0,28
0,25
0,53
0,75
0,9
0,45
0,45
Затененное
s
f2=max
x2*
0,55
0,55
вычислять
0,28
0,41
0,69
обратным
0,28
0,45
0,25
0,7
ходом
0,53
0,65
0,65
0,7
0,65
0,65
0,9
0,28
0,55
0,83
1,06
0,45
0,41
0,86
0,65
0,25
0,9
s2
0,78
0,78
x2**
0,75
0,75
0,28
0,65
0,93
x1**
0,45
0,55
0,65
0,41
1,06
0,78
0,25
1,03
0,9
0,9
x
y(x1)
y(x3)
y(x3)
y(x4)
0,25
0,2
0,2
0,15
0,41
0,33
0,33
0,25
0,55
0,42
0,42
0,4
0,65
0,48
0,48
0,5
0,75
0,53
0,53
0,62
f2=max
x
y(x3)
s
x3
y(x3)
f2(s-x3)
sum
0,28
0,2
0,28
0,28
0,53
0,33
0,2
0,2
0,7
0,42
0,53
0,53
0,9
0,48
0,2
0,28
0,48
1,06
0,53
0,33
0,33
s
f3=max
x3*
0,7
0,7
0,2
0,53
0,73
0,28
0,33
0,28
0,61
0,53
0,42
0,42
0,73
0,9
0,9
0,9
0,2
0,7
0,9
1,1
0,33
0,53
0,86
0,42
0,28
0,7
s3
0,48
0,48
x3**
1,06
1,06
0,2
0,9
1,1
0,33
0,7
1,03
0,42
0,53
0,95
0,48
0,28
0,76
0,53
0,53
x
y(x1)
y(x4)
y(x3)
y(x4)
0,25
0,15
0,2
0,15
0,41
0,25
0,33
0,25
0,55
0,4
0,42
0,4
0,65
0,5
0,48
0,5
0,75
0,62
0,53
0,62
f3=max
x
y(x4)
s
x4
y(x4)
f3(s-x4)
sum
0,28
0,15
0,28
0,28
0,53
0,25
0,15
0,15
0,73
0,4
0,53
0,53
0,9
0,5
0,15
0,28
0,43
1,1
0,62
0,25
0,25
s
f4=max
x4*
0,73
0,73
0,15
0,53
0,68
0,28
0,25
0,28
0,53
0,53
0,4
0,4
0,73
0,9
0,9
0,9
0,15
0,73
0,88
1,1
0,25
0,53
0,78
0,4
0,28
0,68
s4=
0,5
0,5
x4**
1,1
1,1
0,15
0,9
1,05
0,25
0,73
0,98
0,4
0,53
0,93
0,5
0,28
0,78
0,62
0,62
Имитация ручного счета в Excel
E14>=F14
B14
E15>=F14
B15
B16
Лучшее
в B14
Лучшее
в B15
Лучшее
в B16
4.2.2. Распределить имеющиеся ресурсы в размере 250 млн.$ между четырьмя предприятиями, если увеличение выпуска в зависимости от предоставленных средств характеризуется таблицей:
Предприятия
Вложенные средства
1.
2.
3.
4.
4.2.2. Решить предыдущую задачу при условии, что исходные ресурсы в размере 200 млн.$ распределяются между пятью предприятиями, в каждое из которых нельзя вкладывать более 140 млн.$, а прибыль, приносимая каждым предприятием, задана таблицей:
Предприятия
Вложенные средства
1.
2.
3.
4.
5.
4.2.3. Найти оптимальное решение в упр. 4.2.1. при условии, что начальные средства:
а) увеличились на 20 млн.$;
б) уменьшились на 20 млн.$ (использовать результат упр. 4.2.1).
4.2.4. Исходная сумма в 300 млн.$ должна быть распределена между тремя предприятиями при следующих условиях: средства, выделяемые каждому предприятию xk (k=1, 2, 3), не могут превышать величины dk млн.$, которую предприятие может освоить, и позволяют получить продукции на сумму fk(xk) млн.$. Значения dk и fk(xk) даны в таблице:
k
1.
2.
3.
dk
fk(xk)
0.4 x12
100 x2
120 x3
Найти оптимальный план распределения средств.
4.2.5. Решить упр. 4.2.4. для четырех предприятий, если функции dk и fk(xk) заданы таблицей:
0, i= 1,..., 4,
max,
x1 
