Вероятностные модели систем.Ориентированный граф состояния системы. Уравнение Колмогорова

Направленный ациклический граф или гамак есть бесконтурный орграф.

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

Изображение и свойства всех орграфов с тремя узлами

Легенда: С — слабый, ОС — односторонний, СС — сильный, Н — является направленным графом, Г — является гамаком, Т — является турниром

 
 
 
 
 
 
 
 
 
 

     ПОСТРОЕНИЕ  СЕТЕВЫХ МОДЕЛЕЙ: 

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

     По  количеству затрачиваемого времени работа может  быть:

1. Действительной, т.е. требующей затрат времени;
2. Фиктивной, т.е. формально не требующей затрат времени.

 

     Фиктивная работа может реально существовать, например, "передача документов от одного отдела к другому". Если продолжительность такой работы несоизмеримо мала по сравнению с продолжительностью других работ проекта, то формально ее принимают равной 0. Существуют фиктивные работы, которым в реальности не соответствуют никакие действия. Такие фиктивные работы только представляют связь между другими работами сетевой модели.

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

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

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

      

     Кодирование работы:

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

     Методические  рекомендации по построению сетевых моделей:

     При построении сетевого графика необходимо следовать следующим правилам:

1. Длина стрелки не зависит от времени выполнения работы;
2. Стрелка может не быть прямолинейным отрезком;
3. Для действительных работ используются сплошные, а для фиктивных - пунктирные стрелки;
4. Каждая операция должна быть представлена только одной стрелкой;
5. Между одними и теми же событиями не должно быть параллельных работ, т.е. работ с одинаковыми кодами;
6. Следует избегать пересечения стрелок;
7. Не должно быть стрелок, направленных справа налево;
8. Номер начального события должен быть меньше номера конечного события;
9. Не должно быть висячих событий (т.е. не имеющих предшествующих событий), кроме исходного;
10. Не должно быть тупиковых событий (т.е. не имеющих последующих событий), кроме завершающего;
11. Не должно быть циклов.

 
 
 
 
 

     Недопустимость  циклов:

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

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

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

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

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

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

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

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

1. событие,
2. работа,
3. путь.

 

     На рис. 5.1 графически представлена сетевая  модель, состоящая из 11 событий и  16 работ, продолжительность выполнения  которых указана над работами. 
      
     Рис. 5.1.

 
      Работа характеризует материальное  действие, требующее использования  ресурсов, или логическое, требующее  лишь взаимосвязи событий. При  графическом представлении работа  изображается стрелкой, которая  соединяет два события. Она обозначается парой заключенных в скобки чисел (i,j), где i — номер события, из которого работа выходит, а j — номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет определенную продолжительность t (i,j). Например, запись t (2,5) = 4 означает, что работа (2,5) имеет продолжительность 5 единиц. К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой; такие работы называются фиктивными и на графике изображаются пунктирными стрелками.

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

     (i = 1, 2, ..., n).

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

     L₁ = (1, 2, 3, 7, 10, 11), L₂ = (1, 2, 4, 6, 11) и др.

      
     Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают L_Kp, а его продолжительность — t _кр . Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ. 
     Cетевая модель имеют ряд характеристик, которые позволяют определить степень напряженности выполнения отдельных работ, а также всего их комплекса и принять решение о перераспределении ресурсов.

      
     Перед расчетом СМ следует убедиться, что она удовлетворяет следующим основным требованиям: 
     1. События правильно пронумерованы, т. е. для каждой работы (i, j) i <j (см. на рис. 5.2. работы (4,3) и (3,2)). При невыполнении этого требования необходимо использовать алгоритм пере нумерации событий, который заключается в следующем: 
     - нумерация событий начинается с исходного события, которому присваивается № 1; 
     - из исходного события вычеркивают все исходящие из него работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивают № 2; 
     - затем вычеркивают работы, выходящие из события № 2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают № 3, и так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике; 
     - если при очередном вычеркивании работ одновременно несколько событий не имеют входящих в них работ, то их нумеруют очередными номерами в произвольном порядке. 
     2. Отсутствуют тупиковые события (кроме завершающего), т. е. такие, за которыми не следует хотя бы одна работа (событие 5 из рис. 5.2); 
     3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа (событие 7); 
     4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим (см. путь (2,4,3)). 
      
     Рис. 5.2. 
     При невыполнении указанных требований бессмысленно приступать к вычислениям характеристик событий, работ и критического пути. 
 
 
 

     РАСЧЕТ  ОСНОВНЫХ ПОКАЗАТЕЛЕЙ  СЕТЕВОЙ МОДЕЛИ:

     Для событий рассчитывают три характеристики: ранний и поздний срок совершения события, а также его резерв. 
     Ранний срок свершения события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем t_р(1)=0, a t_р(N)=t_Kp(L):

      
     t_р(j)=max{t_р(j)+(i,j)}; j=2,…,N

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

      
     t_n(i)=min{t_n(i)-t(i,j)}; j=2,…,N-1

      
     Этот показатель определяется  «обратным ходом», начиная с завершающего  события, с учетом соотношения  tn(N)=tp(N). 
     Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i):

      
     R(i)=t_n(i)-t_p(i)

      
     Резерв показывает, на какой  предельно допустимый срок можно  задержать наступление этого  события, не вызывая при этом  увеличения срока выполнения  всего комплекса работ.  Для всех работ (i,j) на основе ранних и поздних сроков свершения всех событий можно определить показатели:

 
     Ранний срок начала—  t_pn(i,j)=p(i) ; 
     Ранний срок окончания — t_po(i,j)=t_p(i)+t(i,j); 
     Поздний срок окончания — t_no(U)=t_n(j); 
     Поздний срок начала —t_пн(i,j)=t_n(j)-t(i,j); 
     Полный резерв времени —R_n(i,j)=t_n(j)-t_p(i)-t(i,j); 
     Независимый резерв —  
     R_н(i,j)=max{0; t_p(j)–t_n(i)-t(i,j)}=max{0;R_n(i,j)-R(i)-R(j)}.

 
     Полный резерв времени показывает, на сколько можно увеличить время выполнения конкретной работы при условии, что срок выполнения всего комплекса работ не изменится. 
     Независимый резерв времени соответствует случаю, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие — начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ. 
     Путь характеризуется двумя показателями — продолжительностью и резервом. Продолжительность пути определяется суммой продолжительностей составляющих его работ.  
     Резерв определяется как разность между длинами критического и рассматриваемого путей. Из этого определения следует, что работы, лежащие на критическом пути, и сам критический путь имеют нулевой резерв времени. Резерв времени пути показывает, на сколько может увеличиться продолжительность работ, составляющих данный путь, без изменения продолжительности общего срока выполнения всех работ. 
     Перечисленные выше характеристики СМ могут быть получены на основе приведенных аналитических формул, а процесс вычислений отображен непосредственно на графике, либо в матрице (размерности N*N), либо в таблице.