Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200

• Название: Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
• Анкор: Дискретная Математика
• Дата: 15.09.2022
• Размер: 6.37 Mb.
• Имя файла: S_D_Shaporev_-_Diskretnaya_matematika_-_2004.pdf
• Тип: Учебное пособие; #679116
• страница: 22 из 26

Этап 1. Шаг 1.
 
 
 
 

,
,
0 2
1
s
x
t
d
x
d
x
d
s
d








Первая итерация. Шаг 2.


2 1
,

x
x
S

,
 


9 9
0
,
min
1





x
d
,
 


10 10 0
,
min
2





x
d
Шаг 3.


 
1 9
,
,
,
10
,
9
min
x
d







1
x
x

Шаг 4.
?

t
x

Нет. Переход на начало второго шага.
Вторая итерация. Шаг 2.


3 2
,

x
x
S

,
 


10 12 9
,
10
min
2




x
d
1
x


9
,
3
x


17
,
18
,
 


18 9
9
,
min
3





x
d
9 Шаг 3.


 
2 10
,
,
18
,
10
min
x
d





2

x
x

. Шаг 4.
?

t
x

Нет.
9 Третья итерация. Шаг 2.


t
x
x
S
,
,

4 3

,
 

0
s
12 7 9 t


23
,
 


17 7
0 1
,
18
min
3




x
d
,
10 13 9
 


19 9
0 1
,
min
4




x
d
,
9
 


23 13 0
1
,
min




t
d
2
x


10
,
4
x


19
,
Шаг 3.


 
3 17 23
,
19
,
17
min
x
d




3
x
x

Рис. 3.72.
Шаг 4.
?

t
x

Нет. Переход на начало второго шага
Четвертая итерация. Шаг 2.
 
4

x
S

,
 


19 14 17
,
19
min
4




x
d
,

103
Шаг 3.


 
4 19 23
,
19
min
x
d



,

4
x
x

Шаг 4.
?

t
x

Нет. Переход на начало второго шага
Пятая итерация. Шаг 2.

t
S


,
 


23 9
19
,
23
min




t
d
Шаг 3.
 
 
t
d



23 23
min
,

t
x

Шаг 4.
?

t
x

Да. Конец первого этапа.
Этап 2. Кратчайший путь здесь очевиден, это путь

 

t
x
x
s
,
,
μ
2 2
1



. Максимальный поток по этому пути
 


11 17
,
11
min
μ
1
min max




c

Так как
18
θ

, то
θ
max


; требуется модификация сети.
Положим






0
,
и
11
,
,
2 2



j
i
x
x
t
x
x
s



для остальных дуг. Тогда по третьему пункту правил модификации сети включим обратные дуги


s
x ,
2
и


2
, x
t
. При этом




 
,
11
,

,
10
,
,
11
,

2 2
2




x
t
c
s
x
d
s
x
c


13
,

2


x
t
d
1
x
3
x По четвертому пункту правил характеристики
9(6) всех дуг, где нет потока останутся без изменений,
-13(17) для дуг потока
11


, т. е. только для дуги
9(13)


t
x ,
2
изменятся характеристики


13
,

2

t
x
d
,
s 7(11) 9(14) t
 
,
6 11 17
,

2



t
x
c
По пятому пункту правил
12(11) для насыщенной дуги

 

0
,

,
2 2

x
s
c
x
s
,

(0) 13(6) 9(10)


,

2


x
s
d
В результате имеем новую сеть
-10(11)
2
x 9(13)
4
x


D
U
S
G
,
,

(см. рис. 3.73). Необходимо найти
Рис. 3.73.
кратчайший путь между s и t в этой сети. Так как теперь есть дуги с отрицательным весом, следует применить алгоритм Беллмана – Мура.
Этап 1.
 
   
 
 
,
,
0 2
1
s
Q
t
d
x
d
x
d
s
d







Первая итерация. Шаг 2.


Q
s
x
,

Ø,


2 1
,

x
x
S

,
 


9 9
0
,
min
1




x
d
,
?
9


Да, корректировка очереди.
 
1
x
Q

 








0
,
min
2
x
d
,
?



. Нет, корректировка очереди не проводится.
Шаг 3.

Q
Ø? Нет.
Вторая итерация. Шаг 2.
 



1 1
/
,

x
Q
Q
x
x
Ø,


3 2
,

x
x
S

,
 


21 12 9
,
min
2




x
d
,
?
21


Да, корректировка очереди.
 
2
x
Q

 


18 9
9
,
min
3




x
d
,
?
18


. Да.


3 2
, x
x
Q

Шаг 3.

Q
Ø? Нет.
Третья итерация. Шаг 2.
 
3 2
,

x
Q
x
x


,


4 3
,
,

x
x
s
S

,
?
0 0

Нет, корректировка очереди не проводится.
 


18 7
21
,
18
min
3



x
d
,
?
18 18

Нет.
 


30 9
21
,
min
4




x
d
,
?
30


Да, корректировка очереди.


4 3
, x
x
Q

 


34 13 21
,
min




t
d
,
?
34


Да, корректировка очереди.


t
x
x
Q
,
,
4 3


104
Шаг 3.

Q
Ø? Нет.
Четвертая итерация. Шаг 2.
 
t
x
Q
x
x
,
,

4 3


,
 
4

x
S

 


30 13 18
,
30
min
4



x
d
,
?
30 30

Нет, очередь не корректируется.
Шаг 3.

Q
Ø? Нет.
Пятая итерация. Шаг 2.

t
Q
x
x


,

4
,

t
S


 


34 9
30
,
34
min



t
d
,
?
34 34

Нет, очередь не корректируется.
Шаг 3.

Q
Ø? Нет.
Шестая итерация. Шаг 2.


Q
t
x
,

Ø,

S

Ø.
Шаг 3.

Q
Ø? Да. Конец первого этапа алгоритма Беллмана – Мура.
Итак, кратчайший путь найден. Это путь

 
 

t
x
x
x
x
s
,
,
,
μ
2 2
1 1
2




. Его вес
 
34 13 12 9
μ
2





d
 


6 6
,
11
,
13
min
μ
2
min max




c

Общий поток по двум уже рассмотренным путям равен
θ
18 17 6
11





общ

, т. е. требуется еще одна модификация сети.
Положим опять










0
,
и
11
,
,
6
,
,
,
2 2
2 1
1





j
i
x
x
x
s
t
x
x
x
x
s





для остальных дуг. По третьему пункту правил включаем обратные дуги


s
x ,
1
,


1 2
, x
x
и
 
2
, x
t
, причем последняя дуга уже присутствует.
Полагаем




9
,

,
6
,

1 1



s
x
d
s
x
c
,








13
,

,
17
,

,
12
,

,
6
,

2 2
1 2
1 2






x
t
d
x
t
c
x
x
d
x
x
c
. По четвертому пункту правил все ненасыщенные дуги, где нет потока, остаются без изменений, кроме дуг с потоком


s
x ,
1
,


2 1
, x
x
. Здесь








12
,

,
5 6
11
,

,
9
,

,
7 6
13
,

2 1
2 1
1 1








x
x
d
x
x
c
x
s
d
x
s
c
. По пункту пять правил для насыщенной дуги
 
t
x ,
2







t
x
d
t
x
c
,

,
0
,

2 2
. В полученной после второй модификации сети


D
U
S
G
,
,

необходимо найти кратчайший путь между вершинами s и t . Так как опять имеются отрицательные веса, то снова придется применить
1
x
3
x алгоритм Беллмана – Мура (см. рис. 3.74).
9(6) Этап 1. Шаг 1.
 
 
 





t
d
x
d
s
d
,
0 1
-9(6)
 
s
Q

9(7) -12(6) Шаг 2.


Q
s
x
,

Ø,


2 1
,

x
x
S

,
s 7(11) 9(14) t
 


?
9
,
9 9
0
,
min
1






x
d
Да.
 
1
x
Q

,
12(5)
 


,
0
,
min
2






x
d

(0)

(0) 9(10) Шаг 3.

Q
Ø. Переход на второй шаг.
-10(11)
2
x 9(13)
4
x Вторая итерация. Шаг 2.


Q
x
x
,

1
Ø,
Рис. 3.74.
-13(7)


3 2
,
,

x
x
s
S

,
 


,
0 9
9
,
0
min



s
d
?
0 0

, нет корректировки очереди.
 


21 12 9
,
min
2




x
d
,
?
21


Да.
 
2
x
Q

 


18 9
9
,
min
3




x
d
,
?
18


Да.


3 2
, x
x
Q

Шаг 3.

Q
Ø. Переход на второй шаг.
Третья итерация. Шаг 2.
 


t
x
x
x
s
S
x
Q
x
x
,
,
,
,

,
,

4 3
1 3
2



 


,
0 10 21
,
0
min



s
d
нет корректировки очереди,
 


,
9 12 21
,
9
min
1



x
d
нет корректировки очереди,
 


,
18 7
21
,
18
min
3



x
d
нет корректировки очереди,

105
 


,
30 9
21
,
min
4




x
d


4 3
, x
x
Q

,
 


,
21
,
min






t
d
нет корректировки очереди.
Шаг 3.

Q
Ø. Переход на второй шаг.
Четвертая итерация. Шаг 2.
 
 
4 4
3

,
,

x
S
x
Q
x
x



 


,
30 14 18
,
30
min
4



x
d
нет корректировки очереди.
Шаг 3.

Q
Ø.
Пятая итерация. Шаг 2.


Q
x
x
,

4
Ø,

t
S


,
 


,
39 9
30
,
min




t
d

t
Q

Шаг 3.

Q
Ø.
Шестая итерация. Шаг 2.


Q
t
x
,

Ø,

S

Ø.
Шаг 3.

Q
Ø. Конец первого этапа. Критический путь найден.

 
 
 

,
,
,
,
μ
4 4
2 2
1 1
3
t
x
x
x
x
x
x
s





Его вес
 
39 9
9 12 9
μ
3






d
 


5 10
,
13
,
5
,
7
min
μ
3
min max




c

Таким образом, по этому пути можно пустить поток в пять единиц. Тогда общий поток будет равен
18
θ
22 5
17





общ

Для того, чтобы сформировать поток требуемой величины
18
θ

, необходимо по пути

3
μ
направить поток величиной всего в одну единицу.
Тогда






 
1
,
,
1
,
,
7
,
,
7
,
4 4
2 2
1 1




t
x
x
x
x
x
x
s




Кроме того два предыдущих потока дали


 
17
,
,
11
,
2 2


t
x
x
s


Таким образом, минимальная стоимость всего потока
18
θ

равна

 



















S
x
x
j
i
j
i
j
i
x
x
x
x
d
,
496 1
9 1
9 17 13 11 10 7
12 7
9
,
,

3.27. Элементы сетевого планирования. Критические пути, работы, резервы
При планировании и управлении сложными комплексами работ используются их графические модели – сетевые графики. С математической точки зрения сетевой график – это связный орграф без петель и контуров. Основными понятиями сетевого планирования являются понятия работы и события.
Последовательность работ
Исходная работа
Опирается на работу
Продолжи- тельность работ
1
a
-
3 2
a
-
6 3
a
-
4 4
a
1
a
5 5
a
2
a
1 6
a
2
a
9 7
a
5 3
, a
a
6 8
a
7 6
4
,
,
a
a
a
8
Работа – это любые действия, сопровождающиеся затратами ресурсов и времени и приводящие к определенным результатам. Событие – это результат завершения одной или нескольких работ. Событие является предпосылкой для выполнения работ, следующих за

106 ним. Любая работа на сети может быть определена двумя событиями, между которыми она находится. Событием может начинаться или заканчиваться несколько работ. Работы на сети изображают дугами, а события – вершинами сети.
Сетевой график обладает рядом особенностей, в частности он имеет только одно исходное событие (исток сети) и только одно завершающее событие – окончание всех работ.
Рассмотрим пример построения сети по приведенной ранее таблице последовательности работ.
Работы
2 1
, a
a
и
3
a не имеют предшествующих, поэтому реализация проекта начинается с этих работ, и изобразятся они дугами, выходящими из одной вершины – собы-
2
x тия
1
x . Работе
4
a предшествует рабо-
4
a та
1
a , поэтому дуга
4
a на сети изобра-
1
a жена вслед за дугой
1
a .То же самое с
1
x
s

3
x
5
x
6
x
t

дугами
5
a и
6
a . Далее надо изобразить
2
a
6
a
8
a дуги
7
a и
8
a . Работа
7
a опирается на
3
a
5
a
7
a работы
3
a и
5
a . Итоговая работа
8
a опирается на
4
a ,
6
a и
7
a . На рисун-
4
x ках сети не рекомендуется во избежа-
Рис. 3.75. ния путаницы изображать одновремен- но выполняемые работы параллельными дугами. Однако можно вводить дополнительные события и фиктивные работы (нулевой продолжительности), которые изображаются штриховыми линиями. Если бы, к примеру, работа
5
a опиралась бы еще на
1
a , то между событиями
2
x и
3
x пришлось бы ввести штриховую дугу (см. рис. 3.75).
Имея сеть работ некоторого проекта можно посчитать время выполнения всего проекта и различных его частей, состоящих из разного набора работ. Для этого введем еще несколько определений. Определим сначала минимальное время, за которое можно выполнить все работы комплекса. Для этого найдем продолжительность
 
i
t
μ всех полных путей
i
μ . В нашем случае таких путей четыре:
;
6 5
3 1
:
;
6 5
2 1
:
μ
2 1







6 5
4 3
1
:
μ
;
6 5
4 1
:
μ
4 3







Их продолжительности
 
16
μ
1

t
,
 
23
μ
2

t
,
 
18
μ
3

t
,
 
21
μ
4

t
. Наиболее продолжителен второй путь. Такой путь называют критическим. Этот путь определяет минимальное время выполнения всех работ комплекса. Минимальное время называют критическим сроком и обозначают
кр
t
. Итак, в рассматриваемом примере
23

кр
t
Все работы и события, лежащие на критическом пути, называют критическими, все остальные работы и события – некритическими. Задержка любой критической работы вызывает задержку выполнения всего комплекса. Следовательно, чтобы уменьшить время выполнения комплекса работ, надо сократить сроки критических работ. Некритические работы допускают некоторое запаздывание их выполнения без нарушения критического срока. Это запаздывание измеряется резервом времени событий и работ.
Свершением события называется момент, к которому заканчиваются все входящие в него работы, и может быть начата любая выходящая работа. Некоторые события можно совершать в разные моменты, то есть варьировать свершение этих событий. Например, событие
2
x может свершиться через три дня (по окончании работы
1
a ), но может наступить и позже на срок до семи дней, поскольку на пути
1
μ , где лежит это событие, есть резерв времени
 
7 16 23
μ
1




t
t
кр
дней. Поэтому для событий различают ранний и поздний сроки свершения.

107
Ранним сроком
 
j
p
x
t
свершения события
j
x
называется самый ранний момент времени, к которому завершатся все работы, предшествующие этому событию. Ранние сроки для всех событий могут быть рассчитаны по формуле
 


 




,
,
max
,
j
i
i
p
U
x
x
j
p
x
x
t
x
t
x
t
j
j
i




(3.27.1) где

j
U - множество работ, входящих в
j
x
событие,
 
i
p
x
t
- ранний срок свершения начального события работы


j
i
x
x ,
,


j
i
x
x
t
,
- продолжительность работы


j
i
x
x ,
Поздним сроком
 
i
п
x
t
свершения события
i
x называется самый поздний момент времени, после которого остается ровно столько времени, сколько необходимо для завершения всех работ, следующих за этим событием.
В нашем случае
 
23 6

x
t
п
. Чтобы не нарушался критический срок, событие
5
x должно произойти, в крайнем случае, на восемь дней раньше, поэтому
 
15 8
23 5



x
t
п
Аналогично,
 
10 5
15 2



x
t
п
. Таким образом, поздние сроки событий рассчитываются по формуле
 


  



,
,
min
,
j
i
j
п
U
x
x
i
п
x
x
t
x
t
x
t
i
j
i




(3.27.2) где

i
U
- множество работ, выходящих из
i
x события,
 
j
п
x
t
- поздний срок свершения конечного события работы


j
i
x
x ,
Разности между поздним и ранним сроками свершения события
i
x составляет резерв времени
 
i
x
R
этого события
 
 
 
i
p
i
п
i
x
t
x
t
x
R


(3.27.3)
Резерв показывает, на какой предельно допустимый срок может задержаться свершение события
i
x без изменения срока наступления итогового события t . У критических событий ранние и поздние сроки совершения совпадают, ибо резерв времени у них равен нулю.
Зная сроки свершения событий, можно найти ранние и поздние сроки начала и окончания работы


j
i
x
x ,
. Очевидно, что


 


 



  

   










,
,
,
,
,
,
,
,
,
j
i
j
п
j
i
н
п
j
п
j
i
о
п
j
i
i
p
j
i
o
p
i
p
j
i
н
p
x
x
t
x
t
x
x
t
x
t
x
x
t
x
x
t
x
t
x
x
t
x
t
x
x
t
(3.27.4)
Для работ определяются два резерва времени. Полный резерв времени работы – это максимальное количество времени, на которое можно задержать начало работы или увеличить ее продолжительность, не нарушая критический срок

  
 


,
,
j
i
i
p
j
п
j
i
п
x
x
t
x
t
x
t
x
x
R



(3.27.5)
Формулу (3.275) можно проиллюстрировать следующим рисунком.


j
i
п
x
x
R
,


j
i
x
x
t
,
 
i
p
x
t
 
i
п
x
t
 
j
p
x
t
 
i
п
x
t
Рис. 3.76.
Отдельные работы, помимо полного резерва, имеют свободный резерв времени, составляющий часть полного резерва, остающуюся после исключения резерва времени
 
j
x
R
конечного события
j
x
данной работы


 
 


,
,
j
i
i
p
j
p
j
i
c
x
x
t
x
t
x
t
x
x
R



(3.27.6)
Свободный резерв времени – это запас времени, на который можно отсрочить начало работы или увеличить ее продолжительность при условии, что она начнется в свой ранний

108 срок и при этом ранние сроки начала последующих работ не изменятся. Понятно, что все резервы критических работ равны нулю.
Рассчитаем все резервы времени для событий и работ исходного примера.
2 3 10 1
a 7 4
a
1 3 5 6 0 0 2
a 6 6 6
a 15 15 8
a 23 23 0 0 0 0 5
a
3
a 4 8
a
i
x
7 9
 
i
p
x
t
 
i
п
x
t
2
 
i
x
R
Рис. 3.77.
Все расчеты проводятся в четыре этапа: 1) вычисляют
 
i
p
x
t
; 2)
 
i
п
x
t
; 3)
 
i
x
R
; 4) критический путь.
Этап 1. При вычислении
 
i
p
x
t
перемещаются по сети от события
1
x
s

к событию t в порядке возрастания номеров. Именно,
 
0 1

x
t
p
. Для события
2
x по формуле (3.27.1)
 
  

3 3
0
,
2 1
1 2





x
x
t
x
t
x
t
p
p
Аналогично,
 
  

6 6
0
,
3 1
1 3





x
x
t
x
t
x
t
p
p
Для вершин
4
x и
5
x формулу (3.27.1) необходимо применять в полном объеме, то есть
 




  
   







4 3
3 4
1 1
,
,
,
4
,
,
,
max
4 3
4 1
x
x
t
x
t
x
x
t
x
t
x
t
p
p
x
x
x
x
p


7 1
6
,
4 0
max



,
 






  
   
   








5 4
4 5
3 3
5 2
2
,
,
,
,
,
5
,
,
,
,
,
max
5 4
5 3
5 2
x
x
t
x
t
x
x
t
x
t
x
x
t
x
t
x
t
p
p
p
x
x
x
x
x
x
p


15 6
7
,
9 6
,
5 3
max




Наконец,
 
  

23 8
15
,
6 5
5 6





x
x
t
x
t
x
t
p
p
Получили критический срок. Итак,
 
23 6


x
t
t
p
кр
Этап 2. При вычислении поздних сроков свершения событий перемещаются по сети от t к s в порядке убывания номеров. Так как
 
 
6 6
x
t
x
t
p
п

, то исходное значение
п
t известно. Далее используем формулу (3.27.2).
Например,
 
  

15 8
23
,
6 5
6 5





x
x
t
x
t
x
t
п
п
Аналогично,
 
  

9 6
15
,
5 4
5 4





x
x
t
x
t
x
t
п
п
,
 
  

10 5
15
,
5 2
5 2





x
x
t
x
t
x
t
п
п
Из события
3
x выходят две работы
5
a и
6
a
, поэтому
 




  
   





6 1
9
,
9 15
min
,
,
,
min
4 3
4 5
3 5
,
,
,
3 4
3 5
3







x
x
t
x
t
x
x
t
x
t
x
t
п
п
x
x
x
x
п
. Наконец, из события
1
x выходят сразу три работы
1
a ,
2
a и
3
a
Поэтому здесь
 






  
   
   





0 4
9
,
6 6
,
3 10
min
,
,
,
,
,
min
4 1
4 3
1 3
2 1
2
,
,
,
,
,
1 4
1 3
1 2
1









x
x
t
x
t
x
x
t
x
t
x
x
t
x
t
x
t
п
п
п
x
x
x
x
x
x
п
Этап 3. Для вычисления резервов времени событий достаточно вычесть числа, записанные в правых и левых секторах кружков, друг из друга.
Этап 4. У критических событий резерв времени равен нулю. В нашем примере критическими являются события
1
x ,
3
x ,
5
x и
6
x
. Они и определяют критические работы и критический путь 1-3-5-6.

109
Резервы времен работ сети вычисляются по формулам (3.27.4), (3.27.5) и (3.27.6).
Например,


  

3 3
0
,
,
2 1
1 2
1





x
x
t
x
t
x
x
t
p
o
p
,


 
0
,
1 2
1


x
t
x
x
t
p
н
p
,


 
10
,
2 2
1


x
t
x
x
t
п
о
п
,


  

,
7 3
10
,
,
2 1
2 2
1





x
x
t
x
t
x
x
t
п
н
п


 
  

,
7 3
0 10
,
,
2 1
1 2
2 1







x
x
t
x
t
x
t
x
x
R
p
п
п


 
  

3 3
0 3
,
,
2 1
1 2
2 1







x
x
t
x
t
x
t
x
x
R
p
p
c
В заключение заметим, что критических путей на сети может быть несколько. Они могут включать в себя и фиктивные работы.