СОДЕРЖАНИЕ 

 

ВВЕДЕНИЕ

 

      Одним из важнейших факторов, который должен учитываться в процессе принятия оптимальных решений, является фактор случайности. При учете «случайности» необходимо, чтобы массовые случайные явления обладали свойством статической устойчивости. Это означает, что учитываемые случайные явления подчиняются определенным статическим закономерностям, требования которых не обязательны при учете неопределенности [2] .

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

      Функционирование  широкого класса систем можно представить  как процесс перехода из одного состояния в другое под воздействием каких-либо причин. Например, процесс функционирования ЭВМ характеризуется тем, что в каждый момент времени обработкой информации заняты те или иные блоки. Процесс прохождения обрабатываемой информации по блокам ЭВМ можно рассматривать как процесс перехода системы из одного состояния в другое. В полной мере это относится и к процессу функционирования ЭВМ с точки зрения надежности. В каждый момент времени некоторые узлы работоспособны, а некоторые отказали и восстанавливаются. Если каждому возможному множеству работоспособных (или отказывающих) элементов поставить в соответствие множество состояний системы, то отказы и восстановления элементов будут отражаться переходом объекта из одного состояния в другое [6].

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

1 МАРКОВСКИЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ

 

1.1 Понятие Марковского процесса 

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

      Марковские  процессы являются частным видом  случайных процессов. Особое место  Марковских процессов среди других классов случайных процессов обусловлено следующими обстоятельствами: для Марковских процессов хорошо разработан математический аппарат, позволяющий решать многие практические задачи; с помощью Марковских процессов можно описать поведение достаточно сложных систем [3].

      Случайный процесс, протекающий в какой  либо системе S, называется Марковским, если он обладает следующим свойством: для любого момента времени вероятность любого состояния системы в будущем (при ) и не зависит от того, когда и каким образом система S пришла в это состояние.

      Случайные процессы основаны на понятии случайной функции. Случайной функцией называется функция, значение которой при любом значении аргумента является случайной величиной. Также, случайной функцией можно назвать такую функцию, которая при каждом испытании принимает какой-либо заранее неизвестный вид [1].

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

2.   Классификация Марковских процессов

 

      Классификация Марковских случайных процессов производится в зависимости от непрерывности и дискретности множества значений функций Х(t) и параметра t. Различают следующие основные виды Марковских случайных процессов:

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

б) с непрерывными состояниями и дискретным временем (Марковские последовательности);

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

г)  с непрерывным состоянием  и непрерывным временем [4]. 

3.   Цепи Маркова

 

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

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

      Случайный процесс с дискретным временем можно  представить случайной последовательностью (по индексу k) этих событий которую называют также цепью [1].

      Случайная последовательность называется Марковской цепью, если для каждого шага вероятность перехода из любого состояния в любое состояние не зависит от того, когда и как система оказалась в состоянии . Так как система в любой момент t может пребывать только в одном из состояний , то при каждом k=1,2,… события несовместны и образуют полную группу.

      Основными характеристиками Марковских цепей являются вероятности событий .

      Вероятности называются вероятностями состояний.

      Таким образом, вероятность i состояния на k шаге есть вероятность того, что система S от k до (k+1) шага будет пребывать в состоянии . Сумма вероятностей этих событий для каждого равна 1:

       .                                      (1.1)

      Если  переходные вероятности не зависят от шагов k, то Марковская цепь называется однородной.

      Переходные  вероятности однородной Марковской цепи P_ij образуют квадратную матрицу размера n*n, которой:

1. Каждая строка характеризует выбранное состояние системы, а ее элементы представляют собой вероятности всех возможных переходов за один шаг из выбранного состояния, в том числе и переход в самое себя.
2. Элементы столбцов показывают вероятности всех возможных переходов системы за один шаг в заданное состояние (иначе говоря, строка характеризует вероятность перехода системы из состояния, столбец - в состояние).
3. Сумма вероятностей каждой строки равна единице, так как переходы образуют полную группу несовместных событий:

                                                           (1.2)

4. По главной диагонали матрицы переходных вероятностей стоят вероятности P_ii того, что система не выйдет из состояния Si, а останется в нем [4].

        Если же хотя бы одна вероятность изменяется с изменением шага k, то цепь называется неоднородной. Запишем переходные вероятности в виде квадратной матрицы n порядка, сумма элементов каждой строки равна 1.

                                  (1.3)

      Вероятности задержек можно подсчитать по формуле . Вектор-строка вероятностей состояний в начальный момент времени t=0, непосредственно предшествующий первому шагу, называется вектором первоначального распределения вероятностей.

      Для однородной Марковской цепи вектор-строка вероятностей состояний от k до (k+1) шага, равна произведению вектора-строки вероятностей состояний от (k-1) до k шага на матрицу переходных вероятностей:

       .                                      (1.4)

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

                                       (1.5)

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

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

      Основными вероятностными прогнозными характеристиками Марковской цепи являются вероятности состояний на любом шаге [1].

      Все многообразие Марковских цепей подразделяется на эргодические и разложимые.

      Разложимые  Марковские цепи содержат невозвратные состояния, называемые поглощающими. Из поглощающего состояния, нельзя перейти ни в какое другое. На графе поглощающему состоянию соответствует вершина, из которой не выходит ни одна дуга. В установившемся режиме поглощающему состоянию соответствует вероятность, равная 1.

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

      Для эргодических цепей при достаточно большом времени функционирования (t стремится к бесконечности) наступает стационарный режим, при котором вероятности состояний системы не зависят от времени и не зависят от распределения вероятностей в начальный момент времени, т.е. [4]. 

4.  Теория массового обслуживания

 

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

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

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

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