On dynamic programming on the values in the semigroup

Abstract


For not considered previously discrete optimal control problem with target function values in a linearly ordered Abelian semigroup given characteriza tion of the solvability and on its basis the algorithm seeks optimal process with the help of delivering Bellman values elements of limiting sets. We mark the modifications to this algorithm, when 1) P is nonempty subset of numbers with the natural ordering and the operation producing the maximum of two numbers; 2) P is set of nonnegative numbers with the natural ordering and the addition (or multiplication); 3) P is lexicographical product of m (not less than two) linearly ordered Abelian semigroups; 4) P is lexicographic product of m (not less than two) sets of real numbers with the natural ordering and the addition, and this algorithm gets m-optimal process easier than the previous author’s algorithm.

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
244, Molodogvardeyskaya st., Samara, 443100, Russian Federation
Senior Lecturer, Dept. of Oil and Gas Fields Development

References

  1. Овчинников В. Г. Алгоритмы динамического программирования оптимальных и близких к ним процессов / Труды пятой Всероссийской научной конференции с международным участием (29-31 мая 2008 г.). Часть 4: Информационные технологии в математическом моделировании / Матем. моделирование и краев. задачи. Самара: СамГТУ, 2008. С. 107-112.
  2. Овчинников В. Г. К алгоритмам динамического программирования оптимальных процессов // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2012. No 3(28). С. 215-218. doi: 10.14498/vsgtu1102.
  3. Фор Р., Кофман А., Дени-Папен М. Современная математика. М.: Мир, 1966. 271 с.
  4. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы. М.: Вильямс, 2009. 400 с.

Statistics

Views

Abstract - 12

PDF (Russian) - 3

Cited-By


PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2016 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies