- •По дисциплине «Прикладная математика»
- •1. Линейная производственная задача
- •2. Двойственная задача
- •Задача о «расшивке узких мест производства»
- •3. Транспортная задача линейного программирования
- •4. Динамическое программирование. Распределение капитальных вложений
- •5. Динамическая задача управления производством и запасами.
4. Динамическое программирование. Распределение капитальных вложений
Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с 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) мы считаем заданными, заметив, что их определение - довольно трудоёмкая экономическая задача.
Воспользуемся методом динамического программирования для решения этой задачи.
Введём параметр состояния и определим функцию состояния. За параметр состояния примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk() определим как максимальную прибыль на первых k предприятиях, если они вместе получат рублей. Параметр может меняться от 0 до b. Если из рублей k-ое предприятие получит Хк рублей, то каково бы ни было это значение, остальные -Хк рублей естественно распределить между предприятиями от 1-го до (к-1)-го предприятия, чтобы была получена максимальная прибыль Fk-1(-xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(-xk). Надо выбрать такое значение xk между 0 и , чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:
Fk() = max {fk(xk) + Fk-1(-xk)}
0 X
для k=2,3,....,n .Если же k=1 ,то
F1()=f1().
В нашем случае производственное объединение состоит из 4-х предприятий (n=4).Общая сумма капвложений равна 700 тыс. рублей (b=700) , выделяемые предприятиям суммы кратны 100 тыс. рублей.
Значения функций fj(xj) приведены в таблице 1где, например, число 76 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 76 тыс. руб.
Таблица 1
xj |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
f1(xj) |
0 |
42 |
58 |
71 |
80 |
89 |
95 |
100 |
f2(xj) |
0 |
30 |
49 |
63 |
6 |
69 |
65 |
60 |
f3(xj) |
0 |
22 |
37 |
49 |
59 |
68 |
76 |
82 |
f4(xj) |
0 |
50 |
68 |
82 |
92 |
100 |
107 |
112 |
Прежде всего заполняем таблицe 2. Значения f2(x2) складываем со значениями F1(-x2)=f1(-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Продолжая процесс табулируем функции F3(), x3() и т.д. В таблице 6 заполняем только одну диагональ для значения =700.
Таблица 2
-х2 |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 | |
X2 |
F(-x2) f2(x2) |
0 |
42 |
58 |
71 |
80 |
89 |
95 |
100 |
0 |
0 |
0 |
42* |
58 |
71 |
80 |
89 |
95 |
100 |
100 |
30 |
30 |
72* |
88 |
101 |
110 |
119 |
125 |
--- |
200 |
49 |
49 |
91* |
107* |
120 |
129 |
138 |
--- |
--- |
300 |
63 |
63 |
105 |
121* |
134* |
143* |
--- |
--- |
--- |
400 |
6 |
6 |
48 |
64 |
77 |
--- |
--- |
--- |
--- |
500 |
69 |
69 |
111 |
127 |
--- |
--- |
--- |
--- |
--- |
600 |
65 |
65 |
107 |
--- |
--- |
--- |
--- |
--- |
--- |
700 |
60 |
60 |
--- |
--- |
--- |
--- |
--- |
--- |
--- |
Таблица 3
|
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
F2() |
0 |
42 |
72 |
91 |
107 |
121 |
134 |
143 |
2() |
0 |
0 |
100 |
200 |
200 |
300 |
300 |
300 |
Таблица 4
-х3 |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 | |
Х3 |
F(-x3) f3(x3) |
0 |
42 |
72 |
91 |
107 |
121 |
134 |
143 |
0 |
0 |
0 |
42* |
72* |
91 |
107 |
121 |
134 |
143 |
100 |
22 |
22 |
64 |
94* |
113* |
129* |
143 |
156 |
--- |
200 |
37 |
37 |
79 |
109 |
128 |
144* |
158* |
--- |
--- |
300 |
49 |
49 |
91 |
121 |
140 |
156 |
--- |
--- |
--- |
400 |
59 |
59 |
101 |
131 |
150 |
--- |
--- |
--- |
--- |
500 |
68 |
68 |
110 |
140 |
--- |
--- |
--- |
--- |
--- |
600 |
76 |
76 |
118 |
--- |
--- |
--- |
--- |
--- |
--- |
700 |
82 |
82 |
--- |
--- |
--- |
--- |
--- |
--- |
--- |
Таблица 5
|
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
F3() |
0 |
42 |
72 |
94 |
113 |
129 |
144 |
158 |
3() |
0 |
0 |
0 |
100 |
100 |
100 |
200 |
200 |
Таблица 6
-х4 |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 | |
Х4 |
F(-x4) f4(x4) |
0 |
42 |
72 |
94 |
113 |
129 |
144 |
158 |
0 |
0 |
|
|
|
|
|
|
|
158 |
100 |
50 |
|
|
|
|
|
|
194 |
--- |
200 |
68 |
|
|
|
|
|
197* |
--- |
--- |
300 |
82 |
|
|
|
|
195 |
--- |
--- |
--- |
400 |
92 |
|
|
|
186 |
--- |
--- |
--- |
--- |
500 |
100 |
|
|
172 |
--- |
--- |
--- |
--- |
--- |
600 |
107 |
|
149 |
--- |
--- |
--- |
--- |
--- |
--- |
700 |
112 |
112 |
--- |
--- |
--- |
--- |
--- |
--- |
--- |
Zmax = 197 тыс. руб., причем четвертому предприятию должно быть выделено х4* = 4(700) = 200 тыс. руб. На долю остальных трех предприятий остается 500 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено х3* = 3(700 - х4*) = х3(500) = 100 тыс. руб.
Продолжая обратный процесс, находим х2* = 2(700 - х4* - х3*) = х2(400) = 200 тыс. руб.
На долю первого предприятия останется х1* = 700 - х4* - х3* - х2* = 200 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
х1* = 200; |
Zmax = 197 |
х2* = 200; | |
х3* = 100; | |
х4* = 200 |
Этот план обеспечивает производственному объединению наибольший возможный прирост прибыли 197 тыс. руб. В качестве проверки правильности решения задачи можно использовать равенство
f1(x1*) + f2(x2*) + f3(x3*) + f4(x4*) = Zmax
f1(200) + f2(200) + f3(100) + f4(200) = 58 + 49 + 22 + 68 = 197 = Zmax
Следовательно, полученные решения верны.