1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 32
Текст из файла (страница 32)
в+а!о р (П!(х+ ") — В!(о")) Х Х (Хцл+ о(Л)) о" = 0(л) йь(0) = ! !и Хь, 'в момент Л вЂ” 0 произошел переход в состояние (/, з), «,е « ° *+нзе о(Л) В интервале (О, Л) происходит не ме- нее двух событйй Получаем равенство г';(х) = (г';(х + сс;Л) — г';(а,л))(! — )„(Л) + + ~ ьо! (х + Р') ) пл + ~~р„В! (сс!Л) р(О ~- ! ! + х.'! РА!((Ву(х+ Р') — В,(н")) А+ о(Л). (25) (27) знх, знх, Аналогично предыдущему отсюда следует дифференциальное уравнение а,Р;(х) — сстг";(О) — )уГ;(х) + + ~~Х!,Е!(х)+ ~~д~сх!Р;(О)р(!Р+ ~~ р!)!!Ву(х) = О (26) ! в точках, где все В,(х) иепрерьгвньг, т.е.
всюду в интервале (О, о). Итак, стационарное распределение линейчатого марковского процесса с фиксированным остатком удовлетворяет системе уравнений (23), (26). Очевидно, выполняется таки!е нормирующее условие з эл. линеичАтые мАРкОВские пРоцессы Для любого х ~ О, как видно из (25), ~ (г',(х + а;Л) — Гз(х)) ( — р;(а;Л) + Л; + О (гг) С,Ь; (0) + Л;; следовательно, г';(х) — абсолютно нспрерывиьое фуикции. Поэтому, если ввести преобразование Лапласа — Стнлтьеса Ь;(8) = ~е "к(Р8(8), то в данном интеграле иг';(г) = Р;(Г)й. о Из (26) получаем систему уравнений 8а, Ь, (8) — а;р, (0) — Лрр; (8) -)- ~ ЛИЬ; (8) + + 2, 'а;Р,(0)Р';,"+ Х РоЛИ~~Е(8) = О, (28) онх1 оих где ф,(8) — преобразование Лапласа — Стилтьеса В,(х), Формально система уравнений (28), (23), (27) содержит кбольшео неизвестных, чем уравнений. Недостающие уравнения можно найти яз аналитических соображений.
Так, при конечном числе дискретных состояний процесса, решив систему (28) относительно (Ь,(8)), получим Ьо(8) = л (8) у1(8), (29) где л (8) — определитель системы — некоторый многочлен относительно 8, Л;(8) — выРажение, линейное относительно Рь ооеХ,; с;Р;(0), оои Х,. Так как Ь,(8) — аналитические функции при Пе 8) О, то мы имеем Ьз(8) = О, Х,,(8) = О, „, Ц '(8) = О для каждого корня гт(8) в правой полуплоскости, где г — кратность этого корня. Приведем альтернативный способ составления уравнении непосредственно для неизвестных констант, основанный на вложенной цепи Маркова.
ПуСтЬ 8 — МОМЕНТ ОКОНЧаНИя П-й ОПЕрацИИ, т„ = Ео(à — 0), Тогда (Р„) — однородная цепь Маркова. Обозиачим; ив(8) — переходная функция однородного марковского процесса с интенсивностями перехода Ле,' ив(8) — переходная функция того же процесса с запретом возвращения в множество состояний Х,; аи = ~ии(8) дВ~(г); (31) о Рз — вероятность того, что цепь Маркова с вероятностями перехода Л,/Л, при начальном состоянии о впервые выйдет из множества состояний Х„ перейдя в состояние 1ои Х,.
470 Гл, э. некотОРые классы случАЙных ЛРОцессов ПУсть 1~ — момент начала л-й опеРаЦии, Ъ $з (тз + О) Обозначим х; = 11ш Р (з„= (), 1 ~ Х1; у;= 1пп Р(~„"=(), уыХР Имеем систему уравнений х, = ~~~ у;игн (32) 1н»1 ( «1) %«11) У1 = Х х1(РС +»з Рм г«1). 1Н»1 (ЗЗ) р =- 11,~«х; ~ рф ) изг(1) 111, УСЕ Хз, а~»в р,= р.~р,.') ич(1) в1(д) аг, 1 х1„(зб) (34) Постоянная 11 однозначно определяется условием нормировки (36) 1 Постоянные Рз, 1«еХ„(1и Х„можно определить как решение системы уравнений Л1Р11 = )е +»з ) мззн ' ~ Хзз (37) АНХ либо по Формуле Рп .'5"„Л»; ~ им (1) 111. зе», (38) ФУнкции ие(1) опРеделЯютсЯ Решением системы пРЯмых диф ференциальных уравнений Колмогорова и1;(т) + Лги; (г) = ,'«„Лз«и11(1)1 1ее Хы уее Х1, (39) »е»1 при начальном условии (40) ао(0) = бо.
При условии, что случайный процесс ~(г) зргодичен, решение системы (32) — (ЗЗ) единственно с точностью до постоянного множителя прн условии ~З„~ т,)( зо (нлн ~~ ~у;(~ ао). Через зто решение выражаются зргодические вероятности р1 = Иш Р ($з (1)=Д: З З.З. КУСОЧНО-ЛИНЕЙНЫЕ МАРКОВСКИЕ ПРОЦЕССЫ 171 Функции йо(1) определяются решением системы уравнений иий(з) + Л;ип(г) = ~ Л„;из,(г), з ее Х„1~ Х,. (41) ьнх Заметим, что а;Р; (+ О) пропорциональны постоянным хь й 3.3. Кусочно-линейные марковские процессы 1. Метод дополнительных переменных. В настоящем параграфе будет предчожена обобщенная математическая схема случайпых процессов, при помощи которой можно описать очень широкий класс систем массового обслуживания.
Необходимость в разработке такой схемы возникает в связи со следующими причппами. Во-первых, благодаря непрерывному усложнению реальных систем массового обслуживания отдельные конкретные схемы (с озкиданием, с потерями и т. и.) уже не в состоянии охватить постановки задач, интересующие практика; требуется развитие аналитического аппарата, дающего возможность учитывать большое разнообразие действующих факторов. Во-вторых, нужно выяснить возможности определения важных в практическом отношении характеристик массового обслуживания в заданном аналитическом виде (подобно тому как существует теория интегрирования радикальных выражений, теория разрешимости алгебраических уравнений в радикалах и т.
д.); подобная теория невозмонсна без четкого указания класса объектов, с которыми она оперирует. В-третьих, обобщенная схема нужна для алгоритмизацпи приближенных вычислений и моделирования систем массового обслуживания с применением метода Монте-Карло. Наконец, имеется большое число аадач синтеза оптимальных систем массового обслуживания, которые не могут быть оформлены в стройную теорию без подходящей общей схемы. Мы убеждены, что в настоящее время в связи с внедрением большого числа различных кибернетических систем алгоритмический подход должен стать основным в теории массового обслуживания; достижения в решении конкретных задач следует осмысливать с точки зрения построения алгоритмов, которые при помощи найденного метода давали бы решение целого класса задач.
Очерченная нами задача рассматривалась многими авторами; в литературе существует много обобщенных математических схем для описания процессов массового обслуживания. В первую очередь следует упомянуть схему Кокса [1). Эта схема в общих чертах описывается следующим образом. Рассматривается случайный процесс т(Г) с конечным или счетным множеством состояний Х,. Этот процесс, за исключением некоторых особых случаев, не является марковским, однако в совокупности с дополнительными компонентами $з(г) превращается в марков- 172 ГЛ.
3. НЕКОТОРЫЕ КЛАССЫ СЛУЧАЙНЫХ ПРОЦЕССОВ ский. Любому возможному значению | процесса т(г) соответствует свое число дополнительных компонент. Эти последние возрастают с единичной скоростью и имеют смысл времени от начала какого-либо события; время существования дополнительной компоненты случайно и не зависит от других аналогичных величин. Ниже будет описана схема кусочно-линейных марковских процессов. обобщающая схему Кокса.
Кусочно-линейные марковские процессы предлагались в различных вариантах общности И, Н. Коваленко [61, [7~, [8), В. В, Калашниковым [11, Твеном [1). 2. Кусочно-линейный марковский процесс. Рассмотрим марковский случайный процесс ~(|)=(т(г), $(|)), заданный следующим образом. Пространство состояний процесса Х вЂ” множество пар (|, З,), где | — элемент конечного или счетного мпожества, з« вЂ” вектор (~о ..., $~~,), ~ |~ ~ 0 — «ранг» состояния |, з; > О. Пусть ь(|)=(|, у), у =(у„..., ую).
Тогда с вероятностью Хь|(г за время г(| происходит спонтанный переход у(|) в состояние |. После перехода новое значение Ц|) случайно и имеет измеримую по у функцию распределения В',." ,(х ( р) = Р Д «+ (1) .- х ~ й(г) = р, (1+ 1|) = 1). Два или большее число спонтанных переходов за малое время й может произойти с вероятностью о(Ь), При отсутствии спонтанных переходов в интервале (|, »+ г||) имеем т(|+ Ж) = т(|), $(»+ й)=$(|) — с«,л|, где я; =(с»а, ..., «г«з) — вектор с неотрицательными компонентами. [Заметим, что если $|(Г) интерпретируется как время до окончания какой-либо операции, фактически выполняемой в данном состоянии, то ао=1; если з»(|) — остаточная величина работы, то ао — скорость ее выполнения (мощность обслуживающего прибора).1 Предположим, что Л|= Д~ХЛ( У' (<«.
Не исключается и случай Х„)0: например, при спонтанном переходе т(1) не изменяется, $(|) претерпевает скачок. Пусть в момент 1 некоторая компонента вектора з(Г) обратилась в нуль, т. е. У(1 — О)= |, ~(1 — О) =у, у,=О. Тогда в момент происходит переход ~(1) в новое случайное состояние (й, Цг+О)); н(й,х~|,у) = = Р (т (Г + О) = й, $ (1+ 0) ( х) т (à — О) = |, $ (1 — О) = р). Если одновременное обращение в нуль двух компонент $(1) имеет вероятность О, то вместо Н(...) достаточно задать вероятность Р|А перехода т(|) из | в й при З|(1 — 0) = 0 и условное распреде|в » 3.3. КУСОЧНО-ЛИНЕЙНЫЕ МАРКОВСКИЕ ПРОЦГССЫ 173 ление Ве(х|у) случайного вектора $(в + 0) при указанных условиях.
В моменты скачков определим ь(в) по непрерывности справа. Определенный выше случайный процесс ~(в) назовем кусочно-.«ииейиыз| марковским про|«ессоз«(КЛМП). Компонента г(3) называется его дискретной («качественной») компонентой (переменкой), $,(в) — дополнительными компонентами (переменнымн), "-(3) — вектором дополнительных компонент (переменных). Как лвобой марковский процесс, КЛМП определяется, помимо описанных выше переходных характеристик, начальным распределением Р"' А) лабо начальным состоянием (в„к,).
. Условия регулярности. КЛМП назовем регрлярмыв в интервале (О, 3), если он имеет в нем конечное с вероятностью 1 число скачков при шобом начальном состоянии (|,, х,). КЛМП называется регрлярныл, если он регулярен в интервале (О, Т) для любого 7'. Сформулируем некоторые варианты достаточяых условий регулярности КЛМП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
