On the algorithms of dynamic programming for optimal processes

Full Text

1. Хорошо известно, что метод динамического программирования основывается на использовании информации о решениях вспомогательных подзадач, и необходимость использования такой информации может послужить препятствием к применению метода, так как требует дополнительной памяти и, возможно, мощных процессоров. Кроме того, легко строится пример, когда для хранения указанной информации требуется память в размере большем, чем количество адресов самого современного процессора. Эффективные алгоритмы динамического программирования оптимальных по одному критерию процессов даны в [1, 2], причем предложенные в [2] алгоритмы WO , RO основаны на использовании лишь не исключенных алгоритмом O [2] вспомогательных подзадач и поэтому требуют меньше дополнительной памяти, чем алгоритмы [1]. В настоящей статье, продолжающей исследования [2], алгоритмам WO , RO дается развитие в случаях нескольких последовательно применяемых функций цели p m в виде процедуры WO (Y, V ) и алгоритма RO (ϕ, ψ) для обобщающей задачу [2] следующей задачи дискретного оптимального управления (задачи Am ). Задача Am . Даны: m ∈ N; множества A, B; множество шагов T (1< T <∞) со строгим порядком , подмножеством T0 = {i ∈ T | ∅ = {j ∈ T | j i}} (= T ) начальных шагов и определением π(i) как единственного шага в {j ∈ T | (j i) ∧ (∅ = {g ∈ T | j g i})} — подмножестве шагов, которые непосредственно предшествуют шагу i (∀i∈T \T0); имеющие множественные значения функции X:T →β(A) (β(A) = {C | C ⊂ A}), U : (T \T0 ) × A → β(B), удовлетворяющие неравенствам 0 < X(i) < ∞ (∀i ∈ T ), U (i, α) < ∞ (∀i ∈ T \T0) (∀α ∈ A); функции цели f k : (T \T0 ) × A × B → R (∀k ∈ {1, . . . , m}) и связей s : (T \T0 ) × A × B → A; 215 О в ч и н н и к о в В. Г. множество D, которое образуют процессы, т. е. пары (x, u) функций x : T → A, u : T → B со значениями xi (∀i ∈ T ), ui (∀i ∈ T ) при ограничениях xi = ui (∀i ∈ T0 ), xi = s(i, xπ(i) , ui ) (∀i ∈ T \T0), xi ∈ X(i)(∀i ∈ T ), ui ∈ U (i, xπ(i) ) (∀i ∈ T \T0). Требуется найти называемую (m)-оптимальным процессом пару (x∗ , u∗ ) ∈ Dm , если D0 = D, Dk = f k (i, xπ(i) , ui ) (x, u) ∈ Dk−1 i∈T \T0 f k (i, yπ(i) , vi ) ∀(y, v) ∈ Dk−1 (∀k ∈ {1, . . . , m}). i∈T \T0 Замечание 1. В случае, когда m = 1 = T0 , задача Am формулируется как задача A в [2]. 2. В общем случае наряду с терминами [2] будут использоваться следующие обозначения и термины: τ (i) = {j ∈ T \T0 | π(j) = i} (∀i ∈ T ), M = {i ∈ T τ (i) = ∅, h(i) = {j ∈ T | j i} (∀i ∈ T ), h(T ) = maxi∈T h(i), Tk = {i ∈ T | h(i) = k} (∀k ∈ {1, . . . , h(T )}); пара (Y, V ) называется подходящей, если ее составляют функции Y : T → β(A), V : {(i, α) | i ∈ T \T0 , α ∈ Y (π(i))} → β(B), когда Y (i) = ∅ (∀i ∈ T ); для каждой подходящей пары (Y, V ) множество F (Y, V ) образуют пары (x, u) функций x : T → A, u : T → B со значениями xi (∀i ∈ T ), ui (∀i ∈ T ) при ограничениях xi = = ui (∀i ∈ T0 ), xi = s(i, xπ(i) , ui ) (∀i ∈ T \T0 ), xi ∈ Y (i) (∀i ∈ T ), 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. Следующее утверждение даёт характеризацию разрешимости задачи Am . Теорема 1. Оптимальный процесс в задаче Am существует, если и только если определяемая из равенств X 0 (i) = {α ∈ X(i) | ∅ = {β ∈ U (j, α)| s(j, α, β) ∈ X 0 (j)} (∀j ∈ τ (i))} (∀i ∈ T \M ), X 0 (i) = X(i) (∀i ∈ M ) функция X 0 : T → β(A) удовлетворяет условиям X 0 (i) = ∅ (∀i ∈ T ). При этих условиях указанная функция X 0 : T → β(A) и определяемая при помощи равенств U 0 (i, α) = {β ∈ U (i, α) | s(i, α, β) ∈ X 0 (i)} (∀α ∈ X 0 (π(i))) (∀i ∈ T \T0 ) функция U 0 : {(i, α) | i ∈ T \T0, α ∈ X 0 (π(i))} → β(B) составляют s–согласованную пару (X 0 , U 0 ), удовлетворяющую равенству D0 = F (X 0 , U 0 ). Замечание 2. В указанном замечанием 1 случае с помощью теоремы 1 получается теорема 3 [2]. Замечание 3. В общем случае указанная теоремой 1 функция X 0 : T → β(A) определяется тремя способами: (а) при помощи алгоритма, получаемого из алгоритма O [2] заменой Sh−1 на Th−1 ; (б) при помощи равенств X 0 (i) = {α ∈ X(i) | B(i, α) < ∞} (∀i ∈ T ), если в них значения B(i, α) (∀α ∈ X(i)) (∀i ∈ T ) определяются алгоритмом, получаемым из алгоритма W [2] заменой Sh−1 на Th−1 и функции f на одну из функций f k (∀k ∈ {1, . . . , m}); (в) при помощи равенств X 0 (i) = {α ∈ X(i) | B(i, α) = 0} (∀i ∈ T ), где значения B(i, α) (∀α ∈ X(i)) (∀i ∈ T ) находит следующий алгоритм (алгоритм W ). Алгоритм W . Этот алгоритм использует значения функции f 0 : (T \T0) × A × × B → R, определяемые из условий: f 0 (i, α, β) = 0 в случае (α ∈ X(π(i))) ∧ (β ∈ U (i, α))∧(s(i, α, β) ∈ X(i)) либо f 0 (i, α, β) = 1 в иных случаях (∀i ∈ T \T0) (∀α ∈ A) (∀β ∈ B). Шаг 0. Положить B(i, α) = 0 (∀α ∈ Y (i)) (∀i ∈ M ), h = h(T ), µ = 1. 216 К алгоритмам динамического программирования оптимальных процессов Шаг µ. Если µ = h(T ) + 1, остановиться. Иначе аналогично алгоритму W [2] положить B(i, α) = 1 в случае (∃j ∈ τ (i)) (∅ = {β ∈ U (j, α)|s(j, α, β) ∈ X(j)}), либо положить min B(i, α) = j∈τ (i) β∈{β∈U(j,α)|s(j,α,β)∈X(j)} f 0 (j, α, β) + B(j, s(j, α, β)) в иных случаях (∀α ∈ X(i)) (∀i ∈ Th−1 \M ), заменить h на h − 1, µ на µ + 1 и идти на Шаг µ. Далее предполагается, что оптимальный процесс в задаче Am существует, пара (X 0 , U 0 ) составлена, как указано в теореме 1 и, следовательно, D0 = F (X 0 , U 0 ). 4. Следующее утверждение указывает способ получения для множеств Dk (∀k ∈ {1, . . . , m}) аналогичных D0 = F (X 0 , U 0 ) равенств, на которых основывается динамическое программирование для задачи Am . Теорема 2. В порядке увеличения k при помощи обращений (X k , U k ) = p k = WO (X k−1 , U k−1 ) к следующей процедуре (процедуре WO (Y, V )) получаются s-согласованные пары (X k , U k ), удовлетворяющие равенствам Dk = F (X k , U k ) (∀k ∈ {1, . . . , m}). p Процедура WO (Y, V ). В этой процедуре аргументами являются номер p ∈ {1, . . . , m} и s-согласованная пара (Y, V ). Шаг 0. Положить B(i, α) = 0 (∀α ∈ Y (i)) (∀i ∈ M ), h = h(T ), µ = 1. Шаг µ. Если µ = h(T ) + 1, идти на Завершение процедуры. Иначе аналогично алгоритму WO [2] положить min B(i, α)= j∈τ (i) β∈V (j, α) (f p (j, α, β)+B(j, s(j, α, β))) (∀α ∈ Y (i)) (∀i ∈ Th−1 \M ), заменить h на h − 1, µ на µ + 1 и идти на Шаг µ. p Завершение процедуры. Обозначить WO (Y, V ) пару (Y 1 , V 1 ), где функции Y 1 , 1 1 1 V задаются равенствами Y (i) = {α ∈ Y (i) | B(i, α1 ) = min B(i, α)} (∀i ∈ T0 ), α∈Y (i) Y 1 (i) = Y (i) (∀i ∈ T \T0), V 1 (i, α) = {β 1 ∈ V (i, α)|f p (i, α, β 1 ) + B(i, s(i, α, β 1 )) = = min (f p (i, α, β) + B(i, s(i, α, β)))} (∀α ∈ Y 1 (π(i))) β∈V (i,α) (∀i ∈ T \T0 ). 5. Следующее утверждение даёт обоснование динамическому программированию для задачи Am . Теорема 3. При любой паре (ϕ, ψ) функций (выбора элементов из подмножеств) ϕ : (β(A)\{∅}) → A, ψ : (β(B)\{∅}) → B следующий алгоритм (алгоритм m RO (ϕ, ψ)), используя полученную по теореме 2 пару (X m , U m ), находит значения xi (∀i ∈ T ), ui (∀i ∈ T ) функций x: T → A, u : T → B, составляющих оптимальный процесс в задаче Am . m Алгоритм RO (ϕ, ψ). Шаг 0. Положить ui = xi = ϕ(X m (i))(∀i ∈ T0 ), µ = 1. Шаг µ. Если µ = h(T ) + 1, остановиться. Иначе положить ui = ψ(U m (i, xπ(i) )) (∀i ∈ Tµ ), xi = s(i, xπ(i) , ui )(∀i ∈ Tµ ), заменить µ на µ + 1 и идти на Шаг µ. Замечание 4. В указанном замечанием 1 случае из теоремы 3 получается теоm рема 4 [2] и алгоритм RO (ϕ, ψ) формулируется как алгоритм RO [2]. 217

About the authors

Valeriy G Ovchinnikov

Samara State Technical University

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

References

Supplementary files