Некоторые динамические задачи распределения ресурсов в условиях конфликтных ситуаций

Игровые задачи типа дуэлей были поставлены в конце 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¹³]. Решение этой задачи для случая произвольных монотонных функций меткости принадлежит Фоксу и Кимельдорфу [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 функции меткости равны/, найден синтез оптимальных стратегий в явном виде, в отличие от программных управлений построенных Лэнгом и Киммельдорфом⁴⁰ 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).

ТГ/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. SmithGr. 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¹⁷, 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&.

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. DuetszSofti possig-tc^ asyrfyeZbtc 'cjoafy. Zast. rruxA-^ 0 V/. 17, 1980, M.

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

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

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