Переход от графа к сетевой модели комплекса работ

Поставим на графе прикладную экономико-управленческую задачу и назовем ее задачей управления проектом. Пусть дан ориентированный связный граф без циклов G(N,А). Зададим на нем некоторую функцию Т, таким образом, что каждой дуге графа (ij)ÎА поставим в соответствие некоторое неотрицательное число t_ij . Назовем дуги графа работами, а вершины - событиями. Числа t_ij назовем продолжительностями работ.

 

                                                                                          Таблица 3.2

		Вершины-потомки										Пошаговые суммы
		А	Б	В	Г	Д	Е	Ж	З	И	К	S1	S2	S3	S4
Вершины-предки	А				1							1	0	-----------
	Б	1		1	1		1					4	3	1	0
	В				1			1	1			3	2	0	------
	Г											0	----------------
	Д			1			1	1	1	1		5	5	2	0
	Е										1	1	0	-----------
	Ж										1	1	0	-----------
	З										1	1	0	-----------
	И							1	1			2	2	0	----
	К											0	---------------
Пошаговые суммы	S1	1	0	2	3	0	2	3	3	1	3
	S2	0	------------	0	2	-----------	0	2	2	0	3
	S3	------		------	0		------	0	0	------	2
	S4				--			--	--		0

 

       Слой 1             Слой 2           Слой 3         Слой 4  

                                                                 5

                                                                   А           

       1 Б                                                                          9

                                    3                                                      Г

                                         В                  6

                                                                     Ж

       2 Д                                                                         10

                                                                   7                           К

                                                                      Е

                                     4                  8

                                         И                     З

 

Рис. 3.5. Граф после упорядочения вершин методом исключения потомков и перенумерации вершин

 

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

Фиктивная работа не требует затрат времени или других ресурсов: t_ij = 0; она отражает лишь логическую взаимосвязь между событиями (за i следует j). Обозначается фиктивная работа, как правило, пунктирной стрелкой.

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

        Слой 1          Слой 2          Слой 3         Слой 4  

                                   3

                                      А           

       1 Б                                                     7

                                    4                           Г

                                        В                        8

                                                                     Ж

       2 Д                5                                                 10

                                         Е                                                К

            

                                     6                           9

                                         И                     З

 

Рис. 3.6. Граф после упорядочения вершин методом исключения предков и перенумерации вершин

 

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

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

  а)                                                         б)

   

 

 

Рис. 3.7. Пример избавления от тупика первого рода в сети с помощью двух фиктивных работ: а – технически неверно выполненное начало сети; б – начало сети соответствует требованиям к сетевым моделям проектов

 

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

                                                    б)

а)                                   

 

 

Рис. 3.8. Технически недопустимое (а) и правильное (б) изображение одной и той же логической связи между четырьмя работами

 

Для более наглядного изображения логики взаимосвязи работ может оказаться удобным использование другой сетевой интерпретации графа, при которой узлам придается смысл работ, а дугам - событий. Она носит название "работы-связи", в отличие от введенной ранее "события-операции".

В терминах "работы-связи" фрагмент сети, изображенный на рис. 3.8, независимо от варианта а) или б), выглядит так, как представлено на рис. 3.9.

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

 

Рис. 3.9. Сеть в терминах "работы-связи"; в узлах стоят те же четыре работы, что и на рис. 3.8

В ряде случаев оказывается, что достаточно просто изображаемую в терминах «работы-связи» логическую взаимосвязь между работами не просто выразить в терминах "события-операции" (рис. 3.10).

 

     а                        б

а)

      в                       г

 

           а        б

б)

 

           в         г

Рис. 3.10. Один и тот же фрагмент графа, изображенный в терминах:

а – "работы-связи"; б – "события-операции"

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: