Введение к работе
Актуальность темы. Математическая теория поиска является широко разветвленной, богатой результатами и приложениями областью прикладной математики. Первоначально теория поиска развивалась преимущественно для военных целей, но в последствии выяснилось, что методы этой теории могут' с успехом применяться при исследовании многочисленных проблем производства, в вопросах экономики, экологии, медицины, спорта, нрава, техники и бизнеса. Большой вклад в развитие теории поиска был внесен в работах Альсведе и Вегенера, Бека, Брауна, Купмана, Сартскало, Стоуна и Хеллмана. Среди поисковых задач особое место занимают:
(а) задачи поиска объекта, активно противодействующего обнаружению (например, при поиске подводной лодки противника, при построении системы защиты, предотвращающей проникновение террористов на охраняемые объехты, при патрулировании границ, в борьбе с контрабандой, промышленным пшионажом, в рыбной промысле и т.д.)
(Ь)" задачи поиска в условиях конкурентной борьбы (например,
при поиске нефтяных месторождений и других полезных ископае
мых конкурирующими фирмами, при планировании схем операций
в экономическом нападении, рекламной компании, торговли, бизне
се и т.д.) '
Математическое моделирование таких задач осуществляется метода
ми теории игр, что позволяет найти оптимальные стратегии позодения
конкурирующих сторон. Теорию игр поиска можно классифицировать
по самым разным признакам. Одна из таких классификаций основана
на противопоставлении статических я .ач динамическим, в которых
процесс поиска сводится к некоторому единичному акту. В дншшиче-
сккх же задачах процесі поиска состоит из последовательности (может быть, бесконечной) Шагов поиска и кроие того, сам объект поиска ьиь жет обладать некоторыми динамическими возможностями. Статические задачи рассматриваются методами классической теории игр. Значительный интерес и развитие динамические игры поиска получили после выхода в свет книги Айзекса "Дифференциальные игры". Отметим, что динамические игры поиска тесно связаны с одним из разделов теории дифференциальных игр, а именно, теорией дифференциальных игр с неполной информацией. Большой віуад в развитие теории игр с неполной информацией был внесен в.работах Алперна, Бостона н Востока, Воробьева, Гала, Карлина, Красовского А.Н., Красовского Н.Н., Куна, Куржанского, Ли, Мззалова, Малафеева, Меиикяна, Никольского, Петросяна, Ракла, Сакагучи, Слобожанина, Томского, Черноусько, Чнкряя. Также та играм поиска отметим работы Аугера, Вошбурна, Зеликина, Зенкевича, Дуценко, Петрова, Петросяна, Скитовича, Субел-мана. Развитие теории дифференциальйых игр с неполной информацией стимулировало исследование динамических теоретика - игровых моделей поиска и обнаружения подвижного объекта. В конце 70-х годов в работах Гала было построено решение модельной задачи ("принцесса и чудовище") подвижного объекта, осуществляющего простое движение. В последствии эти работы легли в основу его монографии "Игры поиска." Наиболее систематически теоретико - игровой подход к задачам поиска, впервые, в России был отражен в монографии Петросяна Зенкевича "Оптимальный поиск в условиях конфликта.'' В настояща время, в связи с многообразным спектром проблем, моделируемых по средством игр поиска, одной из наиболее актуальных задач являете создание н дальнейнее развитие методой решения проблем и задач я играм поиска, нахождение оптимального поведения участников в моді лируемых конфликтных ситуациях.
Цель данной работы. Развитие оригинальных методов решения игровых задач, моделирующих процесс поиска, и решение рада известных, но нерешенных до сих пор проблем теории игр поиска.
і Научная новизна. Рассматриваемые в диссертации математические модели поиска могут быть аппроксимированы конечными играми, либо сведены к ним, что в принципе позволяет найти приближенные оптимальные стратегии игроков, используя симплекс метод линейного программирования. Однако, огромная размерность аппроксимиру- ющих конечных игр не позволяет осуществить это практически. Созданные в диссертации оригинальные методы и новые подходы к исследованию целого ряда нерешенных до сих пор проблем и задач-поиска, позволили их успешно решить. А также, для достижения этого, в диссертадии были обобщены некоторые методы теории игр поиска. В частности,
-
Для решения задач по защите объекта, предложенных. Ай-зексом, моделируемых дискретными алтагонистичесхими играми с запаздывапнем информации, разработан подход, позволяющий .расширить класс решения этих задач на случай игры па плоскости, и на случай, когда вероятность поражения проникающего игрока зависит от расстояния между его местоположением и точкой "взрыва". Начдсны оптимальные стратегии поведения игроков и рекуррентные формулы для определения значения игры.
-
Решена дискретная задача, сформулированная Раклом, о поиске точки при помощи двух отрезшз для широкого хласса случаев. Найдены оптимальные стратегия игроков и значение игры. '
-
Решена трехкатерная задала, ейормулировятхяая Насгавом и Томасом, моделирующая проблему яглрулпроваппя пролива с цепью предотвращепия провоза цезглоппого груза контрабанды посредством рекуррентных игр. Нал;,гаітм'оптпналі,ттг-їе стратегии
поведения игроков и значение игры.
4. Обобщен метод, предложенный Лаллеем, что дано возможность решить задачу, сформулированную Галом о защите объекта при отсутстаяи информация у игроков о текущем местоположении противника в случае, когда ищущий игрок имеет ограничение на число поисковых операций. Дан положительный ответ ча вопрос Аугера о существовании оптимальной смешанной стратегии охраны, состоящей только из w чистых стратегий, где w - общее число так называемых "ждать-бежать" стр; .гегий диверсанта. Найдены оптимальные стратегии игроков н значение игры.
.5. Развит метод'нахождения равновесия по Нэшу в неантаго-нистичесхих играх с выбором момента времени и доказательство единственности этого равновесия. В частности, на основе этого метода предложено корректное решение задачи с выбором момента времени, когда момент окончания игры имеет непрерывную функцию распределения. Приведен контрпример на ранееопубликованную по данной тематике работу Тераока. На основе предложенного автором оригинального метода, впервые, решена задача, поста-' вленная'Сакагучи о игре с выбором момента времени, момент окончания которой имеет дискретную функцию распределения. Решено обобщение задачи, сформулированной Хамерсом, о дележе нормаг-лизог-шного бесконечно делимого ресурса с дискаунтньш фактором по времени. С помощью этого нового метода д казана единственность равновесия но Нэшу в исследуемых бесшумных играх с выбором момента времени и наказано, что в случае шумных игр < выбором момента времени свойство единстпенности равновесия п< Нэшу не сохраняется.
б. Развит подход, позволяющий распространить формализм Га
ла для решения задачи, предложенной Айзексом, а играх поиска
' в
полным отсутствием информация. На основе этого подхода решена
задача поиска при условии, если вектограмма скоростей ищущего
отлична от круга. Найдена асимптотика значения игры при ма-
i лом радиусе обнаружения п стратегии игроков; определяющие эту
асимптотику. \
Практическая ценность. Разработанные в диссертации оригинальные методы и позые подходы, использованные при исследовании
ряда теоретике - игровых моделей поиска, создают перспективное на-
Апробация результатов ді:ссертацхпі прошла па международном конгрессе по компьютерным системам п прикладной математике (Санкт-Петербург, 1993), на ме>:игународной конференции по теории игр и экономике (Санкт-Петербург, 1S96), на семинарах по теории игр Санкт - Петербургского государственного университета, Саутгемтон-ского университета, Лондонского упнЕсрсптета, института проблем механики РАН, на семппзре кафедры оптш.іального управления факультета вычислителыюй математики и кибернетики Московского государственного университета и па Cliixt - Петербургском, городском семинаре по теории игр под руководством Пегросяна. їїсслсдсзаяия, проводимые по теми дкесертацгпг, былп Яс?г;>а;ч7ї?іш 12 месячной postdoctoral fellowship Лолдопсісого короллзского с-бщостза н поддср;::г,кы грантом N 93-1-51-27 ЇЛпппстерства Наука, Высзпзй Школы п Технического Образования Российской Федерация.
i7.yCr^T.iz-.-',:'u. Результатыдпг.сертг;г,:іл одублихсгалы й 24 научных
работах, в том числа з одной мх:ографі<;і.
Струи'* ур a PclCotm. Д'ісссртаціті состоит из кт.од'енля, трех глав,
заключения и списка литературы. Общий объем диссертации 250 страниц. Список литературы включает 151 наименование.
