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

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

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

Таблица 21

Gi

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 средств будет получена прибыль GkK), а на инвестирование остальных предприятий (с 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

  2 этап. Безусловная оптимизация.

Определяем компоненты оптимальной стратегии.

1-й шаг. По данным табл. 25 максимальный доход при распределении 5 млн. р. между тремя предприятиями составляет: С1 = 5, F1(5) = 10.8. При этом первому предприятию нужно выделить Х1* = 1 млн. р.

2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий.

С2 = с1 – х1* = 5 – 1 = 4 млн. р.

По данным табл. 24 находим, что оптимальный вариант распределения денежных средств размером 4 млн. р. между вторым и третьим предприятиями составляет:  F2 (4) = 8.6 при выделении второму предприятию Х2* = 2 млн. р.

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

С3 = с2 – х2* = 4 – 2 = 2 млн. р.

По данным табл. 25 находим:

F3(2)  = 5.4 и х3* = 2 млн. р.

Таким образом, оптимальный план инвестирования предприятий:

, который обеспечит максимальный доход, равный

F(5) = G1(1) + G2(2) + G3(2) = 2.2 + 3.2 + 5.4 = 10.8 млн. р.

Яндекс.Метрика