3. Задания по теме "Сетевые модели"
Задание 7. Районной администрацией принято решение о газификации одного из небольших сел района, имеющего 10 жилых домов. Расположение домов указано на рис. 1. Числа в кружках обозначают условный номер дома. Узел 11 является газопонижающей станцией.
Разработать такой план газификации села, чтобы общая длина трубопроводов была наименьшей. Значения коэффициентов условия задачи:
Решение:
Составим расчетную матрицу по данному графу:
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
А8 |
А9 |
А10 |
А11 |
|
А1 |
0 |
80 |
|
|
|
|
|
|
|
|
170 |
|
А2 |
80 |
0 |
100 |
|
|
|
|
|
|
|
230 |
|
А3 |
|
100 |
0 |
120 |
|
|
|
|
|
|
|
|
А4 |
|
|
120 |
0 |
60 |
|
|
|
|
|
330 |
|
А5 |
|
|
|
60 |
0 |
150 |
|
|
|
|
|
|
А6 |
|
|
|
|
150 |
0 |
80 |
220 |
|
|
340 |
|
А7 |
|
|
|
|
|
80 |
0 |
|
100 |
|
|
|
А8 |
|
|
|
|
|
220 |
|
0 |
30 |
30 |
470 |
|
А9 |
|
|
|
|
|
|
100 |
30 |
0 |
30 |
|
|
А10 |
|
|
|
|
|
|
|
30 |
30 |
0 |
530 |
|
А11 |
170 |
230 |
|
330 |
|
340 |
|
470 |
|
530 |
0 |
Выписываем все ребра в порядке возрастания их веса, затем, если при
добавлении ребра, не образуется цикла, то оставляем его на графе и ставим
возле его веса знак плюс, иначе, не добавляем ребро и отмечаем его знаком
минус. Решение сведем в таблицу 5.
Таблица 5
|
Вершины |
Вес |
Добавление |
|
А8,9 |
30 |
+ |
|
А8,10 |
30 |
+ |
|
А9,10 |
30 |
- |
|
А4,5 |
60 |
+ |
|
А1,2 |
80 |
+ |
|
А6,7 |
80 |
+ |
|
А2,3 |
100 |
+ |
|
А7,9 |
100 |
- |
|
А3,4 |
120 |
+ |
|
А5,6 |
150 |
+ |
|
А1,11 |
170 |
+ |
|
А6,8 |
220 |
- |
|
А2,11 |
230 |
- |
|
А4,11 |
330 |
- |
|
А8,11 |
470 |
- |
|
А10,11 |
530 |
- |
После добавления вершин, строим минимальный путь, который показан на рисунке 2, выделяемый жирными линиями и находим его длину.
L=820 – длина минимального пути.
Рис 2.
Ответ: Общая длина трубопроводов равна 820
Задание 8. Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 14. На рис. 2 показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами.
Рисунок 3 – Транспортная сеть
Определить маршрут доставки груза, которому соответствуют наименьшие затраты. Значения коэффициентов условия задачи:
РЕШЕНИЕ.
Найдем минимальные затраты:
U1 =0, U2 =17, U3 =18, U4 =16,
U5 = min { U2+d25, U2+d26 +d65, U3+d36 +d65 } = min { 17+10, 17+12+17, 18+13+17} = 17
U6 = min { U3+d36, U2+d25 +d56, U3+d26} = min {18+13, 17+10+13, 18+12} = 30
U7 = min { U3+d37, U4+d48 +d87, U4+d47} = min {18+9, 16+15+22, 16+11} = 27
U8 = min { U4+d48, U4+d47 +d78, U3+d37 +d78 } = min {16+15, 16+11+22, 18+9+22} = = 31
U9 = min { U5+d59, U6+d69 } = min { 17+22, 30+18 } = min { 39, 48 } = 39
U10 = min { U6+d6,10, U7+d7,10 } = min { 30+21, 27+19 } = min { 51, 46 } = 46
U11 = min { U7+d7,11, U8+d8,11 } = min { 27+20, 31+18 } = min { 47, 49 } = 47
U12 = min { U9+d9,12, U10+d10,12 } = min { 39+37, 46+36 } = min { 76, 82 } = 76
U13 = min { U10+d10,13, U11+d11,13} = min { 46+34, 47+36 } = min { 80, 83 } = 80
U14 = min { U10+d10,14, U12+d12,14 , U13+d13,14 } = min { 46+44, 76+26, 80+25 } = min { 90, 102, 105 } = 90
Минимальные затраты по доставке груза из вершины 1 в вершину 14 равны 90.
Это пути: 1-3-7-10-14 и 1-4-7-10-14.
Ответ: Затраты по доставке груза равны 90 единиц.
Задание 9. Составить сетевой график выполнения работ и рассчитать временные параметры по данным, представленным в таблице.
На основании данных таблицы построим сетевой график (рис. 4)
4
22
2
8
13
0
1
5
6
25
11
31
3
9
16
Рис. 4
Основным временным параметром сетевого графика является продолжительность критического пути. Расчет критического пути проведем в два этапа. Рассмотрим прямой проход:
ti р.н. — ранний срок начала всех операций, выходящих из события i. Если i = 0, то t0р.н=0; tjр.н. — ранний срок начала всех операций, входящих в j, tij — продолжительность операции (i,j)
=
25дн.,
=
25+8 = 33дн.,
=
25+16 = 41 дн.,
=
max
{ 33+22, 41+31} = max
{55, 72} = 72 дн.,
=
max
{ 72+13, 41+9} = max
{85, 50} = 85 дн.,
=
85+11=96 дн.
Прямой проход закончился, начинаем обратный:
=
96 дн.,
=
96-11 = 85 дн.,
=
85-13 = 72 дн.,
=min{85-9,
72-31}= 41,
=
72–22 = 50 дн.,
=min{
50-8, 41-16} = 25 дн.,
=
25-25= 0
Задание 10. Постройте график работ, определите критический путь и стоимость работ до сжатия. Найдите критический путь и минимальную стоимость работ после сжатия.
РЕШЕНИЕ.
Составим график проведения работ (рис.5):
17 28 16 20 22 13 9
1 2 3 4 5 6 7 0
Рис.5
На проведение работ необходимо: 17+28+16+20+22+13+9=125 дн.;
2. График можно улучшить, выполняя некоторые работы параллельно. Получим график (рис.6).
3
28
22
1
2
5
6
17
9
20
4
13
16
Рис. 4
По графику путь (1,2), (2,3), (3,5) , (5,6) имеет продолжительность 76 дн.;
(1,2), (2,5), (5,6) — 46 дн.; (1,2), (2,4), (4,5) , (5,6) - 55дн. Критическим путем графика является путь, на котором находятся работы (1,2), (2,3), (3,5) , (5,6) продолжительностью 76 дн.
График улучшился на 125 — 76 = 49 дн.
График выполнения работ может быть сжат за счет выполнения некоторых операций в максимально интенсивном режиме. Вычислим наклоны кривой "затраты-продолжительность" для каждой операции. Результаты расчетов даны в табл. 6.
Таблица 6
|
Операция |
Наклон |
|
1,2 |
1 |
|
2,3 |
0,67 |
|
2,4 |
2,33 |
|
2,5 |
0,75 |
|
3,5 |
1 |
|
4,5 |
0,5 |
|
5,6 |
1,5 |
Производим сжатие операций (2,3), (2,4), (2,5), (4,5), (5,6).
3
22
22
1
2
5
6
17
7
16
4
11
13
Рис. 4
По графику путь (1,2), (2,3), (3,5) , (5,6) имеет продолжительность 68 дн.;
(1,2), (2,5), (5,6) — 40 дн.; (1,2), (2,4), (4,5) , (5,6) - 48дн. Критическим путем графика является путь, на котором находятся работы (1,2), (2,3), (3,5) , (5,6) продолжительностью 68 дн.
Таким образом, критический путь сокращен с 76 до 68 дней. Определим, сколько предприятию придется заплатить за "сжатие" критического пути:
(19−15) + (24−17) + (28−22) + (26−21) + (24−19) = 27 тыс.р.
Ответ.При нормальном режиме работ критический путь составляет 76 дн., стоимость работ — 123 тыс. р. Критический путь уменьшен до 68 дн., минимальная стоимость работ составляет 123 + 27 = 150 тыс. р. при максимальном режиме.