Теорія прийняття рішень у задачах оптимальної зупинки

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
1. Verfasser:	Андрєєв, М.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2010
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/50070
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Теорія прийняття рішень у задачах оптимальної зупинки / М.В. Андрєєв // Систем. дослідж. та інформ. технології. — 2010. — №4. — С. 69-78. — Бібліогр.: 16 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50070
record_format	dspace
spelling	irk-123456789-500702013-10-05T03:07:24Z Теорія прийняття рішень у задачах оптимальної зупинки Андрєєв, М.В. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Розглянуто правило оптимальних рішень виробника зі зростаючим запасом у даний період, коли задані поточна ціна та ймовірнісний розподіл цін наступного періоду. Побудовано моделі прийняття рішень у задачах оптимальної зупинки марковських послідовностей з детермінованою або випадковою переоцінкою. Наведено байєсову процедуру прийняття рішень у задачі перевірки статистичних гіпотез. Рассмотрено правило оптимальных решений производителя c возрастающим запасом в даный период, когда заданы текущая цена и вероятностное распределение цен последующего периода. Построены модели принятия решений в задачах оптимальной остановки марковских последовательностей с детерминированной или случайной переоценкой. Приведено байесовскую процедуру принятия решений в задаче проверки статистических гипотез. An optimal decision making rule for a producer with growing inventory in the given period and specified the current price and probabilistic price distribution in the following period is given. Decision making models in optimal stopping problems of the Markov sequences with deterministic or stochastic revalue are constructed. The Вayesian decision making procedure in a statistical hypotheses testing problem is performed. 2010 Article Теорія прийняття рішень у задачах оптимальної зупинки / М.В. Андрєєв // Систем. дослідж. та інформ. технології. — 2010. — №4. — С. 69-78. — Бібліогр.: 16 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50070 519.24/.857.3 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
spellingShingle	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Андрєєв, М.В. Теорія прийняття рішень у задачах оптимальної зупинки Системні дослідження та інформаційні технології
description	Розглянуто правило оптимальних рішень виробника зі зростаючим запасом у даний період, коли задані поточна ціна та ймовірнісний розподіл цін наступного періоду. Побудовано моделі прийняття рішень у задачах оптимальної зупинки марковських послідовностей з детермінованою або випадковою переоцінкою. Наведено байєсову процедуру прийняття рішень у задачі перевірки статистичних гіпотез.
format	Article
author	Андрєєв, М.В.
author_facet	Андрєєв, М.В.
author_sort	Андрєєв, М.В.
title	Теорія прийняття рішень у задачах оптимальної зупинки
title_short	Теорія прийняття рішень у задачах оптимальної зупинки
title_full	Теорія прийняття рішень у задачах оптимальної зупинки
title_fullStr	Теорія прийняття рішень у задачах оптимальної зупинки
title_full_unstemmed	Теорія прийняття рішень у задачах оптимальної зупинки
title_sort	теорія прийняття рішень у задачах оптимальної зупинки
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2010
topic_facet	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
url	http://dspace.nbuv.gov.ua/handle/123456789/50070
citation_txt	Теорія прийняття рішень у задачах оптимальної зупинки / М.В. Андрєєв // Систем. дослідж. та інформ. технології. — 2010. — №4. — С. 69-78. — Бібліогр.: 16 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT andrêêvmv teoríâprijnâttâríšenʹuzadačahoptimalʹnoízupinki
first_indexed	2025-07-04T11:32:10Z
last_indexed	2025-07-04T11:32:10Z
_version_	1836715848391196672
fulltext	© М.В. Андрєєв, 2010 Системні дослідження та інформаційні технології, 2010, № 4 69 TIДC ПРОБЛЕМИ ПРИЙНЯТТЯ РІШЕНЬ І УПРАВЛІННЯ В ЕКОНОМІЧНИХ, ТЕХНІЧНИХ, ЕКОЛОГІЧНИХ І СОЦІАЛЬНИХ СИСТЕМАХ УДК 519.24/.857.3 ТЕОРІЯ ПРИЙНЯТТЯ РІШЕНЬ У ЗАДАЧАХ ОПТИМАЛЬНОЇ ЗУПИНКИ М.В. АНДРЄЄВ Розглянуто правило оптимальних рішень виробника зі зростаючим запасом у даний період, коли задані поточна ціна та ймовірнісний розподіл цін наступ- ного періоду. Побудовано моделі прийняття рішень у задачах оптимальної зупинки марковських послідовностей з детермінованою або випадковою пере- оцінкою. Наведено байєсову процедуру прийняття рішень у задачі перевірки статистичних гіпотез. ВСТУП Задача оптимальної зупинки полягає у виборі моменту зупинки, яка базу- ється на послідовному спостереженні випадкових величин з метою отри- мання максимального очікуваного виграшу або мінімальних очікуваних втрат. Задачі такого типу мають місце в теорії статистичних рішень при мі- німізації ризику від неправильно прийнятих рішень, при перевірці статисти- чних гіпотез або оцінюванні невідомих параметрів заданих ймовірнісних розподілів, у дослідженні операцій, коли рішенням може бути заміна устат- кування, вибір секретаря, або регулювання рівня запасу для задоволення випадкового попиту тощо. Історично, ця проблема виникла у послідовному аналізі статистичних спостережень у теорії Вальда [6], яка стосується послідовного критерію від- ношення ймовірностей для перевірки статистичних гіпотез та теорії статис- тичних рішень. Байєсів підхід до розв’язання проблем прийняття статистич- них рішень в умовах стохастичної невизначеності вперше зустрічається у статті Арроу, Блекуелла та Гіршіка [2]. Важливе місце у розвитку і застосу- ванні ідей статистичного послідовного аналізу належить Ширяєву [11]. Уза- гальнення послідовного аналізу на проблеми чистої зупинки без статистич- ної структури реалізовано Снеллом [5]. У монографії Чао, Роббінса та Сигмунда [10] підсумовується розвиток цих досліджень. У статтях автора [14–16] досліджено методи побудови оптимальних моментів зупинки для марковських послідовностей, процесів марковського відновлення та деяких задачах неполадки. Мета роботи — визначити можливості застосувань методології теорії оптимальних рішень у задачах оптимальної зупинки деякої монотонної сто- хастичної послідовності, що описує динаміку зростання рівня «живого» за- М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 70 пасу, оптимальної зупинки марковських послідовностей з детермінованою або випадковою переоцінкою та оптимальної зупинки процесу спостере- жень при побудові байєсової процедури перевірки двох простих статистич- них гіпотез. Для цих різних задач проводиться системний аналіз побудови моделей прийняття рішень на базі теорії оптимальних рішень із використан- ням досліджень, проведених у роботах Гохмана [3], Абдель-Хаміда [1], Ан- дрєєва, Губенка і Штатланда [13] та Чао і Роббінса [12]. ПРАВИЛА ПРИЙНЯТТЯ РІШЕНЬ В ЗАДАЧІ ОПТИМАЛЬНОЇ ЗУПИНКИ ЗРОСТАЮЧОГО РІВНЯ ЗАПАСУ Розглядається задача керування рівнем запасу, що зростає за віком на пото- чному періоді часу, коли задані поточна ціна та ймовірнісний розподіл цін на наступний період. Базова концепція підходу, що розглядається, полягає у знаходженні оптимального правила зупинки у цій задачі. З’ясовується, що оптимальна стратегія передбачає знаходження урізаної цінової функції, яка не є зростаючою відносно рівня зростання за віком наявного запасу. Зростаючим за віком рівнем запасу може бути «живий» товар (домашня рогата худоба, птиця, ділянка будівельного лісу, засіяне поле і т.д.), за зада- ними поточною ціною на цей період та ймовірнісним розподілом цін для наступного періоду. Особа, що приймає рішення (ОПР) (виробник чи фер- мер) має вирішити необхідність продажу свого товару у даний період, або притримати його до наступного періоду. Варто зазначити, що час тут висту- пає на двох рівнях: 1) товар, що розглядається у часі, описується зростаю- чим процесом і 2) процес прийняття рішень за своєю природою реалізується впродовж цього часу. Важливим є і те, що оскільки рішення стосуються дія- льності у майбутньому часі і процес рішень здійснюється на конкретних відрізках часу, то при цьому обов’язково має місце поява ризику. Навіть припускаючи, що фізичний процес зростання рівня запасу може контролю- ватись ОПР, ризик все одно залишається через неуможливлення ОПР по- вною мірою регулювати ціни в ринкових умовах. Ця задача сформульована Гохманом [3], повністю відображає загаловок проблем оптимальної зупинки, систематизовано представленої Чао, Робін- сом та Сигмундом [10]. У розділі 5 цієї книги, автори досліджують пробле- му правил зупинки марковських процесів, зокрема, так звану проблему Елфвінга [4], для якої дана задача є її частковим випадком. Оптимальна стратегія передбачає знаходження урізаної цінової функ- ції, яка визначатиме для кожного рівня запасу наявного за віком товару його ціну, нижче якої фермер притримує свій товар на інший період, і вище якої –– продає свій товар протягом поточного періоду. Для подальшого спро- щення припустимо, що всі операції мають місце на початку періоду. Стан системи визначається віком наявного товару. Наприклад, у випад- ку яловичини, за допомогою функції зростання встановлюється зв’язок ваги, якості і споживчого постачання за віком цього товару. Незважаючи на те, що поточні ринкові ціни відомо, а ціни для наступного періоду невідомо, можна припустити, що вони описуються випадковою величиною, яка має один і той же ймовірнісний розподіл упродовж усіх періодів. Ці ціни є неза- лежними від вікового рівня запасу товару, оскільки його вага «коригується» для змін якості за віком через функцію якості. Теорія прийняття рішень у задачах оптимальної зупинки Системні дослідження та інформаційні технології, 2010, № 4 71 Нехай ),( pxf буде максимально очікуваною вигодою наявного запасу товару, вік якого дорівнює ,x тоді як поточна ціна продажу одиниці його ваги дорівнює .0>p Тоді ( ) ( ) ( ) ( ) ( )[ ]xcxwpxfMpxwpxf −′+= ,1,max, (1) для 1,...,1,0 −= Xx з крайовою умовою ,)(),( pXwpXf ≡ де ( ) 0>xw –– вага товару, вік якого дорівнює ,x )(xc –– вартість одиниці ваги утримання товару від віку x до віку ,1+x а p′ –– випадкова майбутня ціна одиниці ваги, у випадку, коли вік товару дорівнює .1+x Якщо наразі ввести нові змінні ( ) ( ) ( )xwpxfpxg /,, = і ( ) ( ) ( )xwxwxv /1+= (2) для ,1,...,1,0 −= Xx тоді рівняння (1) можна переписати у вигляді ( ) ( ) ( ) ( )[ ]xcpxgxMvppxg −′+= ,1,max, (3) для 1,...,1,0 −= Xx з крайовою умовою .),( ppXg = Значення функції ),( pxg характеризує максимально очікувану вигоду від товару, вік якого дорівнює ,x коли поточна ціна продажу одиниці ваги дорівнює .0>p Для побудови моделі рішень для даної задачі слід зауважити, що оскільки умов- ний розподіл майбутньої ціни p′ за заданої поточної ціни ,p не залежить від ,p тоді з рівняння (3) відразу випливає, що оптимальна стратегія прийняття рішень складається з двох рішень: ( ) :1≡xd ( )xp ρ>якщотовар,продавати , ( ) :0≡xd ( ) ,якщотовар,притримати xp ρ≤ (4) де )(),1()()( xcpxMgxvx −′+=ρ для 0,1, ... , 1.x X= − Це означає, що при прийнятті рішення притримати товар на один період довше, фермер прирівнює максимально можливі поточні витрати –– [ ])()( xcpxw + до максимально очікуваної вигоди від продажу товару на на- ступному періоді –– ),1( pxMf ′+ . Можна показати, що коли 0)( ≤xc для усіх x та )(xw є зростаючою функцією по ,x тоді )(xρ не є зростаючою функцією по .x Але припущен- ня щодо від’ємних витрат від утримання живого товару є такими, що потре- бують субсидування фермера, а це суперечить дійсності і є нереальними; тому слід зосередитись на умовах, які забезпечують лише додатні витрати від утримання живого товару, тобто .0)( >xc Теорема 1. [3] Якщо )(xv і )(xc− –– не є зростаючими функціями по ,x тоді такими самими є функції ),( pXg і ).(xρ Доведення. З огляду на визначення функції )(xρ і допустимих власти- востей функцій )(xv , )(xc та ,0),( >pXg досить показати, що ),( pxg не є зростаючою функцією по .x Для цього використовується метод індукції по .x З рівняння (3) випливає, що .0),(),1( >∀=≥− ppXgppXg Припусти- мо, що ppxgpxg ∀+≥+ ),2(),1( . Тоді з рівняння (3) та умов теореми ви- пливає, що ,),1(),( ppxgpxg ∀+≥ що завершує доведення. М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 72 Цей результат пояснюється таким чином: для детерміністичного випад- ку, оптимальний вік або стан збуту на ринку однозначно визначається зада- ною поточною ціною. Це легко перевірити за умов теореми (коли функція )(xw має спадний до нуля маргінальний темп зростання і функція )(xc не є зростаючою функцією по x ), що зростання ринкової ціни призводить до зменшення оптимального віку або стану для збуту товару на ринку. З цього результату робимо висновок і для стохастичного випадку, що коли фермер вирішує продавати живий товар у віці x за будь-яку ціну, яка дорівнює або більша за ),(xρ тоді можна очікувати, що «діапазон цін» залишиться в «діа- пазоні продаж» у віці .1+x Таким чином, задача зростаючого рівня запасу живого товару у цьому контексті розглядається як конкретний випадок задачі оптимальної зупинки. Ця задача може розглядатись в іншій постановці як проблема заміщення, яку можна розв’язати методами теорії дослідження операцій. ЗАДАЧІ ОПТИМАЛЬНОЇ ЗУПИНКИ МАРКОВСЬКИХ ПОСЛІДОВНОСТЕЙ З ДЕТЕРМІНОВАНОЮ ПЕРЕОЦІНКОЮ Зупинимось на з’ясуванні деяких рівностей для стаціонарних марковських послідовностей, які використовуються при обґрунтуванні процесу прийнят- тя рішень щодо задач оптимальної зупинки. Надалі ),,( PFΩ використовува- тиметься для позначення ймовірнісного простору, а ],2,1,0[ …=N та ),( NnXX n ∈= позначатиме стаціонарну марковську послідовність випад- кових величин, визначених на ),,( PFΩ зі значеннями у вимірному просторі ),( ξE . Для кожного Ex∈ і ,FA∈ )(APx позначатиме умовну ймовірність появи випадкової події A при заданому xX =0 , xM — математичне споді- вання відносно міри xP . Кожна функція f , що використовується тут, буде скінченою і дійсно значною доти, поки не стверджується щось інше; крім того, припустимо, що для кожного Nn∈ , \| ( ) \|x nM f X < ∞ . Термін «час зу- пинки» означатиме «скінчений час зупинки». У роботі [10] автори подають вичерпну методологію теорії оптимальної зупинки. МОДЕЛІ ПРИЙНЯТТЯ РІШЕНЬ У ЗАДАЧАХ ОПТИМАЛЬНОЇ ЗУПИНКИ ОДНОРІДНИХ МАРКОВСЬКИХ ПОСЛІДОВНОСТЕЙ ІЗ ДЕТЕРМІНОВАНОЮ ПЕРЕОЦІНКОЮ При дослідженні задачі оптимальної зупинки однорідної марковської послі- довності з детермінованою переоцінкою знаходять такий момент зупинки цієї послідовності, на якому досягається максимальне значення заданого критерію оптимальності з детермінованою переоцінкою. Декілька конкрет- них прикладів таких задач наведено у статті Абдель-Хаміда [1]. У цьому розділі розглядаються деякі рівності та нерівності для однорі- дної марковської послідовності з детермінованою переоцінкою, які викорис- товуються в подальшому для отримання правил або моделей прийняття рі- шень у задачах оптимальної зупинки з переоцінкою. Теорія прийняття рішень у задачах оптимальної зупинки Системні дослідження та інформаційні технології, 2010, № 4 73 Нехай для однорідної марковської послідовності ),,( xnn PFX з ФПС ),( BX та двох B –вимірних функцій g , c та сталої величини (фактора пе- реоцінки) α , 10 << α , функція виграшу в момент зупинки τ має вигляд ( ) ( )⎥⎦ ⎤ ⎢⎣ ⎡ −∑ − = 1 0 τ τ τ αα n n n x XcXgM , (5) де g трактується як функція виграшу, а c –– як функція плати за одне спо- стереження. Нехай F –– клас усіх марковських моментів, що задовольняють умові ( ) ( ) ( ) 0lim 1 0 = ⎭⎬ ⎫ ⎩⎨ ⎧ >⎥⎦ ⎤ ⎢⎣ ⎡ −∑ − = ∞→ mIXgXgTM m mm n n n x m ταα α . (6) Задача полягає у знаходженні оптимального моменту зупинки ,τ що задовольняє критерію оптимальності ( ) ( ) ( ) ( ) ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −= ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ − ∑∑ − = − = 1 0 1 0 sup 8 * τ τ τ τ τ τ τ αααα n n n x n n n x XcXgMXcXgM , (7) де супремум береться по всіх моментах зупинки, що належать класу F , тоді оптимальний момент зупинки τ визначається як момент першого попадан- ня у множину ( ) ( ){ }0: ≤−= xcxgTxD α , (8) де αT –– оператор очікуваного дисконтного приросту виграшу на один крок уперед, що діє на функцію виграшу g у точці :x =)(xgTα [ ] ,)()( 1 xgXgM x −=α і оптимальний момент зупинки визначається як { }DXn n ∈= :infτ . (9) Має місце основний результат: Теорема 2 [1]. Якщо множина D замкнена і момент зупинки τ задо- вольняє умові (6), тоді τ є оптимальним моментом зупинки. Наведена постановка задачі аналогічна постановці задачі для монотон- ного випадку, що розглянута у розділі 3.5 роботи [10]. Можна порівняти теорему 2 із теоремою 3.3 у роботі [10]. Слід зауважити, що коли 1→α і ,0)( ≡xc тоді має місце монотонний випадок, хоча у цьому випадку наведе- на тут умова (6) не така, як умови (3.15) і (3.17) у [10]. У модель прийняття рішень задачі оптимальної зупинки входять два рішення: рішення 1)( ≡xd відповідає негайній зупинці у стані Dx∈ , а рі- шення 0)( ≡xd відповідає продовженню процесу спостережень у стані ,Dx∈ де }.0)()(:{ >−= xcxgTxD α (10) Приклад 1. Нехай )( nY –– послідовність незалежних однаково розпо- ділених невід’ємних випадкових величин з середнім значенням .∞<µ Не- хай )( nZ –– послідовність незалежних однаково розподілених цілозначних М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 74 випадкових величин з середнім значенням ,λ <∞ причому послідовності )( nY та )( nZ взаємонезалежні. Для ...,2,1=n покладається ∑ = = n i i n ZN 1 і для 0≥x покладається ,0 xX = ∑ = += nN i in YxX 1 Нехай ++ → RRf : –– тотожне відображення. Звідси випливає, що для )1,0(∈α , ( ) ( )xxfT αµλαα −−= 1 . Нехай ++ → RRc : –– неспадна функція. Нехай y — єдиний корінь ал- гебраїчного рівняння ,)()1( αλµα =+− xcx і }.:{inf* yXn n ≥=τ Звідси ви- пливає, що τ задовольняє умові (6) і множина ),[ ∞= yD замкнена. Отже, за теоремою 2, τ є оптимальним моментом зупинки. У модель прийняття рішень для даного прикладу входять два рішення: рішення 1)( ≡xd відповідає оптимальній зупинці у стані ;Dx∈ рішення 0)( ≡xd відповідає продовженню процесу спостережень у стані ,Dx∈ де множина .),( yD −∞= Приклад 2. Нехай )( nY –– послідовність незалежних однаково розпо- ділених випадкових величин з функцією розподілу F із середнім значен- ням .∞<µ Для будь-якого дійсного числа ,x покладається ,0 xX = і для ,...,2,1=n .),...,,(max 1 nn YYxX = Нехай RRf →: –– тотожне відобра- ження. Звідси випливає, що для )1,0(∈α ( ) ( ) ( ) ( )∫ ∞ −−−= x xdyFxyxfT .1 ααα Можна показати, що )(xfTα незростаюча функція від .x Якщо припу- стити, що )(xc є неспадною функцією, тоді )()( xcxfTx −→ α є незростаю- чою функцією. Нехай y буде єдиним коренем інтегрального рівняння ( ) ( ) ( ) ( )∫ ∞ +−=− x xcxdyFxy .1 αα Тому τ задовольняє умові (6) і множина ),[ ∞= yD замкнена у розу- мінні, визначеному вище. Отже, за теоремою 2, τ — оптимальний момент зупинки. У модель прийняття рішень для даного прикладу входять два рішення: рішення 1)( ≡xd , яке відповідає негайній зупинці у стані Dx∈ та рішення 0)( ≡xd , що відповідає продовженню процесу спостережень у стані ,Dx∈ де множина .),( yD −∞= РЕДУКОВАНА МОДЕЛЬ РІШЕНЬ У ЗАДАЧІ ОПТИМАЛЬНОЇ ЗУПИНКИ МАРКОВСЬКОЇ ПОСЛІДОВНОСТІ З ВИПАДКОВОЮ ПЕРЕОЦІНКОЮ Нехай }0,,,{ ≥= nPFXX xnn –– однорідна марковська послідовність у вимірному просторі ),( BX , де )(xg –– невід’ємна B -вимірна функція. Теорія прийняття рішень у задачах оптимальної зупинки Системні дослідження та інформаційні технології, 2010, № 4 75 Поряд з послідовністю }0,,,{ ≥= nPFXX xnn задано послідовність },,{ 21 …βββ = незалежних однаково розподілених випадкових величин ),,10( bM nn =<< ββ причому }0,{ ≥nnβ та }0,{ ≥nX n є незалежними. Позначимо .21 n n ββββ ⋅⋅⋅= Зупиняючи послідовність }0,{ ≥nX n в мо- мент ,n отримуємо випадковий виграш ( ) ( ) .1 0 1 1 ∑ − = − − − n s sn n XcXg s ββ (11) Тут )( nXg –– функція виграшу в момент зупинки, )( sXc можна тра- ктувати як плату за можливість провести чергове спостереження, перебува- ючи у стані sX і β –– як випадковий параметр, яким враховується зміна «цінностей» у часі. Необхідно визначити модель прийняття рішень щодо моменту зупинки, на якому досягається максимально очікуваний виграш. Ця задача зводиться до задачі про оптимальну зупинку двовимірної марковської послідовності }0,,{ ≥= nXY n n n β у фазовому просторі XY ×= )1,0( із функцією виграшу X∈∈= xxyyf ),1,0(),,(),( θθ , причому ( ) ( ) ( ) ( ) X∈∈== xxgxfyf ,1,0,, θθθ . (12) Таким чином, { }0, ≥nYn –– однорідна у часі марковська послідовність з перехідними ймовірностями { } [ ] ( )BxPPyYBYP nn ′′≤==∈+ ,/\|1 θθβ , (13) де }\|{),(,0,),0( 1 xXBXPBxPBB nn =′∈=′<′<′×′= +θθθ . Отже, у вимірному просторі )~,( BY задано марковську послідовність }0,{ ≥= nYY n з перехідним оператором == )()( 1YfMyfT yY ∫= Y )(),( zfdzyP . Нехай xx =),(θϕ –– вимірне відображення →× X)1,0( ),( BX→ ; θθ == ),()( xhyh –– B~ -вимірна функція в Y ; =))(( yg ϕ 0)()),(( ≥== xgxg θϕ –– B -вимірна функція в .X Тоді, зупиняючи послі- довність }{ nY у точці ,)1,0(),( X×∈xθ отримаємо виграш ( ) ( ) ( )[ ] ,,,, xgxhxf θϕθθ = (14) причому для будь-якої вимірної функції ),( BXLf ∈ справедливе співвід- ношення [8]: ( ) ( ) ,Y XT f h h bT gϕ ϕ⎡ ⎤ =⎣ ⎦ (15) де XT –– перехідний оператор послідовності },{ nX а XTb –– добуток XT і оператора множення на сталу ,b причому XTb –– оператор, що зберігає нерівності у просторі ).,( BX За аналогією [8, 13] мають місце наступні результати: Лема 1. Найменша YT -ексцесивна мажоранта функції ),( xf θ є функція ),,( xs θ що задовольняє рівняння Вальда ( ) ( ) ( ){ }, max , , ,Ys x f x T s xθ θ θ= , (16) М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 76 яке, взагалі-то, немає єдиного розв’язку у просторі B~ -вимірних функцій. Лема 2. Найменша YT -ексцесивна мажоранта функції ),( xf θ є функція ( ) ( ) ( ) ,,1,0,, X∈∈= xxxs b θσθθ (17) де функція )(xbσ є найменшою XTb -ексцесивною мажорантою функції )(xg . Лема 3. Якщо функція )(xbσ –– найменша XbT -ексцесивна мажоранта функції ),(xg то вона задовольняє рівняння Вальда ( ) ( ) ( ){ },,max xbTxgx bXb σσ = (18) що має єдиний розв’язок у просторі B -вимірних функцій. Наслідок. Функція )(xbσ є достатньою статистикою у задачі оптима- льної зупинки, а очікуваний фактор переоцінки впливає лише на область оптимальної зупинки. Це твердження випливає із лем 2, 3. Справді, порівнюючи вирази (17) та (18), доходимо висновку про те, що у задачі про оптимальну зупинку з випадковою переоцінкою достатньо спостерігати лише еволюцію одновимі- рної послідовності }.0,{ ≥nX n Зокрема, оптимальний момент зупинки τ визначається як момент першого попадання у множину ( ) ( ) ( ) ( ){ }: , 0 ,b XB x x g x bT g x c xσ= = − ≤ (19) де XbT –– оператор, що діє на функцію виграшу g у стані x , визначає очі- куваний дисконтний приріст виграшу від зупинки на наступному періоді часу, тобто [ ] ),()()( 1 xgXgbMxgbT xX −= і оптимальний момент зупинки визначається як { } inf : nn X Bτ = ∈ . (20) Mає місце наступний основний результат: Теорема 3. Якщо виконуються вище наведені умови (14–15) і множина B замкнена, тоді *τ є оптимальним моментом зупинки. У модель прийняття рішень у даній задачі оптимальної зупинки вхо- дять два рішення: рішення 1)( ≡xd відповідає негайній зупинці у стані ;x B∈ рішення 0)( ≡xd відповідає продовженню на один період часу про- цесу спостережень у стані ,x B∈ де ( ) ( ) ( ) ( ){ }: , 0b XB x x g x bT g x c xσ= = − > . (21) ПОСЛІДОВНІ ПРАВИЛА ПРИЙНЯТТЯ РІШЕНЬ В ЗАДАЧІ ПЕРЕВІРКИ ДВОХ ПРОСТИХ СТАТИСТИЧНИХ ГІПОТЕЗ Нехай …,, 21 YY –– незалежні однаково розподілені випадкові величини із щільністю розподілу f відносно деякої σ -скінченої міри µ на прямій. Теорія прийняття рішень у задачах оптимальної зупинки Системні дослідження та інформаційні технології, 2010, № 4 77 Необхідно перевірити гіпотезу 00 : ffH = щодо гіпотези 11 : ffH = , де 0f і 1f –– задані функції. Втрати, пов’язані з прийняттям гіпотези 1H у випад- ку, коли справедлива гіпотеза ,0H дорівнюють ;0>a втрати через прийнят- тя 0H у випадку, коли справедлива ,1H дорівнюють ;0>b вартість прове- дення кожного спостереження iy дорівнює одиниці. Процедура послідовних рішень ),( Nδ складається з моменту N зупинки спостере- жень та прийняття остаточного рішення .δ Математичне сподівання втрат для рішення ),( Nδ дорівнює ( )NMa 00 +α , якщо справедлива гіпотеза ,0H ( )NMb 11 +α , якщо справедлива гіпотеза ,1H (22) де ),прийнято( 100 HP=α ).прийнято( 011 HP=α Якщо існує апріорна ймовірність π того, що має місце гіпотеза 0H і, отже, ймовірність π−1 того, що має місце гіпотеза ,1H то очікуваний ризик для рішення ),( Nδ задається формулою ( ) ( )[ ] ( ) ( )[ ]NMbNMaNr 1100 1,, +−++= απαπδπ . (23) Для даного моменту зупинки N легко визначити правило остаточного рішення ,δ яке мінімізує ризик ),,( Nr δπ при фіксованих значеннях .,, πba Для цього оцінюється вклад рішення δ у ризик ),,( Nr δπ , що дорі- внює [12]: ( ) ( ) { } ( ) ( ) ( ) 1 0 1 0 1 0 1 1 , прийнято 1 ... ....n n n N n H a b a f y f y d y d yπα π α π µ µ ∞ = = + − + +∑ ∫ ( ) ( ) ( ) { } ( ) ( ) 0 1 1 1 1 1 , прийнято 1 ... ....n n n N n H b f y f y d y d yπ µ µ ∞ = = + − ≥∑ ∫ ( ) ( ) ( ) ( ) ( ) { } ( ) ( )0 1 0 1 1 1 1 1 min ... , 1 ... ....n n n n N n a f y f y b f y f y d y d yπ π µ µ ∞ = = ⎡ ⎤≥ − =⎣ ⎦∑ ∫ ( )[ ] ( ) ( )[ { } ∑ ∫ ∞ = = +−= 1 010 ...1,min n nN nnn yfyfba πππ ( ) ( ) ( )] ( ) ( )nn ydydyfyf µµπ .......1 1111−+ , де ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ....1... ... ..., 111010 010 1 nn n nnn yfyfyfyf yfyf yy ππ π ππ −+ == (24) Для даного моменту зупинки N визначається правило прийняття рі- шень δ ′ таким чином: приймається ,1H якщо nN = та ( ) ,1 ba nn ππ −≤ приймається ,0H якщо nN = та ( )ba nn ππ −> 1 М.В. Андрєєв ISSN 1681–6048 System Research & Information Technologies, 2010, № 4 78 Тоді ( ) ( ) ( ) ( ) ( ) ( ) .,1,,1, 1010 NbNaNbNa δαπδαπδαπδαπ ′−+′≥−+ (25) Отже, відшукання пари ( ), Nδ ′ , яка для даного апріорного розподілу π мінімізує ризик ( )Nr ,,δπ , представляє байєсову процедуру перевірки простих статистичних гіпотез ., 10 HH ЛІТЕРАТУРА 1. Abdel-Hameed M. Identities for Stopped Markov Chains and their Applications // Applied Stochastic Models and Data Analysis. –– 1986. –– 2, № 4. –– P. 193–208. 2. Arrow K.J., Blackwell D., Girshick M.A. Bayes and minimax solutions of sequential decision problems // Econometrica. –– 1947. –– 17. –– P. 213–214. 3. Hochman E. An Optimal Stopping Problem of a Growing Inventory // Management Science. –– 1973. –– 19, № 11. –– P. 1289–1291. 4. Elfving G. A Persistency Problem Connected with a Point Process // Journal of Ap- plied Probability –– 1967. –– 4. –– P. 77–89. 5. Snell J.L. Applications of martingale system theorem and applications // Transac- tions of the American Mathematical Society. –– 1953. — P. 73–101. 6. Вальд А. Последовательный анализ. –– М.: Физматгиз, 1960. –– 325 с. 7. Де Гроот М. Оптимальные статистические решения. –– М.: Мир, 1974. — 492 с. 8. Дынкин Е.Б. Достаточные статистики для задачи об оптимальной останов- ке // Теория вероятностей и ее применение –– 1968. –– XIII. –– № 1. –– C. 150–151. 9. Неве Ж. Математические основы теории вероятностей. –– М.: Мир, 1969. –– 307 c. 10. Роббинс Г., Сигмунд Д., Чао И. Теория оптимальных правил остановки. — М.: Наука, 1977. –– 167 с. 11. Ширяев А.Н. Статистический последовательный анализ. Оптимальные правила остановки. — М.: Наука, 1976. — 272 с. 12. Чао И.С., Роббинс Г. Об оптимальних правилах остановки // Математика (сб. переводов). — 1965. — 9, № 3. — С. 444–454. 13. Андреев Н.В., Губенко Л.Г., Штатланд Э.С. Об одной задаче оптимальной остановки марковских последовательностей со случайной переоценкой // Сб. ст. «Теория оптимальных решений». — Киев: ИК АН УССР. — 1968. — № 5. — С. 100–104. 14. Андреев Н.В. Оптимальная остановка процесса марковского восстановления с малой вероятностью поглощения // Кибернетика и системный анализ. — 1994. — № 6. — С. 176–179. 15. Андреев Н.В. Оптимальная остановка агрегированных и слабо возмущенных дезагрегированных марковских и полумарковских моделей в дискретном времени // Системні дослідження та інформаційні технології. — 2002. — № 3. — С. 139–146. 16. Андрєєв М.В. Синтез оптимальних стратегій планування стохастичного експе- рименту в задачах найшвидшого виявлення неполадки // Системні до- слідження та інформаційні технології. — 2003. — № 3. — С. 111–119. Надійшла 09.12.2009

Теорія прийняття рішень у задачах оптимальної зупинки

Institution

Ähnliche Einträge