|
Дискретная динамическая модель оптимального распределения ресурсов
Для многих экономических и производственных задач характерной является дискретная модель, предполагающая, что величины, описывающие процесс, могут принимать только дискретный ряд значений. Функциональные зависимости в таких задачах задаются, как правило, в виде таблиц, а не аналитически. Однако общая схема их решения методом динамического программирования остается без изменений.
Рассмотрим дискретную динамическую модель на примере задачи распределения инвестиций. Требуется распределить имеющиеся В единиц средств среди n предприятий, доход gi(xi) от которых в зависимости от количества вложенных средств xi определяется матрицей , приведенной в табл. 21 так, чтобы суммарный доход со всех предприятий был бы максимальным.
Таблица 21
gi
x
| g1
| g2
| . . .
| gi
| . . .
| gn
| x1
| g1(x1)
| g2(x1)
| …
| gi(x1)
|
| gn(x1)
| x2
| g1(x2)
| g2(x2)
| …
| gi(x2)
|
| gn(x2)
| xi
| …
| …
| …
| gi(xi)
| …
| …
| xn
| g1(xn)
| g2(xn)
| …
| gi(xn)
|
| gn(xn)
|
Запишем математическую модель задачи.
Определить удовлетворяющий условиям
(32), (33)
и обеспечивающий максимум целевой функции
(34)
Очевидно, эта задача может быть решена простым перебором всех возможных вариантов распределения В единиц средств по n предприятиям, например на сетевой модели. Однако решим ее более эффективным методом, который заключается в замене сложной многовариантной задачи многократным решением простых задач с малым количеством исследуемых вариантов.
С этой целью разобьем процесс оптимизации на n шагов и будем на каждом k-том шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом естественно считать, что в остальные предприятия (с первого по (k – 1)-е) тоже вкладываются средства, и поэтому на инвестирование предприятий с k-го по n-е остаются не все средства, а некоторая меньшая сумма Ck £ B. Эта величина и будет являться переменной состояния системы. Переменной управления на k-том шаге назовем величину xk средств, вкладываемых в k-тое предприятие. В качестве функции Беллмана Fk(Ck) на k-том шаге можно выбрать максимально возможный доход, который можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось Ck средств. Очевидно, что при вложении в k-е предприятие xk средств будет получена прибыль gk(xk), а система к (k + 1)-му шагу перейдет в состояние Sk+1 и, следовательно, на инвестирование предприятий с (k + 1)-го до n-го останется Ck+1=(Ck-xk) средств.
Таким образом, на первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств Cn, . Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е.
На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на k-м шаге для инвестирования предприятий с k-го по n-е осталось Ck средств ( ). Тогда после вложения в k-ое предприятие xk средств будет получена прибыль gk(Сk), а на инвестирование остальных предприятий (с k-го по n-е) останется средств. Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), будет равен:
(30)
Максимум выражения (30) достигается на некотором значении , которое является оптимальным управлением на k-ом шаге для состояния системы Sk. Действуя таким образом, можно определить функцию Беллмана и оптимальные управления до шага k = 1.
Значение функции Беллмана F1(C1) представляет собой максимально возможный доход со всех предприятий, а значение , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина и оптимальным управлением на k-м шаге является то значение xk, которое обеспечивает максимум дохода при соответствующем состоянии системы Sk.
Пример 73. На развитие трех предприятий выделено 5 млн. р. Известна эффективность капитальных вложений в каждое предприятие, заданная значением нелинейной функции gi(xi) представленной в табл. 22. Необходимо распределить выделенные средства между предприятиями таким образом, чтобы получить максимальный суммарный доход.
Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах xi = {0, 1, 2, 3, 4, 5} млн. р.
Таблица 22
x
| g1
| g2
| g3
| 0
| 0
| 0
| 0
| 1
| 2.2
| 2
| 2.8
| 2
| 3
| 3.2
| 5.4
| 3
| 4.1
| 4.8
| 6.4
| 4
| 5.2
| 6.2
| 6.6
| 5
| 5.9
| 6.4
| 6.9
|
Решение.1 этап. Условная оптимизация.
1-й шаг: k = 3. Предположим, что все средства в количестве x3 = 5 млн. р. отданы третьему предприятию. В этом случае максимальный доход, как это видно из табл. 23, составит g3(X3) = 6.9 тыс. р., следовательно:
F3(c3) = g3(x3).
Таблица 23
x3
c3
| 0
| 1
| 2
| 3
| 4
| 5
| F3(c3)
| x3*
| 0
| 0
| -
| -
| -
| -
| -
| 0
| 0
| 1
| -
| 2,8
| -
| -
| -
| -
| 2,8
| 1
| 2
| -
| -
| 5,4
| -
| -
| -
| 5,4
| 2
| 3
| -
| -
| -
| 6,4
| -
| -
| 6,4
| 3
| 4
| -
| -
| -
| -
| 6,6
| -
| 6,6
| 4
| 5
| -
| -
| -
| -
| -
| 6,9
| 6,9
| 5
| 2-й шаг: k = 2. Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим предприятиями. При этом соотношение Беллмана имеет вид
на основе которого составлена табл. 24:
Таблица 24
x2
c2
| 0
| 1
| 2
| 3
| 4
| 5
| F2(c2)
| x2*
| 0
| 0+0
| -
| -
| -
| -
| -
| 0
| 0
| 1
| 0+2,8
| 2+0
| -
| -
| -
| -
| 2,8
| 0
| 2
| 0+5,4
| 2+2,8
| 3,2+0
| -
| -
| -
| 5,4
| 0
| 3
| 0+6,4
| 2+5,4
| 3,2+2,8
| 4,8+0
| -
| -
| 7,4
| 1
| 4
| 0+6,6
| 2+6,4
| 3,2+5,4
| 4,8+2,8
| 6,2+0
| -
| 8,6
| 2
| 5
| 0+6,9
| 2+6,6
| 3,2+6,4
| 4,8+5,4
| 6,2+2,8
| 6,4+0
| 10,2
| 3
|
3-й шаг: k = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета суммарного дохода:
на основе которого составлена табл. 25:
Таблица 25
x1
c1
| 0
| 1
| 2
| 3
| 4
| 5
| F1(c1)
| x1*
| 0
| 0+0
| -
| -
| -
| -
| -
| 0
| 0
| 1
| 0+2,8
| 2,2+0
| -
| -
| -
| -
| 2,8
| 0
| 2
| 0+5,4
| 2,2+2,8
| 3+0
| -
| -
| -
| 5,4
| 0
| 3
| 0+7,4
| 2,2+5,4
| 3+2,8
| 4,1+0
| -
| -
| 7,6
| 1
| 4
| 0+8,6
| 2,2+7,4
| 3+5,4
| 4,1+2,8
| 5,2+0
| -
| 9,6
| 1
| 5
| 0+10,2
| 2,2+8,6
| 3+7,4
| 4,1+5,4
| 5,2+2,8
| 5,9
| 10,8
| 1
|
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|