Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі
An investigated sequential analysis of optimal decision making problems for weakly disturbed Markov and semi-Markov models is based on the sequential solution of optimal stopping problems of nondisturbed aggregate and weakly disturbed dissaggregate models.
Gespeichert in:
| Datum: | 2019 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/176474 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1867334393319653376 |
|---|---|
| author | Andreev, N. V. |
| author_facet | Andreev, N. V. |
| author_institution_txt_mv | [
{
"author": "N. V. Andreev",
"institution": null
}
] |
| author_sort | Andreev, N. V. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-08-20T18:16:43Z |
| description | An investigated sequential analysis of optimal decision making problems for weakly disturbed Markov and semi-Markov models is based on the sequential solution of optimal stopping problems of nondisturbed aggregate and weakly disturbed dissaggregate models. |
| first_indexed | 2025-07-17T10:26:14Z |
| format | Article |
| fulltext |
© Н.В. Андреев, 2002
Системні дослідження та інформаційні технології, 2002, 3 139
TIДC
НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ,
ІНФОРМАТИЦІ ТА
ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ
УДК 519.24.5
ОПТИМАЛЬНАЯ ОСТАНОВКА АГРЕГИРОВАННЫХ И
СЛАБОВОЗМУЩЕННЫХ ДЕЗАГРЕГИРОВАННЫХ
МАРКОВСКИХ И ПОЛУМАРКОВСКИХ МОДЕЛЕЙ В
ДИСКРЕТНОМ ВРЕМЕНИ
Н.В. АНДРЕЕВ
Исследуется последовательный анализ проблем принятия оптимальных
решений для слабовозмущенных марковских и полумарковских моделей на
основе последовательного решения задач оптимальной остановки невозмущенной
агрегированной и слабовозмущенной дезагрегированной моделей.
ВВЕДЕНИЕ
Результаты этой статьи могут быть проинтерпретированы в терминах
некоторых решений проблемы оптимального инвестирования, которая
соответствует задаче оптимальной агрегированной остановки и принятия
решения об обоснованном выборе более перспективного региона страны как
объекта инвестирования на макроэкономическом уровне. В то же время
задача дезагрегированной оптимальной остановки соответствует микроэко-
номическому уровню, включая проблему оптимального выбора некоторого
перспективного экономического или финансового объекта, находящегося в
регионе, выбранном в задаче агрегированной оптимальной остановки.
Рассматриваемые модели могут быть использованы при трактовке и
исследовании не только инвестиционных, но также инновационных и других
процессов. Область их применения охватывает различные сферы человеческой
деятельности.
Для описания детерминированных и стохастических моделей с малыми
возмущениями характерно наличие в уравнениях модели аддитивной
составляющей с малым параметром. Путем разложения в ряд по малому
параметру некоторого функционала, заданного на траектории модели и
характеризующего цену остановки, можно определить цену оптимальной
остановки, удовлетворяющую уравнению оптимальности, выводу и
исследованию которого здесь уделяется значительное внимание.
В настоящей статье рассматривается вероятностная модель ),,( gPE ε с
фазовым пространством состояний (ФПС) E , переходным оператором εP
( 0≥ε — достаточно малый числовой параметр) и с функцией выигрыша
Н.В. Андреев
ISSN 1681–6048 System Research & Information Technologies, 2002, 3 140
)(xg , характеризующей выигрыш от остановки модели { }0, ≥nX n
ε в
состоянии Exx ∈, . Переходный оператор εP , или в конечном случае
матрица вероятностей перехода представляется в виде
10 PPP εε −= , 10 ≤≤ ε , (1)
где 0P — матрица вероятностей перехода невозмущенной цепи Маркова, 1P
— матрица возмущений.
В этом контексте отождествление в некоторых местах терминов
«переходный оператор» и «матрица переходных вероятностей» не вызывает
недоразумений, поскольку они отражают специфику ФПС модели
(бесконечное и конечное), в то время как методика построения модели и
последующей ее оптимизации распространяется на общий случай конечного
или счетного объединения произвольных измеримых ФПС. Матрица или
оператор возмущений 1P играет существенную роль в последующем
агрегировании модели, реализация которого осуществляется на основе
общей теории возмущения приводимо-обратимых операторов на спектре
[1, 5].
Набор ( )gPE ,, ε характеризует также возмущенный процесс марковского
восстановления (ПМВ), представляющий собой возмущенный полумарковский
процесс в дискретном времени. При этом E — его ФПС; εP — матрица
вероятностей перехода вложенной цепи Маркова (ВЦМ) { }0; ≥nX n
ε ;
( ){ }Exxgg ∈= ; — функция выигрыша, построенная с учетом характеристик,
задающих ПМВ { }0,, ≥nX nn θε .
Представление матрицы εP в виде разности стохастической матрицы
0P и матрицы возмущений 1P , умноженной на малый параметр ε в (1),
приводит к двум альтернативным ситуациям:
1) существует поглощающее состояние модели (1);
2) поглощающего состояния не существует и появляется возможность
агрегирования модели (1).
Последнее имеет место при выполнении следующего условия, которому
должна удовлетворять матрица возмущений 1P : сумма элементов каждой
строки матрицы 1P равна нулю.
Пусть { }xnn PFX ,, — однородный необрывающийся марковский процесс
с дискретным временем 0≥n в измеримом пространстве ( )BE, ,
( ){ }Exxgg ∈= , — неотрицательная B -измеримая функция. Обозначим
M класс марковских моментов и будем говорить, что M∈τ задает
некоторое правило остановки. Возникает задача выбора M∈τ с целью
максимизации среднего «выигрыша» ( )τXgM x , где xM — символ
математического ожидания, соответствующего вероятностной мере xP .
Рассмотрим функцию
( ) ( )τ
τ
XgMxs x
M∈
= sup , (2)
Оптимальная остановка агрегированных и слабовозмущенных дезагрегированных моделей
Системні дослідження та інформаційні технології, 2002, 3 141
называемую обычно ценой [2, 3].
Автором получено уравнение оптимальности типа Вальда для цены
оптимальной остановки слабовозмущенных моделей (1), исследованы
вопросы существования и единственности его решения, найдено это
решение и на его основе предложен алгоритм построения оптимального
правила остановки. Исследованы также асимптотические свойства решения
уравнения оптимальности и соответствующее ему асимптотическое
оптимальное правило остановки.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ПЛАНИРОВАНИЯ ЭКСПЕРИМЕНТА
Процесс марковского восстановления (ПМВ) { }0,, ≥nX nn θε с фазовым
пространством состояний ∪
N
k
kEE
1=
= , jiEE ji ≠= ,0∩ [1] определяется
полумарковским ядром ( ) ( ) ∈= ttGptQ kkrkr ,εε [0,∞ ), где ;: εεε ε krkrkr ppp −=
Erk ∈, — переходные вероятности ВЦМ. Очевидно, что расщепленное
ФПС E индуцирует случай нескольких (здесь N ) слабозависимых цепей
Маркова. Блочно-диагональная матрица вероятностей перехода (МВЦ)
( ),,...,10 NPPP diag= описывающая N невозмущенных независимых цепей
Маркова, является эргодической со стационарным распределением
),...,( 00
1
0
Nρρρ = ; 1P — матрица возмущений, соответствующая матрице
0P ; ( )tGk — функция распределения времени пребывания непрерывной
компоненты nθ в состоянии k . Если в состоянии k принято решение об
остановке и время, проведенное в этом состоянии, равно t , то ожидаемый
выигрыш равен ( )tkr , . Функция ( )tkr , — неотрицательная, измеримая по t
и ограниченная по k . Необходимо выбрать правило остановки,
обеспечивающее наибольший выигрыш.
Эта задача сводится к задаче об оптимальной остановке ВЦМ
{ }0; ≥nX n
ε с переходными вероятностями, заданными в виде
{ } ,,...,1,0,/: ,
110
1 NiEkpppkXrXPp i
Er
krkrkrnnkr
i
=∈=−==== ∑
∈
+ εεεε (3)
где МВП { }ErkpP kr ∈= ,;0
0 — невозмущенная цепь Маркова, эргодическая
со стационарным распределением { }N
0
1
00 ,..., ρρρ = ; 1
krp — элемент
матрицы возмущений { }ErkpP kr ∈= ,;1
1 и с функцией выигрыша =)(xg
( ) ( ) ( ) .,,,
0
ExdtGtkrkMr kk ∈== ∫
∞
θ
Пусть ( )EL — множество ограниченных неотрицательных функций на
E ; ( )ELg∈ ; εM — множество моментов остановки, для которых
{ } 1=∞<τP для каждого ε и ( ) ( )ετ
τ
ε
ε
XgMxs x
M
sup
∈
= — цена оптимальной
остановки.
Н.В. Андреев
ISSN 1681–6048 System Research & Information Technologies, 2002, 3 142
Функция ( ){ }Exxss ∈= ;εε является единственным решением
уравнения типа Вальда [1, 4]
{ }cPgs += εε ,max , (4)
где функция средней стоимости непрерывного наблюдения ( ){ }Ekkcc ∈= ;
определена на E , ( ) ( )kkMckc θ,= , а функция ( )kkc θ, характеризует
удельную стоимость наблюдения в состоянии k в течение времени kθ ;
функция ( )tkc , — неотрицательная, измерима по t и ограничена по k .
Марковский момент ετ , определенный формулой
{ }εετ Γ∈= nXn :inf , ( ) ( ){ }xgxsx ==Γ εε : ,
является оптимальным моментом остановки для заданного плана
экспериментов при фиксированном ε .
Для конструктивного нахождения оптимального момента остановки ετ
используем метод укрупнения математической модели с преобразованием
ФПС E в другое ФПС Ê — это первый этап последовательного решения
этой задачи, к рассмотрению которого мы и переходим.
ЗАДАЧА ОПТИМАЛЬНОЙ ОСТАНОВКИ В АГРЕГИРОВАННОМ СЛУЧАЕ
Рассмотрим стохастическое укрупнение исходной модели с ФПС E при
помощи функции i такой, что ( ) ., iExixi ∈=
В результате мы приходим к задаче оптимальной остановки для
последовательности
( ){ }0,ˆ ≥nig n и ( ){ }0,ˆ ≥nic n ,
где ( ) ( ) ( )xgdxig
iE
i∫= 0ˆ ρ , ( ) ( ) ( )xcdxic
iE
i∫= 0ˆ ρ .
Последовательность { }0, ≥nin является марковской цепью с ФПС
{ }NE ,...,1ˆ = , и переходным оператором, для которого
( ) ( ) ( ) ( )11
ˆ
1 ,ˆˆ
1
ifiiPifMifP
Ei
i ∑
∈
== ,
где
( ) ( ) ( ) ( )
⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧
== ∫ ∫
i iE E
iijiij ExPdxExPdxpP ,/,ˆˆ
1
0
1
0 ρρ (5)
,iEx∈ NjijiEEE ii ,...,1,,,\ =≠= .
Здесь все формулы, содержащие буквы с «крышкой сверху» pcg ˆ,ˆ,ˆ
представляют собой результат стохастического агрегирования исходной
Оптимальная остановка агрегированных и слабовозмущенных дезагрегированных моделей
Системні дослідження та інформаційні технології, 2002, 3 143
функции цели g , функции средней стоимости наблюдения c и элементов
стохастической матрицы ВЦМ εP соответственно.
Мы также предположим, что агрегированная модель с МПВ
{ }EjipP ij
ˆ,;ˆˆ ∈= соответствует эргодической укрупненной цепи Маркова
{ }0; ≥nin с одним эргодическим классом состояний со СР { }Nρρρ ˆ,...,ˆˆ 1= ,
( )ELcg ˆˆ,ˆ ∈ ; M̂ — класс марковских моментов для агрегированной модели,
( ) ( )τ
τ
igMks k
M
ˆˆsupˆ
ˆ∈
= ; ( )( )Ekkss ˆ,ˆˆ ∈= — цена оптимальной остановки.
При вышеуказанных предположениях соответствующее уравнение типа
Вальда
}{ csPgs ˆˆˆ,ˆmaxˆ += (6)
имеет единственное решение ŝ вида { }0ˆ,ˆmaxˆ sgs = , где функция 0ŝ
является минимальным решением линейного уравнения csPs ˆˆˆˆ 00 += ,
представленного в виде
*00 ˆˆˆˆ gcRs += 1, (7)
где 1
00 )ˆˆ(ˆ −Π+−= PIR — обобщенный обратный оператор к оператору
Π− ˆ);ˆ( 0PI — стационарный проектор, индуцированный СР ρ̂ ;
постоянная { };ˆˆ),ˆ(ˆminˆ* Eeegg ∈= символ 1 обозначает единицу в Ê .
Поэтому решение агрегированного уравнения типа Вальда можно
представить в виде
{ }0ˆ,ˆmaxˆ sgs = . (8)
Марковский момент, определяемый формулой { }Γ∈= ˆ:inf*
ninτ , где
( ) ( ){ }igisi ˆˆ:ˆ ==Γ является оптимальным моментом остановки планирования
эксперимента для агрегированной модели.
Обозначим через *i состояние агрегированной модели { }0, ≥nin в
момент *τ , так, что ** τ
ii =
ЗАДАЧА ОПТИМАЛЬНОЙ ОСТАНОВКИ В ДЕЗАГРЕРИРОВАННОМ СЛУЧАЕ
Дезагрегирование состояния *i , с помощью преобразования ( )
*
*1* : iEii →
−
,
а также рассмотрение дезагрегированной модели ( )gPE ,,* ε и
соответствующего этому случаю критерия оптимизации представляют
собой второй этап последовательного анализа задачи об оптимальной
остановке. εM — множество моментов остановки ετ для которых
{ } 1* =< εε ζτP , где *
εζ — момент выхода из множества *E , индуцированный
моделью, заданной МПВ
Н.В. Андреев
ISSN 1681–6048 System Research & Information Technologies, 2002, 3 144
{ } { }*
10
* ,;,, ErkppErkpP krkrkr ∈−=∈= εε
ε ,
1,0: 000* =>∈∃ εε ppEk k . (9)
Здесь { }0 — поглощающее состояние модели, которое с положительной
вероятностью достижимо при выходе модели из множества *E .
Пусть ( ) ( )ετ
ετ
ε XgMks k
M∈
= sup , тогда ( )( )*, Ekkss ∈= εε — цена
оптимальной остановки, являющаяся единственным решением уравнения
типа Вальда
{ }csPgs += εεε ,max . (10)
Единственное решение уравнения (10) представляется в виде [4]
{ }0,max εε sgs = , (11)
где { }*
00 , Ekss ∈= εε — решение линейного уравнения
csPs += 00
εεε , (12)
представимого в виде
m
m
mss ∑
∞
=
=
0
0 εε , (13)
где коэффициенты ms определяются рекуррентно в виде [1, 4]
qcs ˆ/ˆ0 = 1, qRs mmm ˆ/ˆ 10 ++= ψϕ 1, 0≥m ,
( )∑
∈
=
*
0ˆ
Ek
k kcc ρ , ∑
∈
=
*
1
0
0ˆ
Ek
kk pq ρ 1.
Здесь 1 — единица в *E ;
0
R — обобщенный обратный оператор оператора
( )0PI − ; { } qcqqc ˆ/ˆˆ0 −=ϕ , { } ,ˆ/ˆˆ 11 qqq mmm −− −= ψψϕ ( )km
Ek
km ψρψ ∑
∈
=
*
0ˆ ,
0≥m .
Ряд (13), представляющий 0
εs , абсолютно сходится для достаточно
малых ε .
Марковский момент, заданный формулой
{ }** :inf ε
ε
ετ Γ∈= nXn , (14)
где множество ( ) ( ){ }kgksEk =∈=Γ εε :*
* , определяет оптимальный момент
остановки при планировании эксперимента для исходной модели
марковского восстановления с малыми возмущениями, которые соответствуют
различным .1, ≤≤ εε o
Оптимальная остановка агрегированных и слабовозмущенных дезагрегированных моделей
Системні дослідження та інформаційні технології, 2002, 3 145
ЗАКЛЮЧЕНИЕ
При решении исходной задачи принятия решений о выборе оптимального
состояния модели мы строим множество εΓ , используя решение уравнения
оптимальности (4), однако определение функции εs прямым путем является
достаточно сложной задачей, принимая во внимание сложность структуры
ФПС E исходной модели { }0,, ≥nX nn θε . Поэтому решение исходной
задачи (4) предусматривает двойное применение решения задач
оптимальной остановки агрегированных (6) и слабовозмущенных
дезагрегированных (10) марковских и полумарковских моделей. Во-первых,
с помощью метода агрегирования (5) иcходной модели мы построили
множество ( ) ( ){ }igisEi ˆˆ:ˆˆ =∈=Γ , содержащее состояние *i , момент
достижения которого соответствует оптимальному моменту остановки *τ̂
агрегированной модели { }0, ≥nin с функциями выиграша ĝ и стоимости
наблюдений ĉ соответственно. Во-вторых, методом разукрупнения ФПС
модели при помощи замены состояния *i на ** i
EE = , мы нашли
оптимальный момент остановки *
ετ , построив множество *
εΓ , которым
определяется решение исходной проблемы принятия решения.
Таким образом, предложен специфический метод декомпозиции
решения задачи принятия решений для исходного случая нескольких
слабозависимых цепей Маркова или процессов марковского восстановления,
представляющий собой двухэтапный процесс случайного поиска. Сначала
поиск проводится поверхностно на агрегированной модели, а последующий
дезагрегированный участок, отобранный ранее, подвергается гораздо более
тщательному изучению. На каждом из этих этапов решается поставленная
задача оптимальной остановки случайного эксперимента, обеспечивающего
максимизацию ожидаемого от поиска дохода.
ЛИТЕРАТУРА
1. Андреев Н.В. Оптимальная остановка процесса марковского восстановления с
малой вероятностью поглощения // Кибернетика и системный анализ.—
1994. — № 6. — С. 176–179.
2. Дынкин Е.Б. Оптимальный выбор момента остановки марковского процесса //
ДАН СССР. — 1963. — 150, № 2. — С. 238–240.
3. Григелионис Б.И., Ширяев А.Н. О задаче Стефана и оптимальных правилах
остановки марковских процессов // Теория вероятностей и ее применения.
— 1966. — 11, № 4.
4. Andreev A.M., Andreev M.V. On the Solution of Optimal Stopping Problem for
Markov Renewal Processes with Small Absorbtion Probability, Abstracts,
Mathematical Theory of Systems and Networks. — Perpignan, France, 2000.
5. Korolyuk V.S., Turbin A.F. Mathematical Foundation of the Lumping of Large
Systems. — 1993. — 264. — 278 p.
Поступила 19.07.2002
|
| id | journaliasakpiua-article-176474 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:26:14Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/d4/74a39f08715e889518b3bbaa890100d4.pdf |
| spelling | journaliasakpiua-article-1764742019-08-20T18:16:43Z Optimal stopping of aggregate and weakly disturbed disaggregate Markov and semi-Markov models in discrete time Оптимальная остановка агрегированных и слабовозмущенных дезагрегированных марковских и полумарковских моделей в дискретном времени Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі Andreev, N. V. An investigated sequential analysis of optimal decision making problems for weakly disturbed Markov and semi-Markov models is based on the sequential solution of optimal stopping problems of nondisturbed aggregate and weakly disturbed dissaggregate models. Исследуется последовательный анализ проблем принятия оптимальных решений для слабовозмущенных марковских и полумарковских моделей на основе последовательного решения задач оптимальной остановки невозмущенной агрегированной и слабовозмущенной дезагрегированной моделей. Досліджується послідовний аналіз проблем прийняття оптимальних рішень для слабозбурених марковських та напівмарковських моделей на основі послідовного розв’язання задач оптимальної зупинки незбуреної агрегованої та слабозбуреної дезагрегованої моделей. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-08-20 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/176474 System research and information technologies; No. 3 (2002); 139-145 Системные исследования и информационные технологии; № 3 (2002); 139-145 Системні дослідження та інформаційні технології; № 3 (2002); 139-145 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/176474/176245 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Andreev, N. V. Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі |
| title | Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі |
| title_alt | Optimal stopping of aggregate and weakly disturbed disaggregate Markov and semi-Markov models in discrete time Оптимальная остановка агрегированных и слабовозмущенных дезагрегированных марковских и полумарковских моделей в дискретном времени |
| title_full | Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі |
| title_fullStr | Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі |
| title_full_unstemmed | Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі |
| title_short | Оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі |
| title_sort | оптимальна зупинка агрегованих та слабозбурених дезагрегованих марковських та напівмарковських моделей у дискретному часі |
| url | https://journal.iasa.kpi.ua/article/view/176474 |
| work_keys_str_mv | AT andreevnv optimalstoppingofaggregateandweaklydisturbeddisaggregatemarkovandsemimarkovmodelsindiscretetime AT andreevnv optimalʹnaâostanovkaagregirovannyhislabovozmuŝennyhdezagregirovannyhmarkovskihipolumarkovskihmodelejvdiskretnomvremeni AT andreevnv optimalʹnazupinkaagregovanihtaslabozburenihdezagregovanihmarkovsʹkihtanapívmarkovsʹkihmodelejudiskretnomučasí |