Автоматика и телемеханика, № 3, 2020

(Институт проблем передачи информации им. А.А. Харкевича РАН, Москва;

Казанский федеральный университет),

Б.М. МИЛЛЕР, д-р физ.-мат. наук (bmiller@iitp.ru)

(Институт проблем передачи информации им. А.А. Харкевича РАН, Москва;

Университет Монаш, Виктория, Австралия;

Казанский федеральный университет),

К.В. СТЕПАНЯН, канд. физ.-мат. наук (KVStepanyan@iitp.ru)

(Институт проблем передачи информации им. А.А. Харкевича РАН, Москва)

ОДНОВРЕМЕННОЕ ИМПУЛЬСНОЕ И НЕПРЕРЫВНОЕ УПРАВЛЕНИЕ

МАРКОВСКОЙ ЦЕПЬЮ В НЕПРЕРЫВНОМ ВРЕМЕНИ¹

Рассматривается непрерывное и импульсное управление марковской

цепью (МЦ) с конечным множеством состояний в непрерывном време-

ни. Непрерывное управление определяет интенсивность переходов между

состояниями МЦ, при этом времена переходов и их направления случай-

ны. Тем не менее иногда требуется обеспечить переход, который ведет к

мгновенному изменению состояния МЦ. Поскольку такие переходы тре-

буют различных воздействий и могут производить различное действие

на состояние МЦ, такие управления можно трактовать как импульсные.

В статье используется мартингальное представление управляемой МЦ и

дается условие оптимальности, которое с использованием принципа ди-

намического программирования приводится к форме квазивариационного

неравенства. Решение этого неравенства может быть получено в форме

уравнения динамического программирования, которое для МЦ с конеч-

ным множеством состояний сводится к системе обыкновенных дифферен-

циальных уравнений с одной линией переключения. Дано доказательство

достаточного условия оптимальности и рассмотрены примеры задач с де-

терминированным и случайным импульсным воздействием.

Ключевые слова: марковская цепь, импульсные управления, квазивариа-

ционное неравенство.

DOI: 10.31857/S0005231020030071

1. Введение

Импульсное управление как воздействие, производящее мгновенные

(в действительности очень быстрые) изменения состояния динамической си-

стемы, детально исследуется с 70-х гг. XX в. В серии пионерских работ

А. Бенсусан и Ж.-Л. Лионс развили теорию стохастического импульсного

управления, в которой обобщили принцип динамического программирования

¹ Работа выполнена А.Б. Миллером и Б.М. Миллером частично за счет средств суб-

сидии, выделенной в рамках Государственной поддержки Казанского (Приволжского) фе-

дерального университета в целях повышения его конкурентоспособности среди ведущих

мировых научно-образовательных центров.

114

и сформулировали условия оптимальности в форме так называемого квазива-

риационного неравенства [1]. Их идеи привели к возникновению нового клас-

са дискретно-непрерывных стохастических систем, которые функционируют

непрерывно (детерминированно или стохастически) между скачками, кото-

рые происходят в моменты применения импульсных воздействий. В стохасти-

ческом анализе эти идеи были подхвачены многими исследователями, развив-

шими теорию кусочно-детерминированных марковских моделей (КДММ), по-

ведение которых между случайными моментами скачков, возможно и управ-

ляемых, подчиняется непрерывной динамике (см., например, [2-4]). Дальней-

шие исследования в области импульсного управления привели к появлению

нового класса управляемых динамических систем, описываемых дифферен-

циальными уравнениями с мерой, которые универсальным способом описы-

вают как импульсные, так и непрерывные воздействия. В этом классе систем

были получены условия существования оптимальных обобщенных решений и

обобщенных управлений-мер и одновременно непрерывных управлений [5, 6]

и получены условия оптимальности в форме обобщенного принципа макси-

мума [7, 8]. В последние годы заметно вырос интерес к управлению марков-

скими цепями (МЦ) и, в частности, к КДММ поскольку эти модели более

приспособлены к решению задач оптимизации и значительно более просты

для моделирования [9-11]. Более того, возникло целое направление, а именно:

марковские процессы принятия решений (Markov Decision Processes (MDP)),

которое весьма востребовано во многих прикладных областях. Здесь можно

привести в качестве примеров: управление системами водохранилищ [12, 13],

где импульсные воздействия проявляются в виде контролируемого сброса во-

ды, например для избежания переполнений; при контроле добычи и использо-

вания природных ресурсов [14, 15]; при управлении Интернетом для избежа-

ния перегрузок [16, 17]; в непрерывном управлении распределением водных

ресурсов с помощью контроля цен потребляемой воды в различных секторах

экономики [18, 19]; при распределении потоков газа в системе газоснабже-

ния при необходимости сглаживания сезонных пульсаций потребления [20].

Во всех этих областях импульсные воздействия, так же как и непрерывные,

возникают весьма естественно как управления, приводящие к быстрым кон-

тролируемым изменениям состояния; в управлении передачей данных — это

освобождение памяти при угрозе переполнения [21]; в управлении системой

водохранилищ — это контролируемый слив излишков воды [19, 22].

Другой причиной растущего интереса к MDP является относительная про-

стота и гибкость моделирования непрерывных и дискретных стохастических

динамических систем с помощью МЦ с конечным множеством состояний [23],

и поскольку точность аппроксимации напрямую зависит от числа состояний,

то постоянно возрастающие возможности доступных компьютеров позволяют

достичь необходимой точности решения задач оптимального управления без

существенных проблем. Кроме того, теория оптимального управления МЦ

как в дискретном, так и в непрерывном времени достаточно развита как для

обычных задач [24], так и для задач с ограничениями на состояние [25-27], по-

этому соответственные численные процедуры могут быть легко реализованы.

Здесь стоит отметить, что для стохастических систем с непрерывным мно-

жеством состояний оптимизация импульсного управления ведет к специаль-

115

ному типу условия оптимальности, а именно: квазивариационному неравен-

ству [1], которое играет роль уравнения динамического программирования.

Это неравенство, даже если существование его решения установлено, весьма

трудно разрешимо даже численно, поскольку требует гладкого сопряжения

решений пары уравнений в частных производных на заранее неизвестной по-

верхности. Более того, оптимальное управление есть случайная мера, лока-

лизованная на этой поверхности, функция распределения которой сингуляр-

на по отношению к мере Лебега, поэтому определить характеристики такого

управления можно лишь с помощью моделирования. Однако в случае МЦ

с конечным множеством состояний эта проблема отсутствует. Для них им-

пульсное управление есть совокупность разделенных во времени пар времен

и интенсивностей приложения импульсных воздействий, а проблема решения

соответствующего квазивариационного неравенства сводится в решению си-

стемы обыкновенных дифференциальных уравнений с одной поверхностью

переключения.

Материал статьи имеет следующую структуру: в разделе 2 дано описание

модели МЦ с непрерывным и импульсным управлениями, в разделе 3 дан

вывод условий оптимальности в форме квазивариационного неравенства и

приведен метод его решения. В разделе 3.3 дано доказательство достаточно-

сти условия оптимальности. В разделе 4 рассматривается численный пример.

Выводы и направления дальнейших исследований приведены в разделе 5.

2. Описание модели и постановка задачи

Используется мартингальное представление управляемой МЦ, следуя опи-

санию, данному в [16, 24, гл. 12] для непрерывного управления, дополненное

членами, описывающими импульсные воздействия. Все процессы рассматри-

ваются на вероятностном пространстве {Ω, F, P }.

Определение 1. Процесс {X_t, t ∈ [0,T]} — есть управляемый марков-

ский процесс с кусочно-постоянными непрерывными справа траекториями.

Пространство состояний этого процесса есть конечное множество единич-

ных векторов S вида e_i = (0,0,... ,0,1,0,... ,0)^т ∈ Rⁿ, т.е. e_i состоит из ну-

левых элементов кроме i-го, который равен единице, символ “т” здесь и да-

лее соответствует транспонированию векторов и матриц. Таким образом,

X_t ∈ S.

2.1. Непрерывное управление МЦ

Предположение 1. Матричная функция A(t,u) с элементами a_ij(t,u)

есть семейство генераторов МЦ, зависящих от времени t ∈ [0, T ], таких что

вектор вероятностей состояния p_t = (p1t, . . . , p^nt)^т, где p^it = P (X_t = e_i) удовле-

творяет прямым уравнениям Колмогорова

dp_t

(2.1)

= A(t, u)p_t.

Здесь управление u ∈ U, где U — некоторое компактное подмножество пол-

ного метрического пространства и A(t, u) непрерывна на [0, T ] × U.

116

Введем непрерывное справа семейство полных σ-алгебр, порождаемых

процессом X_t

F^Xt = σ{X_s : s ∈ [0,t]}.

Предположение 2. Множество U допустимых управлений {u(·)} есть

множество F^Xt -предсказуемых процессов со значениями в U. Это означает,

что если N_t — это количество изменений состояния процесса X, а Xt0 — по-

следовательность состояний начиная с момента времени t = 0, до текущего

времени t ∈ [0, T ], т.е.

Xt0 = {(X₀,0),(Xτ1 ,τ₁),... ,(X_τ

,τNt)}

— есть совокупность состояний и времен скачков, тогда для τNt < t ≤ τNt+1

управление u_t = u(t, Xt0) есть функция от Xt0 и текущего времени t [24, 28].

Для каждого управления u(·) ∈ U процесс {X_t} удовлетворяет стохасти-

ческому дифференциальному уравнению

∫t

(2.2)

X_t = X₀ + A(s,u_s)X_s ds + W_t,

где X₀ — начальное условие, а W_t := {W1t, . . . , W^nt} — квадратично интегри-

руемый (F^Xt , P ) мартингал с квадратичной характеристикой [24, 28, 29]:

∫

diag (A(s, u_s)X_s) ds +

(2.3)

∫t

[

]

A(s, u_s)(diag X_s) + (diag X_s)A^т(s, u_s)

ds,

где diag(X) означает диагональную матрицу с элементами X¹, . . . , Xⁿ.

Замечание 1. Другими словами, процесс X(t) есть решение мартин-

гальной проблемы (2.2), (2.3) для управляемой марковской цепи [24].

2.2. Импульсное управление МЦ

Импульсное управление — это множество I = {(V_i, τ_i), i = 1, 2, . . . , N}, где

τ_i < τi+1 ≤ T, V_i ∈ V(X) и число импульсов не более чем счетно. Примене-

ние импульсного управления в момент времени τ_i приводит к мгновенному

случайному изменению состояния X, так что

(2.4)

ΔXτi = ψ(τ_i,V_i,Xτi-)

A(τ_i, V_i)Xτi- + ΔWτ_i ,

где

[

]

ΔWτi|F^Xτ

= E[ΔWτi|Xτi-] = 0,

(2.5)

ΔWτi

= diag

A(τ_i, V_i)Xτi-)

A(τ_i, V_i) diag(Xτi-

A^т(τ_i,V_i).

Здесь и далее E[·] означает математическое ожидание.

117

Предположение 3. В (2.4) ψ(τ_i,V_i,Xτi-) — случайный оператор, такой

что для любых Xτi- ∈ S, V_i ∈ V(Xτi- ) и τ_i ∈ [0, T ]

(2.6)

Xτi = ΔXτi- + Xτi-

∈ S.

Множество V(X) компактно, функци

A(t, V ) непрерывна по t

A(t, 0) = 0,

и поэтому ψ(τ, 0, X) = 0 для любых τ ∈ [0, T ] и X ∈ S.

2.3. Одновременное непрерывное и импульсное управление МЦ

Объединяя уравнения (2.2) и (2.4), получаем уравнение для совместного

непрерывного и импульсного управления

∫t

∑

(2.7)

X_t = X₀ + A(s,u(s))X_sds +

τ_i≤t

где W^′t — квадратично интегрируемый мартингал с квадратичной характе-

ристикой

∫

∑

〈W_t〉 =

〈ΔWτi 〉 - (diag X_s-)A^т(s, u(s))ds -

τ_i≤t

(2.8)

∫t

∫

- A(s, u(s))(diag X_s-)ds + diag A(s, u(s))X_s-ds.

Цель управления — минимизация критерия качества (2.9)

⎧

⎫

∫

⎨

⎬

∑

J₀[u(·),I] = E

〈φ₀, X_T 〉 +

〈g₀(s, u(s)), X_s〉ds +

〈ψ₀(τ_i, V_i), Xτi-〉_⎭ =

⎩

τ_i≤T

⎧

∫

∑

(2.9)

}ds +

=E⎩φ0I{XT =ek}+g0(s,u(s))I{Xs =ek

k=1

⎫

∑

⎬

ψk0(τ_i,V_i)I{Xτi- = ek}_⎭

τ_i≤T k=1

по множеству F^Xt -предсказуемых управлений u(t) ∈ U и импульсных управ-

лений I. В соотношении (2.9) I{·} означает индикаторную функцию, т.е.

I{A} = 1, если событие A происходит и I{A} = 0 в противном случае.

Предположение 4. Вектор-функция g₀ непрерывна по t и u. Век-

тор-функция ψ₀(t, V ) непрерывна по t и V и удовлетворяет неравенству

ψl0(t,V ) ≥ C > 0 для всех l и допустимых V = 0. Множества U и V компакт-

ны.

118

Замечание 2. Компоненты вектора φ₀ определяют цену терминально-

го состояния X_T , вектор-функция g₀ — интегральную цену промежуточных

состояний, а ψ₀ — цену импульсных управлений.

Замечание 3. В данной статье предполагается наиболее простая фор-

мулировка задачи управления и возможны расширения на:

1) системы со случайной реакцией на импульсное воздействие;

2) задачи с другими типами критериев, например с дисконтированием или

усреднением на бесконечном интервале времени [21];

3) задачи с ограничениями на состояние по аналогии с [25-27];

4) залачи с неполной информацией [24, 30].

3. Уравнение динамического программирования в форме

квазивариационного неравенства

3.1. Условие оптимальности одновременного непрерывного

и импульсного управления

Функция цены в задаче (2.7)-(2.3) имеет вид

⎧

∫

⎨8

φ(t, X) = inf

g₀(s,u(s)),X_s ds +

u(·),I

E⎩φ0,XT

⎫

9

∑

⎬



ψ₀(τ_i,V_i),Xτi-

Xt- = X

= φ(t), X



⎭

t<τ_i≤T

где функция φ(t) ∈ R^N — решение квазивариационного неравенства

⎧

⎪

dφ(t)

⎪Q1(t,φ(t),X) =

+ min

A^т(t,u)φ(t) + g₀(t,u),X

≥ 0,

⎪

u∈U

⎪

⎨

Q₂(t,φ(t),X) = φ(t),X

(3.1)

⎪

]

⎪

- min

A^т(t,V )

φ(t) + ψ₀(t, V ), X

≥ 0,

⎪

V ∈V(X)

⎩

min {Q₁(t, φ(t), X), Q₂(t, φ(t), X)} = 0

с граничным условием φ(T ) = φ₀. Здесь и далее под E понимается единич-

ная матрица соответствующей размерности, а E[·] — по-прежнему означает

операцию взятия математического ожидания.

Замечание 4. Отметим, что соотношения (3.1) должны выполняться

для всех значений X ∈ S, т.е. (3.1) представляет собой систему неравенств,

задающих значение функции цены для всех возможных начальных усло-

вий t, X.

119

3.2. Метод решения квазивариационного неравенства

Квазивариационное неравенство (3.1) для системы с конечным множе-

ством состояний допускает достаточно простой метод решения в отличие от

общего случая системы с непрерывной частью, описываемой диффузионным

стохастическим уравнением [1]. Решение, как и в случае простого уравнения

динамического программирования, определяется в обратном времени [25-27]

с граничным условием φ(T ) = φ₀ для всех компонент вектора φ₀, удовлетво-

ряющих условиям (3.1). Функции φ(t) определяется из первого уравнения

системы (3.1) при решении его от терминальной точки φ(T ) = φ₀ до линии

переключения

{

}

0 = 〈φ(t),X〉 - min

〈φ(t), [E

A(t, V )]X〉 + 〈ψ₀(t, V ), X〉

или

V ∈V(X)

(3.2)

G(t, X) = min

A^т(t,V )φ(t) + ψ₀(t,V ),X〉 = 0.

V ∈V(X)

В задачах импульсного управления существование и единственность реше-

ния квазивариационного неравенства (3.1) играет принципиальную роль [1].

В случае управления МЦ с конечным множеством состояний система нера-

венств (3.1) распадается на конечное число дифференциально-разностных

уравнений соответственно числу состояний. Для каждого значения l = 1,

...,N определим функцию переключения G^l(φ,t) : R^N × [0,T] → R¹ так:

{

}

∑

(3.3)

Gl(φ, t) = min

φ_kA¯_l,k(t,V ) + ψl0(t,V )

V ∈V(e_l)

k=1

В силу непрерывности

A и ψ₀ по t функция переключения непрерывна по

паре (φ, t) и определяет для каждого l линию переключения

{

}

(3.4)

Sw^l = (φ,t,l) : G^l(φ,t) = 0

Таким образом, если

φ(t) = {φ₁(t), . . . , φ_N (t)}^т,

то элементы φ_l(t), l = 1, . . . , N, удовлетворяют системе уравнений

{

}

∑

dφ_l(t)

(3.5)

+ min

φ_k(t)A_l,k(t,u) + gl0(t, u)

= 0, если G^l

(φ(t), t) > 0.

u∈U

k=1

При решении первого уравнения системы (3.5) в обратном времени с гранич-

ными условиями φ(T ) = φ₀ для каждого l = 1, . . . , N, линия переключения

достигается в момент времени {t^l : G^l(φ(t^l), t^l) = 0}. Вследствие условия (3.2)

функция φ остается непрерывной при пересечении линии переключения, од-

нако следующее условие на φ позволяет определить величину импульсного

управления

(3.6)

0 = min

A^т(t,V )φ(t),X

+ ψ₀(t,V ),X

V ∈V(X )

120

Минимизирующее воздействие в соотношении

(3.7)

V = argmin

A^т(t,V )φ(t),X

+ ψ₀(t,V ),X

V ∈V(X )

существует, и далее решение системы (3.5) продолжается в обратном вре-

мени до следующего пересечения с линией переключения. Таким образом, в

точке T_i используется импульсное управление V_i, определяемое сотношения-

ми (3.6), (3.7), а функции φ(t) остаются непрерывными. Описанная процедура

определяет решения квазивариационного неравенства (3.1).

3.3. Достаточное условие оптимальности одновременного импульсного

и непрерывного управления

Предложение 1. Пусть:

a) функции φ(t) ∈ Rⁿ определены с помощью процедуры, описанной в подраз-

деле 3.2, и удовлетворяют уравнению

dφ(t)

(3.8)

+ min

A^т(t,u)φ(t) + g₀(t,u),X

u∈U(X)

на каждом из подынтервалов [T_i,Ti+1) с терминальным условием φ(T) =

=φ₀;

б) управления u^∗(t) на [T_i, Ti+1) выбраны марковскими u^∗(t) = u^∗(t, X_t) и до-

ставляют минимум правой части соотношения (3.8);

в) моменты приложения импульсных воздействий T^∗i = t^∗(X) выбраны в со-

ответствии с соотношением

(3.9)

min

A^т(t^∗(X),V )]φ(t^∗(X)) + ψ₀(t^∗(X),V ),X

= 0,

V ∈V(X)

а импульсные воздействия V^∗i выбраны в соответствии с соотношени-

ем (3.7).

Тогда одновременное непрерывное и импульсное управление {u^∗(·), T^∗i, V^∗i}

оптимально.

Доказательство. Возьмем произвольное непрерывное и импульсное

управление {u(·), I}, соответствующую траекторию, удовлетворяющую на-

чальному условию X^u,It = X, и вычислим величину

∫

ΔJ^Tt = φ(T),X^u,I

- φ(t), X +

g₀(s,u(s)),X^u,I

ds +

(3.10)

∑

ψ₀(T_i,V_i),X^u,IT

= φ(T ), X^u,I

- φ(t), X

+I₁ +I₂,

t≤T_i≤T

121

где φ(t) — решение квазивариационного неравенства (3.1), а X^u,It — решение

уравнения (2.7) с начальным условием X_t = X. Тогда, используя формулу

Ито для X^u,It , получим соотношение

∫T

∫

⁸ dφ(s)

;

ΔJ^Tt =

,X^u,I

ds + I₁ + I₂ +

φ(s), dX^u,Is

Однако

∫

;

φ(s), dX^u,Is

∫T

∫

;

∑

;

φ(s), A(s, u(s))X^u,Is

ds +

φ(T_i)

A(T_i, V_i)XTi-

+ φ(s)dW^′(s).

t≤T_i≤T

Далее, для произвольного управления u, I в соответствии с соотношения-

ми (3.8), (3.9) получаем, что

⁸ dφ(t)

(3.11)

,X^u,I

+ A^т(t,u)φ(t) + g₀(t, u), Xu,I

≥ 0,

(3.12)

φ(T_i)

A(T_i, V_i)XTi- + ψ0(Ti, Vi), XT_i-

≥ 0.

Поскольку интеграл по мартингалу имеет нулевое математическое ожидание,

то, объединяя (3.11) и (3.12), после подстановки в (3.10) для произвольного

управления получаем неравенство

⎧

⎫

∫

⎨8

∑

⎬

g₀(s),u(s)),X^u,I

ds +

ψ₀(T_i,V_i),X^u,I

≥

T_i

E⎩φ(T),XT,I

⎭

t≤T_i≤T

(3.13)

≥ φ(t), X

Но при использовании управления, удовлетворяющего условиям оптималь-

ности, в неравенстве (3.13) достигается равенство. Предложение доказано.

3.4. Задачи с ограничениями

Конечно, задачи с ограничениями заслуживают отдельной публикации,

здесь приводится лишь набросок возможного подхода. Предположим, что

задан набор критериев (3.14) и допустимое решение должно удовлетворять

ограничениям

J_k[u(·),I] ≤ 0 для всех k = 1,... ,M,

122

где

J_k[u(·),I] =

⎧

⎫

∫

⎨8

∑

⎬

(3.14)

g_k(s.u(s)),X_s ds +

ψ_k((τ_i,V_i),Xτi-

=E⎩φk,XT

⎭

τ_i≤T

В предположении непустоты множества допустимых траекторий при допуще-

нии расширения множества управлений до множества управлений-мер мож-

но использовать процедуру лагранжевой минимизации, которая применима,

если множество допустимых значений критериев {J_k} ∈ R^M выпукло. Это

свойство, как показано в [25-27], справедливо для задач управления с непре-

рывными управлениями, однако и для задачи одновременного непрерывного

и импульсного управления его можно также установить для расширенного

класса управлений-мер. Довольно длинное доказательство повторяет в ос-

новном рассуждения, приведенные в [25, 26], и будет предметом отдельной

публикации.

4. Примеры с импульсными управлениями

4.1. Детерминированное непрерывное управление

В данной статье рассматривается модель системы обслуживания с расши-

рением, допускающим импульсное управление, с N = 4 состояниями:

• 1 — “нагрузка ниже нормальной”,

• 2 — “нормальная”,

• 3 — “критически высокая, требующая немедленной очистки буфера”,

• 4 — “переполнение, приводящее к остановке обслуживания или требующее

немедленной очистки очереди заявок и снижения нагрузки до нормаль-

ной”.

Допустимые переходы, соответствующие непрерывной динамике:

• 1 → 2,2 → 3,3 → 4, которые происходят с интенсивностью λ(t) входного

потока заявок;

• 2 → 1,3 → 2,4 → 3, которые происходят с интенсивностью μ(t) ∈ [0,U(X_t)]

обслуживания заявок;

• переходы, соответствующие импульсному управлению, допустимы в со-

стояниях 3, 4 и переводят систему из состояния 3 → 2 и 4 → 2;

• возможны случайные переходы, например при использовании импульсного

управления из состояния 4 → 2 или 4 → 3 с вероятностями p₁ и 1 - p₁

соответственно.

Состояние 4 является критическим, и время нахождения в нем желатель-

но минимизировать. Цель управления — “поддерживать” систему в состоя-

нии 2, сохраняя при этом время нахождения в состояниях 3, 4 на прием-

лемом уровне. Вектор состояния X ∈ R⁴, а матрица интенсивностей пере-

ходов A(t, μ), зависящая от “непрерывного” управления μ, имеет вид (для

123

простоты опускаем зависимости от времени t)

⎛

⎞

-λ

μ₂

⎜

-(λ + μ₂)

μ₃

⎟

A(t, μ) =

⎝

⎠.

-(λ + μ₃) μ₄

-μ₄

Переменные μ₂, μ₃, μ₄ соответствуют интенсивности обработки требований в

состояниях 2-4 соответственно.

Предложенная в статье модель аналогична как задачам управления уров-

нем воды в водохранилище [19, 31, 32], так и задачам управления потоками

данных в интернете [16, 17]. Данная аналогия не столь искусственна, так как

в обоих случаях увеличение уровня (воды или загрузки) происходит случай-

ным образом за счет дождей или входного потока требований, а уменьшение

уровня — за счет испарения и/или потребления различными потребителями:

промышленностью, сельским хозяйством или населенными пунктами, если

речь идет о воде, или за счет выполнения заданий, если речь идет о системе

обслуживания. В первом случае импульсное управление — это контролируе-

мый слив для избежания переполнения водохранилища, во втором — очистка

буфера заданий для избежания перегрузки. Кроме импульсного управления

используется и “непрерывное”, которое уменьшает уровень в первом случае за

счет снабжения потребителей, а во втором — за счет сокращения числа зада-

ний, ожидающих выполнения. Обе модели имеют определенные особенности,

например интенсивность обслуживания может зависеть от длины очереди, но

и в случае водохранилищ интенсивность снижения уровня за счет испарения

может зависеть от сезонных изменений и текущего уровня.

4.2. Детерминированное импульсное управление

Предполагается возможность использования импульсного управления в

состояниях 3 и 4 с переходами 3 → 2 и 4 → 2.

Матрица перехода, соответствующая применению управления V₃, в состоя-

нии 3 в некоторый момент времени τ_i равна

⎞

^⎛1 0 0 0

⎜0

0⎟

A(τ_i, V₃) =

⎝

⎠,

а матрица, соответствующая применению управления V₄, в состоянии 4 в

некоторый момент времени τ_i равна соответственно

⎞

^⎛1 0 0 0

⎜0

1⎟

A(τ_i, V₄) =

⎝

⎠.

Если плата за импульсное управление выбрана как

(4.1)

ψ₀(t,V ) = (0,0,1,1)^т,

124

то условие применения импульсного управления в точке T_i как функция

от φ(T_i) в соответствии с (3.2) задается соотношением

0≤〈φ(T_i)

A(T_i, V_i)X〉 + 〈ψ₀(T_i, V_i), X〉,

которое дает соотношения для значений φ₂, φ₃, φ₄

φ₃(T_i) ≥ φ₂(T_i) + 1, если X = e₃,

(4.2)

φ₄(T_i) ≥ φ₂(T_i) + 1, если X = e₄.

Текущая плата, характеризующая отклонение от “нормального” состояния 2

и плату за обслуживание, равна

⎛

⎞

⎜

+μ²²

⎟

⎜⁰

⎟

(4.3)

g₀(t,μ) =

⎜

⎟

⎝ 1+μ³

⎠

2+μ²

Здесь μ_i ∈ [0, U(e_i)] для i = 2, 3, 4, что соответствует ограничениям на управ-

ления — интенсивностям обслуживания в соответствующем состоянии.

Таким образом, непрерывная часть системы уравнений (3.1) имеет вид:

⎧

⎪dφ1

⎪

= -λφ₁ + μ₂φ₂ + 1,

⎪

⎪dφ2

⎨

= min

[λφ₁ - (λ + μ₂)φ₂ + μ₃φ₃ + μ²²],

μ₂∈[0,U(e₂)]

(4.4)

⎪dφ3

⎪

= min

[λφ₂ - (λ + μ₃)φ₃ + μ₄φ₄ + μ²³ + 1],

⎪

μ₃∈[0,U(e₃)]

⎪

⎪dφ4

⎩

= min

[λφ₃ - μ₄φ₄ + 2 + μ²⁴].

μ₄∈[0,U(e₄)]

Система (4.4) решается от терминальной точки T с граничным условием (4.1)

и, даже если условие применения импульсного управления выполняется, ее

решение остается непрерывным. Далее при реализации решения если система

находится в состоянии 3 или 4 и условие (4.2) имеет место, то применяется

импульсное управление и система переходит в состояние 2. Поскольку в со-

стоянии 2 импульсное управление недопустимо, то применяется непрерывное

управление до тех пор, пока система не перейдет в состояние 3 или 4 и не

будет выполнено условие применения импульсного управления. Состояние 1

не является недостижимым. Система может оказаться в нем как из-за на-

чальных условий, так и за счет “естественной” динамики.

4.3. Стохастическое импульсное управление

В этом случае после применения импульсного управления возможны пе-

реходы из состояния 4 в состояния 2 и 3 с вероятностями p₁ и 1 - p₁ со-

ответственно. Предполагаем что остальные параметры не меняются. Тогда

125

матрица, соответствующая применению импульсного управления, имеет вид

⎞

^⎛1 0 0

⎜0

p₁

⎟

A(τ_i, V_i) =

⎝

⎠.

1-p₁

Условие возможности применения импульсного воздействия имеет вид

φ₄(T_i) ≥ p₁φ₁(T_i) + (1 - p₁)φ₃(T_i) + 1.

Замечание 5. Следует отметить замечательный факт, что функция φ(t)

остается непрерывной в точках применения импульсного управления. Это,

однако, не удивительно, поскольку, как показано в [25-27], компоненты этой

функции совпадают с сопряженными переменными в принципе максимума,

поэтому они не зависят от управления, как и в случае обычной задачи им-

пульсного управления [6-8].

Схожий пример рассматривался в [33].

4.4. Реализация совместного непрерывного и импульсного управления

Необходимо подчеркнуть разницу между системами с непрерывным и дис-

кретным множествами состояний. В первом случае импульсное управление

прилагается, как правило, в начальный момент времени, если система нахо-

дится выше поверхности переключения. Если затем в результате случайно-

го движения система снова приходит на поверхность разрыва, то импульс-

ное управление действует так, чтобы держать систему ниже поверхности пе-

реключения, реализуя так называемое сингулярное управление отталкива-

ния [34]. В этом случае импульсы не разделяются и возникает сингулярное

управление типа Канторовой лестницы. Управления такого типа характерны

для задач импульсного управления стохастическими процессами диффузи-

онного типа. В случае управления цепью Маркова если условие

V(Xτi ) = ∅

имеет место, то после скачка мгновенное применение импульсного управле-

ния невозможно и следующее импульсное управление возможно только тогда,

когда система снова попадает в состояние, где

V(X_t-) = ∅.

Однако если в результате импульсного управления, имеющего случайный или

детерминированный характер, система либо остается на поверхности пере-

ключения, либо попадает в состояние, где снова возможно импульсное управ-

ление, то импульсы могут повторяться до тех пор, пока система не перейдет в

состояние, где импульсное воздействие невозможно. Таким образом возникает

эффект “множественного” импульса (пачки импульсов) [21]. В рассматривае-

мом примере при переходе из состояния 4 в 3 такой эффект возможен, если

в состоянии 3 снова допустимо применение импульса. В этом случае переход

из состояния 4 в 2 происходит в два скачка 4 → 3 → 2, но стоимость тако-

го импульсного воздействия равна суммарной стоимости двух переходов, т.е.

1 + 1 = 2.

126

4.5. Примеры нахождения “непрерывных” и импульсных управлений

В качестве иллюстрирующего примера рассмотрим систему с детермини-

рованным импульсным управлением, описанную в подразделе 2.3 с парамет-

рами:

• T = 1;

• терминальные условия, соответствующие “штрафу” за пребывание в со-

стояниях 1-4 в конечный момент времени равны

(4.5)

φ₀ = φ(T) = (2,0;1,5;3,5;5,0)^т;

• ограничения на управление или скорость обслуживания μ^max2 = U(e₂) = 0,2,

μ^max3 = U(e₃) = 0,4 задаются только для состояний 2 и 3, а состояние 4 со-

ответствует остановке обслуживания, поэтому состояние 4 предполагается

поглощающим.

Таким образом, непрерывная часть системы уравнений (3.1) в этом случае

имеет вид:

⎧

dφ₁

⎪

= -λφ₁ + μ₂φ₂ + 1,

⎪

⎪dφ2

⎨

= min

[λφ₁ - (λ + μ₂)φ₂ + μ₃φ₃ + μ²²],

μ₂∈[0,μ^max2]

(4.6)

⎪dφ3

⎪

= min

[λφ₂ - (λ + μ₃)φ₃ + μ₄φ₄ + μ²³ + 1],

⎪

μ₃∈[0,μ^max3]

⎪

dφ₄

⎩

= λφ₃ + 2.

Решение системы 4.6 в обратном времени для интенсивности потока вход-

ных требований, заданной соотношением

(4.7)

λ(t) = 0,25 cos(2πt) + 0,5,

показано на рис. 1.

Линия переключения (3.2) для допустимого импульсного управления вы-

числяется как SW (t) = φ₃(t) - φ₂(t) - 1 = 0 и приведена на рис. 2. Таким об-

разом, если система находится в состоянии 3 и выполнено условие SW (t) ≥ 0,

то должно использоваться импульсное управление, которое переведет систе-

му в состояние 2. Таким образом, область применения импульсного управле-

ния — это одновременно состояние 3 и временной интервал ≈[0,8; 1, 0].

Заметим, что использование импульсного управления позволяет умень-

шить значение критерия качества, хотя это зависит от вероятности попадания

в состояние 3 на отрезке [0,8; 1,0]. Если это происходит, например, в момент

времени t = 0,8, то значение критерия качества для состояния 3 в момент

окончания процесса t = 1,0 равно φ₂(1, 0) + 1 ≈ 2,5, что меньше, чем без при-

менения импульсного управления, т.е. φ₃(1, 0) ≈ 3,5. Однако для вычисления

значения критерия качества при использовании одновременно непрерывно-

го и импульсного управлений необходимо вычислять значение цены зада-

чи с учетом случайного характера применения импульсного управления, что

127

(t)

4,5

4,0

3,5

3,0

2,5

2,0

1,5

0,2

0,4

0,6

0,8

1,0

Рис. 1. Решение системы (4.6) в обратном времени с терминальными условия-

ми (4.5). 1 — φ₁(t), 2 — φ₂(t), 3 — φ₃(t), 4 — φ₄(t).

1,0

0,5

0,2

0,4

0,6

0,8

1,0

0,5

1,0

Рис. 2. Линия переключения для импульсного управления в состоянии 3. Об-

ласть, где SW (t) ≥ 0, — это область импульсного управления.

должно быть предметом специальной публикации. Другой важный вопрос,

требующий отдельного рассмотрения, — это вычисление функции распреде-

ления состояний при использовании импульсного управления, что приводит

к необходимости решения прямых уравнений Колмогорова, которые в этом

случае будут уже не обыкновенными дифференциальными уравнениями, а

дискретно-непрерывными со случайными временами переключения.

128

5. Заключение

В данной статье развит подход к численному решению задачи стохастиче-

ского управления МЦ с “непрерывными” и импульсными управлениями. Важ-

ной особенностью модели МЦ является более простая процедура определения

условий оптимальности, чем для стохастических систем с непрерывным мно-

жеством состояний. Дальнейшие исследования будут направлены на решение

прикладных задач управления природными ресурсами с использованием мо-

делей МЦ, например для управления водоснабжением [19], распределением

природного газа [20], управлением передачей данных через телекоммуника-

ционные сети с нестабильными характеристиками и, в частности, для связи

и передачи данных с беспилотными летательными аппаратами [30, 35].

СПИСОК ЛИТЕРАТУРЫ

Бенсусан А., Лионс Ж.-Л. Импульсное управление и квазивариационные нера-

венства / Пер. с франц. М.: Наука, 1987.

Bensoussan A., Lions J.L. Contrôle Impulsionnel et Inéquations

Quasivariationnelles. Bordas. Paris: Dunod, 1982.

Yushkevich A.A. Marкov Decision Processes with Both Continuous and Impulsive

Control // Arkin V.I., Shiraev A., Wets R. (eds). Stochastic Optimization. Lect.

Notes in Control and Information Sci. 1986. V. 81. P. 234-246. Berlin. Heidelberg:

Springer. DOI 10.1007/BFb0007100

Gatarek D. Impulsive Control of Piecewise-Deterministic Processes // Zabczyk J.

(eds). Stochastic Systems and Optimization. Lect. Notes in Control and Information

Sci. 1989. V. 136. P. 298-308. Berlin, Heidelberg: Springer. DOI 10.1007/BFb0002690

Dempster M.A.H., Ye J.J. Impulse Control of Piecewise Deterministic Markov

Processes // Ann. Appl. Prob. 1995. V. 5. No. 2. P. 399-423.

DOI 10.1214/aoap/1177004771

Dufour F., Miller B.M. Generalized Solutions in Nonlinear Stochastic Control

Problems // SIAM J. Control Optim. 2002. V. 40. P. 1724-1745.

DOI 10.1137/S0363012900374221

Miller B.M., Rubinovich E.Ya. Impusive Control in Continuous and Discrete-

Continuous Systems. N.Y.: Kluwer Acad./Plenum Publishres, 2003.

DOI 10.1007/978-1-4615-0095-7

Миллер Б.М., Рубинович Е.Я. Оптимизация динамических систем с импульс-

ными управлениями. М.: Наука, 2005.

Миллер Б.М., Рубинович Е.Я. Оптимизация динамических систем с импульс-

ными управлениями и ударными воздействиями. М.: ЛЕНАНД/URSS, 2019.

Dufour F., Horiguchi M., Piunovskiy A.B. Optimal Impulsive Control of Piecewise

Ddeterministic Markov Processes // Stochastics. 2016. V. 88. No. 7. P. 1073-1098.

DOI 10.1080/17442508.2016.1197925

10.

Shujun Wang, Zhen Wu Maximum Principle for Optimal Control Problems of

Forward-Backward Regime-Switching Systems Involving Impulse Controls // Math.

Probl. Eng. 2015. Article ID 892304. http://dx.doi.org/10.1155/2015/892304.

11.

Dufour F., Piunovskiy A.B. Impulsive Control for Continuous-Time Markov Decision

Processes: A Linear Programming Approach // Appl. Math. Optim. 2016. V. 74.

P. 129-161. DOI 10.1007/s00245-015-9310-8

129

12.

Delebecque F., Quadrat J.-P. Optimal Control of Markov Chains Admitting Strong

and Weak Interactions // Automatica. 1981. V. 17. No. 2. P. 281-296.

DOI 10.1016/0005-1098(81)90047-9

13.

Bae J., Kim S., Lee E.Y. Average Cost under the p^Mλ,τ Policy in a Finite Dam with

Compound Poisson Inputs // J. Appl. Probab. 2003. V. 40. No. 2. P. 519-526.

DOI 10.1239/jap/1053003561

14.

Filar J.A., Vrieze K. Competitive Markov Decision Processes — Theory, Algorithms

and Applications. N.Y.: Springer, 1997. DOI 10.1007/978-1-4612-4054-9

15.

Williams B.K. Markov Decision Processes in Natural Resources Management:

Observability and Uncertainty // Ecological Modelling. 2009. V. 220. No. 6. P. 830-

840. DOI 10.1016/j.ecolmodel.2008.12.023

16.

Miller A. Dynamic access control with active users // J. of Communications

Technology and Electronics. 2010. V. 55. No. 12. P. 1432-1441.

DOI 10.1134/S1064226910120168

17.

Miller A., Miller B. Control of Connected Markov Chains. Application to Congestion

Avoidance in the Internet // Proc. 50th IEEE Conf. on Decision and Control and

European Control Conf. (CDC-ECC) Orlando, FL, USA, 2011, December 12-15,

2011. P. 7242-7248. DOI 10.1109/CDC.2011.6161029

18.

Miller B., McInnes D. Optimal Management of a Two Dam System via Stochastic

Control: Parallel Computing Approach // Proc. 50th IEEE Conf. on Decision

and Control and European Control Conf. (CDC-ECC) Orlando, FL, USA,

December 12-15, 2011. P. 1417-1423. DOI 10.1109/CDC.2011.6160566

19.

McInnes D., Miller B. Optimal Control of Large Dam Using Time-Inhomogeneous

Markov Chains with an Application to Flood Control // IFAC-PapersOnLine. 2017.

V. 50. No. 1. P. 3499-3504. DOI 10.1016/j.ifacol.2017.08.936

20.

McInnes D., Miller B., Schreider S. Optimisation of Gas Flows in South Eastern

Australia via Controllable Markov Chains // Proc. Australian Control Conf.

November 3-4, 2016. Newcastle: Engineers Australia.

P. 341-346. DOI 10.1109/AUCC.2016.7868213

21.

Avrachenkov K., Habachi O., Piunovskiy A., Zhang Y. Infinite Horizon Optimal

Impulsive Control with Applications to Internet Congestion Control // Int. J.

Control. 2015. V. 88. No. 4. P. 703-716. DOI: 10.1080/00207179.2014.971436

22.

McInnes D., Miller B. Optimal Control of Time-Inhomogeneous Markov Chains with

Application to Dam Management // Proc. Australian Control Conf. 4-5 November,

2013, Perth, Australia. 2013. P. 230-237. DOI 10.1109/AUCC.2013.6697278

23.

Kushner H.J., Dupuis P.G. Numerical Methods for Stochastic Control Problems in

Continuous Time. 2nd ed. N.Y.: Springer Science+Business Media, 2001.

DOI 10.1007/978-1-4613-0007-6

24.

Elliott R.J., Aggoun L., Moore J.B. Hidden Markov Models. Estimation and Control.

N.Y.: Springer Verlag, 2008. DOI 10.1007/978-0-387-84854-9

25.

Miller B., Miller G., Semenikhin K. Torwards the Optimal Control of Markov Chains

with Constraints // Automatica. 2010. V. 46. P. 1495-1502.

DOI 10.1016/j.automatica.2010.06.003

26.

Миллер Б.М., Миллер Г.Б., Семенихин К.В Методы синтеза оптимального

управления марковским процессом с конечным множеством состояний при на-

личии ограничений // АиТ. 2011. № 2. С. 111-130.

Miller B.M., Miller G.B., Semenikhin K.V. Methods to Design Optimal Control

of Markov Process with Finite State Set in the Presence of Constraints // Autom.

Remote Control. 2011. V. 72. No. 2. P. 323-341.

130

27.

Миллер Б.М., Миллер Г.Б., Семенихин К.В. Регуляризация задачи оптималь-

ного управления марковским процессом с конечным числом состояний при на-

личии ограничений // АиТ. 2016. № 9. С. 96-123.

Miller B.M., Miller G.B., Semenikhin K.V. Optimal Control Problem Regularization

for the Markov Process with Finite Number of States and Constraints // Autom.

Remote Control. 2016. V. 77. No. 9. P. 1589-1611. DOI 10.1134/S0005117916090071

28.

Brémaud P. Point Processes and Queues: Martingale Dynamics. N.Y.: Springer,

1981.

29.

Liptser R.Sh., Shiryaev A.N. Statistics of Random Processes. N.Y.: Springer, 1979.

30.

Miller B., Miller G., Semenikhin K. Optimization of the Data Transmission Flow

from Moving Object to Nonhomogeneous Network of Base Stations // IFAC-

PapersOnLine. 2017. V. 50. No. 1. P. 6160-6165. DOI 10.1016/j.ifacol.2017.08.981

31.

Miller A., Miller B., Popov A., Stepanyan K. Towards the Development of Numerical

Procedure for Control of Connected Markov Chains // Proc. 5th Australian Control

Conf. (AUCC). November 5-6, 2015, Gold Coast, QLD, Australia. 2015. P. 336-341.

32.

Miller B., Stepanyan K., Miller A., Popov A. Towards One Nonconvex Connected

Markov Chain Control Problem. An Approach to Numerical Solution // 2018

Australian New Zealand Control Conf. (ANZCC). Swinburne University of

Technology. Melbourne, Australia, Dec. 7-8, 2018. P. 172-177.

DOI: 10.1109/ANZCC.2018.8606576

33.

Miller A., Miller B., Stepanyan K. A numerical Approach to Joint Continuous and

Impulsive Control of Markov Chains // IFAC-PapersOnLine. 2018. V. 51. No. 32.

P. 462-467. DOI:10.1016/j.ifacol.2018.11.428

34.

Karatzas I., Shreve S.E. Connection Between Optimal Stopping and Singular

Stochastic Control I. Monotone Follower Problems // SIAM J. Control Optim. 1984.

V. 22. No. 6. P. 856-877. DOI 10.1137/0322054

35.

Миллер Б.М., Миллер Г.Б., Семенихин К.В Оптимизация выбора каналов связи

при передаче потока данных с учетом потерь // АиТ. 2018. № 1. С. 84-99.

Miller B.M., Miller G.B., Semenikhin K.V. Optimal Channel Choice for Lossy Data

Flow Transmission // Autom. Remote Control. 2018. V. 79. No. 1. P. 66-77.

DOI 10.1134/S000511791801006X

Статья представлена к публикации членом редколлегии Е.Я. Рубиновичем.

Поступила в редакцию 20.06.2019

После доработки 14.08.2019

Принята к публикации 26.09.2019

131