Процессы управления и устойчивость



жүктеу 30.48 Mb.
Pdf просмотр
бет54/57
Дата27.12.2016
өлшемі30.48 Mb.
1   ...   49   50   51   52   53   54   55   56   57

• S

i−1


закончил обслуживание клиента k[l

k

+ 1] (для i = 1 это



условие не применяется).

Формализуя эти условия, запишем уравнение в терминах идем-

потентного анализа [3], которому удовлетворяет вектор x, состоящий

из четырех компонент:

x(k[l

k

+ 1]) =



=



ε



ε

ε

ε



τ

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

k



компактнее:

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

(k) =





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

=

(4, 3, 1, 6, 2, 5)), при этом вычисления требуют 4,3462 сек. (в среднем



для 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

в

590



положение 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

1



)), продолжит двигаться по ранее выбранной стратегии,

но по траектории симметричной относительно радиуса 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

, с центром в точке K и проходящую через точку p



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

, то он не сможет догнать игрока E на последнем шаге. Такое



отклонение игроку P не выгодно.

Лемма 4. При отклонении на двух последних шагах игрок P не

сможет догнать игрока E на предпоследнем шаге.

Дoказательство. Так как игрок P не может достичь точки e

1

из

точки p



0

за шаг, следовательно, эта точка находится внутри окруж-

ности Апполония для ситуации (p

0

, e



0

) . Следовательно, и все точки

отрезка e

0

e



1

находятся внутри окружности Апполония для ситуа-

ции (p

0

, e



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 выбрал другое

направление, можно его дальнейшую траекторию симметрично отра-

зить от этого радиуса и для стратегий игроков ничего не изменится.

Заключение. В этой работе было показано, что при достаточно


Каталог: bitstream
bitstream -> С. торайғыровтың публицистикасы
bitstream -> Қ атыстық сын есімдердің лексикалық тіркесімділігі
bitstream -> «Қазақ» газетіндегі ұлт-азаттық көтеріліс туралы мақалалардың маңызы
bitstream -> Бегімбай К. М. Дизайн және бейнелеу өнері салаларына
bitstream -> Грам м атические форм ы вы раж ения ком паративны Х отнош ений в научно-популярной лингвистической литературе
bitstream -> СҮттің Қоректік сапасы және сүттегі микроорганизмдер
bitstream -> Қазақ халқының ою-өрнектерінің Қолданылуы
bitstream -> Л. Н. Гумилев атындағы ЕҰу хабаршысы


Поделитесь с Вашими друзьями:
1   ...   49   50   51   52   53   54   55   56   57


©emirsaba.org 2019
әкімшілігінің қараңыз

    Басты бет