 |
Динамическое программирование. Распределение капитальных вложений
|
|
|
|
Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с n переменными представляется как много шаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.
Рассмотрим нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fj(xj) прирост мощности или прибыли на j-том предприятии, если оно получит xj рублей капвложений. Требуется найти такое распределение (х1, х2,..., хn) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли
Z=f1(x1)+f2(x2)+...+fn(xn)
при ограничении по общей сумме капвложений х1 + х2 +...+хn = b, причём будем считать, что все переменные xj принимают только целые значения xj =1,2,...
Функции fj(xj) мы считаем заданными, заметив, что их определение -довольно трудоёмкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи.
Введём параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие получит Хк рублей, то каково бы ни было это значение, остальные x-Хк рублей естественно распределить между предприятиями от 10-го до (к-1)-го предприятия, чтобы была получен максимальная прибыль Fk-1(x-xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(x-xk). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:
|
|
|
Fk(x) = max {fk(xk) + Fk-1(x-xk)}
0 £ X £ x
для k=2,3,....,n.Если же k=1,то
F1(x)=f1(x).
В нашем случае производственное объединение состоит из 4-х предприятий (k=4).Общая сумма капвложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей.
Значения функций fj(xj) приведены в таблице 1.
Таблица 1
| xj | ||||||||
| f1(xj) | ||||||||
| f2(xj) | ||||||||
| f3(xj) | ||||||||
| f4(xj) |
Прежде всего заполняем таблице2. Значения f2(x2) складываем со значениями F1(x-x2)=f1(x-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Продолжая процесс табулируем функции F3(x), x3(x) и т.д. В таблице 6 заполняем только одну диагональ для значения x=700.
Таблица 2
 x-х2
| |||||||||
| X2 | F(x-x2) f2(x2) | ||||||||
| 15* | |||||||||
| 15* | 30* | 41* | 52* | 61* | --- | ||||
| 61* | 70* | 77* | --- | --- | |||||
| --- | --- | --- | |||||||
| --- | --- | --- | --- | ||||||
| --- | --- | --- | --- | --- | |||||
| --- | --- | --- | --- | --- | --- | ||||
| --- | --- | --- | --- | --- | --- | --- |
Таблица 3
| x | ||||||||
| F2(x) | ||||||||
| x2(x) | ||||||||
| x2(x) |
Таблица 4
| x-х3
| |||||||||
| Х3 | F(x-x3) f2(x3) | ||||||||
| 15* | 30* | ||||||||
| --- | |||||||||
| 30* | 45* | 60* | 71* | 82* | 91* | --- | --- | ||
| --- | --- | --- | |||||||
| --- | --- | --- | --- | ||||||
| --- | --- | --- | --- | --- | |||||
| --- | --- | --- | --- | --- | --- | ||||
| --- | --- | --- | --- | --- | --- | --- |
Таблица 5
|
|
|
| x | ||||||||
| F3(x) | ||||||||
| X3(x) | ||||||||
| X3(x) |
Таблица 5
| x-х4
| |||||||||
| Х4 | F(x-x4) f2(x4) | ||||||||
| --- | |||||||||
| --- | --- | ||||||||
| --- | --- | --- | |||||||
| --- | --- | --- | --- | ||||||
| --- | --- | --- | --- | --- | |||||
| --- | --- | --- | --- | --- | --- | ||||
| --- | --- | --- | --- | --- | --- | --- |
Zmax = 107 тыс. руб.,
причем четвертому предприятию должно быть выделено
х4* = х4(700) = 200 тыс. руб.
На долю остальных трех предприятий остается 500 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено
х3* = х3(700 - х4*) = х3(500) = 200 тыс. руб.
Продолжая обратный процесс, находим
х2* = х2(700 - х4* - х3*) = х2(300) = 100 тыс. руб.
На долю первого предприятия останется
х1* = 700 - х4* - х3* - х2* = 200 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
| х1* = 200; | Zmax = 107 |
| х2* = 100; | |
| х3* = 200; | |
| х4* = 200 |
Этот план обеспечивает производственному объединению наибольший возможный прирост прибыли 107 тыс. руб.
В качестве проверки правильности решения задачи можно использовать равенство
f1(x1*) + f2(x2*) + f3(x3*) + f4(x4*) = Zmax
f1(200) + f2(100) + f3(200) + f4(200) = 26 + 15 + 30 + 36 = 107 = Zmax
Следовательно, полученные решения верны.
|
|
|
