Метод динамического программирования позволяет с успехом решать многие задачи экономического планирования.
Ситуация 2. Министерство располагает денежными средствами –– 8 млн усл. ед., которые необходимо распределить между тремя его заводами. Ожидаемый доход предприятия i при условии, что ему выделяют хмлн усл. ед., равен fi(x). Исходные данные содержатся в следующей таблице (для простоты полагаем, что денежные суммы выражаются целыми числами от 0 до 8).
x
f1(x)
0,1
0,2
0,5
0,5
0,6
0,8
0,9
0,9
f2(x)
0,3
0,35
0,4
0,45
0,5
0,5
0,7
0,75
f3(x)
0,2
0,4
0,55
0,6
0,65
0,7
0,75
0,85
Как распределить имеющиеся средства между заводами, чтобы получить наибольшую прибыль?
Пусть в общем случае надо распределить амлн усл. ед. между nзаводами. Поступим следующим образом. Будем считать, что сначала все денежные средства мы отдаем первому заводу, потом разделим их между первым и вторым, затем между тремя заводами. Каждый раз вначале распределяем 1 млн усл. ед., затем 2, 3 и т. д.
Обозначим через Fk(x)наибольший доход, который можно получить, разделив сумму х между предприятия 1, 2, …, k, где 1 £ k £ n, 0 £ х £ а.
Решение задачи будет состоять в последовательном вычислении значений F1(x), F2(x),…, Fn(x)для всех хот 0 до а. Закончим вычислением Fn(a), которое дает оптимальное значение величины дохода.
Прежде всего, найдем F1(x). Поскольку в этом случае все достается только первому предприятию, то F1(x) = f1(x)для любого x.
Предположим, что мы знаем, как лучше разделить х млн усл. ед. между k – 1предприятиями и какой при этом будет суммарный доход, то есть известны значения Fk– 1(x)для всеххот 0 до а. Теперь распределим эти средства между kпредприятиями.
Мы можем выделить заводу kлюбуюсумму от 0до х. Допустим, что она составляет у млн усл. ед.и прибыль завода в этом случае –– fk(у). Тогда на долю первых k – 1заводов приходится (х – у)млн усл. ед. Как лучше вложить их мы знаем и известна прибыль Fk– 1(х – у), получаемая в итоге. Отсюда выводим, что суммарный доход kпредприятий будет равен Fk– 1(x – у) + fk(у).
Можно было бы выделить заводу k и другую сумму, при этом общий доход мог бы увеличиться. Поэтому надо рассмотреть все возможные варианты вложения средств и выбрать лучший. Следовательно,
. (12.4)
Обозначим Yk(x)значениеy, при котором достигается максимум Fk(x).Таким образом, Yk(x)–– это вложение в предприятие k при условии оптимального распределения х млн усл. ед. между предприятиями 1, 2, …, k. Зная Yn(a)и промежуточные значения Yk(х),можно узнать, какую сумму получит каждое из предприятий при оптимальном распределении денежных средств между ними.
Рассмотрим, как это делается для исходных данных в ситуации 2.
Значения Fk(x)и Yk(х), вычисляемые последовательно, будем располагать в таблицах.
Как уже отмечалось, F1(х) = f1(х)для любого х, поэтому сразу получаем доход при финансировании только первого завода. Сведем эти данные в таблицу:
x
F1(х)
0,0
0,1
0,2
0,5
0,5
0,6
0,8
0,9
0,9
Ясно также, то Y1(x) = xдля всех x:
x
Y1(x)
Переходим к распределению денежных средств между двумя заводами.
По формуле
находим:
Действуя далее аналогичным образом, находим F2(х) и Y2(х) для x = 3, 4, …, 8:
x
F1(х)
0,0
0,1
0,2
0,5
0,5
0,6
0,8
0,9
0,9
F2(х)
0,0
0,3
0,4
0,5
0,8
0,85
0,9
1,1
1,2
x
Y1(x)
Y2(x)
Мы определили наибольший доход при финансировании двух заводов.
Осталось распределить денежные средства между тремя заводами. Расчеты ведем по формуле
.
При этом промежуточные вычисления можно не проводить, т. к. значения F3(х) для x = 0, 1, …, 7 уже не нужны.
Имеем:
В итоге получаем таблицы:
x
F1(х)
0,0
0,1
0,2
0,5
0,5
0,6
0,8
0,9
0,9
F2(х)
0,0
0,3
0,4
0,5
0,8
0,85
0,9
1,1
1,2
F3(х)
1,4
x
Y1(x)
Y2(x)
Y3(x)
Таким образом, наибольший ожидаемый доход F3(8) = 1,4 млн усл. ед.
Заметим, что на этом последнем шаге максимум достигается в двух случаях: 0,85 + 0,55 = 1,4 и 0,8 + 0,6 = 1,4. Если третьему заводу выделить 3 млн усл. ед., то сколько досталось второму заводу мы узнаем из второй таблицы: Y2(8 – 3) = Y2(5) = 2. Аналогично, первому заводу досталось Y1(5 – 2) = Y1(3) = 3 млн усл. ед. В итоге первому заводу достается 3, второму –– 2, третьему –– тоже 3 млн. усл. ед.
Если же третьему заводу выделить 4 млн усл. ед., то в этом случае Y2(8 – 4) = Y2(4) = 1 и Y1(4 – 1) = Y1(3) = 3. То есть первому заводу достается 3, второму –– 1, третьему –– 4 млн усл. ед.
В каждом из этих случаев общая прибыль составляет 1,4 млн усл. ед.
Заметим, что величина оптимальной прибыли при распределении денежных ресурсов между предприятиями не зависит от их нумерации.
. (12.4)
.
