On dynamic programming on the values in the semigroup

Full Text

1. Статья продолжает исследования применения динамического программирования [1, 2]. В ней для упрощения алгоритма [2] используется не рассматривавшаяся ранее в общей формулировке и в указанных ниже частных случаях следующая задача дискретного оптимального управления. Задача A. Пусть известно следующее: - пространства A, B; - множество шагов T (1 < |T | < ∞), наделенное строгим порядком иными словами, отношением со свойствами (i j) ⇒ (i = j)(∀i, j ∈ T ), (i g) ∧ (g j) ⇒ (i , j)(∀i, g, j ∈ T ), © 2016 Самарский государственный технический университет. Образец для цитирования О в ч и н н и к о в В. Г. К динамическому программированию по значениям в полугруппе // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2016. T. 20, No 1. С. 158-166. doi: 10.14498/vsgtu1473. Сведения об авторе Валерий Гаврилович Овчинников (ovg.samara@mail.ru), старший преподаватель, каф. разработки нефтяных и газовых месторождений. 158 К динамическому программированию по значениям в полугруппе имеющее подмножество начальных шагов T0 = {i ∈ T |∅ = {j ∈ T |j i}}(= T ), обозначаемые {π(i)} одноэлементные подмножества j ∈ T |(j i) ∧ (∅ = {g ∈ T |j i}) (∀i ∈ T \T0 ) g и удовлетворяющее равенству ∅ = M ∩ T0 подмножество финальных шагов M = {i ∈ T |τ (i) = ∅}, где τ (i) = {j ∈ T \T0 |π(j) = i}; - функции X, U, S с конечными множественными значениями X(i) ⊂ A(∀i ∈ T ), U (i, α) ⊂ B(∀i ∈ T \T0 )(∀α ∈ A), S(i, α, β) ⊂ A(|S(i, α, β)| 1)(∀i ∈ T \T0 )(∀α ∈ A)(∀β ∈ B); - обозначение D множества называемых процессами пар (x, u) функций x, u со значениями xi ∈ A(∀i ∈ T ), ui ∈ B(∀i ∈ T ) при ограничениях xi = ui (∀i ∈ T0 ), xi ∈ X(i)(∀i ∈ T ), xi ∈ S(i, xπ(i) , ui ) ui ∈ U (i, xπ(i) ) (∀i ∈ T \T0 ); - множество P с операцией ⊥ и порядком порядка по правилам (p1 (∀i ∈ T \T0 ), как расширением строгого p2 ) ⇔ (p1 p2 ) ∨ (p1 = p2 )(∀p1 , p2 ∈ P ), являющееся линейно упорядоченной абелевой полугруппой P, ⊥, и, таким образом, имеющее свойства (p1 ⊥p2 )⊥p3 = p1 ⊥(p2 ⊥p3 )(∀p1 , p2 , p3 ∈ P ) (ассоциативность ⊥), p1 ⊥p2 = p2 ⊥p1 (∀p1 , p2 ∈ P ) (коммутативность ⊥), (p1 p2 ) ∨ (p2 p1 )(∀p1 , p2 ∈ P ) (линейность ), (p1 p2 ) ⇒ (p1 ⊥p3 ) (p2 ⊥p3 )(∀p1 , p2 , p3 ∈ P ) (стабильность относительно ⊥); - обозначение обобщённой операции ⊥ с результатом ⊥ q(i) как элеi∈I i∈I ментом Λ(|I|, ω, q) ∈ P, определяемым по функции q : I → P (∅ = I ⊂ T ) из условий k > 1 ⇒ Λ(k, ω, q) = Λ(k - 1, ω, q)⊥q(ω(k))(∀k ∈ N|I| ), Λ(1, ω, q) = q(ω(1)) независимо от выбора биекции ω : N|I| → I (Nm = {1, . . . , m}(∀m ∈ N)) (ср. с замечаниями N.B. [3, c. 62]); 159 О в ч и н н и к о в В. Г. - затраты шагов f (i, γ, α, β)(∈ P )(∀i ∈ T \T0 )(∀γ, α ∈ A)(∀β ∈ B); - обозначение min( ) Q(γ) наименьшего по порядку γ∈Γ значения функции Q : Γ → P. Требуется найти называемую оптимальным процессом пару (x∗ , u∗ ) ∈ D, удовлетворяющую равенству ⊥ i∈T \T0 f i, x∗ , x∗ , u∗ = min i π(i) i ( ) ⊥ i∈T \T0 (x,u)∈D f (i, xi , xπ(i) , ui ). Замечание 1. Если P ⊂ W ∈ {R, Q, Z, N}(1 < |P |), p⊥q = max(p, q)(∀p, q ∈ P ), , то оптимальный процесс (x∗ , u∗ ) ∈ D находится из условия означает max f (i, x∗ , x∗ , u∗ ) = min i π(i) i i∈T \T0 max f (i, xi , xπ(i) , ui ). (x,u)∈D i∈T \T0 Замечание 2. Если P = {p ∈ W |0 p}(W ∈ {R, Q, Z, N}), p⊥q = p + q (либо p⊥q = p · q) (∀p, q ∈ P ), , то оптимальный процесс (x∗ , u∗ ) ∈ D находится из условия означает f (i, x∗ , x∗ , u∗ ) = min i π(i) i i∈T \T0 (x,u)∈D f (i, xi , xπ(i) , ui ) i∈T \T0 f (i, x∗ , x∗ , u∗ ) = min i π(i) i либо (x,u)∈D i∈T \T0 f (i, xi , xπ(i) , ui ) . i∈T \T0 Замечание 3. В задаче A линейно упорядоченная абелева полугруппа P, ⊥, может получаться как лексикографическое произведение линейно упорядоченных абелевых полугрупп Pk , ⊥k , k (∀k ∈ Nm )(m ∈ N\{1}) или, иными словами, определяться из следующих условий: - P - множество функций q : Nm -→ Pk k∈Nm со значениями qk ∈ Pk (∀k ∈ Nm ), 160 К динамическому программированию по значениям в полугруппе - (p q) ⇔ (p = q)∨(∅ = K = {k ∈ Nm |pk = qk })∧(e = min K)∧(pe (∀p, q ∈ P ), - (p⊥q)k = pk ⊥k qk (∀k ∈ Nm ) (∀p, q ∈ P ). e qe ) Замечание 4. Если полугруппа P, ⊥, определяется по замечанию 3, Pk = R(∀k ∈ Nm ), k означает (∀k ∈ Nm ), ⊥k означает + (∀k ∈ Nm ) и, кроме того, S(i, α, β) = {s(i, α, β)} и f (i, s(i, α, β), α, β) k = f k (i, α, β)(∀i ∈ T \T0 )(∀α ∈ A)(∀β ∈ B)(∀k ∈ Nm ), то оптимальный процесс (x∗ , u∗ ) ∈ D является m-оптимальным процессом [2]. 2. В общем случае наряду с обозначениями [2] Tk = {i ∈ T |h(i) = k}(∀k ∈ Nh(T ) ), где h(T ) = max h(i), i∈T h(i) = |{j ∈ T |j i}|, будет использоваться следующее развитие терминов [2]: - пара (Y, V ) называется подходящей, если её составляют функции Y , V со значениями Y (i) ⊂ A(∀i ∈ T ), V (i, α) ⊂ B(∀α ∈ Y (π(i)))(∀i ∈ T \T0 ), когда Y (i) = ∅(∀i ∈ T ); - для подходящей пары (Y, V ) множество F (Y, V ) образуют пары (x, u) функций x, u со значениями xi ∈ A(∀i ∈ T ), ui ∈ B(∀i ∈ T ) при ограничениях xi = ui (∀i ∈ T0 ), xi ∈ Y (i)(∀i ∈ T ), xi ∈ S(i, xπ(i) , ui )(∀i ∈ T \T0 ), ui ∈ V (i, xπ(i) )(∀i ∈ T \T0 ); - подходящая пара (Y, V ) называется S-согласованной, если выполнены условия ∅ = V (i, α) = {β ∈ V (i, α)|∅ = S(i, α, β)∩Y (i)}(∀α ∈ Y (π(i)))(∀i ∈ T \T0 ). 3. Следующее утверждение (теорема 1), развивающее теорему 1 [2], даёт характеризацию (необходимые и достаточные условия) разрешимости задачи A. Теорема 1. Оптимальный процесс задачи A существует, если и только если из равенств X ∂ (i) = X(i)(∀i ∈ M ), 161 О в ч и н н и к о в В. Г. X ∂ (i) = {α ∈ X(i)|∅ = {β ∈ U (j, α)|∅ = S(j, α, β) ∩ X ∂ (j)}(∀j ∈ τ (i))} (∀i ∈ Tk-1 \M )(∀k ∈ Nh(T ) ) (по уменьшению k) получаются непустые множества достижимости X ∂ (i)(∀i ∈ T ). При этих условиях определяемая значениями X ∂ (i) ⊂ A(∀i ∈ T ) функция X ∂ и определяемая значениями U ∂ (i, α) = {β ∈ U (i, α)|∅ = S(i, α, β) ∩ X ∂ (i)} ⊂ B(∀α ∈ X ∂ (π(i)))(∀i ∈ T \T0 ) функция U ∂ составляют S-согласованную пару (X ∂ , U ∂ ), удовлетворяющую равенству D = F (X ∂ , U ∂ ). 4. Далее предполагается, что оптимальный процесс задачи A существует, пара (X ∂ , U ∂ ) составлена, как указано в теореме 1, и, следовательно, D = F (X ∂ , U ∂ ), ∅ = X ∂ (i)(∀i ∈ T ), S(i, α, β) = ∅ = U ∂ (i, α) = {β ∈ U ∂ (i, α)|∅ = S(i, α, β) ∩ X ∂ (i)} (∀β ∈ U ∂ (i, α))(∀α ∈ X ∂ (π(i)))(∀i ∈ T \T0 ). Также предполагается, что так называемые значения Беллмана B(i, α) определены из условий ( ) (i ∈ M ) ⇒ B(i, α) = min β∈U ∂ (i,α) f (i, ψ(S(i, α, β)), α, β), ( ) (i ∈ M ) ⇒ B(i, α) = / min β∈U ∂ (i,α) f (i, ψ(S(i, α, β)), α, β)⊥ (∀α ∈ X ∂ (π(i))(∀i ∈ Tk ) ∀k ∈ Nh(T ) ⊥ B(j, ψ(S(i, α, β))) j∈τ (i) (индукцией по уменьшению k), где ψ - функция выбора при условиях ∅ = C ⇒ ψ(C) ∈ C(∀C ⊂ A ∪ B ∪ T ). Следующее утверждение (теорема 2) в определённых пределах характеризует оптимальность процесса задачи A. Теорема 2. Процесс (x∗ , u∗ ) ∈ D задачи A оптимален, если (и при стабильности вия относительно ⊥, только если) одновременно выполнены усло- ∗ ∗ ∗ B i, x∗ π(i) = f i, xi , xπ(i) , ui 162 (∀i ∈ M ), К динамическому программированию по значениям в полугруппе B(i, x∗ ) = f i, x∗ , x∗ , u∗ ⊥ i π(i) π(i) i ⊥ B(j, x ) = j∈τ (i) ∗ i ⊥ B (j, x ) j∈τ (i) ( ) min ∗ i (∀i ∈ (T \T0 )\M ), ⊥ B(j, α)(∀i ∈ T ). 0 α∈X ∂ (i) j∈τ (i) Замечание 5. В случае замечания 1 (когда нет стабильности относительно ⊥) легко строится задача A с оптимальным процессом, не удовлетворяющим всем условиям теоремы 2. Из теоремы 2 получается Следствие. Значения функций, составляющих оптимальный процесс (x∗ , u∗ ) ∈ D задачи A, находит следующий алгоритм динамического программирования (алгоритм B). Алгоритм B. Этот алгоритм образуют описываемые при помощи псевдоязыка Pascal [4] следующие последовательно выполняемые действия (Цикл 1, Цикл 2, Цикл 3): Цикл 1, находящий элементы x(i, α)(∈ S(i, α, u(i, α))), u(i, α)(∈ U ∂ (i, α)) из условий i ∈ M ⇒ B(i, α) = f (i, x(i, α), α, u(i, α)), i ∈ M ⇒ B(i, α) = f (i, x(i, α), α, u(i, α))⊥ / ⊥ B(j, x(i, α)) j∈τ (i) (∀α ∈ X ∂ (π(i))(∀i ∈ T \T0 ) : for k := h(T ) downto 1 do for для каждого i ∈ Tk do for для каждого α ∈ X ∂ (π(i)) do begin β ∗ := ψ(U ∂ (i, α)); r∗ := f (i, ψ(S(i, α, β ∗ )), α, β ∗ ); if τ (i) = ∅ then for для каждого j ∈ τ (i) do r∗ := r∗ ⊥B(j, ψ(S(i, α, β ∗ ))); if U ∂ (i, α)\{β ∗ } = ∅ then for для каждого β ∈ U ∂ (i, α)\{β ∗ } do begin r := f (i, ψ(S(i, α, β)), α, β); if τ (i) = ∅ then for для каждого j ∈ τ (i) do r := r⊥B(j, ψ(S(i, α, β))); b :=not(r∗ r); if b then begin r∗ := r; β ∗ := β end; end; B(i, α) := r∗ ; x(i, α) := ψ(S(i, α, β ∗ )); u(i, α) := β ∗ end. Цикл 2, (∀i ∈ T0 ) получающий x∗ , u∗ , используя i i B(j, α)(∀α ∈ X ∂ (π(j)))(∀j ∈ T1 ) : for для каждого i ∈ T0 do 163 О в ч и н н и к о в В. Г. begin ∆ := τ (i)\{ψ(τ (i))}; α∗ := ψ(X ∂ (i)); r∗ := B(ψ(τ (i)), α∗ ); if ∆ = ∅ then for для каждого j ∈ ∆ do r∗ := r∗ ⊥B(j, α∗ ); if X ∂ (i)\{α∗ } = ∅ then for для каждого α ∈ X ∂ (i)\{α∗ } do begin r := B(ψ(τ (i)), α); if ∆ = ∅ then for для каждого j ∈ ∆ do r := r⊥B(j, α); b := not(r∗ r); if b then begin r∗ := r; α∗ := α end end; u∗ := x∗ := α∗ i i end. Цикл 3, (∀i ∈ T \T0 ) получающий x∗ , u∗ с использованием x∗ (∀i ∈ T0 ), i i i найденных циклом 2, и использованием (∀α ∈ X ∂ (π(i)) (∀i ∈ T \T0 ) элементов x(i, α), u(i, α), найденных циклом 1: for k := 1 to h(T ) do for для каждого i ∈ Tk do begin x∗ := x(i, x∗ ); u∗ := u(i, x∗ ) end. i i π(i) π(i) Замечание 6. В случае замечания 1 алгоритм B модифицируется по правилам (b := not(p q)) ⇔ (b := not(p q))(∀p, q ∈ P ), (p := p⊥q) ⇔ (p := max(p, q))(∀p, q ∈ P ). Замечание 7. В случае замечания 2, алгоритм B модифицируется по правилам (b := not(p q)) ⇔ (b := not(p q))(∀p, q ∈ P ), (p := p⊥q) ⇔ (p := p + q(p := p · q))(∀p,q ∈ P ). Замечание 8. В случае замечания 3 алгоритм B модифицируется по правилам (b := not(p q)) ⇔ (b := false; k := 1; while (pk = qk ) ∧ (k m) do k := k + 1; if k m then b := not(pk k qk ))(∀p, q ∈ P ), (p := q) ⇔ (for k := 1 to m do pk := qk )(∀p, q ∈ P ), (p := p⊥q) ⇔ (for k := 1 to m do pk := pk ⊥k qk ) (∀p, q ∈ P ). Замечание 9. В случае замечания 4 модифицированный по правилам замечания 8 алгоритм B получает m-оптимальный процесс проще алгоритма [2] за счет неиспользования, нехранения и неполучения s-согласованных пар (X k , U k )(∀k ∈ Nm ), даваемых теоремой 2 [2].

About the authors

Valery G Ovchinnikov

Samara State Technical University

Email: ovg.samara@mail.ru
Senior Lecturer, Dept. of Oil and Gas Fields Development 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

References

Supplementary files