Графы и сети. Харитонова Е.В. - 73 стр.

UptoLike

Составители:

Рубрика:

Таким образом, через 384 дн. предприятие может вернуть кредит в банк. По сравне-

нию с предыдущим случаем (см. п. 2) предприятие вернет в банк деньги раньше на 424 - 384

= 40 дн.

При нормальном режиме работ критический путь составляет 200 дн., стоимость работ

= 265 тыс. р.

Критический путь уменьшен до 157 дн., минимальная стоимость работ составляет 265

+ 75 = 340 тыс. р. при максимальном режиме.

3.5 Минимизация сети

Задача минимизации сети состоит в нахождении ребер, соединяющих все

узлы сети и имеющих минимальную суммарную длину (рис. 3.17).

Рис. 3.17

На ребрах, соединяющих узлы 1, 2, 3, указаны длины. Узел 3 соединен с

узлами 1 и 2 минимальной длиной 4 + 6 = 10. Если соединить узлы 1 и 2, то

возникает цикл и получающаяся сеть не будет минимальный. Отсутствие цик-

лов в минимальной сети дало ей название «минимальное дерево – остов».

Алгоритм решения

Начнем с любого узла и соединим его с ближайшим узлом сети. Соеди-

ненные два узла образуют связное множество, а остальные – несвязное. Далее в

несвязном множестве выберем узел, который расположен ближе других к лю-

бому из узлов связного множества. Скорректируем связное и несвязное мно-

жества и будем повторять процесс до тех пор

, пока в связное множество не по-

падут все узлы сети. В случае одинаково удаленных узлов выберем любой из

них, что указывает на неоднозначность (альтернативность) «минимального де-

рева – остова».

Пример. Телевизионная фирма планирует создание кабельной сети для обслуживания

5 районов-новостроек. Числа на ребрах указывают длину кабеля (рис. 3.18). Узел 1 – телеви-

зионный центр. Отсутствие ребра между двумя узлами означает, что соединение соответст-

вующих новостроек либо связано с большими затратами, либо невозможно.

Найти такое соединение кабелем районов-новостроек, чтобы длина его была мини-

мальной.

РЕШЕНИЕ. Минимальная длина кабеля: 1 + 3 + 4 + 3 + 5 = 16 (рис. 2.19).