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

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

57
3. ОСНОВНЫЕ ТИПЫ ЗАДАЧ И СПОСОБЫ ИХ РЕШЕНИЯ
●
Сетевая модель
– графическое изображение плана выполнения ком-
плекса работ, состоящего из нитей (работ) и узлов (событий), которые отража-
ют логическую взаимосвязь всех операций. В основе сетевого моделирования
лежит изображение планируемого комплекса работ в виде графа. Граф-схема,
состоящая из заданных точек (вершин), соединенных системой линий. Отрезки,
соединяющие вершины, называются ребрами (дугами) графа.
Ориентирован-
ным называется такой граф, на котором стрелкой указаны направления всех его
ребер (дуг), что позволяет определить, какая из двух его граничных вершин яв-
ляется начальной, а какая – конечной. Исследование таких сетей проводится
методами теории графов.
Теория графов оперирует понятием пути, объединяющим последователь-
ность взаимосвязанных ребер. Контур означает такой путь, у
которого началь-
ная вершина совпадает с конечной. Сетевой график – это ориентированный
граф без контуров. В сетевом моделировании имеются два основных элемента
работа и событие.
●
Работа
– это активный процесс, требующий затрат ресурсов, либо пас-
сивный (ожидание), приводящий к достижению намеченного результата.
●
Фиктивная работа
– это связь между результатами работ (событиями),
не требующая затрат времени и ресурсов.
●
Событие
– это результат (промежуточный или конечный) выполнения
одной или нескольких предшествующих работ.
●
Путь
– это любая непрерывная последовательность (цепь) работ и со-
бытий.
●
Критический путь
– это путь, не имеющий резервов и включающий
самые напряженные работы комплекса. Работы, расположенные на критиче-
ском пути, называют критическими. Все остальные работы являются некрити-
ческими (ненапряженными) и обладают резервами времени, которые позволяют
передвигать сроки их выполнения, не влияя на общую продолжительность вы-
полнения всего комплекса работ.
При построении сетевых моделей
необходимо соблюдать следующие
правила.
1. Сеть изображается слева направо, и каждое событие с большим поряд-
ковым номером изображается правее предыдущего. Общее направление стре-
лок, изображающих работы, также в основном должно быть расположено слева
направо, при этом каждая работа должна выходить из события с меньшим но-

Страницы