On the algorithms of dynamic programming for optimal processes

Abstract


The problem of discrete optimal control which has m consistently applied objective functions is formulated. In this problem the optimal process, also called m-optimal, is sought as a pair of functions defined on a finite set of steps at the links by which one function is uniquely defines the other, with the constraints of these functions with inclusion “∈” of their values in the final multiple values of the functions of the known pair. A uniform representation of sets, forming the k-optimal processes for k not greater than m, is given with construction of nondecreasing sequence, upper limited by this pair by the “⊂” inclusions, on the basis of characterization of solvability of the problem.

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

References

  1. Хачатуров В. Р., Веселовский В. Е., Злотов А. В., Калдябаев С. У., Калиев Е. Ж., Коваленко А. Г., Монтлевич В. М., Сигал И. Х., Хачатуров Р. В. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М.: Наука, 2000. 353 с.
  2. Овчинников В. Г. Алгоритмы динамического программирования оптимальных и близких к ним процессов / В сб.: Труды пятой Всероссийской научной конференции с международным участием (29–31 мая 2008 г.). Часть 4: Информационные технологии в математическом моделировании / Матем. моделирование и краев. задачи. Самара: СамГТУ, 2008. С. 107–112.

Statistics

Views

Abstract - 6

PDF (Russian) - 1

Cited-By


Refbacks

  • There are currently no refbacks.

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