2.2 Пример построения сетевой модели

1. Необходимо построить СМ для некоторой программы, которая включает события А, В, С…L, и отображает следующие отношения упорядочения:

1. А, В,С – исходные операции, которые могут начинаться одновременно

2. А и В предшествуют D

3. В предшествует E, F, H

4. F и С предшествуют G

5. Е и Н предшествуют I и J

6. С, D, F, J предшествуют К

7. К предшествует L

8. I, G, L – завершающие операции программы

1. Какое влияние окажет на упорядочение в сети добавление каждой из следующих операций?

• ввод фиктивной операции между 3 и 5 – А предшествует I и J

• ввод фиктивных операций между 3 и 4 – А предшествует I и J

• ввод фиктивных операций между 5 и 6 – Е и Н предшествуют G

• ввод фиктивных операций между 3 и 6 – А предшествует G

2. Какую необходимо ввести фиктивную операцию для получения

• А и В предшествуют G - фиктивную операцию между 3 и 6

• D предшествует G – фиктивную операцию между D и 7, и соеденить с 6 (необходимо перенумеровать события)

• C предшествует D – фиктивную операцию между С и 6, и соеденить с 3 (необходимо перенумеровать события)

2.3 Решение оптимизационных задач методом статических производных. Сущность метода производных

y = f(x) достигает своего экстремума при , x = x ₀

z = f(x, y) достигает своего экстремума при , x = x ₀ y = y ₀

y = f(x₁, x₂, …, x_n) i=1…n, n  2

2.4 Расчет сетевой модели

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

В результате таких вычислений определяются критические и некритические операции

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

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

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

Алгоритм определения критического пути.

Расчет критического пути включает два этапа:

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

ES_i – ранний срок начала всех операций, входящих в событие i

ES₀ = 0 для любых (i, j) D_ij – продолжительность операции (i, j)

Следовательно для вычисления ES_j необходимо сначала определить начало события всех операций (i, j), входящих в событие j.

ES₀ = 0

ES₁ = ES₀ + D₀₁ = 0+2=2

ES₂ = ES₀ + D₀₂ = 0+3=3

2 . Обратный проход. Вычисления начинаются с завершающего события сети и продолжаются по сети до исходного события ( ).

LC_i – поздний срок окончания всех операций, входящих в событие i.

Если i = n, n – номер завершающего события в сети, то LC_n = ES_n. Равенство является отправной точкой обратного прохода. В общем виде для любого события:

LC_i = min{LC_i – D_ij} для любых (i, j)

LC₆ = ES₆ = 19

LC₅ = LC₆ – D₅₆ = 19-6=13

LC₁ = LC₃ – D₁₃ = 6-2=4

После этих двух этапов определяются операции критического пути. Операция (i, j) принадлежит критическому пути, если она удовлетворяет следующим трем условиям:

1. ES_i = LC_i

2. ES_j = LC_j

3. ES_j – ES_i = LC_j – LC_i = D_ij

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

Критический путь: 0,2 – 2,3 – 3,4 – 4,5 – 5,6

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

• позднее начало LS_ij = LC_i – D_ij

• раннее окончание EC_ij = ES_j + D_ij

Различают два основных вида резерва времени:

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

TF_ij = LC_j – ES_i – D_ij = LC_j – EC_ij = LS_ij – ES_i

2. Свободный определяется из предположения, что все операции в сети начинаются в ранние сроки. При этом величина FF_ij для операций (i, j) представляет собой превышение допустимого отрезка времени над продолжительностью операции.

FF_ij = ES_j – ES_i – D_ij

Результаты расчета резервов времени и критического пути

0* - критические операции имеют полный резерв = 0