57)Рекурентное соотношение методов динамического планирования.

Ответ: В основе динамического программирования лежит принцип оптимальности, указывающий на процедуру построения оптимального управления. Так как оптимальной стратегией может быть только та, которая одновременно оптимальна и для любого количества оставшихся шагов, ее можно строить по частям: сначала для последнего этапа, затем для двух последних, для трех и т.д., пока не придем к первому шагу. Приведем математическую формулировку принципа оптимальности для задач с аддитивным критерием оптимальности (сепарабельная функция цели). Для простоты будем считать, что начальное   и конечное   состояния системы заданы. Обозначим через   значение функции цели на первом этапе при начальном состоянии системы   и при управлении   , через   - соответствующее значение функции цели только на втором этапе,…, через   - на i - м этапе, …, через   - на N -м этапе. Очевидно, что Z =   (7.1) Надо найти оптимальное управление u^* = (   ) такое, что обеспечивает экстремум целевой функции (х.х) при ограничениях u   Ω. Для решения этой задачи введем обозначения. Пусть Ω_N, Ω_N -1, N, …, Ω_1, N   Ω – соответственно области определения на последнем этапе, двух последних и т.д.; Ω – область определения исходной задачи. Обозначим через F₁(x_N-1), F₂(x_N-2), …,F_k(x_N-k), … F_N(x₀) - соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т.д., на к последних и т.д., на всех N этапах. Начинаем с последнего этапа. Пусть x_N-1 – возможные состояния системы на начало N – го этапа. Находим:

 .(7.2) u_N   Ω Для двух последних этапов получаем

 . (7.3)

u_N-1   Ω Аналогично:

 (7.4)

u_N-2   Ω

…………………………………………………………………………

 , (7.5)

u_N-k+1   Ω

…………………………………………………………………………….

 . (7.6)

u₁   Ω. Выражение (7.6) представляет собой математическую запись принципа оптимальности. Выражение (7.5) – общая форма записи условно-оптимального значения функции цели для к оставшихся этапов. Выражения (7.2) – (7.6) называются рекуррентными соотношениями (функциональными уравнениями) Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т.е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N-1 этапах и т.д.

58)Принцип оптимальности Белмана на примере задачи.

Ответ: Решим с помощью метода динамического программирования задачу определения оптимальной степени участия синхронных двигателей в компенсации реактивной мощности Q_∑ = 1,8 Мвар, если каждый из двигателей может выдать реактивную мощность соответственно: Q_Д1 = 0,6 Мвар; Q_Д2 = 0,5 Мвар и Q_Д3 = 1,2 Мвар. Потери мощности ΔР, возникающие в синхронном двигателе, зависят от реактивной мощности Q_Д, генерируемой двигателем. ΔР_i представляются нелинейными зависимостями от Q_ДI. Величина потерь мощности, возникающих в первом двигателе составит ΔР₁ = 0,00749 Q₁ + 0.01104   , во втором двигателе - ΔР₂ = 0,01294 Q₂ + 0.02244  и в третьем – ΔР₃ = 0,00973 Q₃ + 0.00797   .

Задача состоит в том, чтобы отыскать такие мощности Q _i, i = 1,2,3, которые обеспечили бы минимум суммарных потерь ΔР_∑ = ΔР₁ + ΔР₂ + +ΔР₃ при соблюдении ограничений по величинам Q_Д i, i =1,2,3, а также по суммарной реактивной мощности Q_∑ = 1,8 Мвар, которую должны скомпенсировать синхронные двигатели. В математическом плане задача сводится к минимизации целевой функции F(x) = ∑f_i(x_i) → min; (7.7)

f₁(x₁) = 0,00749 x₁ + 0,01104   , f₂(x₂) = 0,01294 x₂ + 0,02244   , f₃(x₃) = 0,00973 x₃ + 0,00797   . при соблюдении ограничений: х₁ + х₂ + х₃ = 1,8;

х₁ ≤ 0,6; х₂ ≤ 0,5; х₃ ≤ 1,2; х_i ≥ 0, i = 1,2,3. При использовании метода динамического программирования производим дискретизацию переменных Δx = 0,1. т.е. строим сетку X = 0,0; 1,8 с шагом Δх. Формирование рекуррентных соотношений начинается с к = 1. Поскольку здесь не требуется распределения ресурса между переменными, то рекуррентное соотношение примет вид F₁(X) = f₁(X); поэтому

F₁(0) = f₁(0) = 0,00749·0 + 0,01104 0² = 0;

F₁(0,1) = f₁(0,1) = 0,00749·0,1 + 0,01104 0,1² = 0,00086;

……………………………………………………………

F₁(0,6) = f₁(0,6) = 0,00749·0,6 + 0,01104 0,6² = 0,00847.

Расчеты F₁(X) прекращаются для Х = 0,6, поскольку имеются ограничения х₁ ≤ 0,6.

На втором шаге рекуррентное соотношение имеет вид

F₂(X) = min [F₁(X-x₂) + f₂(x₂)], в силу чего будем иметь:

для Х = 0 F₂(0) = 0 + 0,01294 0 +0,02244 0² = 0;

для Х = 0,1 F₂(0,1) = 0,00086 + 0,01294 0 +0,02244 0² = 0,00086 (х₂=0)

F₂(0,1) = 0 + 0,01294 0,1 +0,02244 0,1² = 0,00152 (х₂ = 0,1)

т.е. минимальным F₂(0,1) = 0,00086 (отмечаем это значение);

для Х =0,2 F₂(0,2) = 0,00194 + 0,01294 0 +0,02244 0² = 0,00194 (х₂=0,0);

F₂(0,2)=0,00086+0,01294 0,1+0,02244 0,1²=0,00238 (х₂=0,1);

F₂(0,2)=0 + 0,01294 0,2 + 0,02244 0,2² = 0,00349 (х₂ = 0,2)

Подобные расчеты продолжаем до Х – 1,1, чем обеспечиваеися одновременное соблюдение ограничений х₁ ≤ 0,6 и х₂ ≤ 0,5. При этом для Х = 1,1 вычисляетсяF₂(1,1) лишь для одного допустимого значения х₂=0,5:

F₂(1,1) = 0,00847 + 0,01294 0,5 + 0,02244 0,5² = 0,02055.

На третьем шаге по рекуррентному соотношению F₃(X) = min [F₂(X-x₃) + f₃(x₃)] вычисляется серия значений F₃(1,8) для х₃=0,7;0,8;0,9;1,0;1,1;1,2. Для х₃ ≤ 0,7расчеты не проводятся, поскольку в этом случае никакие сочетания х₁ и х₂ не обеспечат выполнения ограничения х₁ + х₂ + х₃ = 1,8.

Ход решения задачи методом динамического программирования при Δx = 0,1 Мвар представлен в табл. 7.1

Таблица 7.1

Х	x1	F1(X)	x2	F2(X)	x3	F3(X)
0,0	0,0		0,0
0,1	0,1	0,00086	0,0	0,00086
0,2	0,2	0,00194	0,0	0,00194
0,3	0,3	0,00324	0,0	0,00324
0,4	0,4	0,00476	0,1	0,00476
0,5	0,5	0,00651	0,1	0,00628
0,6	0,6	0,00847	0,1	0,00803
0,7			0,1	0,00998
0,8			0,2	0,01196
0,9			0,3	0,01437
1,0			0,4	0,01724
1,1			0,5	0,02055
1,2
1,3
1,4
1,5
1,6
1,7
1,8					0,9	0,02958

 

Заполнением строки Х = 1,8 завершается «прямой ход» метода динамического программирования. Из табл. 7.1 видно, что минимальное значение целевой функцииF₃(1,8) = 0,02958. Ему соответствует   = 0.9. Тогда х₁ + х₂ = 1,8 – 0,9 = 0,9. Из табл 7.1 видно, что F₂(0,9) = 0, 1437. Ему соответствует   = 0,3. Наконец,   = 1,8 -   -   = 0,6. Таким образом, получено решение   = 0,6;   = 0,3;   = 0.9, а ΔР_∑ = ΔР₁ + ΔР₂ + ΔР₃ = F(x) = ∑ f_i(x_i) → min =0,02958 МВт.