Содержание к диссертации
Введение
1 Теория поиска-одна из основных моделей исследования операции
2 Ступени развития математических моделей поиска .
3 Статические модели поиска
4. Динамические модели поиска неподвижного.
5»Динамические модели поиска движущегося объекта . 34
6.Моделирование процесса поиска на ЦВМ
7 Игровые постановки задач поиске . 36
Выводы
ГЛАВА 2. Модели поиска движущегося обтектэ.Критерии опти мизации.Вероятность обнаружения объекта к заданному моменту времени . 43
1.Основная модель поиска движущегося обїекта.Критерии оптимизации : -Н
2. Развертка процесса поиска во времени
3.Вероятность обнаружения обтектз к заданному моменту времени W:
Рекуррентное соотношение для определения оптимальной стратегии поиска S/
Пример определения оптимальной стратегии для одной частной постановки задачи .
Выводы
ПАВА 3. Некоторые критерии оптимизации при неограниченной длительности поиска . 69
1.Вероятность обнаружения объекта . ff
2 Максилалвная скорость сходимости вероятности обнаиужения
3.Мунимум математического ожидания времени поиска,необходимый для обнаиужения объекта . У$
4.Пример определения оптиоальной стратегии
Вввоыы,... 73
ГЛАВА Вероятность обнаиужения движущегося объекта при бесконечной длительности поиска 80
. Вероятность обнаружения при максимальном собственном числе равном единице
Заключение.
Приложения.. 69
Рикунки 69
Лтеатртурэ
- Динамические модели поиска неподвижного.
- Развертка процесса поиска во времени
- Максилалвная скорость сходимости вероятности обнаиужения
- Вероятность обнаружения при максимальном собственном числе равном единице
Динамические модели поиска неподвижного.
В статических моделях поиска информация об объекте задается один раз и не изменяется. Вероятность обнаружения объекта в точке при условии,что он там находится,есть функция плотности поисковых усилий в этой точке и от времени не зависит. Ретение задачи оптимального распределения средств поиска-это одноразовый выбор распр! деления средств. Оно принимается за один шаг. Поэтому статическая задача поиска-это задача математического программирования.
Параллельно с углублением первоначальной математической модели происходило создание существенно новых моделей поиска,учитывающих возможность распределения сил и средств не только в пространстве, но и во времени.В этом случае одноразовое решение непригодно. процесс покска развивается,решение должно бтть принято на определенный отрезок врнмени гпедед. Зачача оптииизации становится динамической.
Неподвижного объекта подвижным наблюдателем представлены боиьшим количеством работ. Для сымых первых моделей / 24 /,/ 19 / ,/ 25 /хзрактрено дискретное представление проатран CTBа и Вреиени.
В дальнейшем блли развиты модели покска с дискретным и счытным мнооеством состояний объекта и непрерывным временлм,модели покска с непрерывным временем и непрерывным множеством состояний объекта Обзор моделей мы будем ветти в последовательности,которая орре деляется степенью слотности толкования фанта обнаружения.
В первую очередь рассмотрим такие мод,ли,в коыорых пиинята детермиаированная модель обнаружения. Считается,что объект можно обнаружить тодда и тоолько тогдадкогда выполняется ряд услойий: 1 Объект находится там,где его ищут; 2.На поиск затрачена заданная условием задачи сммма средств. Сукъект не знает,какая из этих ситиаций перед ним Но ему извнстны их априорные вероятности. Учитывается ненулевое время,необходимое НЇ переход от одной ситуации к другой, Бооьшое распространение получили модели покска неисправностей в сложных технических устройствах Известны априорное распределение вероятностей местонахождения единственной неисправности ірЛ и время,затрачиваемое на осмотр і -го блока устройства t (всего блоков Уі ).Требуется минимизировать среднее время поиснэ.Решение заключается в просмотре ячеек в порядке убывания отношения Pi А. .
Обобщенная модель дана Глассом / 22 /. Он рассмотрел модели поиска неисправностей в комплексной системе,состоящей из J/ блоков, содержащих a(I),a(2),...i i -( J )деталей или узлов. Предлагается процедура поиска неисправностей,минимизирующие время,затра чиваемое на поиск.Первая модель отражает такую процедуру проверки когда разрешается производить испытания работы каадого блока в целом и испытания отдельных узлов и деталей блока Вторая модель поиска неисправностей в системе построена для такого случая,когда разрешено испытание только отдельных узлов и деталей блока,а за переход от одного блока к другому приходится жертвовать временем на сборку предыдущего и разбор следующего»
В следующей своей работе по теории поиска Гласе также рассмотрел модель поиска,учитывающую ограничения на передвижение субтект которые выражаются временем перехода из одного района осматриваемой области в другой / 23 /. Эта модель носит более общий характер.Дано априорное дискретное распределение вероятностей местоположения объекта по ячейкам р , p j . . . , ,и стоимость осмоТ ра этих ячеек
Развертка процесса поиска во времени
Цикл работ В.И.Аркива / 39-41 /посвящен динамическим моделям поиска неподвижного обтектэ. Приводятся решения большого числа экстремальных задач,связанных с нахождением оптимальных и Є -оптимальных стратегий для минимизации среднего времени поискэ и максимизации вероятности обнаружения н заданному моменту времени. три модели
Модель поиска с дискретным и счетным множеством состояний и дискретным Бременем.Эта модель предусматривает возможность направлю ния поисковых усилий одновременно в несколько ячеек.Вероятность обнаружения точки за время . "С в каждой из них при условии,что точка находится в этой ячейке,есть я в .,где с 0 и О, если точка отсутствует в этой ячейке;К-число одновременно осматриЕЗі мых ячеек. Стратегия поиска есть правило,которое в любой момент времени t устанавливает в каких ячейках должен производиться поиск.Стратегия поиска задается набором функций... где х{_ 1т) =1,ерли "в момент х поиск ведется в противном случае лЕсли процесс поискэ обрывается в момент времени Т,то соответствующая стратегия х- называется Т-урезанной Каждой стратегии т соответствует функционал РСту/ -вероятность обнаружения точки за время Т при стратегии т .Стратегия Ч3 называется равномерно оптмм8льной;если ее любая Т-уреззнзвнэя стратегия оптимальна,Указан явный ЕИД стратегии J „Показано, что J оптимальна и в смысле минимума математического ожидания времени пойбна до обнаружения,Приводится алгоритм реализации равномерно оптимальной стратегии,Рассмотренная задвча обобщает результаты, полученные в /14 /,и /25 /.
Э.Шдель поиска с дискретным множеством состояний и с непрерывным временем,Полученные необходимые условия экстремума формулируются в виде некоторой вариационной задачи,связанной с максимизацией негладкого функционэла,зэдзнного интегралом Лебега-Стильтеез. Функции Si-L{ t )предполагаются выпуклыми.Поставленная в /40 / задача допускает обобщение в следующих направлениях,
Пусть обтект исчезает из і -ой ячейки через случайные промежу! ки времени г ь с функцией распределения R- ( z ).Требуется найти стратегию,максимизирующую вероятность нахождения объекта,
Б.Пусть объект появляется в і -ой ячейке с вероятностью pi через случайное время - с функцией распределения u ( t ),Требуется максимизировать вероятность .нахождения объекта за время Т. Показано,что задачи подобного типа укладываются в схему принципа максимума.Б задачах типа Б представлены некоторые другие функцш налы,з именно:вероятностьобнаружения объекта за время,не превосходящее заданного с момента его появления и математическое ожидание времени запаздывания решения"обтент естъ"от момента появления объекта.Постановка задачи Б перекликается с постановками даннымив Кузнецовым результаты отличаются большей общностью.
.Модели поиска с непрерывным множеством состояний и непрерывны] временем.Положение обтекта в п. -мерном пространстве R- хэрэкт ризуется плотностью априорного распределения ( х )-і ( г) — 25 В момент t =0 начинается процесс поиска,целью которого является определение положения объекта.Поиск ведется-за счет использования некоторого источника энергии единичной мощности,которою можно в каждый момент іремени t распределить по пространству К/1 е плотно стью
Мы считэем,что плотность энергии,пришедшейся -на точку.х в интервале времени ,характеризуется величиной (рекете. Если объект находится в точке х,то значение ,необходимое для его обнаружения,является случайной величиной с заданной функцией распределения П( а , эе, ),измеримой по совокупности переменных почти для всех .Стратегия поиска есть правило,кото рое для любой точки х Е моменте Г устанавливает значение функции Критерий оптимизации прежние;уі доказательство существования и характеризэция оптимальной стратегии сводится к решению вариационной задачи,обобщающей лемму Неймана-Пирсона на случай нелинейного функционала.
Максилалвная скорость сходимости вероятности обнаиужения
Дадим некоторые цифры,иллюстрирующие развитие математических моделей поиска неподвижного объекта, Были выделены два этапа в их развитии. Первый этап охватывает период с 1944 г,по 1959 год.За этот период было опубликовано около 15 работ,посвященных статическим моделям поиска. Эти исследования подготовили появление динамических моделей. В последующие десять лет происходит развитие динамических моделей. Число публикаций,приходящихся на один год,к середине 60-х годов достигает наивысшего уровня,а к концу-заметно стихает. Этот период отмечен увеличением общего количества публикаций до ста. Значительный количественный рост привел в конце 60-х годов к существенным качественным изменениям модели. Подготовленные логикой развития теории поиска и вызванные к жизни запросами практики,к 70-му году появляются первые работы по теори одностороннего поиска движущегося объекта,
Динамические модели одностороннего поиска движущегося объекта Исследования математических моделей поиска неподвижного объекте подготовили подтем теории поиска на качественно новую степень-создание моделей поиска движущегося объекта. Предположена о неподвижности объекта может следовать из существа задачи,как, например при изучении процесса поиска неисправного элемента.Это предположение может вводиться для упрощения модели. Тогда оговари \0 боуил,ег-о ги?иск бел и ко по сравнению соскоростью ооиж&ния Бается,что скорость движенйяУЬбъента и объект можно считать непод
Известна работа Купмана / 2 /,в которой рассмотрен поиск движущегося объекта для случая,когда наблюдателю ИЗЕЄСТНН скорост: и направление движения объекта,а координаты объекта в начальный момент времени заданы вероятностными распределениями. Показано, каким образоы?используя относительное движение задача сводится к задаче поиска неподвижного объекта.
Задача поиска наполняется новым математическим содержанием, когда движение объекта поиска точно не известно наблюдателю. Модель движения объекта представляет самостоятельный интеоес.Вероят-но,что именно трудности,связанные с моделированием движения объекта,явились причиной позднего появления новой модели поиска.
Здесь мы рассмотрим модели ситуации,состоящей в поиске движущегося пассивного (т.е.не располагающего информацией о субъекте,ве ... душем поиск)объектз.
Клейном были опубликованы заметки о возможном подхо-де к построению модели поиска подвижного объекта. Процесс поиска представляется как процесс движения ведущего поиск,обследующего в каждой момент времени один из п районов. Ведущий поиск располагав бюджетом,состоящим из конечного числа единицей системой обнаружена -32 эффентивность которой определяется районом поиска и количеством поисковых средств,затраченных на поиск-в зтом районе Учитывзютея затраты ведущего поиск на переходы из одного района Б: другой.Цель получает информацию о движений наблюдателя,Не это и информации ос новывается стратегия уклонения цели.Предложены два варианта моделі процесса поиска и указаны возможные подходы к решению поставлений: задач.Модель Клейна нельзя формально причислить к игровым йоделя однако,в ней содержатся некоторые теоретико-игровые элементы[5б1. Задача,которую поставил и решил для некоторых частных случаев Поллок/57 /„существенно отличается от задачи Клейна.Марковский процесс движения объекта определяется только его собственным мест положением,Время дискретно.Обтект может находиться Б одном из двух ящиков.Б начальный момент времени объект с вероятностью ЗҐ находится в первом ящике и с вероятностью L- -во втором- ящике Объект перескакивает из одного ящика в другой согласно Марковской переходной матрице,
Вероятность обнаружения при максимальном собственном числе равном единице
Построение математической модели начинается с выбора и формули ровки определяющих физических характеристик,т.е.с воссоздания физической модели поиска. При этом неизбежно приходится опираться на конкретные физические представления об обїектах,чтобы иыеть во можноеть уверенно судить об их свойствах и сравнительной важности этих свойств в данной задаче. Рассмотрим следующее описание еитує ции поиска.
Объект поиска перемещается в ограниченной области. Субъект рас полагает некоторым количеством источников энергии,с помощью кото-рыхпосматрйЕ8ет"область. Пусть зто будут,нзпример,стацион8рные источники световой энергии. Для проведения поиска субїект делит область на ряд подобластей,число которых равно числу источников энергии»и в каждую из них помещает один источник. Источников эне? гии достаточно для того,чтобы считать,что в каждый момент времени объект находится в одной Й ТОЛЬКО в одной подобласти. Движение обтента-это случайный дрейф,состоящий в том,что в случайные момек ты времени объект может перемещаться из одной подобласти в любую другую подобласть.Размерами объекта по сравнению с размерами подобласти можно пренебречь и принять его за точку.
Количество энергии,распространяемой всеми источниками в единицу воемени ограничено. Эту энергию субъект может произвольно распределить по источникам.Перераспределение энергии производится мгновенно.Каждый источник освещает подобласть равномерно.Подобласти изолированы друг от друга тан,что потоки лучистой энергии от рази источников не суммируются,
Если в некоторый момент Бремени объект находится Б освещенной подобласти,то,вообще говоря,необязательно он будет обнаружен даже, если Б подобласти сосредоточена вся выделенная в этот момент времени энергия. У субъекта может появиться лишь ощущение неопределенности, когд8 он не сможет ни утверждать,что объект находится в этой подобласти,ни отрицать этого /М/«
В качестве меры эффективности осмотра подобласти выбрана условная вероятность обнаружения объекта,
Пусть имеется конечное число ячеек,занумерованных числами 1,2... iru .По ячейкам перемещается объект,который требуется нейти.Время дискретно. Процесс движения объекта представлен неоднородной цепью Маркова. Матрица переходов A-Aft).
В каждый момент времени на поиск объекта выделяется сумма средств с ( t ),которая распределяется по ячейкам где СІ (і)-зто доля средств поисна,попзвпшх в і -ую ячейку. Если объект находится в і -ой ячейке,то вероятность обнаружить его там есть а (і ) = cj_ -(/t, c Ct)) . Результат наблюдения определяется вектором
Введем вектор который характеризует вероятностное распределение местоположения объекта в каждый момент времени,. Поиск заканчивается,когда объект обнаружен Поставлены следующие задачи»
1.Пусть длительность процесса поиска ограничена. Найти распределение средств поиска,доставляющее максимум вероятности обнаружения объекта к заданному моменту времени»
2.В том случае,когда время поиска бесконечно,исследовать вопрос о возможности достижения вероятности обнаружения равной единице. Выявить условия,при которых существует такая возможность»
3.Найти распределения средств поиска,доставдякщие -максимум скорости возрастания вероятности обнаружения; -минимум математического ожидания времени поиска,необходимый для обнаружения объекта»
Пусть поиск начинается в момент времени т0 . Если время поис ка ограничено,например» Т единицами дискретного времени,то зада ние отрезка времени
К - номер осмотра по порядку .Области изменения функций c(t) oft) 7.A(t)B о-бщвм случае зависят от времени. Найдем вероятность обнаружения объекта за время I ,если поиск начинается в момент времени
