моделирование СМО ОКМ ДМ экономическая информатика 4GL Теория и практика обработки информации

Дискретные марковские процессы

Во многих случаях модель может быть представлена в виде численно-математической конструкции, то есть математических формул, описывающих моделируемый объект. С развитием имитационного моделирования область применения численно-математических моделей сократилась. Однако актуальность такого моделирования сохраняется для систем, особенно тех, в которых протекают так называемые процессы без последействия, то есть отсутствуют обратные связи, (см. иерархическую классификацию моделей). Процессы без последействия находят место при функционировании многих технических систем. Впервые один из типов такого процесса ввел в научный обиход и исследовал российский математик А. А. Марков, поэтому процессы без последействия и системы, в которых они протекают, названы марковскими, а один из типов такого процесса назван цепью Маркова.

В настоящее время теория марковских процессов разработана широко и детально, в основном, благодаря отечественным ученым А. Я. Хинчину, Б. В. Гнеденко, А. Н. Колмогорову и другим. Популярность этой теории состоит еще и в том, что она может быть применена и к системам с последействием, которые с помощью некоторых ухищрений можно трактовать как марковские.

В этой теме рассматриваются элементы теории марковских процессов и ряд численных моделей, в основе которых лежит допущение о марковости протекающих в моделируемых объектах процессов. К таковым, в первую очередь, относится широкий класс самых разнообразных объектов, имеющих общее название систем массового обслуживания (СМО). Для ряда стандартных структур СМО численные модели, связывающие показатели эффективности СМО с характеристиками элементов СМО, приведены в соответствующих справочниках. Здесь же приводятся классификация СМО и приемы построения графов состояний СМО, позволяющих строить или применять готовые численные модели.

Заметим, что для ряда современных сложных СМО численное моделирование неприемлемо в силу недостаточности адекватных математических средств. В этих случаях следует применять имитационное моделирование, которое детально рассматривается в следующих темах.

В многоэлементных системах с большим числом состояний численное моделирование на основе теории марковских процессов становится весьма громоздким. В этом случае используется так называемый метод динамики средних, который в основе имеет также марковость процесса. Этот метод существенно упрощает численное моделирование для случаев определения средних характеристик состояний моделируемой системы. В этой теме дано обоснование метода и приводятся примеры его применения.

Наиболее полное исследование процесса функционирования систем получается, если известны явные математические зависимости, связывающие искомые показатели с начальными условиями, параметрами и переменными исследуемой системы. Для многих современных систем, являющихся объектами моделирования, такие математические зависимости отсутствуют или малопригодны, и следует применять другое моделирование, как правило, имитационное.

Однако есть ряд конкретных математических схем, проверенных практикой и доказавших эффективность моделированием. Целью изучения настоящей темы является освоение таких математических моделей.

В инженерной практике часто возникает задача моделирования процессов случайной смены состояний в исследуемом объекте. В рамках нашей профессии нас интересуют дискретные состояния. Например, техническое состояние объекта может характеризоваться дискретными состояниями: исправен - неисправен, загружен - находится в простое и т. п. Численность персонала изменяется дискретно, количество объектов, ожидающих обслуживания в очереди, и многое другое.

Вид очередного состояния может определяться случайным образом, смена состояний может происходить в случайные или не случайные моменты времени.

Большой класс случайных процессов составляют процессы без последействия, которые в математике называют марковскими процессами в честь Андрея Андреевича Маркова - старшего (1856 - 1922), выдающегося русского математика, разработавшего основы теории таких процессов.

Сущность процесса без последействия понятна из определения.

Марковский случайный процесс - это такой процесс, в которомвероятность перехода системы в новое состояние зависит только от состояния системы в настоящий момент и не зависит от того, когда и каким образом система перешла в это состояние.

Простые случайные процессы, процессы в физических системах без памяти являются марковскими или могут быть сведен к марковским, если даже имеют память. В последнем случае достаточно в понятие состояния включить всю предысторию смен состояний системы (правда, в этом случае математические сложности численного моделирования таких процессов возрастают на порядки).

А. А. Марков имеет дополнение к фамилии "старший" потому, что его сын - тоже Андрей Андреевич Марков - выдающийся математик, специалист в области теории алгоритмов и др.

А. А. Марков - старший известен также как давший вероятностное обоснование метода наименьших квадратов (МНК), приведший одно из доказательств предельной теоремы теории вероятностей и многое другое.

Дальнейшее развитие теория марковских процессов получила в работах выдающегося отечественного математика Андрея Николаевича Колмогорова.

Марковские процессы делятся на два класса:

дискретные марковские процессы (марковские цепи);
непрерывные марковские процессы.

Дискретная марковская цепь, дискретный марковский процесс - это случайный процесс, при котором смена дискретных состояний происходит в определенные моменты времени.

Непрерывный марковский процесс - это случайный процесс, при котором смена дискретных состояний происходит в случайные моменты времени.

Таким образом, любой марковский процесс на самом деле - дискретный процесс, но происходящий либо в дискретном времени (в искусственной числовой сетке времени), либо в непрерывном (физическом) времени.

Рассмотрим ситуацию, когда моделируемый процесс обладает следующими особенностями.

Система имеет возможных состояний: , ..., . Вообще говоря, число состояний может быть бесконечным. Однако модель, как правило, строится для конечного числа состояний.

Смена состояний происходит, будем считать, мгновенно и в строго определенные моменты времени . В дальнейшем будем называть временные точки шагами.

Известны вероятности перехода системы за один шаг из состояния в состояние .

Цель моделирования: определить вероятности состояний системы после -го шага.

Обозначим эти вероятности (не путать с вероятностями ).

Если в системе отсутствует последействие, то есть вероятности не зависят от предыстории нахождения системы в состоянии , а определяются только этим состоянием, то описанная ситуация соответствует модели дискретной марковской цепи.

Марковская цепь называется однородной, если переходные вероятности от времени не зависят, то есть от шага к шагу не меняются. В противном случае, то есть если переходные вероятности зависят от времени, марковская цепь называется неоднородной.

Значения обычно сводятся в матрицу переходных вероятностей:

Значения могут также указываться на графе состояний системы. На рис. 1 показан размеченный граф для четырех состояний системы. Обычно вероятности переходов "в себя" - , и т. д. на графе состояний можно не проставлять, так как их значения дополняют до 1 сумму переходных вероятностей, указанных на ребрах (стрелках), выходящих из данного состояния.

Не указываются также нулевые вероятности переходов. Например, на рис. 1 это вероятности , и др.

Математической моделью нахождения вероятностей состояний однородной марковской цепи является рекуррентная зависимость

где - вероятность -го состояния системы после -го шага, ;

- вероятность -го состояния системы после -го шага, ;

- число состояний системы;

-переходные вероятности.

Рис. 1. Размеченный граф состояний системы

Для неоднородной марковской цепи вероятности состояний системы находятся по формуле:

где - значения переходных вероятностей для -го шага.

Пример 1. По группе из четырех объектов производится три последовательных выстрела. Найти вероятности состояний группы объектов после третьего выстрела.

Матрица переходных вероятностей имеет вид:

Размеченный граф состояний приведен на рис. 2.

Рис. 2. Размеченный граф состояний четырех объектов

Прежде чем приступить к вычислениям необходимо, ответить на следующие вопросы.

Является ли рассматриваемый процесс поражения целей марковским? Да, так как степень поражения объекта (смена его состояния) не зависит от того - когда и каким образом объект был приведен в настоящее состояние, а зависит только от его текущего состояния.
Подходит ли рассматриваемая задача под схему марковской цепи? Да, так как время представляет собой дискретные отрезки - время между выстрелами (шаги).
Процесс однородный или неоднородный? Есть основания полагать, что процесс однородный, так как переходные вероятности не зависят от времени. Кроме этого, мы полагаем, что объекты - неподвижные и во времени обстрела менять свое положение не могут (что привело бы к изменениям после каждого выстрела).
И, наконец, надо правильно определить начальное состояние системы, так как от этого могут существенно зависеть результаты моделирования. В нашем случае вполне естественно считать начальным состояние - все объекты целы.

Следовательно, есть все основания для применения ранее введенного рекуррентного выражения (2.1).

Решение.Так как до первого выстрела все объекты целы, то .

После первого выстрела все значения вероятностей соответствуют первой строке матрицы переходных вероятностей. Рассчитаем вероятности остальных состояний.

Сформулируем методику моделирования по схеме дискретных марковских процессов (марковских цепей).

Зафиксировать исследуемое свойство системы.
Определение свойства зависит от цели исследования. Например, если исследуется объект с целью получения характеристик надежности, то в качестве свойства следует выбрать исправность. Если исследуется загрузка системы, то - занятость. Если, как в примере 2.1, состояния объектов, то - поражен или непоражен.
Определить конечное число возможных состояний системы и убедиться в правомерности моделирования по схеме дискретных марковских процессов.
Составить и разметить граф состояний.
Определить начальное состояние.
По рекуррентной зависимости (1) определить искомые вероятности.

В рамках изложенной методики моделирования исчерпывающей характеристикой поведения системы является совокупность вероятностей .

При неоднородном марковском процессе переходная вероятность представляет собой условную вероятность перехода

, зависящую от - очередного временного шага. В этом случае должны быть указаны более одной матрицы значений (для некоторых шагов матрицы могут быть одинаковыми).

Например, при нанесении ударов по объектам, которые могут перемещаться (танковая группировка, корабли и т. п.), последние будут принимать меры по рассредоточению средств или другому защитному маневру, вплоть до активного противодействия атакующей стороне. Очевидно, все эти меры приведут к уменьшению поражающих возможностей стороны, наносящей удары, т. е. к соответствующему изменению переходных вероятностей. Процесс становится неоднородным, то есть теряет свойство "марковости". Естественно, это ведет к тому, чтобы применять модели иных, высших иерархических типов, учитывающих обратные связи.

Ссылки

Боев В.Д., Сыпченко Р.П. Компьютерное моделирование

моделирование СМО ОКМ ДМ экономическая информатика 4GL Теория и практика обработки информации

Знаете ли Вы, что гомоморфизм - это одностороннее отношение подобия структур двух систем. Система называется гомоморфной другой системе, если можно указать отношение, отображающее любой допустимый вектор её переменных на вектор некоторых выбранных переменных другой системы, компоненты которого являются компонентами некоторого допустимого вектора её состояния. Обязательное требование к модели - её гомоморфизм моделируемому объекту.

НОВОСТИ ФОРУМА

Рыцари теории эфира