Модель управления конфликтными потоками в классе алгоритмов - (реферат)
p>Все анализируемые далее случайные объекты, применяемые при построении математической модели и связанные с процессом обслуживания, будем конструктивно задавать на некотором полном вероятностном пространстве элементарных случайных событий с вероятностной мерой на - алгебре . Для описания входных потоков заявок будем использовать нелокальный способ. Т. е. нашему рассмотрению подлежит не конкретное требование, а весь их поток. Произвольный входной поток описывается векторной случайной последовательностью , где - число заявок типа, поступивших на промежутке времени по этому потоку. Тип заявок определен меткой (состоянием случайной среды). Поведение случайной среды, для простоты, будем описываеть однородной марковской последовательностьюс двумя состояниями - хорошая погода, и вероятностями перехода . Такие ограничения означают, что смена погоды не слишком часта и что хорошая погода бывает чаще плохой. Подобные выводы позволяют считать, что за время, когда ОУ пребывает в состоянии погода не меняется. Известно, что случайные элементы связаны соотношениями: (1)где некоторые измеримые отображения пространства на , а - последовательность независимых случайных величин с некоторым распределением, в нашем случае, равномерным на интервале. Протекающие процессы обслуживания имеют, в нашей модели дискретный характер и рассматриваются на интервалах времени, порождаемых некоторым случайным точечным процессом на оси времени. Моменты , как правило, определенным образом связаны с моментами смены состояний обслуживающего устройства, их определение будет дано ниже.
3. Описание работы обслуживающего устройства.
В любой момент времени обслуживающее устройство находится в некотором состоянии . Управление входными потоками и трансформациями состояний ОУ с учетом вышеуказанных предварительных замечаний можно описать следующим образом: (2) для .
Обозначим через длину очереди в накопителе по потоку в момент , . Для состояний ОУ предполагаем, что . Случайный точечный процесс при определяется рекуррентным соотношением (3)
где - отображение множества на числовое множество такое, что . Будем называть длительностью фазы (состояния) обслуживающего устройства, а величину длительностью периода ОУ. 4. Потоки насыщения и выбор стратегии механизма обслуживания. Обозначим через , максимально возможное число обслуженных на интервале времени требований потока при наличии в накопителе бесконечной очереди. Тогда соответствующий поток насыщения может быть описан с помощью маркированного точечного процесса, где метка обслуженных заявок на интервале . Интерпритировать подобное описание можно как влияние погодных условий (состояния случайной среды) на механизм обслуживания. Более подробно этот процесс будет рассмотрен ниже. Мы не будем задавать конечномерные распределения маркированных точечных процессов и поскольку при нелокальном описании входных потоков и потоков насыщения можно ограничеться некоторыми свойствами условных распределений дискретных компонент и . Допустим, что величина задает на промежутке число фактически обслуженных заявок потока . Для описания реального процесса обслуживания нужно при любом и каждом указать зависимость (4)
то есть некоторую стратегию механизма обслуживания. На выбор функции (4) естественно наложить следующие ограничения:
;
;
Откуда получим:
; (5)
Автомат, как правило, за промежуток времени обслуживает максимально возможное число машин из потока или все поступающие и находящиеся в очереди машины этого потока, если их число меньше.
Тогда зависимость (4) будет иметь вид:
(6)
Такая стратегия механизма обслуживания, учитывая (5), называется экстремальной.
5. Рекуррентные соотношения для маркированного точечного процесса обслуживания. Свойства условных распределений для дискретных компонент, соответствующих входным потокам и потокам насыщения. Будем описывать поведение системы маркированным точечным процессом с выделенной дискретной компонентой , где - вектор длин очередей по потокам в момент . Для процесса основываясь на равенствах (1)-(3), имеет место следующее рекуррентное соотношение:
(7)
где , , . Здесь векторное соотношение предполагает выполнение равенств при . Принимая во внимание выбранную нами экстремальную стратегию обслуживания , имеем: Для изучения вероятностных свойств метки остановимся на некоторых свойствах условных распределений величин и . Полагаем что в этой модели при фиксированных значениях метки случайные величины и независимы и их условные распределения при любом и при удовлетворяют соотношениям:
; (8. 1) (8. 2)
(9)
где - целая часть величины , а , - средняя интенсивность обслуживания заявок по потоку если случайная среда на интервале находится в состоянии , здесь - интенсивность пуассоновского поступления заявок по потоку , , , - параметры распределения Бартлетта, - целая часть величины . 6. Марковское свойство компоненты .
Итак, мы определили все компоненты нашей модели: входные потоки, алгоритм управления, потоки насыщения и экстремальную стратегию механизма обслуживания. В соответствии со структурой анализируемой системы управления 3 конфликтными потоками требований, максимальный интерес представляет исследование процессов обслуживания по потокам и . Ключевое свойство дискретной компоненты процесса можно сформулировать в виде следующей теоремы: Теорема: Последовательности , и при заданном распределении вектора являются марковскими. Доказательство: Докажем правильность утверждения для последовательности. Сообразно определению, данная последовательность будет марковской, если выполнено равенство
Где
Применяя формулу полной вероятности и принятые в данной модели основные свойства ее случайных элементов, получим:
для правой части доказываемого равенства из тех же соображений получим
Т. е. доказываемое равенство имеет место. Стало быть, случайная последовательностьобразует цепь Маркова с бесконечным счетным числом состояний. Аналогично доказывается марковость последовательностей и .
7. Рекуррентные формулы для одномерных распределений дискретной компоненты маркированного точечного процесса.
Исследуем свойства одномерных распределений
Здесь начальное распределение считается заданным. Получим рекурентные соотношения вида , где - бесконечномерная матрица переходных вероятностей за один шаг процесса . Подробно рассмотрим вероятностные свойства последовательностей и . Из (7) нетрудно получить следующие, реккурентные по соотношения для этих последовательностей:
Заметим что исследование последовательностей и , проводятся аналогично. Введём следующие обозначения:
На основании доказанного свойства марковости рассматриваемых последовательностей и формулы полной вероятности можно видеть что имеют место формулы:
(10)
где суммирование ведётся по
Теперь вычислим условные вероятности:
Окончательно формула (10) примет вид:
Здесь суммрование ведётся по всем точкам
Учитывая вид условных распределений для (8. 1)-(9), нетрудно получить конкретный вид рекурентных формул для одномерных распределений дискретной компоненты. Подробно приведём только вывод формулы для вероятностей при . Используя формулу (11), учитывая что при на интервалах времени ни один из потоков не обслуживается, получим для . где полагаем при .
Вероятности , образуют матрицу
Далее через мыбудем обозначать соответственно целые части величин , где -интенсивность обслуживания по потоку , если случайная среда находится в состоянии . Поскольку при обслуживаются только требования потока ,
рекуррентные соотношения для вероятностей при получаются в виде: (13)
(14)
Так как при происходит обслуживание требований только по потоку , то при получим, что при всех и , а при имеем: (15)
а при любых :
(16)
Наконец для вероятностей имеем при любом , , .
(17)
а при любых , .
(18)
Заметим, что поскольку вероятности для , , то из (12) непосредственно следует, что при всех для , , . Уточним теперь структуру цепи Маркова . Обозначим через . Сформулируем и докажем два вспомогательных утверждения, касающихся общей структуры цепи и асимптотического поведения распределения рассматриваемой цепи Маркова при.
Лемма 1. Пространство состояний цепи Маркова распадается на незамкнутое множество несущественных состояний и минимально замкнутое множество существенных сообщающихся непериодических состояний. Доказательство. Из того, что и для всех , следует что случайный процесс за некоторое конечное число шагов из произвольного состояния с положительной вероятностью по цепочке попадёт в состояние . Следовательно состояние является существенным. Согласно теореме 3. 5 из /7/ совокупность состояний цепи, сообщающихся стакже является существенным. Используя полученные нами рекурентные соотношения (12)-(18) и приведённые выше замечания нетрудно видеть, что множество Покажем, что не содержит других состояний, кроме отмеченных. Возьмём, к примеру, состояние где . Тогда по цепочке переходов цепь Маркова перейдёт из существенного состояния в состояние . Следовательно, состояние является существенным и сообщающимся с . Указанный переход возможен с положительной вероятностью, поскольку и . Аналогично доказывается, что возможен переход из или в любое другое состояние, не принадлежащие множеству . Значит . Поскольку состояние достижимо из любого состояния , то множество не является замкнутым, а содержит единственное замкнутое минимальное . Из очевидного неравенства
следует, что все состояния из будут непериодическими (/8/ стр. 408). Лемма доказана.
Лемма 2. При любом начальном распределении векторной цепи Маркова либо для всех : и в системе не существует стационарного распределения, либо существуют пределы:
такие, что , и всистеме существует стационарное распределение. Доказательство. Из структуры множества и из того, что следует, что векторный случайный процесс из произвольного состояния с положительной вероятностью, не меньшей, чем , за один шаг может достигнуть множества . Обозначим через вероятность того, что рассматриваемая цепь Маркова исходя из произвольного несущественного состояния когда-либо достигнет некоторого существенного состояния из . Известно, что величины , являются решениями системы уравнений вида (8. 6), приведённой в /8/ на стр. 392. Тогда, в силу неравенстваи леммы 1, эта система является вполне регулярной и имеет ограниченное решение, . В этом можно убедиться непосредсвенной подстановкой. По теореме 11 из /9/ это решение будет единственным. Отсюда на основании эргодической теоремы в главе 15 из /8/ получим утверждение доказываемой леммы.
Итак, ассимптотическое поведение одномерного распределения случайного векторного процесса при не зависит от начального распределения .
Заключение.
В конце этой (весьма краткой) работы хочется подвести итог того, что нами было уже сделано:
Была дана общая характеристика случайной среды, системы управления, приведена её функциональная схема;
На содержательном уровне дано определение конфликтности и потоков насыщения системы;
Приведено математическое описание составляющих элементов системы и построен маркированный случайный точечный процесс, моделирующий динамическое поведение системы;
Была доказана теорема марковости выделенной дискретной компоненты процесса . Выведены рекуррентные формулы для одномерных распределений дискретной компоненты маркированного точечного процесса.
Литература.
Куделин А. Н. Модель управления конфликтными потоками в случайной среде: “Теория вероятностей и математическая статистика. Диссертация на соискание уч. степени кандидата ф. -м. н”.
Бронштейн О. И. Рыков В. В. , Об оптимальных дисциплинах обслуживания в управляемых системах // В сборн. "Управление производством", Тр. III Всесоюзн. совещ. по автоматическому управлению. Техническая кибернетика. - 1965. - М. : "Наука", 1967. Рыков В. В. Управляемые системы массового обслуживания // Сборн. "Итоги науки. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. ВИНИТИ АН СССР".
Файнберг М. А. , Файнберг Е. А. Управление в системах массового обслуживания // "Зарубежная радиоэлектроника". Федоткин М. А. Теория дискретных систем с переменной структурой обслуживания квазигенерирующих потоков : "Теория вероятностей и математическая статистика. Диссертация на соискание уч. степени доктора ф. -м. н. ".
Федоткин М. А. Неполное описание потоков неоднородных требований. -"Теория массов. обслуж. " Чжун К. Л. Однородные цепи Маркова. –М. : Мир, 1964.
Феллер В. введение в теорию вероятностей и её приложения. Т. 1, - М. : Мир, 1967. Кантарович Л. В. , Крылов В. И. Приблежённые методы высшего анализа. – М. –Л. : 'ГИФМЛ', 1962.
Страницы: 1, 2
