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

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

На правах рукописи УДК 5192, 519-8.

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

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

(М-0М1 — системный анализ и автоматическое управление

Автореферат

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

Ленинград—1991

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

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

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

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

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

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

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

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

СССР.

///» иши

в

1991 г.

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

А. П. ЖАБКО

' Аутл’з.тьнсот ь тс-уч. Задачи оптимального управления случай:--!?.:« nnci!occ.’'i!".! у.асг.7 г.а?мов теоретическое к практическое зкачен^э. Одно!» «із зетвйй отого направления ярля.отся задачи оптимальной осгч-hcek.í, где по результатам-г.ослодопат-зльно поступав; г.-.х нао;:.э,:гн::Г, получение которых связано с определенней затрата!.-.!, следует додать заключение о тсі.:, сто::? ги еце продолжать на5люде!:.!я і:<г. достаточно дм того, чтебь! принять правильнее ре&еиие. •

Возникновение л интенсивнее развитие ксслессзадой задачи сл-темальной сетансзкл патучилк после появления п Іс-Ч? году книг.: А.Зальдч "Последсвательнкй анализ”, в которой бнл списан один частая метод проверки статистических гхяотзз, который иааггсяася поелеповат-ельньг*. критерием относе кил веролтносто/. Л. Вальдом и £у.. Зольісзицем было доказано, что в задаче различения дзух гипотез при заданных вероятностях ошибочных решений среднее число каблк>дс-к::й этой последовательной процедуры «о боль~э, чем у лзо'сго другого ретагслега сразила. В случае, когда получение Наблюдении, связано с определенными затрата?.".!, последнее ;!?.:еет га-.ное практическое значение. Значительные продвижения а сйлей теории байееозс:-:их ресакких празкл бь;л;г сдеданн в последующих работах А.Зальда, Л;г.Ноль;,озииа, Л.Ёлекуэлга, Ü.А.Гиршка, ГеГрсотз ц других авторов. В І96Г году А.Н.и'.:р-'сн:-з; было дано регение задач;: об оптяузльяом обнаружено моулкга изменения сзоРстз наблюдаемого пропесса (так называемая задача с разладке), которая сказала сильное злкянке на- дальнейшее развитие теории оптимальной остановки, ках э связи с оригинальность» метода соления, так и з связи с прикладної! направленностью cavo:": задачи, поскольку больаей класс задач б радиотехнике, касаддиГся обнаружения сигналов а-цепи, относится к этому тину. Алгоритм обнаружения бь:л основан па саедснии задачи о разладке- к задаче сити-

-'4.- '

:-s::chcfi остановки некоторого марковского процесса. Ответим такне к;.-:-¡14 результате е этоЛ области U.Tnkpva, Т.-Лердена, А.А.Новвко-■:а и др..

Сдкскрег/енно с отит ^.аботаги развивалась оба;ая теория оптиправил остановки. Центральное i-есто в пек замигает задача с i-гбо: s наклучпего объекта. Сбзор результатов ь ртом направления

о найти в об обращен ь-оногра*ии И.Чао, Г.гоббкнса, Л.Сиг-чунда. :ш опткуалышх правил останспки" к статье JB. С. Гоу за ( "Twenty years of secretary problens: a. survey of developments in the . theory of optimal, choice".- Adv. Kenag. St., 1, 1982, p.53-64).

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

останс;ге гоу.ет сказаться ко соьсьм сгределсннк.', напри:.'ер, когда задаче.? наблюдателя^ является остановить пронесс наблюдении как- -ис\но Слкте к некоторому пороговое значешж. Пенят ко "ближе” i.:o-::;ст г.г.сть разное толкование. Так в задачах последовательного ана-;!::-а и&Сдкрешя продолжается до тех лор, пока апостериорная вероятность какой-либо гипотезы ке станет близка к единице, а "близость" определяется по заданы:« потерям в случае юкбочиых teuse-нн.';, которые бывает трудно оценить (ото особенно актуально в задача'/. гсдицинсгоГ: диагностики). В задаче о разладке оптнг/алььое правило кается в смысле бункписнала, учитиг&вдего вероятность "ложкой тревоги" к длину интервала вреуенк гегду наступившей разладкой и м»-сотом ее ебнзр,утекня. Однако июгда трудно сравнить указанное величины кекду собоГ:. .

В связи с. г>ти” представляет интерес рассмотреть 1т.нк:.-акснкй вариант задач оптимальной остановки. Сн кояет бить использован во всех перечисленных Бкие задачах - в задаче с выборе наилуч.юго объекта (нукно выбрать объект лучший, wet' У противника), задаче о разладке {пигрпвает игрок, первш обнаружив!,nii колгнт разлад;-::), алгерит?.'«*. случайного поиска скстрег.'уьа чункппй (ь-.тнгргааег игрок,

■ - 5 - .

нашздлиЯ значение фуншиа больхе, чем у противника), а такяе а ряде задач спт:;:»ального упраолекия случа?.нкї.и процессами. линикакс-ііЬ’м задача?.', оптимальней остановки были- посвяцены рабсгн Гд.Гиль- ■ берта, О.!..оетеллера, М.Сакагучи, іі.Купано, Д.гіакагами, Ы.Ясуда,

".;уі, Е.Г.Енкса, З.З.ЇеренстеГіна, ДЛІ.Петручелли, А.А.как/да-ра, А.Н.Ляпунова, В.К..Голанского, Г.Н..Вюб;:на, З.Л.Пресмана, I’- 1-і. ■ Сснина, г.іі.Ч/та^г/лл:!, Г.АіЧежайлли, Н.В.Елбакидэе и.др.

•Ц°дьа г.збот»; являемся исследование миникаксных проблем и задач спта/ального управления случайными процессами, в которых стра-. тетаями япл?иг.“я моменти остановки няблюдазмш:- процессов.

. Нэу^нз? норкзнз и лозгТическая значимость. Диссертационная • работа посвящена развита» нового направления математической, хкбер-нвтгі'к, геяазего на стыке теория игр» и управляешх случаґиг :х процессов. . • . '

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

Зг.ергіга получены регения иинииакснкх проблем■ оптимальной остановка,. процессы накладений’в которых прздстааляззт собой случайные 5лу*дания, гаяероЕскяе процессы-последовательности испытаний Бернулли, послед'озательностя• независимых. сдинахозо распределенных случайных аздичин. Для яосгжения отого развиты нсзые геокетричес-?;:е нвтоды.нахождения-хдены• з.задачах оптимальной остановки, йтки-максдас проблемі оптимальней остановки мстїно исследовать с поі:сшьп теорет::ко-::гро"кх уетодоз, однако, имеино применяя-кетодч оптимально!*- остановки, в работе удалось получить значитагыше продвижения в отой области. .

. В диссертант: впервке исследован:-' задачи,- е ксторнх решение задччк сктиь-алыюи остановки является сдніік- из этапов оптимального уі;раі>ленкя некоторь-'v случайкіл.' б л ; '>“ с а • і: е . Доказано, что оптиналь-hlx стратегии ле:-:ат в классе порегоьнх стратегий и наГден кх якай! ьі:;; и erpосаногти нуля к бесконечности, ксслсдопаш их сьо"гтЕ£ в к i'.'íKvaKCKOi: иарианте задач. Предложены численные Г’етодн их нахождения. •

: ігу.аСстанкь’с в диссертации к'стодц ре-пл;:зоьаш н ркде численных про: .одур. Ь лабст-атс?к:: узтег/аткческих проблем упраолен::.'! р "У.с.’.с-гик Ч;п;р СО АК СССР под руководств«.: аетсра создай пакет прикладних ¡i; crj"Остановка" ,• предназначенный для регхния разлхчнтх прикладна задач оцтипальноГ остановки. Гіакст ¡/.смет быть использс-Б£>н для кахо'сдения кеетополеуеккя источника ’приі/еое? в т-око, ептк- . •кального управления процесса.: переработки руд1’, оптимального сбора урс«ая Е. Jазлкчш-'х задачах- природопользования, діагностики, нахождения экономных методов распределения памяти сБМ, прек; ацекия наблюдений в задачах случайного поиска глобального экстр eic'.va "'унк-ций, т єьєіікк других задач оптимальной остановки, в то:.: числе - к б кккм/аксной поетаноьке. Пакет "Сстанозка” используется на р.^де i>j)-ганизаций и предприятий Читинской "области. На его основе на Нерчинске;.' полиметаллически.: комбинате совместно со спенналистаї:-/ Читинского политехнического института била внедрена актокатизкропанная система оптимального управления црсгессон переработки слсг.нкх по составу полиметаллических руд, экокс.’/ическпй ссрТект от внедрения которой соетаЕил 50 тыс.рублен (дологсс участие автора 15 тыс. руб.). .

Сснозк.ь'е гезультатк, вітеопкУс'о на ааскту.

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

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

■ 3. Детально изучены спсктрь: случайных блужданий. ¿оказано,

чго с::и полностью определяются соотношениями, куда входят канс;:.:-ческио гссгдпнати З.^элляра.

4. Зпирзггд получени-аналит;:>-:ес!:и5 г.есспия минимахенкх ::pGS-лей, определен:«« на случаен::* блужданиях, вкноро2ек;:х п;:о!:<?;сах, последсзательност.ях исгдлтапнн Ее;: мул л и, псслядсзатглыхстлх неса-зпе:'.мы:< сдипахозс распрсдслоинкх'случаГних величин. Пси .ътом.,. разработан хегоа сведения 1'1:н::?.:2ксксй.задачи к задаче оптимальнее остановки с использованием гесметр:чегуих свойств -туккц’/и пчки. ?с-ceir.ie ¡п?д«;о з классе скованных стратег;:;;, что значительно расширяет класс пелучгннпх другими ззторауа'р^сэняЯ, -котохно искал.; иго среди ’¿г.к-•ул7.ъу:1'.у. чиотих стратегий порогового вида.

5. Згкргис исследогана проблема оптимального уярааленад слу-

ча£ж.: блу~даннем, з когоссЗ стратегиями наблюдателя является момент останов:::! яслоторс:' случайней последовательности процесса, ¿оказано, что оптимальные стратегии дс-ат. з классе порогоаах стратег;:;”, получэ!гы их яяны-з знратакия з окрестности нуля ;i бесконечности, показана монотонность. Предложены численные методы :-:а-хскгдёнил оптимальных порогов. - -

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

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

G. Создан пахнет приклздннх программ-для селения шрокого у.час-

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

Ап: с^агип габоть’ и п»бхккагкк. Ссновнь*? результат;.: дкесерга-икк обседались на сетакар'-ах по статистическому пссдс-дюпательно?:у а!;ах игу в /•.атег/атическо;.’ институте км.В.А.Стенлоиа А;! ССЗГ, в Ле-ни:;;ч.алсксг. к Якутске;.- гесудярстреы-т \нквс:,с1’тстах, ¡’ргутско:.-£ 1/4;-!СЛИТСЛЬНОЬ' ии АК» С* , Читинской институте пгирор::.,х

ресурсов СС ¿Л СССР, а также на I к Г; Бсссюсгншс К01Игр,*ги>»:л>: "Зо-гоктностние »;етоды в дискретной гатегатике" СПстроьаь'Сдек, IIЫ, 1Ш-), Ун БсесокзьсГ: коь’е;-£К1>ии "Про5ле!.:к теореткчес-.ко>” кибернетики" (Иркутск, I1.{.5), I Всс-ицрнок конгрессе ебцоепо гатоь-атичус-кон стьтисгикг. и теории вероятностей кл.Ье] кулхк (Тазкгнт,. ,11гс6), ¡¿егдукародио?. -кок^езьнгии %лте!.'.ат;:чесгиЕ: метод! в ксследоьа.-'.ик операций" (Co.fr.fi, 19с7), Веесог.зной конгТ ереша-.н ’Мспользораь'Ие' ъ:-'-

■ чис.тителыих средств ь экслоп;;:, вкоко.уккс, .'.’едлииье " (Саратов,

1С£Ь), XI Всесоюзно!.' симпозиуме- "Логическое упрагленке с испохьго-аемке» сБн." (Е-рд’хониккдзе, Ш&), XXII И коле-келло.ивиуге по теории вероятносте-Г; к «¡текаткческоР статистике (Ьакур^йки, 1£Ьс ), П Всесоюзно!.: семинаре "С-С'карут.ек’/е иргенепип свойств случаЯт-'Х npoi.ee-ссв" {Йвеккгород, • 1££6), Е ВсаоасзчоР кок~ер-ек:;;а! ".«етодя кибернетики хкуино-технологкчвеких пр.огдееов" (1.;оскьа, .

. Публикации. Основное содержание работа спубликогаис в -работах 0-18].

■ С Г. и стиуктуг.а дкетегтат-ги..-Диссертация состоит - г;« ьреде-

■ шш, пяти глаг, списка литературы из 120 нануевонаний и прилоке-нкя, куда по.’/.ацено описание пакета прикладных пр сгра:.::.' "Остановка". Сбьсг. работы 253 странигти И'Ы.'инописного текста.

_ 4 ' '

■ . -ССЖадШ!. РАБОТЫ .

Во шсдеики дается краткий исторически!' обеср, торгу.тируются

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

Я гланд І "Садачи оптимально;“ остановки" предлагается теоре-.... ткко-кгровед снеуа ичслндсганл.'г задач ритуальной- остановка а классау. стратеги” различного типа. При отом, дается псотакойга задачи ситіяяльноП остановки- с *уккгкяю! знигръ.'.па £ !Х) -и плат:.'

С{Х), определение ілрксяскн< :.-о;.-::нтсз X , :;ункмп! генч тГ(Х) и т.т.. 3 5 1 наедятся стратегии поведения, во § 2 - сг.’еЕ-аннн'3 стратегии, е § 3 - чпетне стратегии. . •

Год стратегией поведения пенкуалеч сектор ЭГ = ___

с ко:/::очеі:та:‘.я жі -р/г =п/хл*Єі] , где Т - уо.чянт сстаное-::и конс^ней :,;аркозси.сг цепи Х'п!иі) на :/по:*естзэ С =(Є{, -.., ),

з под сп.:-к грозі- 3= ( где * р {<ЗС «г В. ) ^

і = 1, К, Сладуидее утверждение яоляется еледствяеи пряУкх уравнений Л. ІчКслї'огороьа. '

-Теорема І.І. Компоненты спектра 3 кездо найти по рорї.-улак

ж-.ч>.,

г і е *■ 1 * '

где величины | . удсзлетасряат системе линейных уравнений

дозь и) * І. в'їли і = Я 1 А(і) = С, вея* ¿фО. 1 а - л

їгс. следствием является утгерздонке, что :.'..чо:г.эстао всех-спектров - вынуглое и заукнутоэ .’/ног.есгво з /2 .

гандо’.-и?а:>пя- на.мнежеитне стратегий позеденая приводит к по-, гяггю з:.:е!:-л:-п-:сй стратегии. Смешанные стратегии будут играть особая рель з г.тчзе Ні при рс-іании уяиккакешаг проблемі3 .5 2 показано, что е!.‘е:\-зннм? стратеги;: ;:о дачт нових спектров, и, следовательно, при

- Ч

рси.сн;-и о'гтпм зззач оптимальной остановки достаточно ограничиваться рассмотрение;.' стратегий поведения. Чистыми стратегиям здесь ' яз.-яэтся ?.’с;.енть! первою попадания з некоторое .множество состоянии.

--I0 - ■ .

• ’

b fÎGJjLi.o.v ряде работ оцтм.:алыюс рьзешо .ищется ккеїшо в атом классе стр-атеги?.. • - . •

Сбично зад&ии оптю/аяьной остановки исслодумтся в случае по-j.o-v.rpt'.''.iAAiy платы га нзблк>;опил. В 5 '4 расспотрош ьаркакт элако-пс;. і каи.оР плати С (ДГ) • ( газеті»:, что задачи с ензкслог.еуонис!1. платоі: нокк/гакл- np>; - сьодоьии задачі! оптимальней оетаноьк/. с. аунк-ii.i; j j- , С J к задаче с кулевой ¡іуніп и^Ґ: ¡.^игрк:.^ | С, fi] ). Ге-;=улыатсг кссяедогакхя яьлкстся . • •

Тс с; 0.V3 1.5. iivcTb ^, ...,СМ- р--кіогьі_ пргдолы.мх ьегоятностс” ü плато?:«}1. для сргодических классов ,

.. .чНд,:-'aj коисксй гспи соответственно. Тогда, если для некого;ого / (û. )< 0 , то опт’.::/:;.’:tне,” стратегий? гіті: погіздаккк пр-ог.есеа .

Г*4 # •

F і.‘НС-і;ЄСГПО t-.^ ЯІІ.ТЛС1 СЯ -СО ; СС-ЛИ Ж; 0 » T0 СПТ‘:~

кальке;: стратегией является vcï/cht первого 'поиадізиия в ілюяостііо

Г - {асе Еу iT(x)=f(x) J , nj-ичс:.* пена lTiif) ксночіи и является

предслої: 1,-рк &(-*• -і пен в элдачах с kohîî ;:і:’/.онтс:.: переоценки cl . • -

' В § 5 получены соотношения, кстоі.іяж полностью определяется спсктрн случайных блужраішй ка гкогсестве |о, І, ... ,icj с іачзлсь-в точкові: lia их осноне ь 5 б предложен числ&н::ь'і: і:етод постгос-нігя по заданный спектра?.: са?..их стг.аіcn:f. іїри его.'.; кепрльзуютея г&комкческпє координаты , внедєнкке Е.5еллер-о::,

ьида. îi4= О, И, = І, ип-и.п^ л Паї- • г£е ’

________ i=f * * ‘

і = ..

Teop-ewa 1.6. Іля того, чтобь: еоктоп S бкл спектром кексто-р.оі’ стратегии X > необходимо, к достаточно, чтоб': выполнялись условия . ' ' ' , ' ‘

к: к

¿ni £; - і) <ÇZ Ôt. гс^ил- £. ; -çTc.

i~D ¿“0

В 5 7 /¡ля исследования задач оптимальней, остановки предлагается 'использовать геоуетричеекяо сзоЯстса ¿унхпии секы, при сгон, з п.1, используя гео:.'зтгичйо?йе- сообг.а^ен!!я, строится оптл!лалькоэ птазило з задаче с независимы:.*:! одинаково рзспрпделенн1’:.;! случайными набледенигкл, а а.2 к п.З предлагается простой reov.err-лчег., способ шхегьдения иск!.: з случае проаззольшх случаГных блуїданий на канонической ккалз, si а п.4 описан гєскетричсск.іГ. :.:сіод псс-т-розкия ценк а задаче с наблядазгой • последовательностью испытании Бернулли. . . ’ . .

Гланз л "Оптимальная остановка наблюдений а задачах ог.тп-кальнсго управления случайней блу-даниліа:” посвящена иссл йд осанн:: задачи оптимального управления случаЛккч блужданиям, сэязакксй с задачей нзилучиего выбора. Икеитсл последовательность -сери;! yl <и))

{ і - I, ; ] - I, 2... } шзаписй?-'Ь!х случайных величин с

одинаковой плотностью распределения. О (U), 0^11^ I . 3 пределах

{ І І ] ■

yt , осуществляется пыбор как з задаче о

секретаре, давший значения Ц* , /*’= I, 2 ... . Требуется орга-

“r(j) .

низоьать выбор та:-:, чтобы последовательность X0(.U)) = ОС. <0J .

* .

SC (и>) = Х+ } 11J .

. * j-<

цперзпо достигала нулогого значения яри :/ини;/.зльноу (либо, наоборот , !.'ак-?'/?.:зльно:.!) Mt., '

3 5 І з соответствии с геометрическими соображениями первой гл-asu г.сеглагзнтзя искать оезение отой задачи з класса not-crosHx

стратегии L і “Z.,______,"Z,. .) ¿ида, соли Z-*~ ¿=Г. v* =Х<о

^ .у»/ к

то я /С-он серн:; зг5лрз9?сп первая по номеру t пелпчкна tf. та/С fC

кая, что у. ^2^ (для задачи на кахонууы^42-); здось -

?..(«) и 0±7.-4 /, *■= £,

.-ления

C.J

Ле:.::а 2.1. ІІлотнссть распределения гибранчой согласно страт-і-

гия i” ( %., . ..,/Z„ .) величины і/ не зависит от нскета сс і

1 "~1 - <ТТ(/с)

- Y¿ т

К имеет Biyj ■

Г 4-І tf-i i-i

;.П". .аг^ач;: і:а rare,

tJ-i А'-і ¿-і

Г Н-1 N-і і-і

1(г,р-[П (<-«№£.ß (’-ЩЬ-1^\ f(p,

,mu(0-!p(pj} , Іл - ¡=да»:ср

к'А^г.у.г-улуя « Í5 2 и 3 ураьт’нг.с ¿ля оптиі.а:.ы:сгс е^едьего

v:,n-~h:'. Т (X) ^'uíJM’t ( ССО'ІіЧ'Т СТКСі;*:0 Т'ÍX': ^ ¿UpШ) - і.'.-

Luh;¡ їіу^я

г ^

j і + inj J Т(аг+ - J,

z о »•' (/ tf.j і&^о)

і * фІТЇсфх^/1

получаем следякдис утв^ч-дсічія. ■ • •

Теорєг.:а 2.1 (случ&й галіті І&І ). F-on;: Ä тйкорс, что ~г-;ї:о;:ь:я-стч;я услоьио Гг{?-ррср^ *1 ■• (cco'1'Fe.i :'і bí.b'i:í‘

¿L C*-[fX?)tyY fГІ* ¿ >• 70 CK1!VS>:M'

стратегия поведения Т*125) определяется,с по>.'си:ыо корогог, ram:-’-:

2; = -ЗГ, / = I......V-Í .

Б i>anrtov.t'pHot; случае (уЭ(у) = I, і'), атк облети пред-

стиглкю? собс.Ч кнтерьали [ Яу, û) к ^ £^, í) , г^екк-».; кот о;'к.:

- 13 -

Ь'суно нз;:т.н кз уравнений -

„ *

У\

*х

мф (±^‘)~й (?%

г.;:;:;: гу;;к:та р (у) у;:с.¿¿-с; улот”.-: р {у\ ¿¿¡¿оо :■ ■.

Лс&га Ц{уб[с, х]: р хр -- ( ) у^п ну.^, то /гсгт г~:о • ТЧ.сс-г'уа <-.£ (слу-'И: |*| ). ¡¡т'и ¡Г-» — оо

Ь'м [ Т(я) - (- т/Ь-ь с)] =0^

г;:, у}(г,у)Лу (п г^-очг- га «кс:;:.у:

'• ’ 11 С - лскгтогая постоки^-.. Г<;

эусу., {'{‘.тк бс'озна'с.-.т'ь 01.т;-.!.’эльм’« в этлчче из (ессг^.тс'’'-

гг; ;;с гакги:-у.:) пи; о:н че;.с-5 27*0= (^¡(т), . . . , 2.// ^(х))

(2 "(х)'=(2.,"(*), . / 2^6*3) ) , то ¡'.х ао>: ■;пс?::ка, как

ЛСКДЗЗКО В 5 4 И'.еет СЛРДУКЕИЙ .4 ИД. ■

Тготг.'.а ¿.3. ¡л?/. . а; —■ — »» -&*х 2 (з:)= 2 ^

2 ^ * 2 • , г,т; 2 ,2 •рп/'едапеш; соотротствсшо

ссотьо^енкл?::;

<

I I

Ъ '

У-1

<чЖ, (г^Н^р 'гчдч

О V* ■ ' /

лЛ*/

■ - 14 - ,

' n • ■

Б § 5 отвечается монотонность оптимальных порогов 2 {X ) и

W • ' - “ -- ' ' .

2 [X ) в любой точке Х<0 ' -

4#ï*;* V*;(*)*'...*' zt(ХК

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

В глааэу П! я ТУ задач:: оптимальной останоаги исследуются 2 кин;:;.:аксноГ; постановке. Изменение критерия влечет изменение' структуры решения. SaveTnv, что возникащие здесь уиниг.-акснко задачи •■îojfjrîo исследовать с псиос.и теор-етикс-йгросых методой. Сдкако,

• зиачптельнъ-е предЕнггеш-.я удается получить,.приуекля кстоды спти-. кальноГ;-остановки..' •

. Глаиа С "Аналитические t-.етоды -ресения игровех задач на г.рап;:-. ло остановки" посЕясцзна исследованию игровых задач, в которой за. дачей игреков является остановить процесс сеоих наблюдений на зна-чекии больхек, чем у противника. В § I предлагается ь'етод сяс-дення так1*х игр к яекотсроГ: специальной задаче оптимально»! останов:-:;:. Используя этот принцип, а ?ак»е разработанные в главе I гео.*.:егр>> ческие методы нахождения йункиии иены, удается рошть сернз игровых задач для различных наблсдаюа^с процессов. 3 § 2 регона.игровая задача Г’(Û4,ffz) двух лин,. когда их наблюдения представляют

еи:а:зтркчные «угучайные блут.дан:;я. *

-1-1 • - Л-(° W

Teopc.va G.I.. асли (uJ) - снгиетричныо случг^нне

блуудания на шо:;естве Е'= |о, I, ..., icj , кз';;:нал::;;-сся з состояниях Я/ и Яд"»- псглсцаЕтлеся б состояниях О, К , то значение кгрц Г {ût,ûi) реви о H - i' Qi- Ûjl)/

.353 каГ-дено режэгаю .игра.: ^.аля нсепг.иетричк:;* случайных блуядани/. цок ото-,: используется гес:.етр..:чэс::'лй i.-етод псст-рог.пйя i:e.;ai с канонических координсГгах, кр.едлохе;й!ь:й з глиге I. Од:ш ко полученгы:: г.иесь результатов тако.’1. Пусть Л^(и) ), .

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

- 15 -

а) . —

Т №)) - схучайже блузданвя ка vnc'secTES h.

І-ИЯХ Of И Ûi У. ПОГЛОЗСНХСК S СОСТОЯНИЯХ' 0 Iі- К , У <^ 'Р ~ ъс~ рскгносту. пг.со/.о/.а в пюбп' гостокяег.о к бп.глно и с/ ~^>p<i Tcoj-t-v.î r.cji’i: п,чя кеко^іг-ого релого uucsi М такого, ч-о 0& ÍH ú(K-l)/z » вьпо'.гі я^тся :'слое:;я

,аг к гм+л ,• ,,

0“ ~ ^ > с/ ' с/ é о/ )/(^¿),

Ечччс-;е :,г: и Г (Я, ,a¿)

н'=-

О-О(ЛсЛ)

w „ .

гкт.. п S ’-íb oí:';Mu'/ crí-aven:?. ггрокс? і.и -і er;v.v:o-

а с

;eco?; : с:, с :

Cri)

■ .tm+l , к ,к+і 1+ol - J -dl

0,i- їм.*-*, к-iу f+ t/ - с/ - с/

, ДЯ7К . л . к-н 4+ ci — с/ — oí

/ - Ar

Л»<,2 .

3 5 4 .-случено іекенис игры Л <0, С) для послс^сва?слы1оз-

теП иепчтвниЛ Беркулди с вероятностью успеха р . При онемении иг-

гсисг заp.-.rvA V oa;.-j4¡»' ситккально? останопки используется •■ансг.:-;-' .. к п

ЧЄСКИО KOOJ ДККЙТЦ ií J =.-1, «я =. (í ~р )/р , tl&Qj и гегл'РТ-

•риюекке ci-oíicra-* сена, ра?работан:пде в гл.ас>о I.

• Дия НГТО~р:.ГГО нг.борз г&якх- чисел D*i,¿l 4. <. i í Аг-і

- * f t- ••■ m

обозначим

ч

I,..-I

;

I ~(-i)(-0 Uit j-o,nL A-2ZZ- 7

Teopcra 1.7. Euäk p гакое, что для в-іех / = 0,[(nt-O/zl п-мсігі-яістол услсп::я -

if+i її 2.ÜZ. І. + 22І. .-м.

о ¡ tí* і

. 40á .2/__. 1 _

.«чг

-2U. +&.

‘¿¿♦і. Lî.lH

то с;

;;ті'.~алькк:.;и в игр s /""* (0,

(0, 0) ярляпїся ev-вей- стратегий , '

предписыва-с^их прекращать наблюдения на tv -сг: іаге, вида

0 ft “і« , і,, , -

; 1 » ✓ М ; .

г ґ L 1=0 1=/+і /

.ñ-U^-tLf A], п-77£7~7 ,,

¿»4>і î=æ^î J' j ' ' J '

В последу сцих 'двух параграфах найдено рссекае для случая процессов с кепрер-кэкым ї.нс-зггьом состояний.. В §. 5 решена игровая сідача, определенная і:а п;'.нероьзккх: процессах и значение пгр-ы полу ч-ю-тся та:-:ое ;ss, как в тєссеї.е 3.1 ;; б § 6 ребека ;трозая задача

для кокс-чкой совокупности незарискгагх сдонакоьо гзс;;;'д-.:.

кепр-егцьно.'' .? ••ккг.кеГ: гаеп'.сдс.мки.1: F* <af)-Hûj£* '•••••чвГкул r.-.v.i"-

.U™t~ï3).lT”t-ï>>]. '

Ttc: u;.<3 Ó.V. Са?.5»-а.чьптк стратеги*!/« ¡-.г; с: .r-,¡;c

стсатгг.:::, одгсдолсшп/е с псишьк» пекогон Z, , ..., Zj/ц , г,”-'

[ Г(г,- • С-С’Н/е ст.ст¿ / : а

У-7 ‘ Ы-1

П

С—- 'I Z.Ñ~2 )+Z П Z.Z -I

i~i j=, J{ ¿., ‘ N-i '

■ Ы-l *-i

i .*■ 7 - P *.

%¡ " s'«> tc=i*( J“i J

‘íii~‘l + ~2.----------------------------:------------ > Lí=l,d-i

‘-{ * Z v-i к-1 •

: 1 + ZZ! /7.2.

- ... _ fc-i+i j*£ J

Б случае tí. = '¿ наСлгдрни:" скстеул 'прсдставляс-" осt'c-Г: одчо урясн/няе для спредолеикя* единственного noj ora 2* : Z4*Z1"im0. Ero реиокне - "зслстоо" сечение интервала [_U, i].

i аср аСстаи;:"!: a 5 I- Гц инют сведская :irj> такого типа к зада чау епт^/ально.” остановка работает к в игренл задача:: Г(аг .. CL ) с нрсксльгс'ик участн/га-;:.. его показано в 5 7 к энтек ь 5 Ь га-'Тч.-я nc.'ii-’oc релизе ^г;и Гщ-,аL ,д3 ) для. cK:/>^Tj.'!;4S'.)r:-; случа

¡’fi блукдек'/Г: ка i*kot<sct¡s* Е ~ ( 0,1,..., •f) •

В глине 1У "С гг, ):«.'чльн::; стратегии - в динатачсских играх на ■¡рагнло ccvafcCbKü" у.сслс.руетог г'кнк’.'.экскк'П гарант задач;-, упрп".. егсго случ-./ксго Oiyyviíü’Kn, которая гарспмггркмяаеь » глат П.

Г асск атукваса с я ^»¡чикиеская игра Г ,р ) ся-.’дугд^го г;т

Пу.едпслс*:!:»!, что из течек ,X¿ на отражательной полуоси гкхед. дэз объекта и начйраг? двигаться случаккьь.'.и. скачка? и и оторочу !:у лг.. 2г;;;;ч1;!;а, на-которую двигается какдкЛ сотрет, спрбпсгя'.'с?.«

таквс, как в главе П. Выигрывает тот из игроков, чеГ: объект пгроьм церсссчет нуль. Такие игры- можно т^ак'ш^дт.ь-га^.хонкя под саг,у сем со случаем: ветрен*. . .

Tarso, как и в главе П,' оснспяуа соль здесь играют стратегии порогового Ек.па. Согласно тесрсгс Носа, реыенис mosst получиться б cvccrfx этих стратегий. Ксслздуя уравнение для значения така": игры . • '

ь}МН(*'+у(* *а+2”)лг^о,*л<о,. ч г*

с иепользосаикеи доказанной в § I в ле?л:е 4.1 непрсрывностьо функции Й (ЗГ,, 2^) в области ЗГ1<0 ъЭ&О, удается показать в § 2, что оптимальными здесь являются чистке стратегии (теорема 4.1). _

. В § 3 ка?дскы оптимальные стратегии игроков, когда йяугдаания находятся в окрестности нуля. ‘ - ■ . .

Теорека '4.2. Существует такая окрестность пуля : jb * Х1л ОС^О, где оптимальные стратегии игроков I и И 1:г.:еют еид и • В paEHCí.'.spHOH случае

найдено аналитическое внразеиие для значения игра |-|( Ж», 2* ) в . этой области. ■

Teopei'a 4.3. Решение уравнения для W (3ff в области ш/еет вид «

Н(*,л)=

j=0

Л в § 4 исследован случай, когда блуждание од::ого яз кгрокоз находится близко, а другого далеко от нуля. ■

. Теорека 4.4. При ОС^-*.— оо оптимальная стратегия игрока I

олт.р^еляется порогаї-'Л Z¿ O

■ Б последней главе У "Численні,'о kctojih ро&екяя задач оптимальной сстаноьки" представлені! числеикие готсдн, разработанное длп дазепхя задач оптимальной остаковк;; к с ток числе, для ¿-еиот.:?! кг-і'суух задач, которна положень: в осисву пикета пр-ккладнкх ш crvavu "Сстаноька", находящегося в щшогендо. В § І описан г.;.;іниі'я цро-сускз наблюден!:;“ в задачах оптимальной остакогки, что псзпслясг в ряде прикладних ьадач значительно увеличить пкип (лп nja оет.г!х:::;г-.

3 ÇÇ с и 3 для тгетсния иггосгіх за.сач Г ( ¿7,,ЯХ) « Г (Of........................ûf/)

/ifí 3, с наблюдения:.';;,- случзПка'к б.’.о"чдажя}.-и на тс-еотае £Г - [и, I, ..., »с] предлагается использовать методы лиіісіїного nj;огі-аітііі.-оьак;їя. . . •

Теорега 5.1. і.гУіоз оптимальное pezeuxs задали «мерного дрог-•^¡.гі-гован;:.'! ' . j

. ,------------------ /

nun ----- « í V, ■*■ ß>.

іжі ' r

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

к Ы (т)

ÇZLZ. Л(р *

* (O . —

ZZZs ,-CAf

7*ö J

< СО со (i) . ---

j-o J J *

.fO ______ . —

¿. &o, j=0,k, t =

¿i 9 fi^-° t ______________1 Г *

(СО ---------1 г ■ .

где l'il і=0ІС| - канонические кооідлнатк дтя случаи .ного

ску'кдания Х^, í - 4jN , дает спектры, огугиуалькых стратеги? в кгі'озоГ: задаче- Г* (ÿ|( пг.к огсм^ найгйньаее значс-нле

сгункнионалз ранно 0. _ ' ■

Гля преизбольнсго случая а 5 4 для пс;:с:-:а с::туап:и гасноиесия a кгр-осих задачах предлагается кодаіикаїзщ итер-атинноґ. процедуры ■ Ь/а^на-гобинссн. 3 5 5 приведены результаты чксленасго кодьлироза-н:;= а здача оп7к."зльного управления случа/кта блуядаиием и блиахоЛ к ней г.с духу задачи динамического распределения паї-.кгн. сБ.'-í. 3 § б І;. скгйчальшгс риска в задаче срокз ка гипотез paccsayj;;:за-

стоя как íyi-.^Lii:." от гитрицк плате^еГ. Гля Нее гтаактся нййкслыо сЕСтр.й^алькгл: -оадач ir* уно^ейтвэ таках vat г иг. к предлагается чке-і:с-тод рссіоьак. . ' .

В грптгкєн;;;: находится' cu/.caiy'.e пакета -прккладпчх прог; а:.:х "ОотаксБка". ilpor.^awii капийакы і-.а язаке Фортран а предназначены для OEM серии 1ÍZ. -

Ст.ногіу-’о т^зультатм дкссег.ту:::и опуб.-.икоЕана а еде-г'-тг'лу гз-бстях:

1. :.!аэалоз В.5. Исследование уравнения для оптпг.альксгс рис-, ка. - В кн.: Вопроси механики-и проїтесссв управления. Еітп.2. Управление динаулческиуи систекаї.:-.!. - Л.: ÜFS , 1579. - c.I£S-I-:.5.

2. Ыазатсэ З.В.. С'птиуальш? р>Лк и :.-атр”і!а платежей. - 3 кк.: Вопроси vexftHssca и процессов управления. Вып.4. ¿¡атекагкческий анализ управляемых процессов. X.: .Jifi , îîbl. - c.I6C-Ic9.

ііазалов 3.3. Об кграх, определенных і;а чуйка?.- кгзззасшагх одинаково распределениях -случайккх величин. - 3 к.ч.: Ветвящиеся- \ процессы. - Петрозаводск: Кі АН СССР, 19cl. - с.ЗС-¿Б. -

4. їяз&яов D.3.-, Сскслоз А.3. Ос сягагалькск: дхкыгйческом распределении нестраничной иауяти. - В кн.: Аатсюгскзцроват» сисіекм управления. Вып.З. - Харьков: XAIi, IScI. - с.32-33.

5. ¡«asa-noB 3.B. C6 onTMMa-ibHCw ynrah.ic-Hi'.n iirjcruvi: c^y^rim-: r;cc."e^oKi7eihi-:ocTHV’/. - 3 ru.: l£:niu:a£HKe oa,iami Teo.p:n yni'aB.T.]

- 2.: JIF„-, Kf£. - c. 175-163.

6. ;..2rs.r!0!< B.3. /Irponas 33^s>ia ocTanoBFH cjiytja?>-:':x (¡.’■.¡wflavvA*.

- B KJI.: B'JJ‘.C.'!rKOCTH!X’ I/CTCiU 3 .CliOKOCTHOl": l’3TC’’3TliKC /TCar.OLT ¿CXS.

I SmccotskoS kohI-. iier.cosasopcK: Ki AH CCCr, ICf-.i. - c.^7.

7. '.laasu&ce 3.B. i'lrror.i.yj v.apyoncKsie ¡.:c::c>;th. - B hh. : Be; c.tt-

Hocrnue sapwn nr;;K-:api!o.'i i-arevarMKM. - Eerpooar-o.noK: Hr.-, KC/.. -t-.C:-;-oc.'. . ' . .

■ c. Lasr.;icp 3.B. V.rpj. ha cjiynafH^x - 3 kh. : Bj-Ou-

TPOI'eTilWSCKC^ KIlCsr.HCTirKi! Ae3KC!.I £OKJ!..’>Ii BcCC0K)3H0K KO!!7, -

¡¡¿k^tck: VpTj, - c.71-72. . ■

i - :..;*n;i.rx« 3.E. Solution of .the gsae'a problem of optimal stop for .the Bernoulli schene. _ tj kh. : ilcr.E^r. Bcc;::!nH'.!3 KOHr^scc 06-DfcTBa i.'a7c-!-aTvnjocKO? CTaTKCTiijni H Teot.JiH set-OHTHOCTefl KV.Bej:iQJE-.ik. - i.'.: Hayh-a, liio. - .o.cSo. '

I0..'.>.sa”O3 B.B. MrposHe :.'0!.'e};TM ccTaHOBtrK. - HoEcciifiiipcK: Kayi:a, IHi7. - IfcS c. ■

il- Ktzalov V.V. Races with rcndoa »djid.- Mathematical Kethoda in Operation Research (abstracts of Int. Conference).-Sofia: Inst, of Math, vith Computer Centre, 1987.- P* 63-

I2.5yHH::«eHKO C.B., 'J.iszjicb B.B. Krrn i:a nr.aEii.io 0C7£H0B«ni tr.nej osckkx n,f creccoB. •- TfcOj.-;u? ecpojttiioctc/; m eo npKh'cnpHae. t.XXal:, b.B, IifG. - c.550-591.

’ Io.’.:a:.a.7CB B.B. C hrkotoi-ux reowevj K'iecKirx i'CTO,nay r premia Ea^a'-i H3 nj.'ar,:-!.”.o octohcug!. - 3 kh.: Bonpoeu onTK.vaxb.Horo ynraivTe-H'.'.n a V.c2z9ficza'.-.KH cn;;na!n:?.. - ilrjryrci:: i'ipr.>, Iff,?. - c.l7,0-lZb.

V, .Bi'Kw+Tnvo C.B., .Vaaazos B.B. -0(5 cnTK’a.ifeBcv yn^njRHra nnci'eocc:.; toccTaiiCi’-HiiKH. - 3 km.: Ber/C.ii’Hocrn-uc re?cp: s :.kt ;-.t-* - • iic'i j.c7ti.-a7K!:o / T?3ncu forx.ii b'jecosnnoS !-:o;:cf. - ¡¿eTrc3?.F:0,-.jK:

ES АН СССР» IS88* - С.23-24. - - _ .

15. Ваяшгааняо С.В., ‘¿азалов В.В. Игра на правило оотапов-кг последовательности наблаг,ея:й {шетроваапоЗ ¡даш. - Кибер-нетака, Я Г, IS89. - с.119-121.

■ 16. Кузда В. 5., Мазалов В.В., Кузлыа JL.A. Об «шкальной

переналадка процесса переработка руса. — В ki. : Лоппеское уи-рахлзняз с кспальзовашкм ЗШ (тезисы докл. XI Есесоазпого спзозмула. — : !.1ГЛ, IS88. - с.376-377.

17. Кузина JÎ.A., Мазалов В.З. "отолд оЗнарузе.тая разладга

в задачах упраалэнпя- продессоы переработка pyjji. — В ка.: Уо-толд ккберяетгкз х^ппщ-технологэтесгах процессов (тезясы докл. И БсесоззяоЗ EOîiiï. ). iüT.i, IS89. - с. 118.

18. г.'азалов.З.З. Экология и проблем: оптаалькай остазов-кя. - В ЕЯ.: Улте:,'лткчесглэ :,:агод1 рационального прироцополв-зоваяля. - Новосибирск: Наука, I9S0. - с.115-125.