Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням

Проведено аналіз оптимальних та асимптотично оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням. Розглянуто також синтез оптимальної стратегії контролю пуассонового процесу....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2003
Автор:	Андрєєв, М.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2003
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Методи аналізу та управління системами в умовах ризику і невизначеності
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/50307
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням / М.В. Андрєєв // Систем. дослідж. та інформ. технології. — 2003. — № 4. — С. 120-132. — Бібліогр.: 7 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50307
record_format	dspace
spelling	irk-123456789-503072013-10-10T03:06:50Z Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням Андрєєв, М.В. Методи аналізу та управління системами в умовах ризику і невизначеності Проведено аналіз оптимальних та асимптотично оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням. Розглянуто також синтез оптимальної стратегії контролю пуассонового процесу. Проведен анализ оптимальных и асимптотически оптимальных стратегий контроля сложных пуассоновских процессов и полумарковских процессов с поглощением. Рассмотрен также синтез оптимальной стратегии и контроля пуассоновского процесса. Analysis of optimal and asymptoticly optimal checking strategies for complex Poisson’s processes and semi-Markov processes with absorption has been performed. Optimal checking strategy synthesis of Poisson’s process is considered too. 2003 Article Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням / М.В. Андрєєв // Систем. дослідж. та інформ. технології. — 2003. — № 4. — С. 120-132. — Бібліогр.: 7 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50307 519.87: (62.50 + 519.718) ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методи аналізу та управління системами в умовах ризику і невизначеності Методи аналізу та управління системами в умовах ризику і невизначеності
spellingShingle	Методи аналізу та управління системами в умовах ризику і невизначеності Методи аналізу та управління системами в умовах ризику і невизначеності Андрєєв, М.В. Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням Системні дослідження та інформаційні технології
description	Проведено аналіз оптимальних та асимптотично оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням. Розглянуто також синтез оптимальної стратегії контролю пуассонового процесу.
format	Article
author	Андрєєв, М.В.
author_facet	Андрєєв, М.В.
author_sort	Андрєєв, М.В.
title	Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням
title_short	Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням
title_full	Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням
title_fullStr	Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням
title_full_unstemmed	Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням
title_sort	аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2003
topic_facet	Методи аналізу та управління системами в умовах ризику і невизначеності
url	http://dspace.nbuv.gov.ua/handle/123456789/50307
citation_txt	Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням / М.В. Андрєєв // Систем. дослідж. та інформ. технології. — 2003. — № 4. — С. 120-132. — Бібліогр.: 7 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT andrêêvmv analízísintezoptimalʹnihstrategíjkontrolûskladnihpuassonovihprocesívtanapívmarkovsʹkihprocesívzpoglinannâm
first_indexed	2025-07-04T11:54:07Z
last_indexed	2025-07-04T11:54:07Z
_version_	1836717229103644672
fulltext	© М.В.Андрєєв, 2003 120 ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 TIДC МЕТОДИ АНАЛІЗУ ТА УПРАВЛІННЯ СИСТЕМАМИ В УМОВАХ РИЗИКУ І НЕВИЗНАЧЕНОСТІ УДК 519.87: (62.50 + 519.718) АНАЛІЗ І СИНТЕЗ ОПТИМАЛЬНИХ СТРАТЕГІЙ КОНТРОЛЮ СКЛАДНИХ ПУАССОНОВИХ ПРОЦЕСІВ ТА НАПІВМАРКОВСЬКИХ ПРОЦЕСІВ З ПОГЛИНАННЯМ М.В. АНДРЄЄВ Проведено аналіз оптимальних та асимптотично оптимальних стратегій конт- ролю складних пуассонових процесів та напівмарковських процесів з погли- нанням. Розглянуто також синтез оптимальної стратегії контролю пуассоново- го процесу. ВСТУП Необхідність контролю систем та процесів різної природи обумовлена про- блемою виявлення неполадок, які виникають у процесі функціонування сис- тем. Для неполадки характерним є момент її появи, зумовлений зносом елементів або деталей, а, взагалі, деякими випадковими і невипадковими збуреннями (ними можна описати той же процес зносу). Якщо систему характеризувати, наприклад, процесом накопичення шкідливих речовин у живому організмі або кількістю мікроскопічних тріщин у технічному обладнанні, то момент виникнення неполадки у цих випадках наступає тоді, коли кількість шкідливих речовин в організмі або тріщин в обладнанні досягає певних критичних рівнів. В постановці задачі про неполадки системи велика увага приділяється вибору конкретного випадкового процесу як математичної моделі функціо- нування реальної системи та визначенню областей «справних» і «несправ- них» станів системи в термінах станів вибраної моделі. Тоді функція конт- рольного органу полягатиме у тому, щоб через певні відтинки часу (випадкові або невипадкові) контролювати процес з метою якнайшвидшого виявлення його «несправного» стану — і в цьому суть аналізу стратегії контролю. В задачах аналізу стратегії контролю для монотонних випадкових мо- делей типу різних модифікацій пуассонового процесу множина «несправ- них» станів визначається числом, що відповідає деякому критичному рівню, а для марковських та напівмарковських моделей — деяким станом погли- нання, який характеризує узагальнений несправний стан систем, і описується Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів ... Системні дослідження та інформаційні технології, 2003, № 4 121 марковськими та напівмарковськими процесами в дискретному часі зі ста- ном поглинання. Стратегія контролю за виявленням неполадки системи — її переходу із справного у несправний стан — характеризується втратами, що описуються деяким функціоналом, визначеним на траєкторіях випадкового процесу, який задає функціонування даної системи. В задачі синтезу стратегії контролю пуассонового процесу інтервали між моментами контролю знаходяться на основі методу динамічного про- грамування. Відмінність між аналізом та синтезом стратегій контролю та керування процесами різної природи обумовлена різними підходами до по- будови вказаних стратегій. В задачі аналізу стратегія контролю підлягає оп- тимізації як програмна стратегія, тобто інтервали між моментами контролю залежать від параметрів контрольованого процесу та критичного рівня. В задачі синтезу стратегія контролю та керування підлягає оптимізації відносно керувань, які приймаються у станах контрольованого або керованого процесу. АНАЛІЗ СТРАТЕГІЙ КОНТРОЛЮ ЗА ПУАССОНОВИМИ ТА НАПІВМАРКОВСЬКИМИ ПРОЦЕСАМИ При аналізі системи із змінним режимом роботи виникає необхідність спостереження або контролю за її станами. Для випадку, коли система може знаходитися в двох станах — справному і несправному, задача оптимальної організації контролю розглянута в роботі [1]. У більш складних системах справні стани можуть бути різними. У даному розділі припускається, що функціонування системи може бу- ти описано марковською або напівмарковською моделями. В якості марков- ських моделей використовуються різновиди пуассонових процесів (пуассо- нів процес, узагальнений пуассонів процес, пуассонів процес із зсувом), а напівмарковської — напівмарковський процес або процес марковського від- новлення з малою ймовірністю поглинання. Контроль за станом системи або її моделі проводиться з урахуванням вартості експлуатації, яка містить: а) вартість кількості контролів за справним станом; б) втрати за відсутність контролю за несправними станами. Стратегія контролю має бути такою, щоб вартість її експлуатації була мінімальною. Розглянемо декілька стратегій контролю. 1. Загальна рандомізована (контроль через довільні випадкові інтерва- ли часу). 2. Експоненціальна (інтервали між проведенням контролю мають екс- поненціальний розподіл). 3. Періодичний контроль (через рівні проміжки часу). Для приведених нижче математичних моделей отримано точні аналіти- чні або асимптотичні вирази, які визначають послідовність моментів часу проведення контролю для вказаних стратегій. М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 122 КОНТРОЛЬ ПУАССОНОВОГО ПРОЦЕСУ Припускається, що функціонування системи описується пуассоновим про- цесом. Стани його, що знаходяться нижче деякого фіксованого рівня, відповідають справним станам системи, а ті, що знаходяться вище цього рівня, — несправним станам. Нехай { }0);( ≥ttξ — однорідний пуассонів процесс, заданий ймовірнісним розподілом { } [ ] tk ektkt λλξ −== !)()(P 0>λ . Через випад- кові проміжки часу ξ з функцією розподілу )(tF , незалежно від процесу )(tξ , проводиться контроль. Якщо в момент контролю виявляється, що процес )(tξ приймає значення kr > , k — ціле, додатне число (це не змен- шує загальності, оскільки для довільного 0>x розподіл xτ (див. нижче) виражається через ][x ), то процес переводиться в початковий стан, у проти- лежному випадку контроль не впливає на процес. Позначимо kτ — час до виходу процесу )(tξ за рівень k ; kν — кількість операцій контролю за цей час; kγ — час перебування )(tξ над рівнем k до виявлення операцією контролю цієї ситуації. Тоді ∑ + = −= 1 1 k m kmk ν τζγ . (1) Нехай вартість кожного проведення контролю дорівнює 0>a , а за одиницю часу перебування процесу )(tξ над рівнем k платиться штраф 0>b . Вартість (ціна) ρ стратегії контролю визначається співвідношенням kkk ba γνρ += . Для визначення середньої вартості контролю візьмемо математичне сподівання від обох частин цього виразу і з урахуванням (1) маємо [ ]kkkk nbna τξρ MMM −++= )1( , (2) де kkn νM= . Виникає задача вибору параметрів функції розподілу )(tF , за яких се- редня вартість контролю буде мінімальною, тобто потрібно визначити мінімальне значення kρM із параметрами функції розподілу )(tF та зада- ними ba, , k . Для експоненціального контролю за заданої функції tetF µ−−=1)( , тобто коли моменти операцій контролю самі утворюють пуассонів процес із інтенсивністю µ , мінімальне значення функціоналу (2) Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів ... Системні дослідження та інформаційні технології, 2003, № 4 123 kkkk nnc τµρ MM −++= 1)1( , b ac = досягається в стаціонарній точці kcλµ =* . Для періодичного контролю за заданої ⎩ ⎨ ⎧ ≥ < = , , ,1 ,0 )( Tt Tt tF тобто коли контроль проводиться через рівні проміжки часу T , для достатньо великого рівня k оптимальний період стратегії періодичного контролю має вигляд λτ kc= . Зазначимо, що мінімальна вартість експлуатації стратегії періодичного контролю з періодом λkcT =* та стратегії експоненціального контролю з інтервалом ξ , розподіленого за експоненціальним законом із параметром kcλµ =* , дорівнює λλρ 12* −= kckM . ВІДНОВЛЕННЯ ПУАССОНОВОГО ПРОЦЕСУ Розглянемо задачу оптимального контролю та відновлення (послідовну за- міну) пуассонового процесу — задачу специфічного керування пуассоновим процесом. Керування або рішення розглядаються тільки в моменти прове- дення контролю і мають досить простий вигляд: продовжувати процес чи переводити його у початковий стан, тобто замінювати його новим таким же процесом. Послідовно відновний процес, який одержується в результаті періодичного контролю }{T процесів { })(tξ , позначимо через )(tη . Процес )(tη є регенеруючим. Нехай { }mtP t m == ∞→ )(lim ηP . (3) У роботі [3] встановлено, що границя (3) існує і 1,1 −≤= km Tn P k m λ , km Tn dueu rm TT P k u T rm rk r r m ≥ − = −− − = ∫∑ , !)( )()( 0 1 0 λ λψ λ , (4) де kn — коефіцієнти Тейлора розкладу породжуючої функції ∑ ∞ = −= 0 )( j jTk k ejT λψ для середнього числа операцій контролю до рівня k . М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 124 КОНТРОЛЬ УЗАГАЛЬНЕНОГО ПУАССОНОВОГО ПРОЦЕСУ Нехай { }0);( ≥ttξ — узагальнений пуассонів процес, тобто ∑ = = )( 0 )( tz k kt ξξ , де )(tz пуассонів процес з інтенсивністю λ , а { })(,...,1,0, tzkk =ξ — по- слідовність незалежних, однаково розподілених невід’ємних випадкових величин з функцією розподілу )(xΦ . Як і в описаному вище випадку, кон- троль проводиться через випадкові проміжки часу ζ , що не залежать від процесу )(tξ і мають ту ж саму функцію розподілу )(tF . Якщо в момент контролю виявиться, що процес приймає значення xy > ( x — додатне число), то процес обривається, і подальший контроль призупиняється, а інакше контроль не впливає на процес. Критерієм стратегії контролю служить середня вартість, яка визна- чається асимптотичним виразом [4] xρM ≍ ∞→+− + xxxc ,ζ ξµλξζλ ζ M MM M , (5) де b ac = , ba, — вартісні параметри стратегій контролю. Розглядаються дві стратегії контролю за узагальненим пуассоновим процесом, які відрізняються функціями розподілу )(tF . Для експоненціального контролю за заданої tetF µ−−=1)( , тобто коли моменти операцій контролю самі утворюють пуассонів процес із інтенсивністю µ , мінімальне значення функціоналу xρM ≍ ∞→+− + xxc ,1 )( 1 µξλξλ µ MMM досягається в точці xc ξλ µ M =* 0 . Для періодичного контролю за заданої ⎩ ⎨ ⎧ ≥ < = , , ,1 ,0 )( Tt Tt tF , тобто коли контроль проводиться через рівні проміжки часу T , для достатньо великого рівня x оптимальний період стратегії періодичного контролю має вигляд ξλ M xcT =* . Мінімальне значення асимптотичного виразу функціоналу xρM за асимптотично оптимальних значень параметрів µ та T розгля- нутих стратегій контролю xρM ≍ ξλξλξλ ξλ MMM M xcx T cxc +− + )()( . Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів ... Системні дослідження та інформаційні технології, 2003, № 4 125 ПЕРІОДИЧНИЙ КОНТРОЛЬ ПУАССОНОВОГО ПРОЦЕСУ ІЗ ЗСУВОМ Нехай { }0);()( ≥−= tttlt ξχ , де { }0);( ≥ttξ — однорідний пуассонів про- цес з інтенсивністю 0>λ , отже }0);({ ≥ttχ — пуассонів процес із зсувом, коефіцієнт зсуву якого 0>l . Через рівні проміжки часу T , що не залежать від процесу )(tχ , проводиться контроль. Якщо в момент операції контролю виявляється, що процес )(tχ приймає значення xy ≥ )0( >x , то процес об- ривається і подальший його контроль призупиняється, інакше контроль не впливає на процес. Для середньої вартості стратегії періодичного контролю }{TF xρM справедливі оцінки [5] T T cm c T cm x x x +≤≤− ρµ , (6) де за умови c<λ ( b ac = , a — вартість проведення контролю; b — вартість одиниці часу від перебування процесу )}({ tχ над рівнем x ) математичне сподівання xm моменту xτ досягнення процесом )(tχ рівня x має вигляд λ− = l xmx . З нерівності (6) випливає, що ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ +≤ T T cmx TxT minmin ρM . Легко переконатися у тому, що мінімум за T функції T T cmx + дося- гається у )()(0 λ−= lxcxT , а значить )(2min λρ −≤ lxcxT M . (7) Результати чисельного розрахунку наведено у табл. 1. Т а б л и ц я 1 . Результати чисельного розрахунку x 10,00 30,00 90,00 )(2 λ−lxc 4,00 6,94 12,00 x T ρµmin 3,88 6,86 11,99 4,0=c 2=l 1=λ З порівняльного аналізу даних табл. 1 видно, що x T ρMmin знаходить- ся досить близько до верхньої оцінки (7). Звідси доходимо висновку, що от- римане таким чином значення періоду стратегії періодичного контролю )}({ 0 xT можна практично використовувати за будь-якого 0>x . М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 126 КОНТРОЛЬ НАПІВМАРКОВСЬКОГО ПРОЦЕСУ З МАЛОЮ ЙМОВІРНІСТЮ ПОГЛИНАННЯ Процес марковського відновлення (ПМВ) { }0;, ≥nx nn θε із скінченним фазовим простором станів (ФПС) { }0:0 ∪EE = , { }NE ,...,1:0 = , { }0 — стан поглинання, задається напівмарковським ядром 10,,,)()( ≤≤∈= εεε ErktGptQ kkrkr , (8) де ε krp — елементи матриці перехідних ймовірностей вкладеного ланцюга Маркова (ВЛМ); { }ttG kk ≤= θP)( — функція розподілу часу перебування ПМВ в стані Ek∈ . Перехідні ймовірності ВЛМ задовольняють умовам Erkpppp rkrkkk ∈== → ,,lim; 0 00 ε ε ε ε . (9) Матриця перехідних ймовірностей { }ErkpP rk ∈= ,;0 0 незбуреного ер- годичного ланцюга Маркова має стаціонарний розподіл { }Ekk ∈= ,: ρρ . Функція розподілу )(tGk абсолютно неперервна )()( tgtG kk =′ . При моделюванні реальної системи за допомогою ПМВ множина E відповідає справним її станам, стан поглинання { }0 — несправному стану. Рівень надійності системи визначається матрицею ймовірностей поглинання { }Ekpk ∈;0 ε . Стан реальної системи в неперервному часі описується на- півмарковським процесом (НМП) [6] )(æ:)(æ tt εη εε = , { }ttt n ≤= εε ζη :max:)( , ∑ = = n k kn 1 : εε θζ . (10) Позначимо через )(tFε та )(tfε відповідно функцію розподілу та гус- тину розподілу часу перебування НМП в E . Нехай ετ — момент поглинання НМП { }0)(æ:min: == tt ε ετ . (11) Тоді використання стратегії, яка передбачає контроль у моменти ,...,,...,, 10 iννν де { }iν — строго зростаюча послідовність, приводить до втрат [ ]∑ ∞ = ++ ≤<−+<= 0 11 )()()( m mmm m m IbIaw ντντνατν εεεε , (12) де a — вартість проведення кожної операції контролю; bt — штраф за пе- ребування системи в несправному стані протягом часу t , 0>b ; )(AI — індикатор випадкової події A ; [ ] )()( APAI =M ; α — коефіцієнт переоцінки штрафу 10 <<α . Переходячи до математичних сподівань в (12), маємо Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів ... Системні дослідження та інформаційні технології, 2003, № 4 127 [ ]∑ ∫ ∞ = + ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ −+−== + 0 1 1 )()()(1 m m m m m m dttftbFaww ν ν εεε νανM . (13) Задача полягає у знаходженні такої стратегії контролю, за якої середні втрати (13) приймають мінімальне значення. При рекурентній стратегії { }iν , коли моменти проведення контролю за- довольняють рекурентному співвідношенню )( )()( 1 1 m mm mm f FFc να ννα α νν ε εε + + − +−= , (14) досягається мінімальне значення критерію середніх втрат (13). Зазначимо, що вибір стратегії контролю (14) не залежить, власне, від величин a і b , а залежить тільки від їх відношення bac = . Функція розподілу )(tFε моменту поглинання НМП в (14) досить складна. Однак за 0→ε )(tFε збігається до експоненціального розподілу із параметром mq=Λ , де ∑ ∈ = Ek kk qq ρ ; ∑ ∈ = Ek kk mm ρ ; kkm θM= . (15) Здійснимо індукцію за ...,2,1, =mm і граничний перехід за 0→ε у рекурентному співвідношенні (14). Це виявляється можливим через обме- женість дограничної функції розподілу )(tFε і в силу того, що існує єдиний граничний експоненціальний розподіл з параметром (15). Переходячи в (14) до границі за 0→ε , отримаємо рекурентне співвідношення ( ) Λ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ −+−= −−Λ + αα α νν νν 0 1 000 1 mmec mm . (16) Це співвідношення використовується для побудови стратегій, серед яких методом перебору початку стратегій },{ 10 νν шукається оптимальна щодо критерію ( ) ( )( )[ ]{ }∑ ∞ = Λ− + Λ−Λ−Λ− −−+−−= + 0 10 11 m mm m mmmm eeebeaw νννν ννα . (17) Обчислювальний процес (16) побудови оптимальної стратегії { }0 iν є збіжним через монотонну залежність функціонала (17) від стратегії { }0 iν . Для стратегій періодичного контролю }{T , коли контроль проводиться через рівні проміжки часу T , за λ α 2 1 2− >c на оптимальному значенні 2 2 0 121 Λ − − Λ + Λ − −= αα cT (18) М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 128 досягається мінімальне значення критерію середніх втрат ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ − + − −− − − = Λ− Λ− Λ− αα 11 1 1 00 0 0 0 0 T e Te b e aw T T T . (19) Зазначимо, що у випадку, коли 1≅α , вираз для періоду контролю 0T (18) стратегії періодичного контролю набуває досить простого вигляду qmccT 220 =Λ= . (20) СИНТЕЗ ОПТИМАЛЬНОЇ СТРАТЕГІЇ КОНТРОЛЮ. ПОРІВНЯЛЬНІ ХАРАКТЕРИСТИКИ ЗАДАЧ СИНТЕЗУ ТА АНАЛІЗУ У задачі синтезу стратегії контролю вибір інтервалу часу, через який має здійснюватись наступний момент контролю, що є предметом дослідження задачі аналізу, визначається як рішення, що приймається у стані контрольованого процесу в даний момент часу. Тому розглянемо синтез оптимальних стратегій контролю та керування на основі принципу ди- намічного програмування, його модифікації та розвинення, а також аналітичний розв’язок рівняння оптимальності, яке випливає з цього прин- ципу. Опишемо стохастичний потік заявок, що приймається деяким при- строєм. Число k заявок, що надійшли, визначає стан S цього пристрою. Рівність ...,0,)( == kStS k (21) означає, що за час t на пристрій поступило k заявок. Позначимо через kx момент надходження k -ї заявки, а через )(tFk та )(tf k — відповідно функцію розподілу та його густину kx . Припускається, що всі kx мають обмежене математичне сподівання. В будь-який момент часу за деяку платню може бути проведений миттєвий контроль пристрою, який дає безпомилкову інформацію про його стан. Послідовність моментів контролю визначає стратегію контролю. При- пускається, що платня за проведення кожного контролю не залежить від ча- су його проведення і дорівнює 0>a . Об’єднання усіх станів )...,1,( += NNkSk , починаючи з деякого 1≥N , яке назвемо критичним числом, утворює критичний стан критS . Час t перебування в критS приводить до штрафу в t , де b — додатне число. При виявленні у пристрої критичного стану його функціонування і по- дальший контроль над ним призупиняються. Задача полягає у знаходженні стратегії, яка б забезпечила мінімальні середні втрати до моменту зупинки. Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів ... Системні дослідження та інформаційні технології, 2003, № 4 129 СИНТЕЗ ОПТИМАЛЬНИХ СТРАТЕГІЙ КОНТРОЛЮ ПУАССОНОВОГО ПРОЦЕСУ [7] Розглянемо випадок, коли потік заявок описується стаціонарним пуассоно- вим процесом. Без обмеження загальності будемо вважати, що інтенсивність процесу 1=λ . 1. Загальна стратегія динамічного програмування Припускається, що засоби контролю дозволяють розрізняти «справні» стани kS , 1,...,1,0 −= Nk . Тоді неважко показати, що в силу марковської власти- вості пуассонового процесу та адитивності функціоналу втрат при знаход- женні оптимальної стратегії достатньо обмежитись марковськими неран- домізованими стратегіями, тобто здійснювати наступний контроль через визначений інтервал kh , який залежить тільки від поточного спостережува- ного стану kS , 1,...,1,0 −= Nk . Нехай прийнята стратегія { }kh . Тоді, позна- чивши через kw середні втрати за умови, що пристрій почав функціонувати із стану kS , 1,...,1,0 −= Nk , використовуючи марковську властивість пуас- сонового процесу та адитивність функціоналу втрат, можна записати реку- рентне співвідношення ∑ ∫ − = −− −++= 1 0 )()()( N ki h kNkkkiik k dFhbhpwaw ττ , (22) де ! )( m ettp tm m − = — ймовірність надходження за час t m заявок, а ∑ − = −−= 1 0 ! 1)( n r t r n e r ttF — функція розподілу надходження n -ї заявки. Після нескладних перетворень вираз (22) приймає вигляд ⎢ ⎢ ⎣ ⎡ + − + − = ∑ − += −1 1 !)(1 1 N ki ki k i h hk ki h wea e w k k ⎥ ⎥ ⎦ ⎤ − +⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−+ ∑ − = !)1(! )( 1 0 k h b r h ekhb r k k r r kh k k , (23) де kw виражається явно відносно 11 ,..., −+ Ni ww . Алгоритм пошуку оптимальної стратегії, який ґрунтується на реку- рентному співвідношенні (23), добре реалізується на комп’ютері. 2. Стратегія рекурентного контролю Припускається, що засоби контролю дозволяють визначити «критичність» або «некритичність» стану, не розрізняючи при цьому між собою справні стани. М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 130 Неважко показати, що цей випадок можна розглядати, якщо формально вважати, що критичне число дорівнює 1 та ∑ − = −−= 1 0 1 ! 1)( N r t r e r ttF — спеціальний розподіл Ерланга порядку, який дорівнює «істинному» критич- ному числу. Припускається, що )(1 tF зосереджена на ),0( T , а T може бути і необ- меженим. Тоді використання стратегії, що передбачає контроль у моменти ...,,...,, 21 iννν , де }{ iν — строго зростаюча послідовність, яка задовольняє умову TL =+1ν (24) ( L називається довжиною стратегії), приводить до середніх втрат ( )[ ][ ]{ } 1 0 111 )(1 xaFabw L m mmmm M−−+−= ∑ = ++ νννν . (25) Розподіли, де T скінченне, називаються скінченними, інші — не- скінченними. Стратегії, де L скінченне, називаються скінченними, інші — не- скінченними. Для нескінченних стратегій умова (24) має сприйматись як гранична. При постійній платні за контроль та лінійній штрафній функції при не- скінченному (скінченному) )(1 tF оптимальна стратегія з необхідністю має бути нескінченною (скінченною). При цьому у випадку скінченного роз- поділу при досягненні моменту часу T здійснюється зупинка процесу без проведення контролю, що формально рівнозначно умові 01 =+Laν . Враховуючи строго зростаючий характер { }iν та умову (24), із необ- хідної умови оптимальності 0= ∂ ∂ k w ν при 10 +<< Lk можна записати реку- рентне співвідношення )( )()( 1 111 1 k kk kk f FF b a ν νν νν + + − +−= , (26) яке використовується для побудови стратегій (серед них шукається оптимальна). Алгоритм, що ґрунтується на співвідношеннях (25), (26), передбачає при побудові оптимальної стратегії контролю оптимальний вибір перших двох моментів 0ν та 1ν контролю. Здебільшого це здійснюється на основі методу простого перебору. Розглянемо ще дві стратегії контролю, аби оцінити ефективність задач синтезу та аналізу стратегій контролю пуассонового процесу. 3. Стратегія експоненціального контролю Припускається, що до виявлення критичного стану контроль здійснюється через випадкові інтервали часу із розподілом tetG µ−−=1)( , тобто моменти Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів ... Системні дослідження та інформаційні технології, 2003, № 4 131 контролю самі утворюють пуассонів процес з інтенсивністю µ . Оцінимо втрати, які матимуть місце за такої стратегії контролю. Нехай перехід в критичний стан відбувається в момент txN = . Тоді, використовуючи властивості пуассонового процесу, неважко показати, що до цього часу було б проведено в середньому tµ контролів, а наступний контроль, який установив би критичність стану, відбудеться в середньому через час µ1 . Звідси ( ) µµ btaw txN ++== 1 . Враховуючи, що Nx має розподіл ∑ − = −−= 1 0 ! 1)( N r t r N e r ttF , після інтегру- вання отримаємо ( ) µµ bNaw ++= 1 . (27) Легко показати, що w досягає мінімуму при Na b =µ , де Nbaaw 2 += . 4. Стратегія періодичного контролю Розглянемо випадок, коли до виявлення критичного стану контроль здійснюється через рівні проміжки часу. Припускається, що період такого контролю дорівнює h . Тоді, підставляючи в (25) hmm =ν , отримаємо baNe r hmhbhw m hm r = ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ −+= ∑ ∑ ∞ = − γγ , ! )()()( 0 . (28) Відшукання оптимального значення *h досить ефективно здійснюється на комп’ютері. Для ілюстрації порівняємо мінімальні втрати при використанні розгля- нутих вище стратегій контролю. Значення мінімальних втрат при 2=γ на- ведені у табл.2 Т а б л и ц я 2 . Значення мінімальних втрат для чотирьох стратегій Стратегія контролю Критичне число (N) 1 2 3 4 1 3,505 3,505 4,828 3,505 2 3,908 3,937 6,000 3,996 3 4,173 4,232 6,898 4,432 4 4,376 4,465 7,656 4,859 5 4,541 4,660 8,324 5,288 6 4,680 4,829 8,928 5,734 М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 132 ВИСНОВКИ З табл. 2 видно, що найменш ефективним є експоненціальний контроль (стратегія 3). Дещо більш ефективний періодичний контроль (стратегія 4), хоча він і програє порівняно з контролем за стратегією 2, тому що не враховується зміна ймовірності настання моменту переходу в критичний стан. При цьому природне зростання різниці з ростом N . Поліпшення можливостей контролю, що характерно при переході від стратегії 2 до стра- тегії 1, дозволяє добитись ще деякого зменшення втрат завдяки суттєвому збільшенню об’єму обчислювальної роботи. З іншого боку, дані, наведені в табл. 2, є ілюстрацією ефективності асимптотичного представлення критеріїв оптимальності розглянутих стратегій контролю різних математичних моделей, які описують реальні процеси в умовах сто- хастичної невизначеності. З порівняльних характеристик задач синтезу та аналізу оптимальних стратегій контролю пуассонових процесів доходимо висновку, що задачі аналізу стратегій контролю, рішення яких ґрунтується на асимптотичних представленнях критеріїв оптимізації, тобто спрощеному аналізі стратегій контролю, складають основу системного піходу в задачах оптимізації стра- тегій контролю пуассонових, а також марковських процесів і процесів мар- ковського відновлення з малими ймовірностями поглинання. ЛІТЕРАТУРА 1. Иваненко В.И., Королюк В.С. Об одном методе синтеза оптимальных систем автоматического контроля // Кибернетика. — 1965. — № 2. — С. 98–101. 2. Андреев Н.В. Анализ некоторых схем контроля за пуассоновским процессом // Кибернетика. — 1968. — № 6. — С. 59–61. 3. Андреев Н.В., Козьмин П.Д. Об асимптотическом контроле и последовательной замене пуассоновских процессов // Техническая кибернетика. — Киев: ИК АН УССР. — 1970. — Вып. 9. — С.102–110. 4. Андреев Н.В. Анализ некоторых схем контроля за обобщенным пуассоновским процессом // Теория оптимальных решений. — Киев: ИК АН УССР, 1968. — Вып. 5. — С. 42–47. 5. Королюк В.С., Андреев Н.В. О некоторой схеме контроля за пуассоновским процессом со сносом // Кибернетика. — 1969. — № 1. — С. 72–74. 6. Королюк В.С., Андреев Н.В. Контроль процесса марковского восстановления с малой вероятностью поглощения // Кибернетика. — 1989. — № 5. — С. 128–129. 7. Тупчиенко А.В. Некоторые задачи контроля стохастических процессов // Кибернетика. — 1973. — № 2. — С. 95–98. Надійшла 10.09.2003

Аналіз і синтез оптимальних стратегій контролю складних пуассонових процесів та напівмарковських процесів з поглинанням

Репозитарії

Схожі ресурси