On the dynamic programming algorithm under the assumption of monotonicity

Abstract


We formulate a discrete optimal control problem, which has not been considered earlier, which arises in the design of oil and gas networks. For this problem we set four theorems so that you can have a process, the optimal process and the optimum value. Necessary and sufficient conditions we give in Theorem 1. Under these conditions, by Theorem 1, we get not empty attainability intervals. For each interval, we choose the grid-a subset of its points, where by an arbitrary point of interval, we find the nearest point on the left. By means of such approximations, we define the Bellman functions on the grids. Using Bellman functions in Theorem 2 we give the process and we evaluate its deviation from the optimal process. In Theorem 2, we guarantee, that the given process is optimal when the attainability intervals and their grids coincide. In other cases, to get the optimal process, we use Theorem 3 and Theorem 4. In Theorem 3 we set that the process given in Theorem 2, is minimal in the lexicographical order which we introduce using Bellman functions. In Theorem 3 we give procedure that builds, if possible, in this order, the next process, skipping only the processes that are not optimal. We find the optimal process and the optimal value by Theorem 4, starting from the process given in Theorem 2, using one or more calls of the procedure given in Theorem 3.

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

References

  1. В. А. Емеличев, В. Г. Овчинников, “Применение метода построения последовательности планов к решению задачи обустройства нефтяных месторождений” // Докл. АН БССР, 1982. Т. 26, No 4. С. 344-347.
  2. В. Г. Овчинников, “Алгоритмы динамического программирования оптимальных и близких к ним процессов” / Труды пятой Всероссийской конференции с международным участием (29-31 мая 2008 г.). Часть 4, Информационные технологии в математическом моделировании / Матем. моделирование и краев. задачи, Самара: СамГТУ, 2008. С. 107-112.
  3. В. Г. Овчинников, “К алгоритмам динамического программирования оптимальных процессов” // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2012. No 3(28). С. 215-218. doi: 10.14498/vsgtu1102.

Statistics

Views

Abstract - 9

PDF (Russian) - 3

Cited-By


PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2014 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