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

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

3.28. Линейные графики
Наряду с сетевым графиком при анализе и оптимизации комплекса работ применяется и линейный график. Построим его для нашего примера. На дугах исходного линейного графика проставлены в скобках интенсивности потребления ресурса. Найдем по этому линейному графику критический путь, критический срок, критические работы и резервы временни некритических работ. На присунке 3.78 вначале изображен исходный сетевой гра-
2
x фик для того, чтобы яснее бы-
4
a ли видны последовательности
1
a работ. Ниже – линейный гра-
1
x
s

3
x
5
x
6
x
t

фик. Он имеет две шкалы -
2
a
6
a
8
a шкалу времени и шкалу пот-
3
a
5
a
7
a ребления ресурса. Проанали- зируем линейный график. Наи-
4
x большей отметки времени на
20 на нем
23

t
соответствует
4 5 30 работа (5, 6), значение
23

t
20 5 6 и является критическим сро-
3 4 50 ком. Ясно, что будучи заклю-
3 5 чительной работой комплекса,
50 работа (5, 6) является крити-
2 5 ческой. Непосредственно ей
30 предшествует работа (3, 5) а
1 4 этой работе (1, 3); обе эти ра-
40 боты также являются крити-
1 3 ческими. Все остальные рабо-
50 ты – некритические. Крити-
1 2 ческие работы на линейном
t графике выделены жирной че-
0 5 10 15 20 ртой.
120 120 90 120 120 70 50 30 По линейному графику можно легко найти резервы шкала потребления ресурса времени
 
j
i
R
п
,
некритичес-
Рис. 3.78. ких работ. Например, работу
(4, 5) в случае необходимости можно отсрочить или увеличить время ее выполнения на два дня. То же самое касается и работы (1, 4). Ее можно сдвинуть на три дня. Таким образом,
 
2 5
,
4

п
R
,
 
5 4
,
1

п
R
. Определяя
 
4
,
1
п
R
, мы учли возможность сдвига работы (4, 5).
Если же оперировать только с работой (1, 4) и не затрагивать последующие работы, то найдется свободный резерв времени данной работы. У работы (1, 4) свободный резерв три дня, то есть
 
3 4
,
1

c
R

110
Аналогично из линейного графика получим
 
7 5
,
2

п
R
,
 
7 2
,
1

п
R
,
 
7 5
,
2

c
R
,
 
0 2
,
1

c
R
. Для построения шкалы потребления ресурса в ходе работ, спроектируем на ось
Ot начальные и конечные точки работ. В полученных промежутках нужно просуммировать интенсивности всех работ, расположенных над этими промежутками. Например, для
 
7
,
6

t
интенсивность равна 50+50+20=120 единиц.
Одной из самых распространенных оптимизационных задач сетевого планирования является задача о сохранении срока выполнения комплекса работ при ограниченных ресурсах. Она возникает в случаях, когда для реализации комплекса работ в плановой срок имеющихся ресурсов недостаточно.
Когда работ мало (одна, две) ответить на вопрос об отсрочке работ, об их очередности и тому подобное можно с точки зрения здравого смысла. Если же работ много, придется упорядочить эти работы и следить какая из них вызывает превышение ресурса. Пусть в условиях разобранного ранее примера требуется установить время начала и окончания работ так, чтобы завершить комплекс в возможно меньшее время, при условии, что расход ресурса в любой момент не должен превышать 100 единиц.
Первый шаг.
20 Рассмотрим промежуток
4 5 30
 
6
,
0

t
. Здесь расположено
20 5 6 четыре работы: (1,2), (1, 3),
3 4 50 (1, 4) и (2,5). Для выявления
3 5 работ, подлежащих отсрочке,
50 прежде всего упорядочим их.
2 5 Выпишем полные резервы
30 времени:
 
7 2
,
1

п
R
,
1 4
 
5 4
,
1

п
R
,
 
0 3
,
1

п
R
,
40
 
7 5
,
2

п
R
. В порядке воз-
1 3 растания полного резерва
50 времени присвоим номера ра-
1 2 ботам (1, 3) - № 1, (1, 4) -
t № 2, (1, 2) - № 3, (2, 5) - № 4.
0 5 10 15 20 В отведенный ресурс уклады-
70 40 120 120 120 100 50 30 ваются только две работы
№ 1 и № 2. Поэтому работу шкала потребления ресурса № 3, т. е. работу (1, 2), а след
Рис. 3.79. за ней и работу (2, 5) сдвига- ем до момента
6

t
; ресурс времени это позволяет, критический срок от этого не увеличится. Положение работ после первого шага показано на рисунке 3.79.
Второй шаг.
Рассмотрим отрезок
 
7
,
6

t
. Здесь
 
1 2
,
1

п
R
,
 
2 4
,
3

п
R
,
 
2 5
,
4

п
R
,
 
0 5
,
3

п
R
Номера работ по возрастанию полного резерва времени: (3, 5) - № 1, (1, 2) - № 2, (3, 4) - № 3,
(4, 5) - № 4. Предел ресурса полностью выбирают первая и вторая работы. Таким образом, следует сдвинуть работу (3,4), а вместе с ней и работу (4, 5) на один день вправо. Положение работ комплекса после второго шага показано на рисунке 3.80.
Третий шаг.
 
8
,
7

t
. Полные резервы времени работ на этом отрезке равны
 
1 2
,
1

п
R
,
 
0 5
,
3

п
R
,
 
1 4
,
3

п
R
. Работа (1, 2) уже длится, следовательно, сдвигать надо работу (3, 4) и следующую за ней работу (4, 5).
Четвертый шаг.
 
9
,
8

t
. Работы (1, 2) и (3, 5) уже длятся, у работы (3, 4) полный резерв времени ра-

111 20 вен нулю. Тем не менее имен-
4 5 30 но эту работу необходимо
20 5 6 сдвигать на один день вправо.
3 4 50 Вместе с ней сдвинутся рабо-
3 5 ты (4, 5) и (5, 6), тем самым
50 критический срок будет уве-
2 5 личен на один день. Положе-
30 ние работ комплекса после
1 4 четвертого шага изображено
40 на рисунке 3.81.
1 3 Пятый шаг.
50


10
,
9

t
. Полные резервы
1 2 работ на этом отрезке време-
t ни таковы:
 
2 5
,
2

п
R
,
0 5 10 15 20
 
0 5
,
3

п
R
,
 
0 4
,
3

п
R
,
70 40 100 120 120 50 30 Сдвигаем на два дня вправо шкала потребления ресурса работу (2, 5).
Рис. 3.80.
Шестой шаг.


15
,
11

t
. Работы (3, 5) и (4, 5) уже длятся, необходимо сдвигать на четыре дня впра-
20 во работу (2, 5). При этом на
4 5 30 четыре дня увеличится кри-
20 5 6 ческий срок. Теперь ресурс
3 4 50 нигде не превышен, плани-
3 5 рование работ комплекса за-
50 кончено. Итоговое положе-
2 5 ние работ изображено на ри-
30 сунке 3.82.
28

кр
t
дней.
1 4 По последнему линей-
40 ному графику составлена
1 3 следующая таблица со срока-
50 ми начала
н
t и окончания
о
t
1 2 работ комплекса.
Рассмотренный метод -
0 5 10 15 20 t эристический, он не обеспе-
70 40 100 120 120 70 20 30 чивает всегда точную мини- мизацию времени выполне- шкала потребления ресурса ния работ, но дает хорошее
Рис. 3.81.
приближение к этому. Его
Сроки
Работы
(1, 2)
(1, 3)
(1, 4)
(2, 5)
(3, 4)
(3, 5)
(4, 5)
(5, 6)
н
t
7 0
0 15 6
6 10 20
о
t
10 6
4 20 7
15 15 28 основные этапы таковы.
1) Анализируется шкала потребления ресурса, и выделяются отрезки, где это потребление превышает установленный предел.
2) Определяются на первом временном интервале, где есть превышение ресурса, работы, подлежащие отсрочке. Для этого все работы упорядочиваются по возрастанию пол- ных резервов времени. Первые номера отдают работам, начатым ранее анализируемого про-

112 20 4 5 30 20 5 6 3 4 50 3 5 50 2 5 30 1 4 40 1 3 50 1 2
t
0 5 10 15 20 25 28 70 40 100 70 50 30 шкала потребления ресурса
Рис. 3.82.
межутка.
3) Производят последовательное (по возрастанию номеров) суммирование интенсивностей потребления ресурса. Как только суммарная интенсивность превысит установленный предел, слагаемое, вызвавшее превышение, отбрасывают, а соответствующую ему работу назначают к отсрочке и так далее до полного перебора всех работ на данном промежутке.
4) Производят преобразование линейного графика: сдвигают назначенные к отсрочке работы и работы, следующие за ними. Строят новую шкалу потребления ресурса.
5) Если на преобразованной шкале вновь имеются промежутки, где суммарная потребность в ресурсе превышает предел, то алгоритм повторяется, начиная с пункта два до тех пор, пока не останется промежутков, в которых наблюдается превышение предела ресурса.
После завершения процесса оптимизации получают линейный график, по которому можно выделить критический путь. Он, как правило, отличается от критического пути исходного графика составляющими его работами. Изменится (увеличится) и продолжительность нового критического пути, то есть критический срок. Это неизбежное следствие ограничения ресурса, используемого при производстве работ комплекса.
В нашем примере работы, входящие в новый критический путь, есть:
(1, 3)-(3, 5)-(2, 5)-(5, 6), а его продолжительность увеличилась на пять дней. На практике обычно возникают еще более сложные задачи с дополнительными ограничениями на состав и сроки проведения работ. Для их решения разработаны более сложные алгоритмы сетевого планирования и составления расписаний.
3.29. Практическое занятие № 10. Потоки в сетях.
Сетевые и линейные графики
3.29.1. По данной матрице пропускных способностей дуг

графа G найти максимальный поток от вершины
1
x
s

до вершины
7
x
t

и указать минимальный разрез, отделяющий s от t .

113 1)

























































14 28 17 15 10 19 13 13 7
11 8
9 16 18 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
2)



























































9 7
4 5
5 7
12 8
6 17 11 9
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
3)

























































7 6
5 9
4 10 5
4 4
3 3
8 5
10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
4)


























































5 18 9
3 8
7 4
3 7
6 9
15 5
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
5)



























































8 14 10 13 11 12 8
11 7
26 9
10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
6)

























































7 6
9 5
12 4
11 5
6 10 12 8
8 10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
7)
























































9 15 12 11 9
16 12 10 20 17 17 7
11 14 12 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
8)


























































9 7
16 5
13 12 19 15 11 6
8 18 10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
9)

























































10 14 8
12 19 11 9
6 10 14 11 8
9 7
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
10)


























































7 12 8
6 15 24 10 6
17 9
18 8
5 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11)
























































4 15 12 8
6 15 12 18 10 12 7
12 11 9
12 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12)



























































7 14 6
13 15 10 9
10 7
9 20 11 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13)

























































13 7
8 12 4
7 8
10 19 14 10 11 8
10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
14)


























































7 5
11 8
15 9
6 19 13 7
14 15 8
7 6
5 4
3 2
1 7
6 5
4 3
2 1