Процессы управления и устойчивость
жүктеу/скачать 30,48 Mb. Pdf көрінісі
|
|
• S i−1
закончил обслуживание клиента k[l k + 1] (для i = 1 это условие не применяется). Формализуя эти условия, запишем уравнение в терминах идем- потентного анализа [3], которому удовлетворяет вектор x, состоящий из четырех компонент: x(k[l k
= ε ε ε ε τ 1 (k[l k + 1])
ε ε ε ε τ 2 (k[l k + 1]) ε ε ε ε τ 3 (k[l k + 1]) ε x(k[l k + 1])⊕ 586 ⊕ τ 1 (k[l
k ]) e ε ε ε τ 2 (k[l k ]) e ε ε ε τ 3 (k[l k ]) e ε ε ε τ 4 (k[l k ]) x(k[l k ]).
(1) Здесь символ ⊕ обозначает идемпотентное сложение. Формула (1), которую можно кратко записать x(k[l
k +1]) = A
2 (k[l
k +1], k[l
k +1])x(k[l k +1])⊕A
1 (k[l
k +1], k[l
k ])x(k[l
k ]),
является неявным уравнением относительно x(k[l k + 1]), решение ко- торого имеет вид x(k[l
k + 1]) = (A 2 (k[l
k + 1], k[l k + 1]))
∗ (A 1 (k[l k + 1], k[l k ])x(k[l
k ]),
где (A 2 (k[l k + 1], k[l k + 1]))
∗ соответствует матрице:
e τ 1 (k[l
k + 1])
τ 1 (k[l k + 1])τ
2 (k[l
k + 1])
τ 1 (k[l k + 1])τ
2 (k[l
k + 1])τ
3 (k[l
k + 1])
· · · · · ·
ε ε ε e ε ε τ 2 (k[l k + 1])
e ε τ 2 (k[l
k + 1])τ
3 (k[l
k + 1]) τ
3 (k[l
k + 1]) e
. Предположим теперь, что клиент k несет убытки (издержки) h 0 k
время обслуживания серверами клиенты терпят убытки h 1 k , h 2 k , h 3 k и h 4 k за такт времени. Прибывая в буфер, клиенты формируют очередь σ j = (l 1 , . . . , l N )
мальности (здесь l k — номер в очереди клиента k). Убытки клиента k при сформированной очереди σ j расcчитыва- ются по формуле: F σ j k = x 1 (k[l
k ])h
0 k + 3 i=1
(x i+1
(k[l k ]) − x i (k[l
k ]))h
i k + τ i (k[l
k ])h
4 k . 587 Введя переменные x 0 (k[l k ]) и x
5 (k[l
k ]) и положив x 0 (k[l
k ]) ≡ 0,
x 5 (k[l k ]) = x
4 (k[l
k ]) + τ
4 (k[l
k ]), можно записать выражение для F σ j
компактнее: F σ j k = 4 i=0
(x i+1
(k[l k ]) − x i (k[l
k ]))h
i k . Издержки каждого клиента принимаются за функционалы, для которых могут быть найдены компромиссная точка, вектор Шепли и т.д. [2]. Для приводимого ниже примера построен алгоритм нахож- дения компромиссного решения. 2. Численный пример. Для рассматриваемой модели запро- граммирован алгоритм нахождения компромиссного решения при любом количестве серверов и количестве клиентов не более 9. Это ограничение обусловлено тем, что при количестве клиентов равном 10 для вычислений требуется 290,3 МБ памяти, а при количестве клиентов равном 11 – 3,5 ГБ памяти. Для 4 серверов и 6 клиентов при заданных времени обслужива- ния клиента k сервером i и убытках за такт времени: τ i
2 3 4 2 5 1 4 1 1 3 1 7 3 5 7 4 2 8 6 7 3 4 9 3 , h
i k = 3 2 3 5 1 9 5 2 1 3 3 1 4 7 2 2 3 4 2 2 8 9 8 5 9 5 3 2 4 2 компромиссная точка достигается при 311-м порядке очереди (σ j =
для 6 запусков программы) процессорного времени и 34,6 КБ памяти на персональном компьютере Intel PentiumIII-650 MHz. Литература 1. Baccelli F., Cohen G., Olsder G.J. Quadrat J.-P. Synchronization and Linearity: an algebra for discrete event systems. New-York: John Wiley & Sons, 1992. 2. Малафеев О.А. Управляемые конфликтные системы: Учеб. посо- бие. СПб.: Изд-во СПбГУ, 2000. 280 с. 3. Маслов В.П., Колокольцов В.Н. Идемпотентный анализ и его при- менение в оптимальном управлении. М.: ФИМЛ, 1994. 142 с. 588
Оглоблин Я.В. Санкт-Петербургский государственный университет Об оптимальности радиальной стратегии Рекомендовано к публикации профессором Петросяном Л.А. Введение. В этой работе рассмотрена игра простого преследо- вания в круге, которая является одним из вариантов игры простого преследования. Данная задача на полуплоскости была решена Пет- росяном Л.А. Им была предложена стратегия параллельного сбли- жения, которая решает игру для догоняющего игрока и сводит за- дачу к задаче теории управления. Эта же стратегия является оп- тимальной и для игры на плоскости. Впервые эта стратегия была рассмотрена в [1]. В статье вводится понятие радиальной стратегии, которая явля- ется аналогом стратегии параллельного сближения, но для случая круговой границы. Будет показана ее оптимальность для радиаль- ной исходной ситуации. В игре простого преследования есть два игрока: догоняющий (P ) и убегающий (E). Игра рассматривается на плоскости. Игроки управляют поведением точек p и e, соответственно. В каждый мо- мент времени игроки выбирают управляющие векторы u (игрок P ) и v (игрок Е) и система дифференциальных уравнений, описывающая игру, имеет вид: ˙p = u(p, e, v), ˙e = v(p, e), ||u|| ≤ α, ||v|| ≤ β, α < β. После наступления момента поимки (совпадения точек игро- ков) игра заканчивается. Выигрышем игрока E называется время от момента начала игры до момента поимки. Выигрыш P равен вы- игрышу E со знаком минус. Игра происходит в круге, следовательно: ρ(O, p) ≤ R, ρ(O, e) ≤ R, где R – радиус круга, в котором происходит игра, а точка O – центр этого круга. Этот круг в дальнейшем будет называться игровым кругом. Граница его – ограничение игры. Радиальная ситуация – ситуация, в которой точки игроков на- ходятся на одном радиусе и точка p находится ближе к центру, чем точка e, или точки игроков совпадают. 589
Невырожденная ситуация – ситуация, в которой если игроки применяют погонную стратегию, то точка e достигнет границы игро- вой области (границы круга) до того как наступит момент поимки. Будем рассматривать игру, в которой начальная ситуация обла- дает свойством невырожденности и радиальности. В этой работе бу- дет показано, что оптимальной стратегией игрока P будет сохране- ние радиальности в течении всей игры (радиальная стратегия), при условии, что игрок E придерживается оптимальной стратегии. Замечание 1. Игра заканчивается на границе, если оба игро- ка пользуются оптимальными стратегиями. Это было доказано в [2] для игры без дискриминации игрока E, но то же доказательство без изменений проходит и для данного случая. Замечание 2. В дальнейшем, для простоты игрок будет ассоци- ироваться с точкой, которой он управляет, так как это не приведет к неоднозначности. Например, вместо слов "Игрок P перемещает свою точку из . . . в . . . ", будет написано "Игрок P переместился из . . . в . . . ". Вместо слов "Наступил момент поимки" — "Игрок P поймал игрока E". Упрощение. В дальнейшем будет изучаться упрощенный вари- ант игры. Будем предполагать, что выбор игроками направления вектора скорости происходит не непрерывно, а через некоторые ин- тервалы времени. В начале интервала оба игрока выбирают свои скорости (при этом игрок P знает выбор противника) и потом в те- чение всего интервала двигаются с этими скоростями. По оконча- нии интервала игроки снова выбирают свои скорости на следующий интервал. При этом поимка может произойти и внутри интервала. Длины интервалов могут быть сколь угодно малыми и неравными между собой. При этом также считаем, что в множестве точек вы- бора нет точек сгущения. Эти интервалы будем называть шагами. 1 этап. Игрок P совершает обгон по радиусу, если из радиаль- ной ситуации за шаг он смещается так, что угол между радиусами, проходящими через исходное и конечное его положение больше, чем у противника. Игрок P отстает по радиусу, если из радиальной ситуации за шаг он смещается так, что угол между радиусами, проходящими через исходное и конечное его положение меньше, чем у противника. Допустим, что в некоторый момент времени игрок P решил со- вершить обгон по радиусу (см. рис. 1) и перешел из положения p 0 в
положение p 1 , в это же время игрок E перешел из положения e 0 в положение e 1 . Построим точку p 1 так, что отрезок p 1 p 1 ортогонален радиусу Oe 1 и точка F пересечения отрезков p 1 p 1 и Oe 1 делит отре- зок p 1 p 1 пополам. Тогда ситуация (p 1 , e
1 ) ничем, кроме симметрии, не отличается от (p 1 , e 1 ). Но положения p 1 игрок P может достичь за тот же шаг, не используя всех своих возможностей, так как от- резок p
0 p 1 короче, чем p 0 p 1 . А следовательно, это не оптимально. Очевидно, что такая ситуация будет верна для любого положения в игре, когда начальная ситуация радиальная. Таким образом доказа- на следующая лемма. Рис. 1.
Лемма 1. Когда игрок P начинает отклоняться от радиальной стратегии, то оптимальным может быть только отклонение с отставанием по радиусу. В радиальной ситуации игроку E неважно, в какую сторону от радиуса смещаться. Поэтому для простоты рассуждений будем счи- тать, что игрок E будет выбирать движение в ту же сторону от теку- щего радиуса, что и на предыдущем промежутке времени, если игрок P использует радиальную стратегию или движется с отставанием по радиусу. В момент, когда игрок P начинает обгонять по радиусу (си- туация (p 1 e
)), продолжит двигаться по ранее выбранной стратегии, но по траектории симметричной относительно радиуса Oe. В итоге результат обгона по радиусу становится эквивалентен отставанию, но P продвигается на меньшее расстояние, чем мог бы. 2 этап. Предположим, что игрок P отклонился от радиальной стратегии на предпоследнем шаге. Точку, в которой происходит по- 591
имка, обозначим K. Траектория будет локально центральновыпуклой на отрезке тра- ектории, если для каждой угловой точки этого отрезка выполняет- ся условие: меньший из углов, образованных линейными отрезками траектории, сходящимися в этой точке, содержит в себе центр игро- вого круга. Если на отрезке траектории все окончания шагов явля- ются угловыми точками, тогда будем говорить о локальной строгой центральновыпуклости. Лемма 2. Оптимальная траектория движения игрока P ло- кально строго центральновыпукла, если игрок E смещается по оп- тимальной траектории. Рис. 2.
Доказательство. Допустим, что игрок E смещается на двух по- следних шагах по выбранной стратегии так, что траектория смеще- ния не центральновыпуклая (см. рис. 2). Тогда, если игрок E вместо такого поведения переместится из положения e 0 в точку K по прямой, то он достигнет точки K быст- рее, чем по выбранной стратегии. Очевидно, что если игрок P не мог поймать игрока E до точки K, то не сможет и при таком из- менении стратегии. При подобном смещении игрок E оказывается в точке K до конца последнего шага. Таким образом, получаем, что игрок E может улучшить свою стратегию. Эти рассуждения прохо- дят и для большего числа шагов, на которых траектория E будет внешневыпуклой. Следовательно, стратегия игрока E, не дающая центральновыпуклую траекторию, неоптимальна. Теперь предположим, что игрок E смещался на двух последних шагах по прямой, т.е. точка e 1 лежит на отрезке e 0 K. Следовательно, 592
так как скорость игрока P выше и сам игрок ближе к центру игро- вого круга, то радиальная стратегия игрока P будет давать строго центральновыпуклую траекторию. Если сместить точку e 1 дальше от центра игрового круга, чтобы траектория стала центральновы- пуклой, то траектория игрока P станет тем более центральновыпук- лой. Лемма доказана. Рис. 3.
Рассмотрим отклонение на 3-х шагах (см. рис. 3). Предположим что игрок P отклоняется с отставанием по радиусу. Строим окруж- ность L k
1 и L
p , с
центром в точке p 0 и проходящую через точку p 1 . Дуги этих окруж- ностей можно увидеть на рисунке. Пересечение кругов, ограничен- ных этими окружностями, достигается игроком P только при обгоне по радиусу, так как траектория игрока P строго центральновыпукла. Построим точку p 1 на дуге окружности L p с отставанием по радиусу. Отрезок p 1 K больше, чем p 1 K, а значит игрок P не успеет добежать до точки K на последнем шаге. Заменим окружности L p и L
k на касательные, проходящие через узлы траектории Р. Это не даст ошибки в результате. Лемма 3. На последнем шаге игрок P , двигаясь из положения p 1
Доказательство. Построим прямую L p , ограничивающую мно- жество, которое может достичь игрок Р на предпоследнем шаге из точки p
0 (см. рис. 4). Построим прямую L k , ограничивающую множе- ство точек, из которых игрок P может достичь точку K на последнем шаге. Так как радиальная траектория игрока P центральновыпук- 593
ла, то точка p 1 (отклоненная) и точка K будут по разные стороны от прямой L k . Следовательно, для ситуации (p 1 , e
1 ), точка K лежит Рис. 4. в круге Апполония. Тогда весь отрезок e 1 K содержится в круге Ап- полония. Следовательно, какую бы точку на отрезке e 1 K не выбрал игрок Р, он достигнет ее позже, чем игрок Е. Лемма доказана. Построим множество, ограниченное прямой L k , радиусом, про- ходящим через e 1 , и границей игрового круга. Назовем его прибли- женным множеством достигаемости (S k ) точки K для игрока P на последнем шаге (см. рис. 4) (для построения точного множества надо использовать не прямую, а дугу L k как на рис. 3). Из доказательства леммы 3 видно, что если игрок P отклонится и к началу последнего шага не окажется в одной из точек множества S k
отклонение игроку P не выгодно. Лемма 4. При отклонении на двух последних шагах игрок P не сможет догнать игрока E на предпоследнем шаге. Дoказательство. Так как игрок P не может достичь точки e 1 из
0 за шаг, следовательно, эта точка находится внутри окруж- ности Апполония для ситуации (p 0 , e 0 ) . Следовательно, и все точки отрезка e 0 e 1 находятся внутри окружности Апполония для ситуа- ции (p 0
0 ). Т.е. поимка в них невозможна, если игрок E не будет отклоняться от своей стратегии. Лемма доказана. 3 этап. Рассмотрим отклонение на трех последних шагах. Лемма 5. На первом шаге игрок P не сможет поймать игрока Е. 594 Рассуждения ничем не отличаются от леммы 4, только другие обозначения. Лемма 6. Если игрок P на первом шаге отклонится от радиаль- ной стратегии, то он не сможет на втором шаге догнать игрока Е. Рассуждения полностью аналогичны рассуждениям леммы 3 (с изменениями в обозначениях), при этом точка e 2 находится не на окружности Апполония, а внутри. Откуда следует, что и весь от- резок e
1 e 2 находится внутри окружности Апполония для ситуации (p 1 , e 1 ) и для ситуации (p 1 , e
1 ). Лемма доказана. Лемма 7. Если игрок P отклонился на первом шаге, то вне зависимости от того, как он двигался на втором шаге, он не смо- жет догнать игрока E на последнем шаге. В том числе, и в точке K. Доказательство этой леммы приведем лишь схематично. Как и в лемме 3 строится множество S k . Затем, для этого множества также строится приближенное множество достигаемости S k за предпослед- ний шаг. Игрок P , отклонившись на первом шаге с отставанием по радиусу, не может попасть в множество S k , соответственно, на вто- ром шаге он не попадает в S k и в итоге, к концу третьего шага, он не попадает в точку K. Это означает, что выигрыш игрока E увели- чивается. Замечание 1. Точно также, при отклонении за n шагов до конца игры, строится система множеств достигаемости, и получается, что игрок P не попадает в соответствующие множества вовремя, даже если он через несколько шагов вернется на общий с E радиус. Что приводит к уменьшению выигрыша. Замечание 2. При построении доказательства предполагалось, что игрок E не меняет своей траектории, кроме случая обгона по радиусу. Из доказательства легко увидеть, что если игрок E будет рационально реагировать на отклонение игрока P от радиальной стратегии, то он выиграет не меньше. Если игрок E движется строго по радиусу к границе игрового круга, то смысла уходить с радиуса у игрока P нет, так как это при- ведет лишь к потерям. А значит, и в этом случае игроку P выгодно придерживаться радиальной стратегии. Таким образом, доказана следующая теорема. Теорема. Если игроки оказались на одном радиусе, причем иг- рок P ближе к центру игрового круга и E использует централь- 595
новыпуклую траекторию, то оптимальным поведением для игрока P будет сохранять радиальную ситуацию до момента поимки, а оставшуюся часть скорости тратить на сближение с игроком Е. Замечание 1. В формулировке теоремы не упоминается условие невырожденности исходной ситуации, так как в случае вырожденной игры оптимальной стратегией для обоих игроков будет погонная, а она при радиальной исходной ситуации для игрока P совпадает с радиальной стратегией. Замечание 2. При доказательстве теоремы везде использова- лось предположение, что игрок E на каждом шаге, когда исходная ситуация радиальная, при выборе направления движения всегда вы- бирает одно и то же. Это не является ограничением стратегий игрока Е, так как радиальная ситуация симметрична относительно радиу- са, на котором находятся игроки. И в случае, если E выбрал другое направление, можно его дальнейшую траекторию симметрично отра- зить от этого радиуса и для стратегий игроков ничего не изменится. Заключение. В этой работе было показано, что при достаточно жүктеу/скачать 30,48 Mb. Достарыңызбен бөлісу:
|