On the dynamic programming algorithm under the assumption of monotonicity

Full Text

1. Статья продолжает исследования применения динамического программирования при предположениях монотонности [1]. В ней в отличие от работ [1-3] устанавливаются утверждения (теоремы 1-4), обосновывающие отыскание оптимального процесса, для введения которого служит являющаяся случаем [3] следующая задача. ISSN: 2310-7081 (online), 1991-8615 (print); doi: http://dx.doi.org/10.14498/vsgtu1257 © 2014 Самарский государственный технический университет. Образец цитирования: В. Г. О в ч и н н и к о в, “К алгоритмам динамического программирования при предположениях монотонности” // Вестн. Сам. гос. техн. ун-та. Сер. Физ.мат. науки, 2014. № 1 (34). С. 186-191. 186 К алгоритмам динамического программирования при предположениях монотонности Задача. Пусть известно следующее: - множество шагов T (= {1, . . . , n}) со строгим порядком ством T0 = {i ∈ T : ∅ = {j ∈ T : j i}}(= T ) , подмноженачальных шагов, определением π(i) как единственного шага в подмножестве предшествующих непосредственно 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}; - непустые интервалы [ai ..bi ](= {α ∈ Z : ai чисел Z (∀i ∈ T ); - функция s со значениями si (α, β) ∈ {γ ∈ Z : ai α bi }) множества целых γ} (∀i ∈ T \T0 ) (∀α, β ∈ Z), функция f с значениями fi (α, β) ∈ R (во множестве вещественных чисел) (∀i ∈ T \T0 ) (∀α, β ∈ Z) и функция U с конечными (||Ui (α)|| < ∞) значениями Ui (α) ⊂ Z (∀i ∈ T \T0 ) (∀α ∈ Z) при предположениях монотонности (α δ) ⇒ (fi (α, β) fi (δ, β)) ∧ (si (α, β) si (δ, β)) ∧ (Γi (α, β) ⊇ Γi (δ, β)) (∀i ∈ T \T0 ) (∀α, β, δ ∈ Z), где Γi (α, β) = {γ ∈ Ui (α) : si (α, γ) β}; - обозначение D множества называемых процессами пар (x, u) функций x, u со значениями xi ∈ Z (∀i ∈ T ), ui ∈ Z(∀i ∈ T ), удовлетворяющих ограничениям xi = ui (∀i ∈ T0 ), ui ∈ Ui (xπ(i) ) (∀i ∈ T \T0 ), xi = = si (xπ(i) , ui ) (∀i ∈ T \T0 ), xi ∈ [ai ..bi ](∀i ∈ T ). Требуется найти оптимальный процесс (x∗ , u∗ ) и оптимальное значение r∗ из условий (x∗ , u∗ ) ∈ D, F (x∗ , u∗ ) = r∗ , r∗ = min F (x, u), F (x, u) = (x,u)∈D fi (xπ(i) , ui )(∀(x, u) ∈ D). i∈T \T0 Замечание. В частном случае получающегося, когда Z заменяется на R, варианта этой задачи существование оптимального процесса охарактеризовано в [1]. В общем случае с использованием Tk = {i ∈ T : h(i) = k}(∀k ∈ [1..h(T )]), 187 В. Г. О в ч и н н и к о в где h(i) = ||{j ∈ T : j i}||, h(T ) = max h(i), i∈T характеризацию существования оптимального процесса даёт следующая теорема. Теорема 1. Для задачи следующие условия равносильны: - оптимальный процесс существует; - индукцией a0 = ai (∀i ∈ T0 ), i a0 = i min β∈Ui a0 π(i) si (a0 , β)(∀i ∈ Tk ) π(i) (вверх по k) (∀k ∈ [1..h(T )]) определяются числа a0 ∈ [ai ..bi ](∀i ∈ T ). i При выполнении этих условий с помощью равенств [a0 ..b0 ] = [a0 ..bi ](∀i ∈ M ) i i i индукцией [a0 ..b0 ] = {α ∈ [a0 ..bi ] : Γj (α, b0 ) = ∅(∀j ∈ τ (i))}(∀i ∈ Tk \M ) i i i j (вниз по k) (∀k ∈ [0..h(T ) - 1]) получаются множества достижимости [a0 ..b0 ](∀i ∈ T ) (ср. [2]), имеющие элементы xi (∀(x, u) ∈ D). i i 2. Далее предполагается, что по теореме 1 найдены непустые интервалы [a0 ..b0 ](∀i ∈ T ), и, следовательно, для множеств Ui0 (α) = Γi (α, b0 ) выполнены i i i условия Ui0 (α) = ∅ и si (α, γ) ∈ [a0 ..b0 ](∀γ ∈ Ui0 (α)) (∀α ∈ [a0 ..b0 ])(∀i ∈ T \T0 ). i i π(i) π(i) Также предполагается следующее: - D0 = {(x, u) ∈ D : ui = ai (∀i ∈ T0 )}; - ({a0 } ⊂ Yi ⊆ [a0 ..b0 ]) ∧ (||Yi || ci ) (где ci - заданные границы мощноi i i стей) (∀i ∈ T ); - (a0 α) ⇒ (pi (α) = max{γ ∈ Yi : γ α})(∀α ∈ Z)(∀i ∈ T ); i - с помощью равенств Bi (γ) = 0(∀γ ∈ Yi ) (∀i ∈ M ) аналогичной использованной алгоритмом [2] индукцией min (fj (γ, β) + Bj (pj (sj (γ, β)))) (∀γ ∈ Yi )(∀i ∈ Tk \M ) Bi (γ) = j∈τ (i) 0 β∈Uj (γ) (вниз по k) (∀k ∈ [1..h(T ) - 1]) определены функции Беллмана Bi со значениями Bi (γ) ∈ R(∀γ ∈ Yi )(∀i ∈ T ); - Ψi (α) = min Φi (α, δ)(∀α ∈ [a0 ..b0 ]) (∀i ∈ T \T0 ), где Φi (α, β) = π(i) π(i) 0 δ∈Ui (α) = fi (α, β) в случае i ∈ M или Φi (α, β) = fi (α, β) + Bi (pi (si (α, β))) в случае i ∈ M ; / 188 К алгоритмам динамического программирования при предположениях монотонности - по правилу (β <α γ) ⇔ ((Φi (α, β) < Φi (α, γ)) ∨ ((Φi (α, β) = Φi (α, γ)) ∧ (β < γ))) i (∀β, γ ∈ Ui0 (α)) во множестве Ui0 (α) введён порядок <α (∀α ∈ [a0 ..b0 ])(∀i ∈ T \T0 ); i π(i) π(i) - в произвольном непустом подмножестве C ⊆ Ui0 (α) минимальный по порядку <α элемент обозначен mα (C) (∀α ∈ [a0 ..b0 ])(∀i ∈ T \T0 ). i i π(i) π(i) Конструирование (в определенном случае оптимального) процесса даёт следующая теорема Теорема 2. Процесс (z, w) ∈ D 0 с оценкой F (z, w) - r∗ F (z, w) - Ψi (aπ(i) ), i∈T1 оптимальный в случае Yi = [a0 ..b0 ](∀i ∈ T ), строит по обращению следуюi i щая процедура: ПРОЦЕДУРА first(): НАЧАЛО: положить k = 0, xi = ui = ai (∀i ∈ T0 ); СЛЕДУЮЩИЙ УРОВЕНЬ: увеличить k на 1; x положить ui = mi π(i) Ui0 (xπ(i) ) (∀i ∈ Tk ), xi = si (xπ(i) , ui ) (∀i ∈ Tk ); если k < h(T ), идти на СЛЕДУЮЩИЙ УРОВЕНЬ; ЗАВЕРШЕНИЕ first: обозначить first() пару (x, u). 3. В случае Yi = [a0 ..b0 ] (∃i ∈ T ), когда отыскание оптимального процесса i i не гарантировано теоремой 2, ради упрощения предполагается следующее: j < g(∀j ∈ Tk-1 )(∀g ∈ Tk )(∀k ∈ [1..h(T )]); fi (xπ(i) , ui )(∀j ∈ T \T0 )(∀(x, u) ∈ D0 ); Fj (x, u) = i∈[ T0 +1..j] Oj (x, u) =   Ψg (xπ(g) ) при ∅ = Gj = {g ∈ T \T0 : π(g) < j < g}, g∈Gj 0 в остальных случаях (∀j ∈ T \T0 )(∀(x, u) ∈ D0 ). Следующее утверждение (теорема 3) устанавливает минимальность по определенному порядку процесса в теореме 2 и способ построения по этому порядку следующего, если возможно, процесса с пропуском построения лишь не являющихся оптимальными процессов. Теорема 3. Следующие предложения верны. 1) Процесс в теореме 2 минимален по лексикографическому порядку на D0 , вводимому правилом x ((x, u) (z, w)) ⇔ ((uj = wj (∀j ∈ [1..i - 1])) ∧ (ui 4. В общем случае получение оптимального процесса даёт следующая теорема. Теорема 4. Оптимальный процесс (x∗ , u∗ ) и оптимальное значение r ∗ находит при помощи first() и нескольких обращений к процедуре next(x, u, r) следующий итерационный алгоритм. АЛГОРИТМ: НАЧАЛО: положить (x , u ) = f irst(), r = ∞; ИЗМЕНЕНИЕ: положить (x, u) = (x , u ); ИТЕРАЦИЯ: положить r = F (x, u); если r < r , положить (x , u ) = = (x, u), r = r; положить (x , u ) = next(x, u, r ); если (x, u) = (x , u ), идти на ИЗМЕ- НЕНИЕ; ЗАВЕРШЕНИЕ АЛГОРИТМА: положить (x∗ , u∗ ) = (x , u ), r∗ = r ; остановиться.

About the authors

Valery G Ovchinnikov

Samara State Technical University

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

References

Supplementary files