Главная | Обратная связь | Поможем написать вашу работу!

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

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

Основные положения теории графов. Теория графов — область дискретной математики, которая занимается исследованием и решением разнообразных проблем, связанных с объектом, называемым графом. Первые работы по теории графов были выполнены в XVIII в. Леонардом Эйлером. Назовем графом G (N, А) совокупность двух конечных множеств: N — множества вершин или узлов гоафа и А — множества пар этих вершин, называемых ребрами графа. Из определения следует, что граф может быть задан аналитически простым перечислением элементов обоих множеств. Например:

{N}₁ⁿ = 1, 2, 3, 4, 5, 6, где число вершин п = 6;

{N}₁ⁿ = 3-6; 5-1; 2-4; 4-6; 6-5; 1-3; 2-3; 4-1, где число ребер k = 8.

Однако наибольший интерес представляет второй способ его задания — графический. Зададим на плоскости множество nb виде кружков и множество А в виде линий, соединяющих эти кружки. Тогда тот же граф будет иметь вид, представленный на рис. 4.8. Ребро считается ориентированным, если порядок следования вершин в соответствующей паре (ij) Î Aстрого задан. Такие пары называются дугами графа и изображаются на рисунках стрелками. Граф G (N, А) называется ориентированным, если все элементы его множества А - дуги.

Рис. 4.8. Граф Рис. 4.9. Ориентированный граф

Если считать заданный выше граф ориентированным, то его графическое представление будет таким (рис. 4.9). Путь в ориентированном графе - это последовательность сцепленных одинаково ориентированных дуг, т. е. это такая последовательность дуг, в которой каждая вершина, конечная для предыдущей дуги, является начальной для последующей. Цикл в графе - это путь, начинаюшийся и заканчивающийся в одной и той же вершине. На рис.4.9 есть цикл - 1-3, 3-6, 6-5, 5-1.Вырожденный цикл, состоящий из одной дуги (ii) Î А называется петлей. Цикл в неориентированном графе или цикл, составленный из дуг без учета их ориентации, называется контуром.

Граф называется связным, если при любом разбиении множества его вершин на два подмножества всегда найдется хотя бы одна дуга, принадлежащая множеству Л, связывающая вершины двух этих подмножеств. Заданный нами ранее граф — связный. Граф Н (N, А) является графом-деревом, если для него выполняются два из трех условий: 1) это связный граф; 2) число его ребер на единицу меньше числа вершин, т. е. k = п - 1; 3) он не имеет контуров. Граф Н (N, А*) является подграфом-деревом графа G (N, А), если H(N,A*) — это граф-дерево, построенный на том же множестве узлов, что и G (N, А), а множество его ребер А* & А. Один из возможных вариантов подграфа-дерева графа, изображенного на рис. 4.8, представлен на рис. 4.10.

Рис. 4.10 Подграф-дерево неориентированного графа

Для выполнения формальных преобразований и постановки прикладных задач удобна матричная форма задания графов. Полную информацию о графе дает матрица смежности вершин (матрица репрезентативности графа). Это квадратная матрица размерности п ´ п, вкоторой единицы ставятся на пересечении i-х строк и j-х столбцов для всех дуг (ij) Î А. Остальные клетки матрицы содержат нули. Если граф ориентированный, то вершинам i, называемым вершинами-предками, соответствуют строки матрицы, а вершинам j,называемым вершинами-потомками, — ее столбцы. Матрица смежности вершин графа, заданного с помощью рис. 4.9, показана в табл. 4.1.

Таблица 41

Матрица смежности вершин графа

	Вершины-потомки
1	2	3	4
Вершины-предки	1
2
3
4
5
6

Число единиц в матрице равно размерности множества А. Если граф не содержит петель, то его главная диагональ заполнена нулями Любое ребро неориентированного графа можно представить как совокупность двух противоположно направленных дуг. Это значит, что матрица репрезентативности неориентированного графа включает два полных комплекта единиц и является симметричной относительно главной диагонали.

Постановка задачи управления проектом. Пусть дан ориентированный связный граф без циклов G (N, А). Зададим на нем некоторую функцию Т таким образом, что каждой дуге графа (ij) Î Апоставим в соответствие некоторое неотрицательное число t_ij. Назовем дуги графа работами, вершины — событиями, а числа t_ij — продолжительностями работ. Работа — это некоторое действие, сопровождающееся затратами времени, материальных, трудовых и финансовых ресурсов. Фиктивная работа не требует затрат времени или других ресурсов: t_ij = 0; она отражает лишь логическую взаимосвязь между событиями (за i следует j). Обозначается фиктивная работа, как правило, пунктирной стрелкой. Событие — это промежуточный этап выполнения комплекса работ. Событие означает, что все предшествующие ему работы завершены и существуют необходимые и достаточные условия для начала следующих за ним работ. С учетом введенных определений граф представляет собой сетевую модель комплекса работ. Такую модель можно отнести к группе од-нопродуктовых моделей, так как на ней подлежит контролю только один параметр — время.

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

a) б)

Рис. 4.11. Пример избавления от тупика первого рода в сети

с помощью двух фиктивных работ:

а - технически неверно выполненное начало сети; б - начало сети соответствует требованиям к сетевым моделям проектов

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

Рис. 4.12. Технически недопустимое (а) и правильное (б)

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

⇐ Предыдущая 18 19 20 21 222324 25 26 27 Следующая ⇒