Динамическое программирование.

21

Распределение капитальных вложений

Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.

Знакомство с методом динамического программирования проще всего начать с рассмотрения нелинейной задачи распределения ресурсов между предприятиями одного производственного объединения или отрасли. Для определенности можно считать, что речь идет о распределении капитальных вложений.

Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f_i(x_i) прирост мощности или прибыли на j-м предприятии, если оно получит x_i рублей капитальных вложений. Требуется найти такое распределение (x₁, x₂, ..., x_n) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

 

z = f₁(x₁) + f₂(х₂) +... + f_n(x_n)

при ограничении по общей сумме капитальных вложений

                

                       x₁ + x₂ +... + x_n = b

причем будем считать, что все переменные x_j принимают только целые неотрицательные значения

x_j = 0, или 1, или 2, или 3, ...

Функции f_j(x_j) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача.

Воспользуемся методом динамического программирования для решения этой задачи.

Введем параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получают x рублей. Параметр x может изменяться от 0 до b. Если из x рублей k-е предприятие получит x_k рублей, то каково бы ни было это значение, остальные x - x_k рублей естественно распределить между предприятиями от первого до (К-1)-го так, чтобы была получена максимальная прибыль F_k-1(x - x_k). Тогда прибыль k предприятий будет равна f_k(x_k) + F_k-1(x - x_k). Надо выбрать такое значение x_k между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению

 

F_k(x)=max{f_k(x_k) + F_k-1(x-x_k)}

0 £ x_k £ x

для k = 2, 3, 4, ..., n. Если же k=1, то

F₁(x) = f₁(x)

Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций f_j(x_j) приведены в таблице 1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.

22

Таблица I

 

Прежде всего заполняем табл. 2. Значения f₂(x₂) складываем со значениями F₁(x - x₂) = f₁(x- x₂) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.

Продолжая процесс, табулируем функции F₃(x), (x) и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700. Наибольшее число на этой диагонали:

Z_max = 155 тыс. руб.,

причем четвертому предприятию должно быть выделено

 х^*₄  = ₄ (700) = 300 тыс. руб.

На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено

x^*₃ = ₃ (700-x^*₄) = ₃ (400) = 200 тыс. руб.

Продолжая обратный процесс, находим

x*₂ = ₂ (700 - x*₄ - x*₃) = ₂ (200) = 100 тыс. руб.

На долю первого предприятия остается

x*₁ = 700 - x*₄ - x*₃ - x*₂ = 100 тыс. руб.

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:

x*₁ =100; x*₂ =100; x*₃ = 200; x*₄ = 300.

Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 155 тыс. руб.

Студенту рекомендуется проверить выполнение равенства

f₁(x*₁) + f₂(x*₂) + f₃(x*₃) + f₄(x*₄) = z _max

Таблица 2

	x - x2	0 100 200 300 400 500 600 700
x2	F1(x - x2) f2(x2)	0 20 34 46 53 55 60 60
0	0	0 20* 34 46 53 55 60 60
100	18	18 38* 52* 64 71 73 78
200	29	29 49 63 75 82 84
300	45	45 65* 79 91 98
400	62	62 82* 96 108
500	78	78 98* 112*
600	90	90 110
700	98	98                                                              .

 

23

                                                                                                            

 

Таблица 3

x	0 100 200 300 400 500 600 700
F2(x)	0  20  38  52  65  82  98 112
` (x)	0    0 100 100 300 400 500 500

 

                                                                                                                 Таблица 4

	x - x3	0 100 200 300 400 500 600 700
x3	F2(x - x3) f3(x3)	0 20 38 52 65 82 98 112
0	0	0 20 38 52 65 82 98 112
100	25	25* 45* 63* 77 90 107 123
200	41	41 61 79* 93 106 123
300	52	52 72 94* 112 126
400	74	74 94* 112* 126*
500	82	82 102 120
600	88	88 106
700	90	90                                                              .

 

Таблица 5

x	0 100 200 300 400 500 600 700
F3(x)	0  25  45  63  79  94 112 126
(x)	0  100 100 100 200 400 400 400

 

Таблица 6

	x - x4	0 100 200 300 400 500 600 700
x4	F3(x - x4) f4(x4)	0 25 45 63 79 94 112 126
0	0	126
100	30	142
200	52	146
300	76	155*
400	90	153
500	104	149
600	116	141
700	125	125                                                              .

 

⇐ Предыдущая12345Следующая ⇒

Поделиться: