Дискретная динамическая модель оптимального распределения ресурсов

Для многих экономических и производственных задач характерной является дискретная модель, предполагающая, что величины, описывающие процесс, могут принимать только дискретный ряд значений. Функциональные зависимости в таких задачах задаются, как правило, в виде таблиц, а не аналитически. Однако общая схема их решения методом динамического программирования остается без изменений.

Рассмотрим дискретную динамическую модель на примере задачи распределения инвестиций. Требуется распределить имеющиеся В единиц средств среди n предприятий, доход g_i(x_i) от которых в зависимости от количества вложенных средств x_i определяется матрицей , приведенной в табл. 21 так, чтобы суммарный доход со всех предприятий был бы максимальным.

Таблица 21

Запишем математическую модель задачи.

Определить удовлетворяющий условиям

(32), (33)

и обеспечивающий максимум целевой функции

(34)

Очевидно, эта задача может быть решена простым перебором всех возможных вариантов распределения В единиц средств по n предприятиям, например на сетевой модели. Однако решим ее более эффективным методом, который заключается в замене сложной многовариантной задачи многократным решением простых задач с малым количеством исследуемых вариантов.

С этой целью разобьем процесс оптимизации на n шагов и будем на каждом k-том шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом естественно считать, что в остальные предприятия (с первого по (k – 1)-е) тоже вкладываются средства, и поэтому на инвестирование предприятий с k-го по n-е остаются не все средства, а некоторая меньшая сумма C_k £ B. Эта величина и будет являться переменной состояния системы. Переменной управления на k-том шаге назовем величину x_k средств, вкладываемых в k-тое предприятие. В качестве функции Беллмана F_k(C_k) на k-том шаге можно выбрать максимально возможный доход, который можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось C_k средств. Очевидно, что при вложении в k-е предприятие x_k средств будет получена прибыль g_k(x_k), а система к (k + 1)-му шагу перейдет в состояние S_k+1 и, следовательно, на инвестирование предприятий с (k + 1)-го до n-го останется C_k+1=(C_k-x_k) средств.

Таким образом, на первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств C_n, . Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е.

На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на k-м шаге для инвестирования предприятий с k-го по n-е осталось C_k средств ( ). Тогда после вложения в k-ое предприятие x_k средств будет получена прибыль g_k(С_k), а на инвестирование остальных предприятий (с k-го по n-е) останется средств. Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), будет равен:

(30)

Максимум выражения (30) достигается на некотором значении , которое является оптимальным управлением на k-ом шаге для состояния системы S_k. Действуя таким образом, можно определить функцию Беллмана и оптимальные управления до шага k = 1.

Значение функции Беллмана F₁(C₁) представляет собой максимально возможный доход со всех предприятий, а значение , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина и оптимальным управлением на k-м шаге является то значение x_k, которое обеспечивает максимум дохода при соответствующем состоянии системы S_k.

Пример 73. На развитие трех предприятий выделено 5 млн. р. Известна эффективность капитальных вложений в каждое предприятие, заданная значением нелинейной функции g_i(x_i) представленной в табл. 22. Необходимо распределить выделенные средства между предприятиями таким образом, чтобы получить максимальный суммарный доход.

Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах x_i = {0, 1, 2, 3, 4, 5} млн. р.

Таблица 22

Решение.1 этап. Условная оптимизация.

1-й шаг: k = 3. Предположим, что все средства в количестве x₃ = 5 млн. р. отданы третьему предприятию. В этом случае максимальный доход, как это видно из табл. 23, составит g₃(X₃) = 6.9 тыс. р., следовательно:

F₃(c₃) = g₃(x₃).

Таблица 23

2-й шаг: k = 2. Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим предприятиями. При этом соотношение Беллмана имеет вид

на основе которого составлена табл. 24:

Таблица 24

3-й шаг: k = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета суммарного дохода:

на основе которого составлена табл. 25:

Таблица 25

Не нашли, что искали? Воспользуйтесь поиском по сайту: