3. Методы разработки математических моделей дискретных цепей маркова

Математическая модель предстоящих действий разрабатывается в соответствии с содержанием экономико-математической постановки задачи. При формировании математической модели определяются:

• замысел моделирования, который включает в себя определение и уточнение с математической точки зрения:

• уяснение ЭМПЗ:

• можно ли удовлетворить условия поставленной задачи;

• являются ли заданные условия избыточными, недостаточными, противоречивыми, неоднозначными;

• определение достаточности и достоверности указанных основных параметров, необходимых для математического моделирования;

• выделить те условия задачи, которые необходимы для ее решения математическими методами, и определить их взаимосвязь;

• определение частных целей моделирования;

• определение дополнительных показателей эффективности, если они не указаны в ЭМПЗ;

• формализованное представление исследуемой ситуации;

• перечень управляющих параметров для каждого варианта исследуемой ситуации;

• выбор математического аппарата моделирования;

• математическая формулировка задачи:

• формульные зависимости, используемые для вычисления элементов матрицы переходов за один шаг процесса в случае однородного процесса или нескольких таких матриц в случае неоднородного процесса;

• формульные зависимости основного показателя эффективности или параметра, ему эквивалентного;

• численный метод реализации модели;

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

1. 3.1 Математическая формулировка задачи

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

S₁  S₂  S₃  …  S_к  …  S_п. (4)

Пример 1.

Так, например, погрузка судна, не может быть произведена раньше его выгрузки.

Случайные процессы, протекающие в системе S, состоят в том, что в последовательные фиксированные моменты времени t₁; t₂; t₃; … t_к; … t_n система оказывается в тех или иных состояниях.

Следовательно, функционирование системы можно рассматривать как стохастический процесс, характеризующийся последовательностью случайных событий. Условимся обозначать S_i^k событие, состоящее в том, что после k шагов система находиться в состоянии S_i. Шаг системы k – называется действие, которое позволяет судить о смене системой своих состояний в фиксированные моменты времени. Случайный процесс, происходящий в системе S, будем рассматривать как функцию целочисленного аргумента .

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

Рисунок 2.  Граф-процесса состояний системы

Обозначим вероятности событий как , … , . Тогда для каждого шага k процесса системы имеет место равенство:

(5)

Равенство суммы вероятностей несовместных событий, образующих полную группу – называется нормирующим.

Вероятность перехода системы S из состояния S_i в состояние S_j на k шаге, пользуясь введёнными выше событиями можно записать как условную вероятность. Условная вероятность перехода системы S из состояния S_i в состояние S_j на k шаге равна:

(6)

Если при любом k события S₁^k; S₂^k; S₃^k;… S_m^k;… S_п^k образуют полную группу несовместных событий и для каждого шага условная вероятность перехода p_i,j^k из состояния S_i в любое состояние S_j не зависит от того, когда и как система пришла в состояние S_i, то такая случайная последовательность событий называется Марковской цепью.

Если проставить эти вероятности на граф-процесса состояний системы – то такой граф называется размеченным (см. рис. 3).

Р исунок 3.  Размеченный граф-процесса состояний системы

На размеченном графе принято проставлять не все переходные вероятности, а только те из них, которые меняют состояние системы, т.е. не равные нулю. Кроме того, излишне проставлять на графе и «переходные вероятности задержки» p_i,i, так как каждая из них дополняет до единицы сумму переходных вероятностей, соответствующих всем стрелкам, исходящим из данного состояния.

Совокупность p_i,j^k _,записанных в виде прямоугольной таблицы – составляют матрицу вероятностей перехода, являющейся основой модели исследуемой ситуации. Матрица вероятностей переходов за один, k-й шаг процесса, имеет следующий вид:

(7)

где p_i,j^k - вероятность того, что система, находящаяся в состоянии S_i, в результате k-го шага перейдёт в состояние S_j;

i – номер строки или исходного состояния системы ( );

j – номер столбца или последующего состояния системы ( ).

По главной диагонали матрицы стоят вероятности p_i,i^k, это означает, что система не выходит из состояния S_i , а остаётся в нем. Если некоторые переходные вероятности p_i,j^k = 0 – это означает, что за один шаг переход системы из i-го состояния в j-е состояние невозможен.

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

1. Матрица всегда квадратная, т.е. i=j (ее размер определяется числом состояний системы);

2. (сумма вероятностей в каждой строке матрицы составляет полную группу несовместных событий и следовательно равна единице). Это свойство используется для проверки правильности заполнения матрицы вероятностей перехода и для контроля за правильностью вычислений;

3. Элемент j столбца может рассматриваться как условная вероятность перехода системы в j-e состояние при условии, что до перехода она была в i-м состоянии.

С помощью переходных вероятностей можно описать основные состояния дискретной цепи МАРКОВА.

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

Два состояния S_i и S_j называются сообщающимися, если система с положительной вероятностью за f шагов переходит из состояния S_i в S_j и за l шагов возвращается в первоначальное состояние.

Состояние S_i называется поглощающим, если вероятности перехода подчиняются условиям:

при (8)

В нашем примере на рис. 2 состояния S₁ по S_m+2 являются несущественными. А состояние S_n являются существенным, т.к. из любого состояния S_i система может перейти в данное состояние, а из этого состояния система уже не выходит. Кроме того, состояние S_n является и поглощающим.

Если p_i,j^k от шага к шагу не меняются p_i,j⁽ⁱ⁾ = … = p_i,j⁽ⁿ⁾, такая дискретная цепь Маркова называется однородной. В матрице перехода однородной Марковской цепи индекс k опускается. Если p_i,j^k от шага к шагу меняются p_i,j⁽ⁱ⁾  …  p_i,j⁽ⁿ⁾, такая дискретная цепь Маркова называется неоднородной.

Часто в экономической области нас интересует результат действий за k шагов процесса, поэтому в лекции в начале рассмотрим модели ДЦМ с конечным числом шагов.