Далее проводим условную оптимизацию.
4-й шаг. Используем уравнение (*). Обозначим через Z4 функцию, стоящую в скобках, Z4 = 0.1x4+0.5s3; функция Z4 – линейная возрастающая, так как угловой коэффициент 0,1 больше нуля. Поэтому максимум достигается на конце интервала [0, s3] (рис. 42).
|
Следовательно, Z4*(s3) = 0.6s3 при X4*(s3) = s3.
3-й шаг. Уравнение
Находим s3 из уравнений состояний: s3 = 0.8s2-0.1x3 и, подставив его выражение в правую часть уравнения, получаем:
Как и в предыдущем случае, максимум достигается при x3 = s2; т. е. Z3*(s2)=1.02s2 при X3*(s2) = s2.
2-й шаг. Из уравнения состояний: s2 = 0.8s1-0.1x2, поэтому первое функциональное уравнение при k=2 примет вид:
Линейная относительно x2 функция Z2* = 1.31s1-0.002x2 убывает на отрезке [0, s1], и поэтому ее максимум достигается при х2 = 0 (рис. 43).
|
При этом: Z2*(s1) = 1.316s1, при X2*(s1) = 0.
1-й шаг. s1 = 0.8s0-0.1x1. Первое функциональное уравнение при k=1 имеет вид:
Как и в предыдущем случае, максимум достигается в начале отрезка, т. е.: Z1*(s0)=1.5528s0 при X1*(s1)=0.
На этом условная оптимизация заканчивается. Используя ее результат и исходные данные, получаем:
Zmax = Z1*(10000), Zmax = 15528.
Далее:
X1* = 0, Y1* = s0 = 10000
(все средства выделяются второй отрасли) ®
® s1* = 0.8×10000-0.1×0 = 8000 Þ X2* = 0, Y2* = s1 = 8000
(все средства выделяются второй отрасли) ®
® s2* = 0.8×8000-0.1×0 = 6400 Þ X3* = 6400, Y3* = 0 ®
(все средства выделяются первой отрасли) ®
® s3* = 0.8×6400-0.1×6400 = 4480 Þ X4* = 4480, Y4* = 0
(все средства выделяются первой отрасли).
Оптимальная прибыль за 4 года, полученная от двух отраслей производства при начальных средствах 10000 ед., равна 15528 ед. при условии, что первая отрасль получает по годам (0; 0; 6400; 4480), а вторая отрасль соответственно (10000; 8000; 0; 0).
8.6. Дискретная динамическая модель оптимального распределения ресурсов
Для многих экономических и производственных задач характерной является дискретная модель, предполагающая, что величины, описывающие процесс, могут принимать только дискретный ряд значений. Функциональные зависимости в таких задачах задаются, как правило, в виде таблиц, а не аналитически. Однако общая схема их решения методом динамического программирования остается без изменений.
Рассмотрим дискретную динамическую модель на примере задачи распределения инвестиций. Требуется распределить имеющиеся В единиц средств среди 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. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета суммарного дохода:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
