Методы оптимальной остановки в оптимизационных и минимаксных задачах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

/пз

ЛЕНИНГРАДСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

/"2йО ■/? правах рукописи

^^У.сух^с УДК 519.2, 519.8

МАЗАЛОВ Владимир Викторович

МЕТОДЫ ОПТИМАЛЬНОЙ ОСТАНОВКИ В ОПТИМИЗАЦИОННЫХ И МИНИМАКСНЫХ ЗАДАЧАХ

01.01.09 — математическая кибернетика

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Ленинград—1990

Работа выполнена в Читинском институте природных ресурсов СО А¥ СССР.

Официальные оппоненты:

доктор технических наук НЕЛЕПИН Р. А.;

доктор физико-математических наук НОВИКОВ А. А.;

доктор физико-математических наук ТОМСКИЙ Г. В.

Ведущая организация — Институт математики и механик! УО АН СССР.

Защита диссертации состоится «_» _ 1990 г

в _ часов на заседании специализированного Ученого совет:

Д-063.57.33 по присуждению ученой степени доктора физико-математиче ских наук при Ленинградском государственном университете (Ленинград В. О., 10 линия, д. 33, ауд. 88).

С диссертацией можно ознакомиться в библиотеке имени А. М. Горь кого Ленинградского государственного университета (199164, Универсн тетская наб., д. 7/9).

Автореферат разослан «_» _ 1990 г

Ученый секретарь специализированного совета кандидат физико-математических наук Л. В. ХАРИТОНОВ

- 3 -

СЕЦАЯ ХАРАКТЕЖЕШ ГЛБОТЫ

Актуальность тсуч. Задачи оптимального управления-случаинн?::: процесс?.!,г.! кь:ект парное теоретическое у.т практическое значение. Сд-ной из ветвей этого направления являятея задачи оптимальной остановка, где ас результатам-последовательно псс гупаю.'Д'.х наблюден:::'-, получение'хотогух связано с" определен!•>.?»и ззгратат/и, следует сде-дать ззкдвченке о ток, сто::? ."и еце продолжать Н1б.яюди:ля или и:-: достаточно для того, чтобы принять правильнее регение'.

Бозкяшргекие и интенсиэнсе развитие исследоээдов задачи сл-тиуальнсЛ сс-тансзкн получил;: после появления в К'^7 году ккнм А.Зальда " "Последсвательнк-Д анализ",-в которой енл списан один частный гетод проверки статистических гипотез, который назывался последовательны« критерием отнесения вероятностей. Л.Зальдо:.: и ¿bs. Зсль*оаи1;ем бкло доказано, что в задаче различения двух гипотез при заданных вероятностях одкбечных решений среднее число наблоде-ний о т о л последовательной процедуры не бедыге, чем у лзбего другого редакдего правила. 3 случае, когда получение наблюдений связано с определенным: затратами, последнее ку.еет важное практическое значение. онзчптельние продвижения в сбдей теории байесовских ресащих правил были едэданн в поеледукцих работах А.Зальда, Ля.ЗальрОБииа, Д.Елекуэлга, А.Г/рг:пг'а, ГеГроота и других авторов. 3 1951 году Д.К.ииг.яеэки Сьтло дано, решение задачи сб оптимальном обнаружении :.:о:,:."кга г.зхекенкя свойств наблядаеуого пропесса (так называемая задача с разладке), которая сказала еллыгсе злияннз на- дальнейшее развитие теории оптимальной остановки, как з связи с оригинальность» кетсда с еденяя, так и в связи с прикладной направленностью са:/ой задачи, поскольку больдей класс задач б радиотехнике, касакцийся обнаружения сигналов в цепи, относится к этоку типу. Алгоритм обна-руг.екия бъ'л основан на сведении задачи о разладке- к задаче опта-

галььсй остановки некоторого марковского проигсса. Стоеткм также ¡.•i.riiiv результаты в г то!! области К.ПэЬ^а, Т .Ладена, А.А.Новико-

\ч< 1! др. -

• Одновременно с отк!.'и работами развивалась о6е;эе теория опти-.vur.bHL-x правил остановки. Центральное место б ней занижает задача с гмСоге наклучпыо объекта. Обзор результатов ь ртом направлен'.'.'.! i.:o-~ho ш?ти в обобгеакзей ыоногра-Тии П.Чао, ГЛ-оббинса, Л.Сигкунда. 'Ткг,_: ия опткуьльных прагкл остановки" к статье Jl.C.Poysa { "Twenty years of secretary problems: a survey of developments in the theory of optinal choice".- Adv. Kaneg. St., 1, 1982, p.53-64).

- 3 ряде задач, оптимально»": остановки вид йункпки вкигрипа при оатаноьг.е' адгет сказаться не с-оьсы: определенны, например, когда задаче/ наблюдателя является остановить пронесе наблюдений как -1.:о'-.:но Слито к KeKOTO.LO.vy noj.oroEo.vy значений. Понятие "блкд.е" ко-::хт п/.еть разное толкование. Так б задачах последовательного анализа наблюдения продолжаются до тех пор, пока апостериорная вероятность какой-либо гипотезы не станет близка к единице, а "близость" определяется по задании!.: потерям в случае ошибочных jezse-ни?, которне бнЕает трудно оненить(ото особенно актуально v зада-чау. медицинскоп диагностики). В задаче о разладке оптимальное правило ищется в смысле йункниснала, учитывающего вероятность "ложной тревоги" к длину интервала вреуенк ме?'ду на ступи г-гх-к раз-лапкой и кокситам ее обнаружения. Однако кяогда трудно сгаьн;пь указанные величин:-.' между собсГ:.

В связи с: откм представляет интерес рассмотреть минимаксной карнант задач оптимальной остановки. Сн м.охет бнть йспольоор&к во бс.гх перечисленных выше задачах - б задаче с Енборе наилучшего объекта (нукно -выбрить объект лучший, чем у противника), задаче о разладке ! г-ги грива ет игрок, первым обнаруякбьйй mci.'sht разладки), алгоритма?, случайного поиска зке.тремума функций (¿''игркг.ает игрок,

насэджй значение ^ункагл больае, чем у противника), а такяе в ряде задач оптимального управления случайкккя процессами. !йшккакс-1-:ь;:.1 задачам'оптимальной остановки-были-поевяцены работа fcs.Гиль- • берта, О,.'.,остеллера, 'J. Сакагучи, ¿¡.Курано, Д.Какагаяи, ¿¡.Ясуда,

Е.Г.Еннса, З.З.Ференстейка, ЛJJ.Петру челли-, А.А.какт.уга-ра, Д.Н.Ляпунова, B.K.iovai-CKoro, Г.Н.Дюбкяа, З.Л.Прескат, П.У. Сснгна, F.H.Читасвхлля, Г.А.Чеизвялли* Н.В.йлбакидзе и.др.

Пельа паботи является исследование минимаксных проблем и задач спт;:г.:аль.чого управления' случа'Рньг/и прок-еса-'И, а которых стра-. тегияуи являются-уоненти остановки нлблюдаеунх- процессов."

. научная новизна и .практическая знач:::,;ость. Лкссертакиошая работа посвящена раззити» ноэого направления математической. ¡«бар-кет;::« , лЕг'л:цего на'стыке теории nrj) и управляемых случал!: ::<: процессов. ■ '

В -диссертаиии развит оригинальный, подход к исследованию задач оптимальной остакозги с помощью спектрсз-стратегий, которые, кая показано в работа.образуют выпуклое замкнутое кноу.естэо в евклидово:.-: пространстзе. Переход от сложных проетранстз измеримых функций, которжя-яйлявтся стратегии, к простак пространствам для'спектроз. даэт большие праииуцества. •

Впервые получены ресенкя ыиниыэхснкх проблем оптимальной остановки,/процессы наблюдений' в которых представлявт собой случайные блуждания, пннероЕскяе процессы-последовательности испытаний Бернулли, последовательности независимых, одинаково распределенных случайно: величин. Для достижения этого развиты новые геометрические кзтоды нахождения- пекы з.задачах оптимальной остановки. йш;;-уаксянв проблекы оптимальней огтанозяи можно исследовать с гояялыо теоретжо-кгрсзкх кетодоз," однако, икенно применяя-методы оптимально'/ остановки,в работе удалось получить значительные продви-лог>'я" я отом области.

. В диссертации впервге исследованы задачи,- в которых решение задччк оптимальной остановки является од ни е- из отапоь оптимального упрзьления некоторым случайны:.' блугданием. доказано, что оптимальнее стратегии ле~ат в классе пороговых стратегий и найден к:: я; • ьид и окрестности нуля и бссгокечнсютк, ксслсдосаки их «.оГства в шчкь-акскок варианте задач. Предложены численные гетодн их нахождения.

:азрабстаннуе в диссертации уезодн реп.-;:зоьаии и виде численных про::од\р. Ь лабератогин узтсг.*аткческкх проблем управления г скслогик Ч1П1Р СО АН СССР под руководство;; агтера создан пакет приклад »их программ "Остановка"предназначекнки для рег.ения различна пргклздтгх задач одтккальной остановки. Пакет кокет бить использован для нахождения местополотенпя источника 'примесей н реке, оптимального управления процессе;.: переработки гудч, оптимального сбора уро:-;ая е.различных задачах природопользования, диагностики, нахождения экономных методов распределения памяти. £Бт, прекращения наблюдений в задачах случайного поиска глобального экстрен/а ^унк-ций, решения других задач оптимальной остановки, в том числе - и б минимаксной постанське. Пакет "Остановка" используется на ряде организаций .и предприятий Читинской "области. На его основе на Кер-чинском полиметаллическом комбинате совместно со специалиста!.';; Читинского политехнического института была внедрена автоматизированная система оптимального управления процессом переработки слсг.нкх по составу полиметаллических руд, экономический згрТект от внедре-. кия. которой состегил 50 тыс.рублей (долегое участие автора 1а тыс. руб.).

Сенозже результаты, внносумнс на заикту.

I. Предложена теоретико-игровая схема исследования задач оптимальной остановки в классе стратегий'различного типа, изучены их скойстга, свойства их спектров.

.2. Разработаны новые геометрические методы построения цены з задачах оптимально;'! остановки.

3. Летально изучены спектры случайных Сдуддакий. ¿оказано, что они полностью определяются соотношениями, куда входят канонические координаты З.'1эллега.

4. Впе^слс получены- аналитические решения минимаксных проблем, опроделенннх на случайных Слушаниях, аинеровских процессах, последовательностях испытаний Бернулли, последовательностях нгса-знен.мых одинаково распределенных "случай:11:х величин.. При :>том, разработан метод. сведения минимаксной задачи к задаче оптимальней остановка с использог-анпек геометрических свойств рункнии пени. Ре-сесие найдено в классе смешанных стратегий, что значительно расширяет класс полученных другими авторами решений, 'которые искал:: его сред;: специальна чистых стратегий порогового вида.

. 5- Впервые исследована проблема оптимального управления случайна-": блуг-да:п:ем, з которой стратегиями каблядателя язллвтея момента остзновки не:;отсрсй случайной последовательности процесса. Показано, что оптимальные стратегии лезаъ о классе пороговая стратегий, получены их явные выразен;«; з окрестности нуля и бесконечности, показ а;'а их моното.чнссть. Прэдлснеку численные методы нахождения оптимально порогов.

6. Оригинальной является постановка задачи и разработанные кегоды исследован:« минимаксного варианта задзчи упрггеления случайным елу-данием. Доказано, что ситуация разкоаесия леки? з классе стратегий порогового вида, исслздозан их нид, получены .аналитические решения в окрестности .нуля и их асимптотический вид.

7. Разработаны новые- численные методы рекения канккакеш« • проблем оптимальней остановки путем сведения их к задачам линейного программирования или процедуре Бсауна-Робинсон.

В. Создан г:а:-т.т прикладных программ- для - рете-ния т;рокого яла с-

са задач оптимальной остановку.;, в ток числе л г- кинигаксно;.« варианте. . -

Апробация работы и'публикации. Ссновнке результат;,: диссертации оСсутдахксь на сегикарах по статистическому последовательному анализу с йатеь'атическоь: кнстк^тс кк.Б.А.Стеклова .Aíi CC'J?, в Яс-нингралекга:-к Якутском государетвекни .ижверсттетах, Иргутскоу шчислитедьног иентре СС АН CCUt, Читинско:; институте пркродплх ресурсов СС АН ££Сг, а такне на I и П Ь?.есся;ьн!;х конргрекцинх "Зс— гоятност'Ше х.стоды в дискретной гатегатике" (Пстрсьавсдек, itfcó, . Ii.-i.-fc), ,4i Бессоюзной коь'среннии "Проблемы теоретической кибсрне-тики" (Иркутск, 1Ы.5), I ■ Всилрноу конгрессе сбцестса г2?е:.-атеч',о— кок статистики и теории вероятностей ин.Ьериулли (Ташкент,.lücG), ¡вегдукародноС • ков?еренгии "¿дтег.атичесгие. кеголы е исследовании операций" (София,. 16£7), Всесоюзной коийеренпни "использование вычислительных средств ь экологии, экономике, ¡/едипине" (Саре^ОЕ, IC'ÉS), XI Все.ссвзноу см.:псзиу;.'е "Логическое управление с использованием ЕВи!" (Ьрдчоникидзе, K-Í.'b), XXII Еколе-коллодьиууе по теории вероятностей и математической статистике (Ьакуриани, И88.), í¿ Все-совзкок семинаре "Обнаружение изменения свойств случайных процессов" (йвекигород,• I9fc6), С Всесоюзно? KOK-f ерекпии "Уе.тодн кг.Сер— •нетики хигико-технологкчееккх пропл-сссв" (Москва, If-tí).

Публикации.' Основное содержание работа спубдккоганс в работах D-I83.

■ Сг,- - »• к структура Еисс.егтаиик.. ^иссертагкя состоит- из введения, пяти глав, списка литературы из 120 наименований и приложения, куда по;.;е^ено. описание пакета прикладных п:«грш.й' "Остановка' Сбьег. работы 253 стр;анини «/атйнописного текста.

. ССИКЬКАШЕ РАБОТЫ

Во введения дается крап-кий исторический обзор, гЧ^иу'дируютея

i

■ - s -

пели диссертации и основные результаты, кратко излагается- содержание работы.

В г.'П"е I "Задачи оптимальна," остановки" предлагается тяор-з---тико-игровчя схема исследовании задач оптимальней- остановки в классах етратегиТ: различного типа. При этом, дается постановка задачи оптимальной остановки- о рунккиям-а зыягрьса j- !Х) и л.гт» . CilГ), определение марковских моментов Î* , Р.'нкнип гены lT\X) и т.д. Б 5 I взодятся стратегии поведения, во § 2 - сме^аннуе стратегии, s ? 3 - чистое стратегии.

Под стратегией поесд&ния понимается векторл~= с компонентами Ж^ =Pfr*/l ] » где Т- коаант останов-

ки конечной марковской цепи ССп'и)) на мно:~еетзе El ),

з под опкгрсм- S» ( где jS.e £> {ЗГ, ** &£ ),

i = I, К. Следующее утяер-^дение является следствием прямых уравнений ¿-¡'-.Колмогорова. '

-Теорема- I.I. Компоненты спектра S кояно найти по формулам

г ^«Ь

где величина j удовлетворим системе линейных уравнений

здесь S" vî) = I. если i = <Х и = 0, если L^Ct,

а - а

' Его.следствием является утверждение, что множество всех-спектров - вшг.'клое и замкнутое множество з R- .

гандом/зания- на. множестве стратегий поведения приводит'к по-. кяга> смйчйнной стратегии. Смешанные■ стратегии будут играть особую гель в глаэе Ш при решении :/инн;.-акс;пи: проблем.3 % 2 показано, что ^меганнрд стратегии не даят новых спектров, и, следовательно, при решении сЛнлн'.« задач оптимальной остановки достаточно ограничи-зэться рассмотрением стратегий поведения. Чистыми стратегиями здесь галяатся моменты первого попадания з некоторое множество состояний.

«

Ь болы;, о:.: ряде работ оптимальное реление .ищется именно в атом классе стратегий. ' •

Обычно задач:; оптимальной остановки исследуится в случае по-ло-птелънок платы га наблюдения. В § 4 рассмотрены1 вариант знако-п< ;:и:сп:-;о# плати С (ЯГ) (саметим, что задачи с зкакслер-егонноГ: ■ п.па'.оГ логнпгакт при сйсдйпки задач;; олткг/альнсй остановки с dyiut-г за,чаче с ну.'.ьвоЯ qyui:;-;iui\ ыягркха J О, ¿J ). Ге-."уль-атсм исследования кьляетея

Ttcre.va 1.5. пусть , ..., - зс-к'ор.-и

й.'гг^елыйж .нероятностсй и плате-:«!: для оргодическкх классоз , . ...,,мар-кокской г.сш; соответственно. Тогда, если для некоторого / i^K* , то оптимально;» стратегий? прч; попадании прог:ссса в множество яелясгея Г =00 ; если в« , то спти-

. к»льпой стратегиеГ: является vckcht первого попадания в гнояостяо Г"* - | ХеЕ! : lf(x) ^ffa)}.! причеу цена if гскечнз и ясляется предела-.; jtpv.d.-* 4 пен tQ(Jf) в задачах с коэ£;?:шкситси переоценки ol.

' В § 5 получены соотношения, гстоиг/и полностью определяются спектры случайных блууданий на множестве |о, I, ... ,1с] с начале;-.' б точкеДп ¡¡а их основе ь 5 б предложен числен::«:" метод построения по заданный спектра?.: сами>: стратегия. При гтох; используются к&конкчеокгге координаты,... , введенное 2.1-еллер-о::, ьвд а. = 0,"И, = . г f." •

i = ..

Те op ема I.E. Хля того, чтобы -вектор S был спектр, он некоторой стратегии *JT , необходимо и достаточно, чтобы выполнялись условия

КГ 1С

t'O

В 5 7 для исследования задач оптимальной, остановки предлагается использовать геометрические свойства функции пены, при ото:.;, з гг.1, используя геометрические соображения, строится оптимальное правило в задаче с независимыми одинаково распределении;/;« случай-ню.:;; наблюдения;.'.;!, в п.2 и п.З предлагается простой геометрический способ нахождения иены з случае пронззолыых случайных блужданий на канонической ¡скале, и в п.4 описан геометрический метод построения цснк в задаче с наблюдаемой последовательностью испытаний Берну лла.

Глава Л "Оптимальная остановка наблюдений з задачах оптимального управления случайна'.::! блужданиями" посвящена исследовании задачи оптимального управления случайным блужданиям, связанной с задачей наилучшего выбора, "/¡меется последовательность серий^/(Ш) ( £ = I, ;_/=!, 2... ) независимых случайных величин с

одинаковой плотностью распределения р , I . В пределах

кандск. серии ^ ____осуществляется снбор как в задаче о

секеетаге, дагиий значения Ц1 /* = I, Г:____ Тос-буется осга-

низоеать выбор так, чтобы последовательностьИ)) = ОС. <0^

±

х+п: г/4 1-< Щ)

впервые достигала нулевого значения при .уиням.альноу .(либо, наоборот, максимально-.:)

3 § I э соответствии с геометрическими соображения:.';! первой гласи предлагается искать сезечие отой задачи а классе помгоэых

К-1

ст-атег

, .... ^ ) гида, если Я < О,

, /с

то я /С-ой серии забирается первая по номеру г. величина такая, чти (для задачи на максимум ); здесь ^ =

Ломнд 2.1. Плотность распределения 'собранной согласно стратегии Т (Ъ^ , .. ^ ^ ) величины ^ не зависит от немела еру;-»

1С и к»/еет вид

Г И-1 А/-/

дл>: .аадачи из »/а г га:-ум -

г И-1 А'-У

рСу)^ , 1А - »„таякср Л.

А.чалнр;р у я ь §§ 2 и-З уравнение для олтиг. а.\ы;сгс с-рсдньго ;.альи т.(») И (сос-тресствеичо Т (Ж) = дсстк-

Х'ЛиИЛ нуля

г /

получае:.- следующие. -утве^тйрм'кя. •

Teo.f-ei.-a 2.1 (случай уаллг /*/ ). Есл;: X тьковс, что. выполняете1? услоьио / Т(х-ц-)р(ч)ац. { •• (сс-отгс! п ьг.:ч:г-А/-* . в (• у О Г V <Г

стратегия поведения Т(2) определяется, с по>,'отьл породсв, гагяу-:

= . /= I......

Б равномерном случае « I, 1Л. от/. области пред-

стасляв? собой интервалы [ Ду , к [ Х^, , границы который

»/.окно найтк кз уравнсик."

"м-

*у

^К-*» АЬ/

л

V ~ „ • г /Н

?у;:к:л:.ч р (у) удовлетвс; яот уелоьи.'у: р О-соо . Лебега 1]: р у) = о} нулю, то .— г

• Tf. oy-p.va (случч?. бель.:;:л |*| ). Ьри - оо

Ьм\ Т(х) - (- т/Ь+- с)] = о,

Ь - ) ' » С - НСКСТО; ап псстс"..::-!-.

з?с;:, с?-;: обо значить оптимальные в задаче на ¡.ини;.;,;.- (ссответсг-

г-г.-нс максиму;.:) .пороги через (г^х), ... , -2^ (х))

- ) , то ¿X ваиитотма, ка-показано в 5 4 кнеет следуасхЯ вид.

Теорема 2.3. при . а: — - • - 2'6*0 = 2. ,

2 ^ » -2 , где ,2 определен!.: соотисягстпоино соотношениями -

<

I I

1

Н-1

о а! о $ _ »

V

• - М "

\

В § 5 отмечается монотонкость оптимальных иосогов 2 (X ) и

ш " ---

2 {X) в любой точке х<б

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

В главах Е! и 1У задачи оптимальной остановки исследуются з минимаксной постановке. Изменение критерия влечет изменение структуры решения. Заметим, что возникающие здесь минимаксные задачи мс:кно исследовать с псно^ью теоретико-игровых методов. Однако, . значительные продвижения удается получить,.применяя методы спти-. мальной остановки. ' •

Глава С "Аналитические методы /решения игровых задач на прави-. 1 ло остановки" посвящена исследованию игровых задач, в которой задачей игроков является остановить процесс своих наблюдений на зна-' чскии большем, чем у противника. В § I предлагается метод сведения таких игр к некоторой специальной задаче оптимальной остановки. Используя этот принцип, а такке разработанные в главе I геометрические методы нахождения функции пены, удается решить серпэ игро—. вкх задач для различных наблюдаемых процессов. В § 2 решена игровая задача /"*(й4) двух лип,, когда их наблюдения представляет

симметричные случайже бл'/ядания. * • - '■ ~со а)

Теорема 3.1. ьсли. Х^ ,(й>), X -(й)) - симметричные случайнее блуждания на множестве ЕГ = I,..., к| , начинавшиеся з состояниях Л( и алу, поглсцал-лиеся в состояниях 0,К, то значение игр« Г ка„а£ равно ( й,- а^/а г.-

3 § 3 каРдеко реззкис игрл: Г*Щ ) для несимметрична случайных блугдан'.!-/. При с-том используется геометрический метод построения гены в канонических координатах, предлшонный з главе I.

м

Один из полученных здесь результатов такой. Пусть *£{&)),

с началом в состоя

- 15 -

а) ~

Х^ (и)) - случайные блууда.чкя па множество Ь.

ниях 01 и й^ и поглощением а состояниях' О ¡: (С , :: ¡^ , р - вероятности перехода в любом состоянии влево и вправо и о( ,'р <[ Тесдема Ксли для некоторого нелого числа Ш такого, ч^о

№. £ (» выполняется условия

то значение игр н Г* (¿7,,равно

Н*--

«г

а сгект;:.; 5 и Б

лс:::д соотнесениями

оп'тмалы-пгх стратегий игреков х.и « опроде-

СП)

1+Л ~ Л -Л

I =

1т+1 «-л. . -о/ -о/

, ип+г . к . к+1

<+Л -Ы

/ -Аг

3 5 4 получено рее«икс игры .Г* (О, С) для последовательностей иелнтаппй Бергулли с вероятностью успеха р . При сведении иг-гевег задачи-к задачам оптимальной остановки используются кзкоки-

А Я

ческие координаты =.-!-> Ил-_{1 ~р ■ )/р , к геометрические сгойстг." йена, разработанные а глаье'1.

• ./ля нггото-.-ого набора нель:хчкгел ■<. £ К-1

< I ... т

обозначим

* / ¿-о 7"

Т'.огсга 1.7. Если р такое, что для всех £ = 0,|[Оп-ОЛ1 н-'лслняггся условия ■

гПИ+ги. .-и; ■

Г ¡=о j

¿-о У '¿^гж 1хе*£

-211. ,

¿Ы с

г-и* у * ^ ,

то с;,тиг*злык:.;и в игр-а Г* (0, 0) являются сизси стратегий Х^У пг.едппс1;вао,а>: прекращать наблюдения на п, -си таге, вида

р ¡> I- ^ ¿=0 " 7

+£П\-о\-П1. Ип-^л ч'/-г

В пссладусзих двух параграфах найдено решение для случая процессов с кет.рзркзчш.', гксягстви.;. состояний.. 3 §-о решена игровая задача, определенная на пинеровских процессах и значение игры полу чается такое яе, как в тессе;.« 3.1 и в § 6 решена игровая задача

для конечной совокупности независимых сдинакок» гасп; од;;.,е!.;;:г: г. неп;сркъноГ :*''ккг.ией еасп'.едслен.п': f (*)"на j£ сг.'ЧйГых :-e.v:".;;-.

Т^о;. ема Сптимальнг;.".: стратегия:--::'. к--л ист "й нгрсго;;;;о

„ д _ ►

стратегии, определеннее с пемопъ» порогов i, , ..., Z^ , г;-:-{ ГС FÍZu-l)} - ение систем" ;,ja н-. й

У-/ ' V-i

N-i «-*

I * zn n

Z, ^ z«»< *■= ,v< /-t У

11 1 * V-i

í+ZZ: /7 г.

/r-<*i J

Б случае bí = 2 наблюдений система 'представляет собой, одно уравнение для определения-единственного порога í* : Его решение - "золотое" сечение интервала [_0, i).

газгаботанний в 5 I- принцип сведения игр такого типа к задачам оптимальной остановки работает и в игровых задачах Г* (flf, -•-> Д ) с нееголыт.'.'л'. участниками. сто показано в § 7 и затек в 5 Ь sü^Tw-я полное регение иг; н ГЦ'-.йд ) для симметричных случай-•Hi'-í блугд«1:ий на гчог'-ет; й.у £ ~ ( О, i,..f}

В главе "Сптпучльннз стратегии в дин5>г.!Чпсгих играх ка правило оетансм-:;:" исследуется ккникакекнй вариант задачи управляемого случайного блуг-дания, которая рзе^матрп-а.саеь н глаю ii. Гасскатр-инаечся динамическая игра f ( Xt,Xz,fJ ) «ч'тоняямч) гида. Предположим, что из точек j", - на отрицательной полуоси ркхсдл-два объекта и начинают двигаться случайны;.?« скачка?, и в сторону ¡.-у- • ля. Величина,-на-которую двигается качдкй объект, определяется

: - 18;-

также, как в главе П. Выигрывает тот кэ игроков, чей объект лервыт,« цересочет нуль. Такие игры- можно трактс2дгн-£2Н.Х0нки под парусом со случайны.: ветром-.

Tarso, как и в главе ¡7," осковнуа роль здесь играат стратегии порогового Еига. Согласно теореме Носа, решение йене? получиться . в смесях этих стратегий. Исследуя уравнение для значения такси игры .

Li *

с использование« доказанной в § I в лсу.ме 4.1 непрерывностью сгупк-цки И(Г,,ТХ) в области *íí*0 УДаетоя показать в § 2, что

опти:.'йяьни.:к здесь язляэтея чистке стратегии (теорема 4.1).

В § 3 найдены оптимальные стратегии игроков, когда блу:кдания

находятся в окрестности нуля.

Теорема 4.2. Существует такая окрестность нуля U-:

' У *

где оптимальные стратегии игроков I и П имеют ви и . В равномерном случае( р(у)=

найдено аналитическое выражение для значения игрц |~| (Я^, ) в отой области.

Теорема 4.3. Решение уравнения для Н (X, в области Ц^ имеет еид «

„, V, V/ ¿А/+Г I)/

П (;//♦<)

И в 5 4 исследован случар, когда блуждание одного из игроков находится близко, а другого далеко от нуля.

Теорема 4.4. Три — со оптимальная стратегия игрока I

- IS -со ,

определяется порогами Z^ i ~1,tJ-t.

5 последней главе У "Численные методы рейекия задач оптимальной остановки" представлены численные методы, х-азработажые для репения задач оптимальной остановки и в тем числе, для решения игровых задач, которые положены в основу пакета прикладных щсграгм "Остановка", находящегося в приложении. В § I описан гриниип пропуска наблюдений в задачах оптимальной остановки, .что позволяет в ряде прикладных ьадач значительно увеличить выигркз при остановке. В §5 £ и 3 для решения игровых задач Г (£7,,^) и Г(ûj,

с наблюдениями,- случайными блужданиями на множестве 1£ = {и, I, ..., к-} предлагается, использовать методы линейного программирования. .

Теорема 5.1. Х.ябоэ оптимальное решение задачи линейного лрог-■раммнрокания и

JL, . (о min ¿.-; и *■ &.

при ограничениях

К H (m) а)

rzrz1 л ty) *^и, у=i

* СО . _

СО со (о —-Çs. и , ¡-щ

j-o J i 1 .Ci) _ ___

(СО —\ f ' где ÎU. j-0,K.j ~ канонические координаты для случа;.ново

(i) , —

блучдакия X^ , L * 4, N , дает спектры^оптигальных стратегий в игровой задаче- Г i(ft> при .отём^ПШконьзее значение

■тункпионалз равно 0. __. ■

Лт.ч произвольного случая" в 5 4 для псиона ситуации равновесия-в игрОЕСУ. задачах предлагается уодкЗикаиия итеративной пропедуры Г-гауна-гоби'лсск. 3 § 5 приведены результаты численного моделирования задачи опгкязльнсго управления случайннм блужданием и близкой • к ней по духу задачи динамического• гаепредрленкя паи-дти. 2ÏÏ.L 3 5 б i \ ьк:.ч:л оптимального риска в задаче г.рсьетки гипотез гасспатрива-ется как 'Зунк::и.<: от *.а?рицк платежей. Лля нее ставится несколько окстг.ьхаг.ьнк>: задач iуко*сствг таких к-атри:: и предлагается чис-ле.в'.нй метод редения.

В прпле;:енпп находится'списание пакета прикладных прсг: а:/л: "Остановка". Программы написаны на язаке '¿ортран я предназначены для серии ЕС.

Соновнг'о т-.зультать! диссертация опубликоваин в спзиугуяг га-бс.та х :

1. ¿азалоз В.5. Исследование уравнения для оптимального риска. - В кн.: Вопроси механики и пропесссв управления. Был.2.-Управление динамически:.';: системами. - Л.: ЛИ*, 1979. - с.1£У-1".5.

2. Мазало а З.В.. Сптиуалыи.» рЛк и катрииа платежей. - 3 кн.: Вопросы »леханкки и пропессоа управления. Вып.4. .'¿»тематический анализ управляемых процессов.'-JI. : ЛП>, ISbl. - c.l6C-IôS.

й. юазадов З.В. Об играх, определенных на еу:,?.:ах иезааасийнх одинаково распределенных -случайных величин.! - Б кн.: •Ве-твжциеея-процессы. - Петрозаводск: КЗ АН СССР, lîrtl. - с.ЗС-ос.

4. i-азалов 3.3., Соколов А..З. Со сптиуальнс:.: дикат.-ическом распределении нестраничной памяти. - В кн..: Авто^атизироваин-й систекк управления. Зьщ.З. - Харьков: XA1I, IScI. - с.32-33.

о. ¡.¡азалов В.З. Об оптимальном управлении игровыми случаГан.^;; последовательностями. - В ун.: Грикладнке задачи теории управления.

- Л.: JTj , Кт2. - с.175-163.

6. Завалов В.5. Игровая задача остановки случайных блуждании.

- В кн.: Вероятностное метсдн в дискрютной математике /тезисн дскд. I Бсесокпко?. кон!'. -'Петрозаводск; К4 АН СССР, КВ.;. - с.4?.

7. иззалев З.В. Кгроулле марковские моментн. - В кн.: Вероятностное задачи прикладной математики. - Петрозаводск: Г;Р„', Kg/. -О.62-69.

с. Разалев В.В. Нгрц. ка случайных блуждания::. - 3 кн.: Дроб-г.огм теоретической кибернетики /тезисы докл.,'»Б Всесоюзной конр, -Игкутск: ¡-IpfV, ISt5. - с.71-72.

5. Завалов З.В. Solution of .the gaae'e problem of optimal stop for the Bernoulli scheae. _ В кн.: ПерЕкГ. Бсепкрний конгресс общества математической статистики и теории вероятностей им. Берну л-ли. - и'.: Наука, 1966. - с.696.

Ю..'йзалоз В.В. Игровые моменты остановки. - Новосибирск: Наука, 1967. - 1Ь9 с.

II- KezaloT T.V. Races with random wind.- Mathematical Methods in Operation Research (abetracts of Int. Conference).— Sofia: Inst, of Kath. with Computer Centre, 1987.- p. 63.

ХЗ.Винкиченко С.В., ¿¡азалов В.В. йгрв на правило остановки вине; овски" дгсгессов. •- Теор-ия вероятностей и ее применение. т.ХХХШ, в.З, ier.G. - с.550-591.

'."азалсв З.В. С некоторых геометрических методах,решения

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

о

ния и ксдодсганик сперапий. - Иркутск: ИрП>, 19-Г.Р. - с. 120-1Г.&.

14.Викнкчеь'-о С.Б., .'„азалов В.З. Об оптимальном управлг.;;;--:; прог.ессс:.; ьосстзнс."Л«.-ия. - 3 кн.: Вероятноегние метсдн в ?;т.крзт-ь'Ой катекатике / тезисы докл.и Всесоюзной кокс-. - Петрозаводск:

HS АН СССР» 1988» - с.23-24» - .....

15. Вгнигченко C.B., ^азалов B.B. Игра на правило остапов-kz ко еле 3.0 вате ль нос кг наблз^снпй ¿дгелровашоЛ - Клбер- . нетака, ff Г, IS89. - c.IIS-121.

16. Кузлл В.5., .Мазолов В.В., Кузина i.A. Об оптиулльно"; переналадка, процесса горе работки руо:. - В кн. г Лог:яесгяе уп-равлзяпэ с использованном ЗВ.! (тезисы докл. H Есассазпого спяюзиуна. — И. : îffiî, IS88. - ç.376-377.

17. Кузина I.A., Ь-азалов В.З. "о толу об наружен ля разладки в за-дчах управлзщш- проздссоа переработка руда. — В кн.: Метода юзЗерлетша х^Ежо-технологстеских процессов (тезясы т;окл. Ш Бсесо-зяоХ конф.). - : У IT.!, ISS9. - с. 118.

18. ¡.'а залов. 3.3. Экология и проблегз оптиг-дльксл остановки. - В кн. : Натеттгчаскцэ рационального природопользования. - Новосибирск: Наука, 1980. - с.115-125.