Марковские случайные процессы

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

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

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

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

Марковский случайный процесс («процесс без последствий») — это такой процесс, для которого характерно свойство: на вероятность любого состояния системы в будущем (при )для каждого момента времени влияние оказывает только ее состояние в настоящем (при). То есть, вероятность системы не зависит от способа перехода системы из одного состояние в другое. Это связано с тем, что развитие процесса осуществлялось в прошлом [7].

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

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

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

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

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

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

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

 

Рис. 5.1. Граф состояний и переходов:

а — обычный; б — размеченный

Допустим, что существует система S, которая предусматривает n дискретные состояния:

 

 

Каждое состояние представлено в виде прямоугольника, стрелки же ГСП изображают возможные переходы из одного состояния в другое.

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

Допустим, что система S представлена в качестве прибора, находящегося в одном из пяти состояний; - в рабочем состоянии, - списан.

ГСП системы отражен на рис. 5.1, а.

 

Транспортная задача

 

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

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

Если мы находим решение сбалансированной задачи, то сумма объемов производства на всех m пунктах-поставщиках будет эквивалентна сумме объемов потребления на всех n пунктах получателях:

 

.

 

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

Следовательно, оптимальное взаимодействие поставщиков и потребителей предполагает минимальные суммарные затраты на транспортировку:

 

.

 

Кроме того, каждому потребителю достается необходимое количество продукта:

 

,

 

Количество произведенного поставщиком продукта:

 

.

 

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

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

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