Вероятностные сети

Оглавление

Введение 4

1.Сетевое планирование. Понятия и определения. 5

1.1.События 5

1.2.Правила  построения сетевого графа 6

1.3. расчет  временный параметров сетевого  графика 6

2.Вероятностыне сети 8

2.1.Бета-распределения 8

2.2. Метод  Монте-Карло 11

2.3.Алгоритм  метода РЕRТ 11

2.4. Задача 13

Заключение 17

Список использованной литературы 18

Приложение А 19

 

 

 

Введение

Поиски более эффективных способов планирования сложных процессов  привели к созданию принципиально  новых методов сетевого планирования и управления (СПУ).

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

Первые системы, использующие сетевые  графики, были применены в США в конце 50-х годов и получили названия СРМ (английская аббревиатура, означающая метод критического пути) и PERT (метод оценки и обзора программы). Система СРМ была впервые применена при управлении строительными работами, система PERT— при разработке систем "Поларис".

В России работы по сетевому планированию начались в 60-х годах. Тогда методы СПУ нашли применение в строительстве  и научных разработках. В дальнейшем сетевые методы стали широко применяться и в других областях народного хозяйства.

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

Но не всегда бывает известно время выполнения работ. Потому что это не всегда легко предсказать сколько именно времени будет потрачено. И тема моей курсовой будет являться как раз способом расчета всех параметров в условии не определенности( вероятности)

В своей работе я рассмотрю  для начала основные понятия сетевого планирования и потом переду непосредственно  к основной теме, а именно к вероятностным  сетям.

 

1.Сетевое планирование. Понятия и определения.

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

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

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

1. сетевые графики в терминах «дуги-операции» (под операцией понимается какая-то работа). В таких графиках вершины, называемые событиями, соответствуют моментам времени начала или окончания одной или нескольких операций, а дуги — операциям;
2. сетевые графики в терминах «дуги-связи», в которых операции изображаются вершинами сети, а дуги показывают порядок выполнения (взаимосвязь) отдельных операций.

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

1.1.События

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

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

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

1.2.Правила построения  сетевого графа

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

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

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

          5) номер начального события любой операции должен быть меньше номера ее конечного события;

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

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

После составления списка операций приступают к процедуре построения сети.

1.3. расчет временный  параметров сетевого графика

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

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

Предшествующий событию путь — это путь от исходного события до данного.

Следующий за событием путь есть путь от данного события до завершающего.

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

Характеристики событий

1. Ранний срок свершения события , j=1…N характеризующий самый ранний срок завершения события всех путей, в него входящих. Этот показатель определяется «прямым ходом» по графу модели, начиная с начального события сети.
2. Поздний срок совершения события ,i=0,…,N-1 характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей, следующих за этим событием. Этот показатель определяется «обратным ходом» по графу модели, начиная с завершающегося события сети.
3. Резерв времени события показывает, на какой срок максимально можно задержать наступления этого события, при этом не увеличивая срока выполнения работ.

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

1. Продолжительность работы :.(задается по условию задачи или исходя из нормативов времени, установленных для данного вида работ).
2. Ранний срок начала работ: .
3. Ранний срок окончания работы:
4. Поздний срок начала работы:
5. Поздний срок окончания работы:

 

2.Вероятностыне  сети

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

Расчет параметров и анализ сетей  случайной структуры связаны  с известными трудностями. Поэтому  на практике обычно применяются детерминированные сети со случайными временными оценками операций. Такие сети называются вероятностными.

При исследовании вероятностных сетей  возможны два случая: 1) операции не являются новыми, и мы приближенно  знаем для каждой из них функцию  распределения продолжительности  выполнения; 2) операции являются новыми, малоизученными, и для них функции  распределения продолжительностей неизвестны. В первом случае по известной  функции распределения нетрудно определить среднее значение (математическое ожидание) и дисперсию продолжительности выполнения каждой операции. Во втором случае применяется метод усреднения. Исходными данными для метода усреднения являются вероятностные оценки продолжительности каждой операции: а — минимальная продолжительность (оптимистическая оценка) операции; b — максимальная продолжительность (пессимистическая оценка) операции; т — наиболее вероятная продолжительность (мода) операции. Эти оценки времени задаются ответственным исполнителем или группой экспертов.

2.1.Бета-распределения

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

Функция плотности бета-распределения (рис.1) имеет вид:

 

Где p и q – параметры распределения ,зависящие от вида операций; c-нормирующий множитель,

определяемый из условия

 

 

                                           

Рисунок-1

Поизвестной функции распеределения f(t) находятся числовые характеристики опереций :

-среднее значение (математическое  ожидание) продолжительности операции:

 

-дисперсия:

 

Статистический анализ, проведенный  эмпирико-экспериментальным путем разработчиками математического аппарата системы PERT, позволил установить, что . Следовательно,

 

 

После определения математических ожиданий продолжительностей операций по формуле (1) проводится расчет временных  параметров сети, как и в детерминированном  случае. Длительность критического пути рассматривают как математическое ожидание случайной величины :

 

Дисперсию продолжительности  пути считают равной сумме дисперсий  продолжительностей операций ,находящимся  на критическом пути

 

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

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

        (3)

Где - функция Лапласа, которую берем из таблиц[приложение А]; ;

По формуле (3) можно вычислить  вероятность выполнения любой операции в заданный срок.

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

2.2. Метод Монте-Карло

Рассмотрим подход к определению  математического ожидания и дисперсии операций (i,j) сетевого проекта на основе двух оценок: оптимистической а и пессимистической b. Многочисленные эмпирико-экспериментальные исследования двухоценочной методики показали, что в бета-распределении величины p и q, определенные для большого количества сетевых моделей, близки к постоянным значениям: р = 1, q = 2. Выбрав их в качестве стандартных показателей степени, получим функцию, которая относится к классу бета-распределений и имеет следующие параметры:

-математическое ожидание

 

           - дисперсия

 

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