Элементы теории графов и их технические приложения - 51 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

51
Рассмотрим вторую дугу в таблице
4,3
u с весом 7
4,3
=
l . Снова находим все
пути, идущие от узла 3 до узла 4. 423
→→ с весом 6 и 423 →→ с весом 5.
Дуга
4,3
u также удаляется из исходного графа, т.к. 57 > . Далее
дуга
6,4
u
′
с весом
7
6,4
=
′
l
путь 654 →→ с весом 75
<
удаляется,
дуга
5,2
u
с весом
6
5,2
=l
путь 542 →→ с весом 63
<
удаляется,
дуга
2,3
u с весом 4
2,3
=l путь 23 → с весом 43
<
удаляется.
В результате выполнения шага 2 в таблице останутся дуги с весами:
ij
u
6,3
u
6,5
u
2,3
u
′
3,1
u
4,2
u
2,1
u
5,4
u
ij
l
5 4 3 3 2 1 1
Шаг 3. Выбираем первую дугу
6,3
u с весом 5
6,3
=
l . Так как по условию она входит в
граф в обязательном порядке, переходим к рассмотрению следующей дуги
6,5
u с
весом
4
6,5
=l . Для этой дуги не существует другого пути от вершины 5 к вершине 6,
оставляем ее и переходим к следующей. Аналогичная проверка показывает для дуг
2,3
u
′
,
3,1
u ,
4,2
u таких путей тоже не существует. Переходим к рассмотрению дуги
2,1
u
с весом 1. Для концевых вершин этой дуги существует путь 231
→→ , поэтому
дуга
2,1
u из графа удаляется. Дуга
5,4
u оставляется, т.к. не существует другого пути
между вершинами 4 и 5. Итак, в результате выполнения шагов 2 и 3 из исходного
графа (рис. 62) получен искомый частичный граф (рис. 63), сумма весов дуг
которого равна
∑
=
+
+
+
++= 18
6,36,55,44,22,33,1
lllllll
iK
. Множество дуг этого графа
составят дуги
6,3
u ;
6,5
u ;
2,3
u ;
3,1
u ;
4,2
u ;
5,4
u с весами 5; 4; 3; 3; 2; 1.
11. Постановка исследований оптимальных задач при наличии
ограничений.
Большое практическое значение имеет группа задач, связанных с выполнением
комплекса работ при наличии ограничений на порядок их выполнения, длительность
каждой работы, выделяемые ресурсы и т.п. С такими задачами приходится
сталкиваться при решении вопросов календарного планирования и оперативного
управления, как в производстве, так и в сфере обслуживания населения.
Задачи подобного рода
разнообразны, и их исследование проводится в рамках
различных научных дисциплин. В теории сетевого планирования основное
внимание уделяется определению порядка выполнения сложных разработок,
включающих в себя большое число взаимосвязанных работ, требующих
многочисленных исполнителей и значительных материальных затрат. В теории
упорядочения рассматриваются вопросы установления порядка выполнения
большого комплекса однородных работ с помощью
одного или нескольких
специализированных устройств, машин, приборов. В теории массового

Страницы