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

ВВЕДЕНИЕ

ГЛАВА I. Дискретные дуэли

§1.1. Постановка задачи.

§1.2. Существование седловой точки.

§1.3. Сведение решения дискретной дуэли к решению экстремальной задачи.

ГЛАВА 2. Дуэли пулеметчиков

§2.1. Постановка задачи.

§2.2. Связь дуэлей пулеметчиков с дискретными дуэлями.

§2.3. Бесшумная дуэль пулеметчиков со ступенчатыми функциями меткости.

§2.4. Шумная дуэль пулеметчиков с непрерывными функциями меткости, связанными соотношением i-PJt)'(i-PAt))e

ГЛАВА 3. Шумная дуэль пулеметчика со снайпером

§3.1. Постановка задачи.

§3.2. Т -партии и 7~-стратегии.

§3.3. Решение игры.

Игровые задачи типа дуэлей были поставлены в конце 40-х годов и с тех пор исследования в данной области не прекращаются. К дуэлям приводят многие практически важные задачи. Среди них задачи получения гарантированных результатов в моделях эксплуатации экономических объектов и функционирования сложных систем в условиях неопределенности, задачи исследования конфликтных управляемых процессов [ i] , [ 2 ] , [25 ] .

Дуэлью называется антагонистическая игра следующего вида [ I 1 . Игроки обладают определенными ресурсами CI ^ О и $ ^ О и используют их в течение заданного промежутка времени с целью достижения успеха. Применение в момент ~t некоторого ресурса А ^ приводит к успеху с вероятностью, зависящей только от времени ~t и ресурса Л

Как только j -й игрок / J' = *> 2 / достигает цели, он выигрывает величину j ^ О / /] 1 ^ & / и игра прекращается. Если игроки одновременно добиваются успеха, то платеж первому игроку составляет /I / — Дz . Игра завершается нулевым выигрышем, если ни одному из игроков не удается добиться успеха в течение заданного промежутка времени. Платежная функция игры есть математическое ожидание выигрыша первого игрока.

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

Если игрок расходует свой ресурс только единичными порциями, то его называют снайпером, моменты использования ресурса - выстрелами, а вероятность достижения успеха в момент ~Ь функцией меткости. Обычно предполагается, что функции меткости монотонно возрастают от нуля в начале промежутка до единицы в конце [ I ] , [2 ] . В ряде работ эти ограничения ослаблены [3 ] , [4 ] .

Если игрок располагает бесконечно делимым ресурсом, который может использоваться непрерывно в течение всего рассматриваемого промежутка времени, то его называют пулеметчиком.

Подробное изложение результатов, достигнутых в изучении дуэлей до 1960-го года, содержится в книге Карлина [I] . Библиография до 1972-го года дана в работе Е.Б.Яновской [2] .В книге Дрешера [ 3] рассмотрены многочисленные примеры. По классификации Н.Н.Воробьева [5] все дуэли можно отнести к общим позиционным играм. Дуэль пулеметчиков можно рассматривать как дифференциальную игру, но в силу специфики функции платежа традиционные методы теории дифференциальных игр [б] , [ 7 ] , [81 к ней не применимы. Дуэль снайперов представляет собой частную разновидность игры с выбором нескольких моментов времени [I] , [2]. Если игры с выбором одного момента времени в настоящее время полностью исследованы [ I ] , [9] , [ю] , то в случае многократного действия аналитическое решение найдено только для дуэлей. Метод сеток приближенного решения игр с выбором момента времени разработан Э.Г.Давыдовым [10] , а затем обобщен М.Г.Фуругяном

Г II 3 , ["12 ] на случай игр с выбором нескольких моментов времени и некоторые другие классы игр с разрывной функцией платежа.

В зависимости от характера информации о поведении противника, дуэли подразделяются на шумные, бесшумные и смешанные. Дуэль называется шумной, если в любой момент времени ~t игроки располагают информацией о поведении противника до момента ~Ъ , и бесшумной, если такая информация отсутствует. В бесшумной дуэли снайперов чистые стратегии игроков образуют симплексы конечномерных евклидовых пространств, а в шумной представляют собой отображения, сопоставляющие паре текущих значений ресурсов момент очередного действия. Бесшумная дуэль снайперов изучена Рестрепо [ 26 J . Шумная дуэль снайперов, обладающих произвольными ресурсами и равными функциями меткости, решена Блекуэллом и Гиршиком 1^13] . Решение этой задачи для случая произвольных монотонных функций меткости принадлежит Фоксу и Кимельдорфу [27 J , [28]. Ими получен следующий результат. Пусть (У гпп (Pi j Pz ) -шумная дуэль снайперов с ресурсами /72 и (1 , функциями меткости Pj (t) / -ijZ , ~t € L О, / J / и коэффициентами ценности /1 i ^ Д z - / . Функции меткости непрерывны и не убывают. Тогда существуют двухиндексные последовательности t ij / i> j' = ij / такие, что и vif = i- 2 п a - л rtjcy))

J K-i d «2/7 U'Pz(tiK))-i, причем tij монотонно убывает по каждому индексу.

7Х lj есть значение игры Cf ij (Pi, Р%) , a tij оптимальный момент очередного действия хотя бы одного из игроков в игре Сгпгп (Р*> Р&) / лг > L ; /г ->/' /, если текущие значения ресурсов составляют t и j соответственно.

Шумная дуэль снайперов с немонотонными функциями меткости решена В.Г.Жаданом [ 4 ] . Дуэль снайперов, в которой игроки получают информацию лишь о некоторых выстрелах противника, называется смешанной. Решение смешанной дуэли с одним действием у каждого игрока приведено в книгах Карлина [ lj и Дрешера [з]. Различные варианты смешанных дуэлей с действиями у одного игрока и одним действием у другого исследовались Смитом [29] , Стышинским [30 J , [31] , А.С.Михайловой Г14], Орловским и Радзиком [32] - [Зб] , Курису [37] . Общая смешанная дуэль не изучена.

Среди дуэлей с непрерывным расходом ресурса / дуэли двух пулеметчиков и пулеметчика со снайпером/ ранее исследовались только бесшумные. Эти дуэли относятся к классу игр на функциональных пространствах [ i] , [2] . Стратегия пулеметчика в бесшумной дуэли есть функция одной переменной - времени, которая характеризует интенсивность расхода ресурса в данный момент. Дуэль двух пулеметчиков была сформулирована и частично решена Данскиным и Дкилменом [ 38] . Решение дуэли снайпера с единственным действием против пулеметчика приведено в книге Карлина [I] . Игры, напоминающие дуэль снайпера с пулеметчиком, но с функцией платежа более общего вида исследовались Е.Б.Яновской 16 ] , Данскиным [ 39 J . Дуэль пулеметчика против снайпера с многими действиями не рассматривалась. Решение дуэли пулеметчиков с платежом - вероятность успеха первого игрока / /f^ — У , A z - О / - дано в книге Карлина fl] .В работе Е.Б.Яновской [15]это решение обобщено на случай произвольных коэффициентов ценности Л f и Д

В вышеперечисленных работах изучены дуэли, в которых чистые стратегии пулеметчика - функции интенсивности расхода ресурса -ограничены общей константой. В качестве функции меткости принимается плотность вероятности успеха JU (t) , причем предполагается, что О ^ JU ft ) < У . Решение основывается на применении леммы Неймана-Пирсона СI J .

Лэнг и Кимельдорф [ 40 J , [41 ] предложили другой подход к дуэли пулеметчиков. Построенная ими модель получается из дуэли снайперов путем перехода к пределу при бесконечном дроблении ресурсов игроков. Ее отличие от дуэли Карлина состоит в следующем.

1. Игра рассматривается на отрезке Z O^i ] / вместо СО} , как у Карлина/.

2. Снимается предположение об ограниченности функций интенсивности расхода ресурса, что делает невозможным применение леммы Неймана-Пирсона.

3. Функцией меткости Р ft) пулеметчика, как и снайпера считается вероятность достижения успеха при использовании в момент ~t единичного ресурса, а условие Jl{ f^) = О , JU (О } - У , которое накладывается Карлиным [ I ] , заменяется более естественным предположением Р /О) - О t Р({)={ .Функции JU ft) и P(t) связаны соотношением JU [t)= -Сп (i-P(t)) . Соответствующие изменения внесены в платежную функцию игры,

Лэнгом и Кимельдорфом [ 41 1 дано решение вышеописанной бесшумной дуэли двух пулеметчиков для случая абсолютно непрерывных и монотонных функций меткости. Асимптотические свойства дуэлей проанализированы в работах [42^/43] .Фокс [44]распространил решения ряда дуэлей с одинаковыми коэффициентами ценности игроков / = ~ /»в том числе решение шумной дуэли снайперов Г27 ] , бесшумной дуэли пулеметчиков [ 41 J , на случай произвольных коэффициентов /)с'

Во всех изученных вариантах бесшумных дуэлей пулеметчик имеет оптимальную чистую стратегию, а снайпер лишь смешанную. Бесшумная дуэль пулеметчиков как в постановке Карлина-Яновской, так и в модели Лэнга-Кимельдорфа, есть игра с седловой точкой. Стратегии бесшумной дуэли являются программными и образуют подмножество в множестве стратегий соответствующей шумной дуэли. Наличие седло-вой точки в дуэли пулеметчиков означает, что игрок не может улучшить гарантированный результат за счет использования информации о поведении противника f18, с. 168J . Оптимальные стратегии бесшумной дуэли являются оптиамльными и для соответствующей шумной С 42, с. 155] . Однако применение программных оптимальных стратегий в условиях шумной дуэли не позволяет игроку, используя по- • ступающую информацию, корректировать свое поведение с учетом возможных ошибок противника для повышения выигрыша. Таким образом, весьма важной для приложений является задача нахождения оптимальных стратегий в виде синтеза, которые обеспечивают управление расходом ресурса по принципу обратной связи и позволяют оптимальным образом учитывать ошибки противника.

Задача построения синтеза оптимальных стратегий решена Фоксом и Кимельдорфом [27 для шумной дуэли снайперов, а дня дуэлей с непрерывных расходом ресурса не рассматривалась.

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

Функции меткости в дуэлях традиционно предполагаются непрерывными, в то время как на практике эффективность использования ресурса часто меняется дискретно, что соответствует дуэлям со ступенчатыми функциями меткости. В данной работе изучены бесшумные дуэли пулеметчиков с кусочно-постоянными функциями меткости, на которые существующие методы решения дуэлей пулеметчиков с непрерывными функциями меткости [l 7 , f 15] , [417 не распространяются. В качестве аппарата для исследования таких дуэлей использованы новые дискретные аналоги дуэлей пулеметчиков - дуэли с дискретным временем и бесконечно делимым ресурсом, впервые поставленные и изученные в настоящей работе.

Работа состоит из трех глав, разделенных на 10 параграфов, и приложения.

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

В [40] - [43] дискретной дуэлью называется дуэль снайперов.

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

В §3 минимаксная задача методами геометрического программирования [ 17 1 сведена к задаче максимизации. Анализ полученной экстремальной задачи показал, что она обладает рядом полезных с вычислительной точки зрения свойств, позволяющих применять для ее решения любые релаксационные методы. Приведены необходимые и достаточные условия экстремума и простые формулы для вычисления оптимальных стратегий игры по координатам экстремальной точки.

Во второй главе рассматриваются дуэли пулеметчиков. В §1 дана постановка задачи для случая кусочно-непрерывных функций меткости. Чистыми стратегиями являются неубывающие кусочно-нецрерыв-ные функции расхода ресурса.

В §2 доказана теорема о предельном переходе от дискретных дуэлей к дуэли пулеметчиков. В силу этой теоремы из выпукло-вогну-тости платежа дискретной дуэли вытекает, что этим свойством обладает и дуэль пулеметчиков. Таким образом, утверждение Карлина, что в симметричном случае / /}х = /) ^ = / / платежная функция дуэли пулеметчиков не является выпукло-вогнутой [ I, с. 645 J ошибочно, и применение Е.Б.Яновской [ 15 J метода решения несимметричной дуэли пулеметчиков / = О /, основанного на выпукло-вогнутое ти функции платежа [ I J , к общему случаю / /)± ,

Л^ произвольные/ вполне обосновано, вопреки возражениям Лэнга и Кимельдорфа [ 40 J .

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

В §4 сформулирована шумная дуэль двух пулеметчиков, и для случая, когда функции меткости игроков связаны соотношением i-Pz(t) = (4-Pt(t))C , с >0 при С = i функции меткости равны/, найден синтез оптимальных стратегий в явном виде, в отличие от программных управлений построенных Лэнгом и Киммельдорфом ^40 J , /41 J .

В третьей главе дано решение шумной дуэли пулеметчика против снайпера с многими действиями. Такая игра возникает, например, при нахождении гарантированного результата функционирования системы в следующей задаче распределения ресурсов. Использование ресурса осуществляется непрерывно в течение определенного промежутка времени в условиях, когда в системе, обеспечивающей выполнение поставленной цели, в любой момент времени можем наступить критическая ситуация /в экономической модели - падение спроса/, цри которой система с определенной вероятностью выходит из строя. Вероятность разрушения системы тем больше, чем позже наступает критическая ситуация, общее число которых в течение рассматриваемого промежутка времени ограничено. Состояние системы характеризуется текущим значением ресурса и максимальным возможным количеством критических ситуаций на оставшемся промежутке времени. Корректировка интенсивности расхода ресурса происходит непрерывно в соответствии с информацией о состоянии системы, поступающей без задержки. Эффективность использования ресурса возрастает со временем. Моменты наступления критических ситуаций априори неизвестны, что с точки зрения гарантированного результата , эквивалентно наличию разумного противника.

В §1 приведена математическая постановка задачи. Содержание §2 составляет изучение класса стратегий / /^стратегии/, определяемых убывающими последовательностями убывающих функций 77? fe) Т 'к (ос) < О , О < Тп fx) < i 9 jc> о /. Основной результат этой главы состоит в следующем. Пусть Сг am (Pi у Рг ) - шумная дуэль пулеметчика, располагающего ресурсом OL при меткости Pi ft) против снайпера с пъ действиями и функцией меткости Рz ft) .

Функции меткости непрерывно дифференцируемы, не убывают,

Pjfo)*0 .PjCp'i 'p/f*>y при -t < i , p£(t)> О при ^ > J .

Тогда существуют последовательности Тп f-*1) /указанного вида/ и ТУ a ft) такие, что сс ftt - (Ax + Ai)<ncpj6nfi-P±(Tafc()btJ= о (Ai + flM(i-Pz (Т£(Х)))- А

ТГ/i foe) есть значение игры & осГ1 (Pi> Р?> ) » а паРа Т-стратегий, соответствующих данной последовательности Т, образует седловую точку.

Для решения игры &агп СР* * Р* ) достаточно определить первые /71 функций последовательности 7/г fx) на отрезке L О, (X ] . В §3 выведена и исследована система обыкновенных дифференциальных уравнений 1-го порядка относительно функций 7~/г, (ос) . Она является рекуррентной, т.е. /С -е уравнение системы содержит лишь первые /С функций. /У йк^пг/j и интегрЕфуется последовательно. В точке х - О , где задано начальное условие 7~Kfo)-i / К = /j . . . JTL / правая часть системы имеет особенность, поэтому для численного решения системы необходимы специальные методы. Описание соответствующего алгоритма и текст программы на ФОРТРАНе вынесены в приложение. Приведены некоторые результаты вычислений на ЭВМ в виде таблиц функций ~Т~f( (эс) и значений игры.

Основные результаты диссертации опубликованы в работах ^45j, (46 "Л , £47].

В заключение автор выражает искреннюю признательность своему научному руководителю Э.Г.Давыдову за помощь и постоянное внимание к работе.

1. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.

2. Яновская Е.Б. Бесконечные антагонистические игры. Итоги науки. Серия: Теория вероятностей, мат. статистика, кибернетика, 1972.

3. Дрешер М. Стратегические игры. М.: Советское радио, 1964.

4. Жадан В.Г. Шумные дуэли с произвольными функциями меткости. -В сб.: Исследование операций. Выпуск 5. М.: Щ АН СССР, 1976.

5. Воробьев Н.Н. Современное состояние теории игр. Успехи мат. наук, т. 25, 1970, №8.

6. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1974.

7. Субботин А.И., Ченцов А.Г. Оптимизация гарантии в задачах управления. М.: Наука, 1981.

8. Айзеке Р. Дифференциальные игры. М.: Мир, 1967.

9. Шифман М. Игры с выбором момента времени. В сб.: Бесконечные антагонистические игры. М.: Физматгиз, 1963.

10. Давыдов Э.Г. Методы и модели теории антагонистических игр. М.: МГУ, 1978.

11. Фуругян М.Г. 0 приближенном решении некоторого класса бесконечных антагонистических игр. Вестник МГУ. Серия: Выч. математика и кибернетика, 1978, №2.

12. Фуругян М.Г. Приближенное решение класса бесконечных антагонистических игр с полунепрерывной платежной функцией. Вестник МГУ. Серия: Выч. математика и кибернетика, 1980, №2.

13. Блекуэлл Д., Гиршик М.Г. Теория игр и статистических решений. М.: Иностранная литература, 1958.

14. Михайлова А.С. Смешанные дуэли . В сб.: Теоретико-игровые вопросы принятия решений. М.: ЦЭМИ АН СССР, 1973.

15. Яновская Е.Б. Об играх типа дуэли с непрерывным огнем, -Изв. АН СССР. Техн. кибернетика, 1969, М.

16. Яновская Е.Б. Об антагонистических играх, разыгрываемых на функциональных пространствах. Литовский мат. сборник,1968, т.

17. Даффин Р., Питерсон Е., Зенер К. Геометрическое программирование. М.: Мир, 1972.

18. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

19. Давыдов Э.Г. Игры, графы, ресурсы. М.: Радио и связь, 1981.

20. Демьянов В.Ф. Минимакс: дифференцируемость по направлениям. Л.: ЛГУ, 1974.

21. Шилов Г.Е. Математический анализ. Специальный курс. М.: Физматгиз, 1961.

22. Мак-Кракен Д., Дорн У. Численные методы и программирование на ФОРТРАНе. М.: 1977.

23. Крылов В.И., Бобков В.В., Монастырский П.И. Вычислительные методы. М.: Наука, 1977.

24. Демидович Б.П., Марон И.А., Щувалова Э.З. Численные методы анализа. М.: Физматгиз, 1962.

25. CxUCmarL L. Орсш/соп anafysts а-поС tfie thco^Lf o-f Cfccrnes ; ал ao/irettc'strtg exampleJ. GLmeb. itcct. Clssoc/atc'o/г j I/. 45, 1950, M.

26. Rcsttepo R.-A. ~Facticat piofitems шъоСъ-сп^ sebc Ъаб actions. /Inn.Matt, ttudes, 1957, №9.

27. Fox M.y ttirveldotf 6r. S. Л/о isg Duets. SI AMJ, Appi. Meet/I.^ I/, 17, 1969, №3.

28. Fox M., HcmeEdotf &. S. VaCues and shooting times in no isg (duets. J. /)rrre*. Statist.Ussoc. > v/. 65f I970> №329.

29. Smith- Gr. CL duet г-Jit/i li-lent-noisg gun, bets us noisy gun., Cottofy. rnctXk.,V. 17, 1967, Щ.

30. Sttjszgnski fj. f)rt n-sifent vs noisg duel xditk aiGibtaby accuracy functions. — Zast. rnat.V. 14, 1974.

31. Stgszgnski А. ft silent noisy vetsus Siteat due£. — Zast. mod, 1^17, 1980, M.

32. Radzik T.y OtioWski К. A mixed game of timing ' irnxotbing (р + п)*1 actions'.Zast. rnat., 1/. 15, I976, лз.

33. Ot low ski tt^ Radztk Т. А к noisg} n-si&nt vs one-noisg duet zJit/i eqaa б accuracy functions. - Zast. mat. ъ V- 15, 1976, щ.

34. DiCowski K., Radzck T. (2 game 0/ timing with tc noisy and n siterd actions э-etsus Опг noisg actio fb. — Zast. mait^v. 16, 1979, №3.

35. Radzik T,? OiCouJski K. Ct mixed gcome of timing : investigation of st^at&<gies.Zast. mat. 3 1/. 17, 1982, m.

36. RacLzik Т. y Oitowski fc. Ci mixed gameof tinning : piofitem of optirna^cty, ^ast.mat.^1.. 17, 1982, Ш.

37. Наши Т. Зи/o-noisy-гнялид -one~si&*it сй/е£utitk есрлав accuracy functions . р/оилла£ cf Оptспи 2 at со/г tkeoly cuid ^pp^- t/. 39, 1983, №2.

38. Ъа/isktn J, Oilman L. (2 gcurne оъ&ь function, space. RiTritta mat, Ыкстг. PaA/rta.^V/. 4, 1953, M.

39. Dariskin J. M. Q ^cvtul аг^ spaces of рсоёа-tititij distributions. А/аъс*£, Pes. Logout.QucObt , v. ii, 1964, №2-3.

40. Lanj J. P.j dime Мог/ G-, 2>ue£s ulotA corttcauousfiling. Management Scce/zcc> К 22, 1975, M.

41. Lang JP.? kcrndc/otf Cr. Si tent Duels idctk noncUscx&tc ^i/ic/icj. — SI AM ЛррЕ. NccU^V. 31, 1976, №3.

42. Hcmetdoif L ал^ У-P. Qsymptoit'c p^opvdies of поп-oUsciete, duets. J. /)pp£.Plo4aiitit^ > I/. 14, 1977.

43. Kimeidotf Gr} Lang if. P. CLsy mptotic plopeities of oHjczete, cLue^S. J. Appi.Pioi.jV. 15, 1978.

44. Pox M. Duets -zSofti possig-tc^ asyrfyeZbtc 'cjoafy. Zast. rruxA-^ 0 V/. 17, 1980, M.

45. Посицельская Л.Н. Бесшумная дуэль двух пулеметчиков со ступенчатыми функциями меткости. Изв. АН СССР. Техн. кибернетика, 1982, М.

46. Давьщов Э.Г. ,Посицельская Л.Н. Шумные дуэли. М.: Щ АН СССР, 1982.

47. Посицельская Л.Н. Шумная дуэль пулеметчика со снайпером.В сб.: Некоторые вопросы прикладной математики и программного обеспечения ЭВМ. М.: МГУ, 1982.