Сетевые методы в планировании (стр. 2 из 4)

4. Прямое (декартово) произведение графов.

Прямым произведением множеств Х{x₁.......x_n} и Y называется множество Z, элементами которого являются всевозможные пары вида x_i , y_j , где x_iÎX, y_jÎY. Обозначают: Z=X x Y.

G₃(X₃,Гх₃) = G₁(X₁,Г1х₁)ÇG₂(X₂,Г2х₂), где X₃=X1ÇX2, а Гx₃=Г1х1ÇГ2х2

Пример. (рис 2.3)

G₁(X,Гх)=G₁(X₁,Гх₁) G₂(Y,Гy)= G₂(X₂,Гх₂)

X={x₁ x₂ x₃ } Y={y₁ y₂}

Гх₁=0 Гу₁={y₁ y₁}

Гх₂={x₁ x₃} Гу₂={y₁}

Гх₃=0

Z=X x Y={x₁ y₁, x₁y₂, x₂y₁, x₂y₂, x₃y₁, x₃y₂}

Z={z₁ z₂ z₃ z₄ z₅ z₆}

Рис 2.3

7. Расширение графа.

Расширение графа - это превращение, линии, соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии.

8. Сжатие графа.

Сжатие графа - это превращение элементарного пути, соединяющего две любые вершины графа, в линию.

9. Стягивание графа.

Если граф содержит вершины Х₁ и Y₁ , то операцией стягивания называется исключение всех дуг между вершинами Х₁ и Y₁ и превращение всех вершин в одну общую вершину Х.

Некоторые числа теории графов

Пусть существует мультиграф с b вершинами, p ребрами, и R компонентами связности, тогда цикломатическое число мультиграфа определяется равенством:

V= p-b+R

Матрицы для графов

Матрицей смежности графа G(X,Гх), содержащего n вершин называется квадратная бинарная матрица А(G) n x n , c нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.

Матрицей инциденций ориентированного графа G(X,U) называется прямоугольная матрица порядка [m x n] n - мощность множества Х,m - мощность множества U. Каждый элемент которой определяется следующим образом:

1, если х_i - начало дуги U_j

a_ij = -1, если х_i - конец дуги U_j

0, если х_i - не инцидентна дуге U_j

Пример.

Построим матрицы смежности (М1) и инциденций (М2) для графа G(X,U) (рис 2.1).

Рис 2.1

Дополнительная матрица графа G(X,U) представляет собой квадратную матрицу А¹ , которая получается из матрицы смежности этого графа путем замены всех нулей единицами и наоборот.

Деревья и прадеревья

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

Прадрево - ориентированное дерево.

Корень прадерева - вершина у которой Р⁺(х)=0.

Глава 2

Календарное планирование программ сетевыми методами

Сетью называется конечный граф G(X,Y) , без циклов и петель, ориентированный в одном общем направлении от вершин V, являющимися входами графа, к вершинам W, являющимися выходами.

Сетевое планирование и управление программами включает три основных этапа: структурное планирование, календарное планирование и оперативное управление.

Этап структурного планирования начинается с разбиения программы на четко определенные операции. Затем определяются оценки продолжительности операций и строится сетевая модель (сетевой график, стрелочная диаграмма), каждая дуга (стрелка) которой отображает работу. Вся сетевая модель в целом является графическим представлением взаимосвязей операций программы. Построение сетевой модели на этапе структурного планирования позволяет детально проанализировать все операции и внести улучшения в структуру программы еще до начала ее реализации. Однако еще более существенную роль играет использование сетевой модели для разработки календарного плана выполнения программы.

Конечной целью этапа календарного планирования является построение календарного графика, определяющего моменты начала и окончания каждой операции, а также ее взаимосвязи с другими операциями программы. Кроме того, календарный график должен давать возможность выявлять критические операции (с точки зрения времени), которым необходимо уделять особое внимание, чтобы закончить программу в директивный срок. Что касается некритических операций, то календарный план должен позволять определять их резервы времени, которые можно выгодно использовать при задержке выполнения таких операций или с позиций эффективного использования ресурсов.

Заключительным этапом является оперативное управление процессом реализации программы. Этот этап включает использование ñåòåâîé ìîäåëè è êàëåíäàðíîãî ãðàôèêà äëÿ ñîñòàâëåíèÿ ïåðèîäèческих отчетов о ходе выполнения программы. Сетевая модель подвергается анализу и в случае необходимости корректируется. В этом случае разрабатывается новый календарный план выполнения остальной части программы.

Сетевая модель

Сетевая модель отображает взаимосвязи между операциями и порядок их выполнения (отношение упорядочения или следования) Как правило, для представления операции используется стрелка (ориентированная дуга), направление которой соответствует процессу реализации программы во времени. Отношение упорядоченное между операциями задается с помощью событий. Событие определяется как момент времени, когда завершаются одни операции и начинаются другие. Начальная и конечная точки любой операции описываются, таким образом, парой событий, которые обычно называют начальным событием и конечным событием. Операции, выходящие из некоторого события, не могут начаться, пока не будут завершены все операции, входящие в это событие. По принятой в СПУ терминологии каждая операция представляется ориентировано дугой, а каждое событие — узлом (вершиной). Не требуется, что длина дуги была пропорциональна продолжительности операции, а графическое изображение дуг не обязательно должно представлять прямолинейный отрезок.

1

i j

3 4

2

(а) (б)

Рис. 3.1

На рис. 3.1 а приведен типичный пример графического отображения операции i, j с начальным событием i и конечным событием j. На рис. 3.1 б показан другой пример, из которого видно, что для возможности начала операции (3, 4) требуется завершение операций (1,3) и (2, 3). Протекание операций во времени задается порядком нумерации событий, причем номер начального события всегда меньше номера конечного. Такой способ нумерации особенно удобен выполнении вычислений на ЭВМ.

Правила построения сетевой модели

Правило 1. Каждая операция в сети представляется одной и только одной дугой (стрелкой). Ни одна из операций не должна появляться в модели дважды. При этом следует различать случай, когда какая-либо операция разбивается на части; тогда каждая часть изображается отдельной дугой. Так, например, прокладку трубопровода можно расчленить на прокладку отдельных секций и рассматривать прокладку каждой секции как самостоятельную операцию.

Правило 2. Ни одна пара операций не должна определяться одинаковыми начальным и конечным событиями. Возможность неоднозначного определения операций через события появляется в случае, когда две или большее число операций допустимо выполнять одновременно. Пример этого случая приведен на рис. 3.2 а, где операции А' и В имеют одинаковые начальное и конечное события. Чтобы исключить такую «ошибку» между А и

(a) (б)

рис 3.2

конечным (начальным) событием или между В и конечным (начальным) событием, вводится фиктивная операция D . Рис. 3.2 б иллюстрирует различные варианты введения такой фиктивной операции D. В результате операции А и В определяются теперь однозначно парой событий, отличающихся либо номером начального, либо номером конечного события. Следует обратить внимание на то, что фиктивные операции не требуют затрат ни времени, ни ресурсов.

Фиктивные операции позволяют также правильно отображать логические связи, которые без их помощи нельзя задать на сети. Предположим, что в некоторой программе операции А и В должны непосредственно предшествовать С, а операции Е непосредственно предшествует только В. На рис 12.3 а эти условия отраженыневерно, так как, хотя упорядочения между А. В и С показаны правильно, из этого фрагмента следует, что операции Е должны непосредственно предшествовать обе операции А и В. Правильное представление указанных условий дает фрагмент, изображенный на рис 12.3 б в котором используется