Основные компоненты сетевой модели.

ВВЕДЕНИЕ  

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

Методы сетевого планирования и управления (СПУ), разработанные в начале 50-х годов, широко и успешно применяются доя оптимизации планирования и управления сложными разветвленными комплексами работ, требующими участия большого числа исполнителей и затрат ограниченных ресурсов. Для оптимизации сложных сетей, состоящих из нескольких сотен работ, вместо ручного счета следует применять типовые макеты прикладных программ по СПУ, имеющиеся в составе математического обеспечения ЭВМ.

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

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

Таким образом, методы сетевого моделирования относятся к методам принятия оптимальных решений.

 

 

СЕТЕВОЕ ПЛАНИРОВАНИЕ

Упорядочение сетевого графика. Понятие о пути.

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

Правила упорядочивания:

1. Все стрелки и ориентируемые дуги должны быть направлены слева направо (в одном направлении).

2. Работа – ориентированные дуги, должны быть направлены от события с меньшим номером к событию с большим номером.

Упорядочивание сетевых графиков производится путем размещения события по слоям: на первом слое размещается начальное событие и мысленно вычеркивается из этого события все исходящие работы, на втором слое размещаются полученные события без входящих работ, вновь вычеркиваются все исходящие работы из события второго слоя. В результате формируется событие третьего слоя без входящих работ и т.д.

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

Полный путь – любая последовательность соединенных вершин от начальных до завершающих событий.

  Критический путь (L) – полный путь, имеющий наибольшую продолжительность.

 

1.4. Методы определения критического пути

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

К методам определения критического пути относят:

1. Метод простого перебора – определяются все полные пути сетевого графика, рассчитывается их длительность и выбирается путь с максимальной длительностью.

2. Графический метод – строится линейная диаграмма в декартовой системе координат, где по оси ОХ откладывается длительность работы, а по оси ОУ – сами работы. Отрезки диаграммы соединяются в пути, критическим считается тот путь, последний отрезок работы которого располагается дальше всех от нуля по оси ОХ. Сам критический путь выписывается, начиная с последнего отрезка и возвращаясь к начальному событию.

3. Метод, основанный на расчете резервов времени события – для каждого события сетевого графика рассчитываются временные характеристики. События, имеющие нулевой резерв, относятся критическому пути.

 

Характеристики работ:

1. Ранний срок начала работы:

(i,j) = (i)

2. Ранний срок окончания работ:

(i,j) =  (i) + t (i,j)

3. Поздний срок окончания работы:

 (i,j) = (j)

4. Поздний срок начала работы:

 (i,j) =  (j) – t(i,j)

5. Полный резерв времени работ:

 (i,j) = (j) - (i) – t (i,j)

 (i, j) показывает, на сколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится.

6. Частичный резерв времени первого вида:

 (i,j) = (j) - (i) – t(i,j)

 (i, j) есть часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события.

7. Свободный резерв времени:

 (i, j) =  (j) -  (i) – t (i, j)

 (i, j) представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события.

8. Независимый резерв времени работ:

 (i, j) =  (j) - (i) – t (i,j)

 (i, j) =  (i, j) – R(i)

 (i, j) – часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки.

9. Резерв времени пути:

R(L) =  – t (L)

Все резервы времени неотрицательны, вместо отрицательных величин используется ноль.

10.  Проверка резервов

 (i, j) =  (i, j), если начальное событие i принадлежит критическому пути;

 (i, j) =  (i, j), если завершающее событие j принадлежит критическому пути;

 (i, j) =  (i, j) =  (i, j), если событие (i, j) принадлежит критическому пути.

Для наглядности все временные характеристики можно представить в виде линейной диаграммы (Рис. 1.1.).

 

Рис. 1.1. Линейная диаграмма взаимосвязи временных характеристик.

УПРАВЛЕНИЕ СЕТЕВЫМ ГРАФИКОМ

Стоимость»

Для оптимизации сетевого графика используется частная оптимизация (уменьшение стоимости проекта). При использовании метода «время - стоимость» предполагают, что уменьшение продолжительности работ пропорционально возрастанию ее стоимости. Каждая работа (i, j) характеризуется продолжительностью t (i, j), которая может находиться в пределах

 , где

a (i, j) - минимальная возможная продолжительность работы (i, j);

b (i, j) - максимальная продолжительность этой работы;

t (i, j) - наиболее вероятная продолжительность работы (i, j).

При этом стоимость C (i, j) работы (i, j) заключена в границах:

С_max - минимальная стоимость работы, оптимистическая оценка стоимости работы, стоимость при минимальных сроках выполнения работы;

C_min - максимальная стоимость работы, пессимистическая оценка стоимости работы, стоимость при максимальных сроках выполнения работы.

Далее при оптимизации вычисляют:

h (i, j) - коэффициент увеличения затрат от ускорения работы (i, j);

C (i, j) - наиболее вероятная стоимость проекта

Таким образом, увеличение продолжительности работ может привести к уменьшению стоимости проекта, но продолжительность каждой работы целесообразно увеличить на такую величину, чтобы не изменить ранние сроки наступления всех событий сети. Это означает с одной стороны - продолжительность каждой работы можно увеличить на свободный резерв времени, с другой - эта продолжительность не должна превышать предельно допустимую продолжительность b (i, j).

Оптимальную продолжительность работы можно найти на основе соотношения:

 или

где ;.

В этом случае стоимость выполнения работы находят по формуле:

Оптимизированный проект имеет суммарную стоимость:

 

Коэффициенты напряженности

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

 

Где t (L_max) - продолжительность отрезка максимального пути, проходящего через данную работу;

t ^' _кр – продолжительность отрезка максимального пути, совпадающего с критическим путем;

t _кр – продолжительность критического пути.

Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам:

К_н(i, j)>0,8 – критическая зона;

0,6≤К_н≤0,8 – подкритическая зона;

К_н<0,6 – резервная зона.

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

 

 

СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

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

При определении временных параметров сетевого графика до сих пор предполагалось, что время выполнения каждой работы точно известно. Допустим, продолжительность работы t (i, j) заранее неизвестна, т.е. является случайной величиной и задается законом распределения. Следовательно, характеризуется своими числовыми характеристиками:

(i, j) – среднее значение или математическое ожидание;

σ² (i, j) – дисперсия (мера отклонения от среднего значения).

В этих условиях полагаем:

§ закон распределения непрерывный;

§ закон распределения является унимодальной функцией (функция, имеющая единственный интервал возрастания и единственный интервал убывания);

§ закон распределения имеет две точки пересечения с осью абсцисс;

§ закон распределения обладает положительной асимметрией (максимум кривой смещен влево относительно медианы).

Этим свойством удовлятворяет β – распределение.

Для определения числовых характеристик (i, j) и σ² (i, j) на основе экспертных оценок задают величины:

1. t_onm (i, j)= a (i, j) – оптимистическая оценка, т. е. продолжительность работы при благоприятных условиях;

2. t_nec (i, j)= b (i, j) – пессиместическая оценка, т.е. продолжительность работы при неблагоприятных условиях;

3. t _нв (i, j)= { t (i, j) } – наиболее вероятная оценка.

В этом случае для β – распределения можно получить соотношения:

При достаточно большом количестве работ, принадлежащих некоторому пути L можно использовать предельную теорему Ляпунова: Если случайная величина X представляет собой сумму очень большого числа взаимно независимых случайных величин, влияние каждой из которых на всю сумму ничтожно мало, то случайная величина X имеет распределение, близкое к нормальному распределению.

На основании этой теоремы можно утверждать, что продолжительность пути имеет нормальный закон распределения со средним значением  и дисперсией

где

В рамках планирования в условиях неопределенности могут решаться две взаимообратные задачи:

1. Оценка вероятности того, что срок выполнения проекта t _кр не превзойдет заданного директивного срока T находится по формуле:

2. Обратная задача: определение максимального срока выполнения проекта T, который возможен с заданной надежностью β.

z_β – нормированное отклонение случайной величины, определяемой функцией Лапласа 𝜱 (z_β)= β.

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

Содержание лабораторного практикума

1. Выбрать сетевой график согласно выданному варианту;

2. Провести проверку соответствия сетевого графика требованиям;

3. Упорядочить сетевой интерфейс;

4. Определить критический путь (критические пути) сетевого графика методом простого перебора и графическим методом;

5. Расчитать временные характеристики событий и работ сетевого графика;

6. Провести оптимизацию сетевого графика по методу «Время – Стоимость»

7. Рассчитать коэффициенты напряженности работ и сгруппировать их по зонам;

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

 

Требования к выполнению лабораторных работ

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

2.Лабораторная работа должна содержать:

· Титульный лист;

· Содержание лабораторной работы;

· Выполненные задания с подробными расчетами и формулами;

· Заключение;

· Список использованных источников.

3. Лабораторная работа сдается на бумажном носителе.

 

Варианты заданий

1.

 

 

2.

 

ВВЕДЕНИЕ  

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

Методы сетевого планирования и управления (СПУ), разработанные в начале 50-х годов, широко и успешно применяются доя оптимизации планирования и управления сложными разветвленными комплексами работ, требующими участия большого числа исполнителей и затрат ограниченных ресурсов. Для оптимизации сложных сетей, состоящих из нескольких сотен работ, вместо ручного счета следует применять типовые макеты прикладных программ по СПУ, имеющиеся в составе математического обеспечения ЭВМ.

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

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

Таким образом, методы сетевого моделирования относятся к методам принятия оптимальных решений.

 

 

СЕТЕВОЕ ПЛАНИРОВАНИЕ

Основные компоненты сетевой модели.

Основными понятиями сетевых моделей являются понятия события и работы.

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

Термин работа используется в СПУ в широком смысле:

1.Действительная работа – протяженный во времени процесс, требующий затрат ресурсов. Каждая действительная работа должна быть конкретной, четко описанной и иметь ответственного исполнителя.

2.Ожидание – протяженный во времени процесс, не требующий затрат.

3.Зависимость или фиктивная работа – логическая связь между двумя или несколькими работами (событиями), не требующими затрат труда, материальных ресурсов или времени. Она указывает, что возможность одной работы непосредственно зависит от результатов другой. Естественно, что продолжительность фиктивной работы принимается равной нулю.

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

Таким образом, начало и окончание любой работы описываются парой событий, которые называются начальными и конечным событиями. Поэтому для идентификации конкретной работы используют код работы (i, j), состоящий из номеров начального (i -го) и конечного (j -го) событий.

                             

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

 

1.2. Методические рекомендации по построению сетевых моделей.

При построении сетевого графика необходимо соблюдать ряд правил:

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

 

 

                                                               

2. В сетевых графиках не должно быть «хвостовых» событий, т.е. событий, не имеющих входящих работ (кроме начального события).

 

                                                                   

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

 

 

                                                                        

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

4. Два события соединяются не более чем одной работой.

 

                                                           

5. В сетевых графиках должно быть только одно исходное и одно завершающее событие.