Файл: Точек, являющихся образом множества объектов, и множества линий.docx

_ij.

Требования к графу:

1. 
   в графе не должно быть петель и циклов;
   
2. 
   если две или несколько работ должны начинаться одновременно, но привязаны к различным вершинам–истокам, то между этими вершинами должно быть отмечено ожидание (для этого используется пунктирная линия, означающая фиктивную работу.
   

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

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

1. 
   вершина–исток x₀ есть начало работ по проекту в момент времени t(x₀);
   
2. 
   вершина–сток х_kесть окончание всех работ в момент времени t(x_k);
   
3. 
   дуги–работы τ₀₁ и τ₀₂ имеют начало в момент времени t(x₀);
   
4. 
   вершина–событие х₁ есть окончание работы τ₀₁ в момент времени t(x₁) = t(x₀)+τ₀₁, который определяет возможное начало двух работ τ₁₂ и τ₁₃;
   
5. 
   вершина–событие х₂ есть момент окончания двух работ τ₀₂ и τ₁₂. При наличии нескольких дуг–работ, заходящих в одну вершину–событие, следует вычислять для этого события ранний момент его наступления t^р(x_i) как наиболее позднее окончание всех предшествующих работ, то есть . Поэтому работа τ_2kне может начаться раньше ;
   
6. 
   вершина–событие х₃ есть окончание работы τ₁₃ в момент времени t(x₃) = t(x₁)+τ₁₃ и определяет возможность начать работу τ_3k. Однако, так как работы τ_2k и τ_3k должны начаться одновременно, следует найти максимальное время ожидания t_ожид = max{t(x₂), t(x₃)} и начать работы одновременно в соответствии с t_ожид;
   
7. 
   дуги–работы τ_2k и τ_3k обеспечивают завершение проекта к моменту времени . Следовательно, наибольшая продолжительность работ по проекту есть максимальное значение t_k.
   

---

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

При наличии нескольких дуг–работ, исходящих из одной вершины–события, следует определять для каждого события поздний момент его наступления t^п(x_i) как наименьшее ранее время окончания последующих работ, то есть . Расчет поздних моментов наступления каждого события следует начинать с момента окончания всех работ над проектом – x_k.Для событий, связанных с ожиданием, ранний и поздний моменты времени вычисляются по формулам: и .

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

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

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

Алгоритм расчета раннего момента наступления событий:

шаг 1: принять для начальной вершины графа и шаг итерации r = 0,

шаг 2: определить на шаге итерации rранний момент наступления события x_j: , где – ранний момент наступления события x_i, τ_ij – продолжительность работы от события, имеющего :

---

а) если к вершине x_jподходит одна дуга (i, j), то принять ,

b) если к вершине x_jподходит несколько дуг {(i, j)}, то сравнить их и найти максимальное значение раннего момента наступления события x_j: ,

шаг 3: если r = (n–1), то конец, иначе принять r= r+1 и перейти к шагу 2.

Алгоритм расчета позднего момента наступления события:

шаг 1: принять для конечной вершины графа и шаг итерации r= 0,

шаг 2: определить на шаге итерации rпоздний момент наступления события по формуле: , где – известный поздний момент наступления события , – продолжительность работы (i, j) от события , имеющего :

а) если от вершины отходит одна дуга (i, j), то принять ;

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

шаг 3: если r= (n–1), то конец, иначе принять r= r+1 и перейти к шагу 2.

Алгоритм расчета резерва времени события:

шаг 1: принять r= 0, где r– шаг итерации,

шаг 2: определить на шаге итерации rиндекс события x_iи резерв времени на событие: ,

шаг 3: если r= (n–1), где n – число вершин, то конец, иначе принять r= r+1 и перейти к шагу 2.

Алгоритм расчета резерва времени на работу:

шаг 1: принять r= 0 и выделить любую дугу (

---

i, j),

шаг 2: вычислить резерв времени на работу (i, j): ,

шаг 3: если r= m, где m – число дуг, то конец, иначе r= r+1, выделить новую дугу (i,j)и перейти к шагу 2.
Пример: на рисунке приведена сетевая модель проекта, в которой для компактного изображения параметров каждого события каждая вершина представлена кругом, разделенным на четыре сектора: в одном секторе указан индекс вершины i, в другом – ранний момент события t^р(x_i), в третьем – поздний момент события t^п(x_i) и в четвертом – резерв времени на событие t⁰(x_i). Требуется найти критический путь.

Решение задачи разобьем на 4 шага:

1. 
   расчет раннего момента наступления каждого события;
   
2. 
   расчет позднего времени наступления каждого события;
   
3. 
   расчет резерва времени каждого события;
   
4. 
   расчет резерва времени на исполнение каждой работы и определение критического пути.
   

Расчет раннего момента наступления каждого события

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

1. 
   вершины с одной входящей дугой – 1, 3, 4, 7: для них ранние моменты наступления событий рассчитываются сразу после определения раннего момента наступления события для вершины-истока;
   
2. 
   вершины с несколькими входящими дугами – 2, 5, 6, k: для них конечный результат рассчитывается только после расчетов ранних моментов наступления событий для всех вершин-истоков и является в некотором смысле «отложенным»;
   
3. 
   вершины, связанные фиктивной работой, – 4 и 5: для них рассчитываются ранние времена наступления событий без учета ожидания и в соответствии с п.1) и 2), а затем полученные значения выравниваются в сторону бόльшего.
   

---

Определим последовательность расчетов в соответствии с исходной сетью и особенностями вершин:

1. 
   поскольку вершины 0, 1, 3 формируют переход, можно сначала решить задачу для вершин 1 и 3 (при t^p(0)=0):
   

r	i	j=h(i)
0	0	1
1	1	3

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

r	i	j=h(i)
2	0	2
3	1	2
4	1	5
5	3	5

---