Буслаев А.П. Вероятностные и имитационные подходы к оптимизации автодорожного движения
Подождите немного. Документ загружается.
Математическая
х(l
- p(L -
1,
8))p(L,
8)(1-
(1
-
p(L,
8 +
l))р+
+Ps(L - 1,8 + l)p(L - 1,8)(1 - p(L, 8 +
l))Р,
171
8 = 1,2.
(3)
Поясним
формулу
(1).
Пусть
p,(i,j, t) -
вероятность
,
что
в
момент
времени
t
в
клетке
(i,
j)
находится
АТС
типа.
Выпишем
формулу
для
Ps(i,
8,
t + 1),
Т.е.
для
вероят
того,
что
в
момент
времени
t + 1
в
клетке
(i,
8)
1,2,
...
, L),
находится
АТС
8-ГО
типа,
т.е.
АТС,
на
~.ЦЯIцеl~СЯ
на
"своей"
полосе.
Это
событие
может
осуще
в
следующих
взаимно
исключающих
друг
друга
1)'
В
момент
времени
t
в
клетке
(i,
8)
находится
АТС
типа,
причем
перемещения
АТС
не
происходит.
Веро
IFm,,,,nt-m"L
выполнения
этих
условий
равна
ps(i,
8,
t)(l
-
(1
-
p(i
+ 1,8, t))p).
2)
В
момент
времени
t
клетка
(i,8)
свободна,
а
в
клетке
..
•
(i
-
1,
8)
находится
АТС
8-ГО
типа,
которое
перемещается
в
.
:клетку
(i,
8).
Вероятность
выполнения
этих
условий
равна
(i - 1,8, t)(1 - p(i,
8,
t))p.
3)
В
момент
времени
t
в
клетке
(i
-
1,
8 + 1)
находится
АТС
8-ГО
типа,
а
клетки
(i - 1,8)
И
(i,8)
свободны,
при
чем
АТС
переходит
в
клетку
(i,8).
Вероятность
выполне
ния
этих
условий
равна
ps(i
- 1,8 +
1,
t)(l
- p(i
-1,8,
t))(l-
p(i,
в,
t))p.
4)
В
момент
времени
t
в
клетке
(i, s +
1)
находится
АТС
в-го
типа,
клетки
(i -
1,
В),
(i -
1,
s + 1), (i,
В),
(i +
1,
В)
сво
бодны
и
АТС
перемещается
в
клетку
(i,
в).
Эти
события
.
происходят
с
вероятностью
ps(i,
s +
1,
t)(l-
p(i
-1,
в,
t))x
(1
- p(i -
1,
s +
1,
t))(l - p(i,
в,
t))(l - p(i+
1,
в,
t))(l
-
р).
5)
В
момент
времени
t
в
клетке
(i,
s +
1)
находится
АТС
.
B~ГO
типа,
клетки
(i -
1,
В),
(i -
1,
s + 1), (i,
В)
свободны,
а
метка
(i +
1,
В)
занята.
В
этой
ситуации
перемещение
АТС
в
клетку
(i,
В)
происходит
с
вероятностью
1.
Вероятность
выполнения
перечисленных
условий
равна
ps(i,
8,
t)
х
(1-
p(i
-1,
в,
t))(l-
p(i
-1,
s +
1,
t))(l-
p(i,
в,
t))p(i +
1,
в,
t).
! i
i
I i
I
1,
;' ;
" i
172
Глава
7.
Сегрегация
А
ТП
в
соответствии
с
формулой
полной
вероятности
полу
чаем
Ps(i,
в,
t +
1)
=
Ps(i,
8)(1 -
(1
-
p(i
+ 1,
в,
t))p)+
+Ps(i
-
1,
в,
t)(1 - p(i,
8,
t))p+
+Ps(i
-
1,
s +
1,
t)(1 -
p(i
-
1,
в,
t))
х
х(1
- p(i,
в,
t))p+
+Ps(i,
s + 1, t)(1 -
p(i
-
1,
в,
t))
х
х(1-
p(i
-
1,
s +
1,
t))(1-
p(i,
в,
t))x
х
(1
-
p(i
+ 1,
в,
t))(1 -
р)+
+Ps(i,
в,
t)(1 -
p(i
-
1,
в,
t))x
х(l-
p(i
-
1,
s +
1,
t))
х
х«1-
p(i,
в,
t))p(i +
1,
в,
t).
Переходя
к
пределу
при
t
-t
00,
получаем
(1).
Формулы
(2)-(3)
выводятся
аналогично
формуле
(1).
Сделаем
следующее
замечание.
Формула
(3)
не
учиты-
вает
возможность
выхода
из
тупикового
состояния.
Если
бы
выход
из
тупикового
состояния
отсутствовал,
то
стаци
онарная
вероятность
тупикового
состояния равнялась
бы
1.
Значения
же
Pl(2,
L)
и
Р2(1,
L),
удовлетворяющие
получен
ной
системе
уравнений,
не
равны
1
в
силу
того,
что
система
выведена
при
допущении
о
независимости
вероятностей
со
стояний
ячеек.
Учет
правила
выхода
из
тупикового
состо
яния
внес
бы
принципиальные
усложнения.
Приближенный
способ
решения
данной
системы
уравнений
не
мог
бы
быть
осуществлен
в
том
виде,
в
котором
он
описан
ниже,
из-за
того,
что
в
уравнение
для
ps(L, s + 1)
должно
бы
было
вхо
дить
не
только
p(L,
8),
но
и
ps(L,
В)
и
PS+l(L,
в).
Для
того,
чтобы
осуществить
приближенное
решение
системы
уравнений
(1)-(3),
за.меним
ее
с.л.едующеЙ
рекур
рентно
решаемой
системой,
которая
nо.л.учаетс.я
из
исход
ной
cucme.ubl
за.меноЙ
в
правой
части
уравнений
значений
·3.
Математическая
модель
173
60го
аргу,м,ента
6
фУН'I'>'Цu.яx
p(i,j), i
иди
i + 1
на
i - 1
элементарными
преобразованиями
(отметим,
что
замена
ДЛЯ
вероятностей занятости
клетки
каким
А
те
независимо
от
его
типа;
естественно
предпола
,
что
такие
вероятности
в
меньшей
степени
зависят
от
чем
значения
ps(i,
Л)
:
ps(i,8) =
Ps(i
- 1,8)+
+Раи
- 1,8 +
1)(1
-
p(i
- 1,8))+
, +ps(i,8 +
1)(1
- p(i - 1,8))2(1 -
p(i
- 1,8 +
1))
1 -
Р
+
р
+ps(i,8 +
1)(1
-
p(i
- 1,8))(1 -
p(i
- 1,8 + l))p(i,
8)!,
р
8=1,2;
i=2,
...
,L,
(4)
ps(i,8 +
1)
=
[(1
- p(i - 1,8))2(1 - p(i - 1,8 + 1))+
+(1 -
(1
- p(i - 1,8))(1 - p(i - 1,8 +
l)))Х
х
(1
- p(i -
1,
8))2
р
+
+(1 -
(1
-
p(i
- 1,8))(1 - p(i - 1,8 + 1)))(1 - p(i - 1,8))
Х
xp(i - 1,8)(1 -
p(i
- 1,8 +
l)))р+
+p(i - 1,8)(1 -
p(i
- 1,8 + l))p)]-l
Х
Х[Раи
- 1,8 +
1)(1
-
(1
- p(i - 2,8))(1 -
p(i
- 2,8 +
l)))х
х
(1
-
p(i
-
1,
8))p(i - 1,8)(1 - p(i - 1,8 +
l))р+
+Ps(i
- 1,8 + l)p(i - 1,8))(1 -
p(i
- 1,8 +
l))р],
8 = 1,2; i =
2,
..
. , L -
1,
(5)
ps(L,8 +
1)
=
[1
-
(1
- p(L - 1,8))2(1 - p(L - 1,8 + 1))+
+(1 -
(1-
p(L -
1,8))(1-
p(L
-1,8
+
l)))х
х(l-
p(L
-1,
8))2
p
]-lХ
x[Ps(L
-1,8
+
1)(1-
p(L -
2,8))(1-
p(L - 2,8 +
l)))х
'i,
i .,
,1
i
,
174
Глава
7.
Сегрегация
А
ТП
х(l-
p(L -
1,
8»p(L
-1,
8)Х
х(l
- p(L
-1,8
+
l»р+
+p,,(L -
1,8
+ l)p(L - 1,8)(1 - p(L - 1,8 + l»)p),
8 = 1,2.
(6)
Положим
p,,(l,j) =
р~Л,
где
значения
р~Л
(8
= 1,2,
j = 1,2)
заданы,
Т.е.
в
клетке
(1,
Л,
j = 1,2,
с
вероятностью
p~)
находится
АТС
первого
типа,
с
вероятностью
p~)
нахо
дится
АТС
второго
типа
(при
этом
р~Л
и
p~)
таковы,
что
р~Л
+
p~)
=
Т)
и
с
вероятностью
1 -
т
клетка
(1,
j)
свободна.
Можно,
например
положить
p~)
=
ТВ
(j = 1,2; 8 - 1,2).
В
этом
случае
вероятность
того,
что
входящее
во
вторую
зону
АТС
относится
к
фиксированному
типу,
не
зависит
от
полосы,
на
которой
это
АТС
находится,
и
равна
доле,
которую
составляют
АТС
данного
типа
от
общего
количе
ства
АТС.
Если
же
в
обозначениях,
аналогичных
исполь-
зовавшимся
в
предыдущих
пунктах,
положить
р);}
=
т
{3;
(j =
1,
2),
p~2)
=
т(l
-
(31),
p~l)
=
т(l
-
(32),
то
это
будет
соответствовать
случаю,
когда
АТС,
вошедшее
во
вторую
зону
по
j-й
полосе,
стремится
перейти
на
другую
полосу
с
вероятностью
1 -
(3;.
Используя
последовательно
формулы
(4)-(6)
с
учетом
граничных
условий,
получим
приближенные
значения
ста
ционарных
вероятностей
состояний
клеток
зоны
П.
Стационарная
вероятность
q
тупикового
состояния
при
сделанных
допущениях
о
независимости
вычисляется
по
формуле
q = Pl(L,
2)P2(L,
1).
(7)
Для
того,
чтобы
система
вновь
вернулась
в
тупиковое
состояние,
пара
клеток
(L,l)
и
(L,2)
должна
сменить
со
стояние
в
среднем
~
раз,
в
предположении
о
независu.мости
состо.янtJ..Я
этой
пары
клеток
в
каждый
момент
времени
от
ее
состо.яниЙ
в
другие
моменты
времени.
175
Чтобы
приближенно
вычислить
среднее
время
между
Т'J'пиковыми
состояниями,
нужно
умножить
значение
~
на
.
'.U<>.LI.L~"''''
время
пребывания
пары
клеток
в
неизменном
состо
·
JlНии.
Среднее
значение
времени
пребывания
пары
клеток
.
~
неизменном
состоянии
различно
для
разных
пар.
Будем
·
nриб,/шженно
с'Читать,
'Что
это
зна'Чение
приближенно
равно
среднему
времени
пребывания
?C.t&emt\;tI.
в
неизменном
состоянии.
Предположим,
в
свою
очередь,
что
состоя
ние
t\;летt\;и
(i,
j)
изменяется
с
вероятностью
1,
если
сво
бодна
t\;летt\;а
(i,j
+ 1),
и
с
вероятностью
р,
если
t\;летt\;а
(i,j
+ 1)
занята,
но
свободна
t\;дemt\;a
(i +
1,Л.
В
соот
ветствии
с
зтим
предполагаем,
что
вероятность
изменения
·
состояния
клетки
в
фиксированный
момент
времени
равна
l-т(1-(1-т)р)
и
соответственно
среднее
время
пребывания
·
клетки
в
неизменном
состоянии
равно
l-r(l-(l-r)p)'
Умножая
последнее
значение
на
~,
получаем
следующую
приближен
ную
формулу
для
среднего
времени
Т
междУ
тупиковыми
состояниями:
1 1
Т=
.-
1 -
т(1
-
(1
-
т)р)
q
в
обозначениях,
использовавmихся
в
пп.
1, 2,
имеем
1
Т=
kk'
(8)
Исследование
решения
системы
уравнений
дм
стацио
нарных
вероятностей
состояний
t\;дemot\;.
Чтобы
оценить
скорость
изменения
значений
Pl
(i,
j), j =
1,2,
по
i,
положим
в
правой
части
формул
(4), (5)
значения
p(i -
1,Л
равными
константе:
РР)
=
т/3,
p~2)
=
т(1
-
/3),
p&l)
=
т(1
-
/3),
176
Глава
7.
Сегрегация
АТП
p~2)
=
r/З,
(
.
1)
-
(1)
(2) - . -
о
1 L 1
Р
z,
-
Рl
+
Рl
-
т,
Z - , ,
•••
, - ,
(
.
2)
-
(1) (2)
- . -
о
1 L 1
Р
z,
-
Р2
+
Р2
-
т,
Z - , ,
•••
, - •
Пусть
с
=
[(1
-
r)З
+
(1
-
(1
-
т)2)(1
-
т)2(1
+
т)р+
+т(1
-
т)р]-1
Х
(9)
(10)
х[(1
-
(1
-
т?)(1
-
т)2
тр
+
т(1
-
т)р],
(11)
D = 1 - r +
С[(1
_
r)з
1
-
р
+
р
Формулы
(4), (5)
с
учетом
(9)-(12)
принимают
вид
ps(i,
s)
=
Ps(i
-
1,
s) + Dps(i -
1,
s + 1),
s =
1,
2;
i =
2,
...
,
L;
Ps(i,
s +
1)
= CPs(i -
1,
s + 1),
(12)
(13)
s = 1,2; i =
2,
...
, L -
1.
(14)
.
Из
формулы
(14)
видно,
что
значения
ps(i, s + 1)
с
ро
стом
i
стремятся
к
нулю
и
образуют
убывающую
геометри
ческую
прогрессию
со
знаменателем
С.
При
увеличении
значения
i
на
1
вероятность
того,
что
в
клетке
(i,2)
находится
АТС
первого
типа,
уменьшается
в
1
С
раз.
Из
формул
(13), (14)
видно,
что
разность
ps(i,
В)-
-Ps(i - 1,
s)
также
образуют
геометрическую
прогрессию
со
знаменателем
сп.
Пусть
А
=
(aij
)2Х2
-
матрица
размера
2
х
2
с
элементами
ан
=
1,
а12
=
О,
а21
=
п,
а22
=
С.
Матрица
А
имеет
собственные
значения
>'1
= 1
и
>'2
=
С.
7.3.
Математическая
модель
177
Уравнению
удовлетворяет
вектор
Стремление
вектора
(Рl
(i, 1),
Рl
(i,
2))
с
ростом
i
к
сво
.
ему
предельному
значению
iA
будет
тем
более
быстрым,
чем
меньше
значение
С,
т.е.
чем больше
отличается
от
1
второе
собственное
значение
матрицы
А.
Мате.мати'Чес-ка.я
.моде,л,ь
2.
Перейдем
к
рассмотрению
второго
варианта
модели
се
грегации.
Его
отличие
от
первого
варианта
заключается
в
том,
что
во
второй
зоне
переход
на
другую
полосу
разре
шен
даже
в
случае,
если
он
осуществляется
в
клетку,
распо
ложенную
перед
клеткой,
занятой
другим
АТС.
Вводится
..
также
правило,
позволяющее
АТС
избежать
столкновений.
Для
того,
чтобы
анализ
модели
не
был
слишком
усложнен,
это
правило
сформулируем
в
простом
виде,
но
при
этом
требования
данного
правила
оказываются
несколько
избы
точными.
В
данном
варианте
модели
перемещение
АТС
на
клетку
вперед
запрещено,
если
хотя
бы
в
одной
из
клеток
пары,
расположенной
непосредственно
впереди,
находится
АТС.
Проведе.м
фор.ма,л,ь'Ное
оnиса'Ние
nрави,л,
nере.меще'НиЙ
А
те
из
-к,л,ето-к
второй
ЗО'НЫ.
Предположим,
что
в
мо
мент
времени
t k-e
АТС
s-ro
типа
находится
в
клетке
(i,8 +
1)
(8
=
1,
...
,L
- 1),
т.е.
Qks(i,8 +
1,t)
= 1
и
Q(i,
8,
t) = Q(i + 1,8, t) = Q(i +
1,8
+
1,
t) =
о.
Тогда
с
вероятностью
р
Qks(i + 1,8, t +
1)
= 1
(данное
АТС
пере
двигается
на
клетку
вперед
с
переходом
на
другую
полосу),
а
с
вероятностью
1 -
р
имеем
Qks(i,
8,
t +
1)
= 1
(АТС
пе
реходит
на
другую
полосу
без
продвижения
вперед).
Если
Qks(i,8 +
1,
t)
=
1,
Q(i,
8,
t) =
о,
Q(i + 1,8, t) + Q(i +
1,8 +
1,
t) >
о,
то
Qks(i,
8,
t +
1)
= 1
(АТС
с
вероятно
стью
1
переходит
на
другую
полосу
без
продвижения
впе
ред).
Если
Qk6(i,8 +
1,
t) =
1,
Q(i,
8,
t) >
о,
Q(i + 1,8, t) =
178
Глава
7.
Сегрегация
А
ТП
Q(i + 1,8 +
1,
t) =
о,
то
с
вероятностью
р
имеет место
ра
венство
Qks(i +
1,8+
1,
t +
1)
=
1,
т.е.
АТС
передвигается
на
одну
клетку
вперед,
оставаясь
на
"чужой"
полосе.
Если
Qks(i,
8,
t) = 1
и
Q(i + 1,8, t) = Q(i + 1,8 +
1,
t) =
о,
то
с
вероятностью
р
имеем
Q(i + 1,8, t +
1)
= 1
(АТС,
нахо
дящееся
на
'~своей"
полосе,
продвигается
по
ней
на
клетку
вперед).
Если
Qks(L,
8,
t) =
1,
Q(L+ 1,8,
t)
=
о,
то
с
вероятностью
р
имеем
Qks(L + 1,8, t +
1)
=
1.
Если
Qks(L,8 +
1,
t) =
1,
Q(L,
8,
t+
1)
=
Q(L+
1,8, t)
=0,
то
Qks(L+
1,8+
1,
t+
1)
= 1
с
вероятностью
р
и
Qks(L,
8,
t +
1)
= 1
с
вероятностью
1-
р.
Если
Qks(L, 8 +
1,
t) =
1,
Q(L,
8,
t) =
о,
Q(L + 1,8, t) >
о,
то
Qks(L,
8,
t +
1)
=
1.
ПравU,/I,а
nере.м.ещен'U.Я
АТС
uз
~,/I,eтo~
первой
зоны
остаютс.я
тa~и.м.и
же,
~a~
в
nерво.м.
варианте
.м.оде,/l,и
за
UС~,/I,юче'Н.uе.м.
того,
что
АТС
не
могут
попаС1:Ь
в
клетку
(8,1), i = 1,2,
из
клетки
(8,
N)
или
клетки
(8
+
1,
N)
(по
следняя
пара
клеток
первой
зоны),
если
хотя
бы
в
одной
из
клеток
(1,1)
и
(1,2)
находится
АТС.
Выполняются
следующие
соотношения,
которые
выво
дятся
аналогично
соотношениям
(1)-(3):
ps(i,8) =
Ps(i,
8)(1
-
(1
- p(i +
1,
8))Х
х(1-
p(i + 1,8 +
l))р)+
+Ps(i - 1,8)(1 - p(i, 8))(1 - p(i, 8 +
l))р
+
+Ps(i -
1,8 +
1)(1
- p(i - 1,8))(1 - p(i,
8))(1
-
p(i
+
1,
8))Р
+
+ps(i,
8 +
1)(1
- p(i, 8))(1 - p(i + 1,8))
Х
х(1
- p(i + 1,8 +
1))(1-
р)+
+Ps(i,
s +
1)(1-
p(i,
8))Х
х(1
-
(1
-
p(i
+
1,8))(1-
p(i + 1,8 + 1))),
8
= 1,2; i =
2,
...
, L -
1;
(15)
ps(L,8) =
Ps(L,
8)(1
-
(1
- p(L +
1,
8)Р)
+
7.3.
Математическая
модель
+Ps(L -
1,
8)(1
~
p(L,
8))(1
-
p(L,
8 +
1))р
+
+Ps(L - 1,8 +
1)(1
- p(L - 1,8))
Х
Х
(1
- p(L,
8))(1
- p(L, 8 +
1))р+
+ps(L,8 +
1)(1
- p(L,
8))(1
- p(L + 1,8))(1 -
р)
+
+ps(L,8 +
1)(1
- p(L, 8))p(L + 1,8),
179
8 = 1,2;
(16)
ps(i,8 +
1)
=
Ps(i,
8 + 1)p(i,
8)
х
х(1-
(1-
p(i +
1,8))(1-
p(i
+ 1,8 +
1))р)
+
+Ps(i - 1,8 + 1)p(i - 1,8)(1 - p(i,
8))(1
- p(i, 8 +
1))р,
8 = 1,2; i =
1,
...
, L -
1;
(17)
Ps(L,
8 +
1)
=
Ps(L,
8 + 1)p(L,
8)
+
+Ps(L - 1,8 + 1)p(L - 1,8)(1 - p(L,
8))(1
- p(L, 8 +
1))р,
8=
1,2.
(18)
Как
и
при
рассмотрении
первого
варианта
модели,
заме
ним
в
правой
части
уравнений
значения
первого
аргумента
в
функциях
р(
i,
j)
- i
и
i + 1
на
i
-1.
Проведя
такую
замену
в
(13)-(16),
получим
ps(i,8) = ps(i,- 1,8)+
+рви
- 1,8 +
1)(1
-
p(i
- 1,8))+
+ps(i,8 +
1)(1
-
p(i
- 1,8)) 1 -
Р
+
р
(
.
1)
1 -
(1
- p(i - 1,8))(1 -
p(i
- 1,8 +
1))
1
+P
s
'l,8+
1
(О
1)
0-,
-P'l-
,8
Р
8 = 1,2; i =
1,
О О
• , L -
1;
(19)
ps(L,8) =
Ps(L
- 1,8)(1 - p(L - 1,8 +
1))
+
+Ps(L - 1,8 +
1)(1
- p(L - 1,8))(1 - p(L - 1,8 + 1))+
180
Глава
7.
Сегрегация
АТП
1-р
+Ps(L, 8 + 1)(1 - p(L -
1,8))-
+
Р
1
+Ps(L - 1,8 +
1)-,
8 = 1,2;
(20)
р
Ps(i,
8 +
1)
=
=
[1
- p(i
-1,
8)(1-
(1
~
p(i
-1,8))(1-
p(i
-1,
8 + l))p)]-l
Х
xps(i - 1,8 + l)p(i - 1,8)
Х
х(l
- p(i -
1,8))(1-
p(i -
1,8
+
l))р,
8 = 1,2; i =
1,
...
, L -
1;
ps(L,8 +
1)
=
[1
- p(L,
8)]-1
х
xps(L -
1,8
+ l)p(L - 1,8)(1 - p(L, 8 +
l)р,
8 = 1,2.
(21)
(22)
Для
оценки
скорости
изменения
значений
Ps(i,
8+
1)
по
i
положим
в
правой
части
формулы
(21)
значения
p(i -
1,Л,
j = 1,2,
равными
константе,
а
именно,
p(i,j)=r,
j=1,2;i=0,1,
...
,L-1.
Пусть
с
_
т(1-
т)2
р
- 1 -
т(1
-
(1
-
т)2
р
)'
или,
что
зквивалентно,
с
=
т(1-
т)р
.
1 +
т(1-
т)р
(23)
Тогда
формула
(21)
принимает
вид
Ps(i,8+1)=Cps(i-1,8+1),
8=1,2;
i=1,
...
,L-1,
(24)
и,
таким
образом,
значение
ps(i, s +
1)
с
ростом
i
стремится
к
нулю,
образуя
геометрическую
прогрессию
со
знаменате
лем
с.
Формулу
(24)
будем
использовать
и
при
i = L.