Барабаш С.Б. Экономико-математические методы и модели
Подождите немного. Документ загружается.
Начало работы и ее завершение являются событиями, называемыми
соответственно начальным и конечным событием данной работы.
На сетевом графике события изображаются кружками, а работы —
стрелками. Для обозначения событий обычно используются целые числа:
1, 2, 3, ...; а для обозначения работ используются либо буквы: А, В, С, ...,
либо пары чисел (i, j), где i — номер начального события, j —номер
конечного события для данной работы.
При построении сетевого графика следует основываться на
следующих правилах.
1.
В сетевом графике должно быть одно начальное и одно конечное
событие. На рис. 4.1(а) изображен график, не удовлетворяющий этому
правилу; а на рис. 4.1(б) показано, каким образом его можно изменить,
чтобы обеспечить выполнение первого правила: необходимо ввести
фиктивные работы А', В', С', D' (на рисунке они обозначены пунктирными
стрелками) и фиктивные начальное (нулевое) и конечное (шестое)
события.
2.
В сетевом графике не должно быть замкнутых контуров (см. рис.
4.2(а)). При возникновении такой ситуации следует еще раз изучить
исходные данные и путем пересмотра состава работ и (или) логических
связей между ними добиться устранения замкнутого контура в сетевом
графике.
(а) (б)
Рис. 4.1. Иллюстрация первого правила построения сетевых графиков
3. Любые два события в сетевом графике могут быть непосредственно
связаны не более чем одной работой. На рис. 4.2(б) изображен фрагмент
сетевого графика, не удовлетворяющий этому правилу.
(а) (б) (в)
Рис. 4.2. Иллюстрация второго и третьего правил построения сетевого графика
Устранить такую ситуацию можно, введя новое фиктивное конечное
событие для одной из работ и фиктивную работу, соединяющую новое
конечное событие со старым (см. рис. 4.2(в)).
2
1
2
3
1
2
3
1
А
В
С
А
В'
В
А
В
2
1
0
3
5
4
2
5
6
4
3
1
А
В
С
D
А'
В'
В
А
В
С
D
D'
С'
Построение сетевого графика начинается с изображения начального
события, которое обводится кружком. Из начального события выпускают
стрелки, соответствующие работам, которым не предшествуют другие
работы. В нашей задаче такими работами являются A, F и L. Первый этап
построения сетевого графика представлен на рис. 4.3.
F
A
L
Рис. 4.3. Первый этап построения сетевого графика
На следующем этапе построения сетевого графика изображают
работы, которым предшествуют уже отмеченные работы A, F и L, или, что
то же самое, которые опираются на A, F и L. Просматривая список работ,
видим, что на работу L опираются работы C и E. Поэтому завершаем
работу L (конец этой работы является событием, которое изображается
кружком), а из вновь построенного события выпускаем стрелки,
соответствующие работам C и E. Этот этап построения сетевого графика
изображен на рис. 4.4.
F
A
L
C
Е
Рис. 4.4. Второй этап построения сетевого графика
Далее выбираем из списка работ те, для которых отмечены на графике
все предшествующие. Это работы G и K. Обе они опираются на работы A
и C. Введем событие — окончание работ A и C.
Рис. 4.5. Третий этап построения сетевого графика
L
A
C
F
K
G
E
Из него выпускаем стрелки, соответствующие работам G и K (см. рис.
4.5).
Далее, на работы K и G опираются две работы — D и H. Сведем
стрелки, соответствующие работам K и G, в круг, обозначающий общее
для них конечное событие. Из этого события выводим стрелки,
соответствующие работам D и H (рис. 4.6).
Рис. 4.6. Четвертый этап построения сетевого графика
A
F
C
E
K
G
D
H
L
Теперь осталось отметить одну работу из списка — это работа B. Она
опирается одновременно на работы F и H. Сведем их в одно событие, из
которого выведем стрелку, соответствующую работе B. На эту работу, так
же, как и на работы D и E, не опирается ни одна работа. Поэтому они
являются завершающими работами сетевого графика.
Проведем стрелки, обозначающие эти работы, в общее для них
конечное событие. Это событие будет конечным для всего графика. Два
заключительных этапа построения графика изображены на рис. 4.7.
Рис.4.7. Заключительные этапы построения сетевого графика
A
F
C
E
K
G
D
H
L
B
В полученном графике есть две работы, K и G, имеющие одни и те
же начальное и конечное события. Необходимо устранить эту ситуацию.
Для этого введем фиктивное событие, конечное для работы G, и
фиктивную работу G
1
, соединяющую введенное фиктивное и конечное для
работы K события. Фиктивные событие и работу обозначим пунктирной
линией. Результаты построения представлены на рис. 4.8.
Далее необходимо пронумеровать события сетевого графика.
Очевидно, что сетевой график выглядит более естественно, если номера
предшествующих событий меньше номеров последующих событий.
A
F
K
D
H
C
E
G
L
B
GB
1
B
Рис. 4.8. Сетевой график работ
Рассмотрим простой метод упорядочения сетевого графика, который
позволяет добиться того, чтобы все последующие события имели большие
номера, чем предшествующие события. Этот метод основан на понятии
ранга события. Все события сетевого графика подразделяются на ранги. К
одному рангу может относиться несколько событий. Нумерация событий
производится в соответствии с принадлежностью к тому или иному рангу.
Чем выше ранг, тем больший номер имеет событие. Внутри одного ранга
нумерация событий произвольна.
Рис. 4.9. Ранжирование событий сетевого графика
Проведем упорядочение построенного сетевого графика. Начальное
событие относим к нулевому рангу и перечеркиваем одной чертой все
стрелки-работы, выходящие из этого события, то есть стрелки,
обозначающие работы A, F, L. К первому рангу относим те события,
которые не имеют входящих неперечеркнутых стрелок (см. рис. 4.9 (а)).
Таким событием будет одно — конечное для работы L. Далее,
перечеркиваем двумя чертами работы-стрелки, выходящие из событий 1-го
ранга, то есть работы C и E (см. рис. 4.9(а)). Ко второму рангу относим те
события, которые теперь не имеют входящих неперечеркнутых стрелок.
Таким будет событие, конечное для работ A и C. Продолжая описанный
процесс упорядочения, который изображен на рис. 4.9(б), получим, что к
третьему рангу относится конечное для работы G событие; к четвертому
— конечное для работ K и G
1
событие; к пятому — конечное для работ F и
H событие; к шестому — конечное событие сетевого графика.
1
A
(
18
)
F
(
34
)
C
(
8
)
K
E (32)
(
7
)
D
(
18
)
H
(
11
)
2
3 5
L
(
8
)
6
7
B
(
8
)
4
G
1
(
0
)
G
(
7
)
L
A
B
K
C
D
E
F
G
G
1
H
( ) а
F
A
B
K
C
D
E
G
G
H
1
L
(б)
Рис. 4.10. Сетевой график строительства торгового павильона
Упорядоченный сетевой график строительства торгового павильона
изображен на рис. 4.10, на котором рядом с буквой, обозначающей работу,
в скобках проставлено число, равное сроку ее выполнения в нормальном
режиме. Фиктивной работе G
1
припишем нулевую длительность
выполнения.
Путь — это любая последовательность работ, в которой конечное
событие каждой работы совпадает с начальным событием следующей за
ней работы. Полный путь — это путь от начального до конечного события
сетевого графика. Например, в построенном сетевом графике
строительства торгового павильона последовательности работ P
1
= {L, C,
G}, P
2
= {A, K} образуют пути, а последовательности P
3
= {F, B}, P
4
= {A,
K, D} образуют полные пути.
Продолжительность или длительность выполнения работ будем
обозначать буквой t с индексом наименования работы. Так, t
A
—
длительность выполнения работы A. При расчете временных
характеристик сетевого графика продолжительность выполнения работ
удобнее обозначать через t
ij
, где i — номер начального, а j — номер
конечного события данной работы. Например, t
A
≡ t
13
= 18, t
H
≡ t
56
= 11.
Сумма продолжительностей работ, составляющих путь P, выражает
продолжительность или длину всего пути, и обозначается через t(P).
Например,
t(P
1
) = t
L
+ t
C
+ t
G
≡ t
12
+ t
23
+ t
34
= 8 + 8 +7 = 23;
t(P
3
) = t
F
+ t
B
≡ tB
16
+t
67
= 34 + 8 = 42.
Полный путь, имеющий наибольшую продолжительность,
называется критическим путем, а длина критического пути называется
критическим временем или критическим сроком сетевого графика и
обозначается через T
кр
. Критическое время — это наименьшее время
выполнения всего комплекса работ. Сетевой график может иметь
несколько различных критических путей, но все они должны иметь одну и
ту же длину.
Критическая работа — работа, задержка начала которой приводит к
увеличению срока всего проекта. Критическая работа входит в
критический путь. Критическое событие — событие, расположенное на
критическом пути.
Критические пути могут быть найдены путем перебора всех полных
путей и определения их продолжительности. Однако, в сетевой модели,
содержащей достаточно много работ, перебор всех полных путей может
занять много времени. Существует простой алгоритм нахождения
критического пути и критического времени, основанный на понятии
раннего времени наступления события.
Раннее время наступления i-го события (обозначается ) — это
момент времени, раньше которого событие i не может наступить. Каждое
событие может наступить только тогда, когда будут выполнены все работы
на всех путях, ведущих от начального события графика к данному
событию. Поэтому раннее время наступления i-го события равно
наибольшей длине путей, ведущих от начального события к i-му событию.
Т
i
P
P
i
Т
Рассчитаем для всех событий сетевого графика. Время
наступления 1-го, начального, события сетевого графика будем считать
равным нулю, то есть
P
i
Т
Т
P
1
0
=
. Далее последовательно находим ,..., .
Так как событие 2 наступает сразу после выполнения работы L,
«выходящей» из начального события, то раннее время наступления 2-го
события равно времени выполнения работы L. Поскольку t
P
Т
2
Р
Т
7
L
= t
12
= 8, то
= t
Т
P
2
12
= 8.
Далее определяем раннее время наступления 3-го события, к
которому от начального ведут два пути — {A} (первый путь) и {L, C}
(второй путь). Следовательно, согласно определению раннего времени
наступления события:
Т
P
3
= max {t
A
, t
L
+ t
C
} = max {t
13
, t
12
+ t
23
} = max {18, 8 + 8} = 18.
Если находить исходя из определения, то придется выявлять все
пути, ведущие от начального события к i-му. По мере увеличения i
количество таких путей будет увеличиваться, и нахождение
превратится в громоздкую и трудоемкую процедуру. Этого можно
избежать, используя найденные для событий под номером k,
наступивших раньше i-го события. Действительно, 3-е событие не может
наступить раньше, чем:
Т
i
P
Т
i
P
Т
k
P
• будет выполнена работа A,
• будет выполнена работа C, которую можно начать выполнять только
после наступления 2-го события.
Следовательно,
Т
P
3
= max{ +t
Т
P
1
A
, +t
Т
P
2
C
} = max{ +t
Т
P
1
13
, +t
Т
P
2
23
} = max{0+18, 8+8} = 18.
Аналогично,
Т
P
4
= + t
Т
P
3
G
=
Т
+ t
P
3
34
= 18+7 = 25,
Т
P
5
= max{ + t
Т
P
3
35
, + t
Т
P
4
45
} = max{18+7, 25 + 0} = 25,
Т
P
6
= max{ + t
P
Т
1
16
,
Т
+ t
P
5
56
} = max{0+34, 25+11} = max{34, 36} = 36,
P
Т
7
= max{ +t
P
Т
2
27
, +t
P
Т
5
57
, + t
P
Т
6
67
} = max{8+32, 25+18, 36+8} =
= max{40, 43, 44} = 44.
Таким образом, раннее время наступления конечного события
сетевого графика составляет 44 дня; то есть раньше, чем за 44 дня,
торговый павильон не может быть построен. Следовательно,
Т
кр
= = 44.
P
Т
7
Алгоритм определения критического пути, который обозначим через
P
P
кр
, состоит в следующем. Рассмотрим формулу, по которой было найдено
критическое время:
Т
кр
= = max{ +t
P
Т
7
P
Т
2
27
, +t
P
Т
5
57
, + t
P
Т
6
67
}= + t
P
Т
6
67
= 44,
и определим работу, на которой достигается максимум в этой формуле.
Очевидно, что это работа (6, 7), то есть работа В. Она принадлежит
критическому пути и является критической. Далее рассматриваем раннее
время наступления события, которое является начальным для работы B, то
есть раннее время наступления события 6:
P
Т
6
= max{ + t
P
Т
1
16
, + t
Т
P
5
56
} = 36.
Максимум достигается на работе (5, 6), то есть работе H. Поэтому
эта работа является критической. Далее, рассмотрим раннее время
наступления события 5, начального для работы H:
Т
P
5
= max{
Т
+ t
P
3
35
, + t
Т
P
4
45
} = max{18+7, 25+0}= max {25, 25}=25.
Поскольку максимум достигается на двух работах (3, 5) и (4, 5), то
обе эти работы — K и G
1
— являются критическими. Следовательно, у
сетевого графика есть, по крайней мере, два критических пути.
Продолжим определение критических работ того пути, который
содержит работу K. Так как
Т
P
3
= max{ +t
Т
P
1
13
, + t
Т
P
2
23
} = +t
P
Т
1
13
,
то работа (1, 3), то есть работа A, является критической. Поскольку ей не
предшествуют какие-либо работы, то первый критический путь определен:
= {A, K, H, B}.
кр
P
1
Теперь найдем критический путь, содержащий работу (4, 5), то есть
работу G
1
. Так как
Т
P
4
= + t
Т
P
3
G
=
Т
+ t
P
3
34
= 18+7 = 25,
то работа (3, 4), то есть работа G, является критической. Поскольку
Т
P
3
= max{ + t
Т
P
1
A
,
Т
+ t
P
2
C
} = max{ +t
Т
P
1
13
, + t
Т
P
2
23
} =
Т
+ t
P
2
23
,
то работа (1,3), то есть работа A, является критической. Таким образом,
найден второй критический путь: = {A, G, G
кр
P
2
1
, H, B}.
1
0
A
(
18
)
F
(
34
)
C
(
8
)
E (32)
K
(
7
)
G (7)
D (18)
2
8
3
18
5
25
6
36
7
44
B
(
8
)
4
25
GB
1
B
(
0
)
Н
(
11
)
L (8)
Рис. 4.11. Сетевой график с критическими путями
На рис. 4.11 критические пути выделены жирными линиями. На этом
рисунке каждый круг, обозначающий событие, разделен на две части. В
верхней части указан номер события, а в нижней — раннее время
наступления этого события.
Стоимость S строительства торгового павильона определяется как
сумма стоимостей выполнения всех работ при нормальном сроке
выполнения каждой. При этом стоимость фиктивной работы G
1
полагают
равной нулю. Итак,
S = 81+ 60 + 70+ 89 + 111 + 108 + 51 + 60 + 51 + 55 = 736 (тыс. руб.).
Таким образом, получены следующие результаты:
• критический срок Т
кр
= 44 дня;
• критические пути = {A, K, H, B}; = {A, G, G
кр
P
1
кр
P
2
1
, H, B};
• стоимость строительства в нормальном режиме S = 736 тыс. руб.
3) По условию задачи необходимо сократить период строительства на
2 дня, то есть вместо 44 дней построить павильон за 42 дня и добиться
этого с минимальными дополнительными затратами. Сокращение срока
строительства может быть обеспечено только путем сокращения сроков
выполнения работ, принадлежащих критическому пути, а сокращение
срока выполнения любой работы требует дополнительных затрат. Для
разных работ дополнительные затраты на ускорение различаются.
Поэтому, сокращая время выполнения тех критических работ, которые
требуют наименьших дополнительных затрат, можно добиться
минимального удорожания всего комплекса работ.
Будем предполагать, что затраты на ускорение выполнения каждой
работы прямо пропорциональны периоду ускорения. Так, например, для
работы B плата за ускорение составляет 8 тыс. руб., а максимальное
ускорение этой работы составляет 2 дня, таким образом, каждый день
сокращения приводит к дополнительным затратам в 8/2 = 4 (тыс. руб.).
Аналогично, для остальных работ дополнительные затраты на один день
ускорения рассчитываются по формуле
Δ
ускнор
t
t
−
=Δ
δ
,
где δ — плата за ускорение работы, а
нор
t
,
уск
t
— ее длительности при
нормальном и ускоренном режимах выполнения.
Рассчитанные по этой формуле удельные затраты на ускорение
приведены в следующей таблице
Работы
A B C D E F G H K L
Максимальное сокращение
времени выполнения (дни)
1 2 1 4 3 5 1 2 1 2
Удельные затраты на ускорение
(тыс. руб./день)
5 4 4 2 2 3 3 2 3 3
Как отмечалось выше, уменьшение периода строительства может
быть достигнуто только за счет ускорения выполнения критических работ.
Но ускорение критических работ может привести к тому, что на сетевом
графике возникнут другие критические пути, отличные от уже выявленных
путей.
Сокращая время выполнения критических работ, необходимо
отслеживать появление новых критических путей. Иначе может
возникнуть ситуация, при которой сокращение продолжительности работ,
лежащих на «старых» критических путях, не приведет к сокращению
продолжительности выполнения всего комплекса, так как период
строительства павильона будет определяться критическим временем новых
критических путей.
Если такие пути появляются, то следует сокращать время
выполнения работ таким образом, чтобы продолжительность каждого
критического пути уменьшалась на одно и то же количество дней.
Следовательно, для сокращения срока завершения строительства на один
день может потребоваться сокращение времени выполнения не одной
работы, а сразу нескольких. В этом случае для сокращения времени
выполнения будем выбирать работы таким образом, чтобы общие
дополнительные затраты на ускорение были минимальными.
Итак, при уменьшении срока выполнения всего комплекса работ с
минимальным удорожанием необходимо учитывать:
• возможные сроки сокращения критических работ;
• удельные стоимости удорожания работ;
• принадлежность одной и той же работы к разным критическим путям.
Единовременно, то есть за один шаг, сократить критический срок на
требуемое количество дней, как правило, не удается. При таком
сокращении можно не заметить появления новых критических путей, и
сокращение продолжительности работ, лежащих на «старых» критических
путях, на самом деле не приведет к сокращению продолжительности
выполнения всего комплекса.
Самый надежный способ состоит в последовательном сокращении
критического времени на один день на каждом шаге. Рассмотрим
критические пути = {A, K, H, B} и = {A, G, G
кр
P
1
кр
P
2
1
, H, B}. Им
принадлежат общие работы A, H и B. Среди этих работ наименьшие
удельные затраты на ускорение имеет работа H. Поэтому среди общих для
критических путей сетевого графика работ следует выбрать для
сокращения работу H. Сокращение ее срока выполнения на один день
повлечет увеличение ее стоимости на 2 тыс. руб.
Заметим, что не всегда наиболее выгодно сокращать именно общую
работу критических путей. Иногда удельные затраты на ускорение общей
работы могут быть столь высоки, что сокращение нескольких работ (по
одной из каждого критического пути) может привести к меньшему
увеличению стоимости проекта, чем сокращение этой одной работы.
Однако в данном случае на первом этапе выгодней сократить срок
выполнения общей для двух путей работы H.
Действительно, рассмотрим критические работы, принадлежащие
разным критическим путям: работу K (путь ) и работы G, G
кр
P
1
1
(путь ).
Сокращение работы K на один день приведет к ее удорожанию на 3 тыс.
руб. Кроме того, для уменьшения критического времени сетевого графика
необходимо будет сократить одну работу из пути . Это может быть
только работа G, так как фиктивную работу сокращать нельзя. Сокращение
работы G на один день приведет к ее удорожанию на 3 тыс. руб. Итого,
сокращение срока строительства на один день за счет уменьшения сроков
выполнения работ K и G приведет к удорожанию проекта на 3 + 3 = 6 тыс.
руб. Это больше, чем при сокращении работы H. Следовательно, на первом
этапе сокращения нужно выбрать работу H.
кр
P
2
кр
P
2
1
0
A
(
18
)
F
(
34
)
C
(
8
)
E
(
32
)
K
(
7
)
G
(
7
)
D
(
18
)
2
8
3
18
5
25
6
35
7
43
B
(
8
)
4
25
G
1
(0)
Н
(
10
)
L
(
8
)
Рис. 4.12. Первый шаг сокращения сетевого графика
Итак, новый срок выполнения работы H составляет 10 дней, новая
стоимость проекта равна
736 + 2 = 738 (тыс. руб.).
Для того чтобы проверить, не появились ли новые критические пути,
построим сетевой график после сокращения работы H и найдем его
критические пути (см. рис.4.12).
Заметим, что теперь при расчете раннего времени наступления
события 7 максимум достигается как за счет работы B, так и за счет работы