Сетевая модель — реферат

2.4. Задачи для самостоятельного решения.

В задачах, приводимых ниже, даны работы и их длительность. Необходимо построить сете­вую модель, разбить по слоям вершины и дуги, найти критический путь и вычислить все резервы событий и работ.

23. t(0,1)=5, t(0,2)=9, t(1,3)=7, t(1,4)=3, t(2,3)=11, t(2,5)=6, t(3,6)=7, t(4,3)=10, t(4,5)=1, t(4,7)=4, t(5,8)=15, t(6,9)=13, t(7,3)=7, t(7,6)=3, t(7,8)=6, t(7,10)=10, t(8,9)=6, t(8,10)=5, t(9,10)=8.

Решение:

Построим первоначальный рисунок заданного сетевого графика работ:





Рис.1 Изображение заданного сетевого графика

Определение. Говорят, что вершина предшествует вершине (краткая запись ), если существует путь ненулевой длины от к .

Так как в графе нет контуров, то при выполнении отношения не может выполняться (иначе из двух путей : от к и от к можно составить контур, содержащий вершины и ).

Для упорядочения вершин применяется метод разбивки графа на слои.

Разбить все вершины ориентированного связного графа без контуров на слои означает, что множество вершин графа нужно разбить на подмножества S(1), S(2),...,S(k), называемые слоями, удовлетворяющие следующим условиям :

1) все элементы данного слоя S(i) не имеют предков в следующих слоях S(i+1), S(i+2),..., S(k), элементы первого слоя не имеют предков, а элементы последнего потомков;

2) порядок вершин из одного слоя безразличен, т. е. не существует пути, соединяющего вершины одного слоя.

Разбиение на такие слои всегда существует.

Первый метод разбивки на слои.

В таблице 1 выписаны работы (дуги) и время их выполнения.

Таблица 1


Похожие работы