Сетевое планирование. 
Вероятностные сети

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

1.1 События

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

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

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

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

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

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

2.4 Задача Заключение Список использованной литературы Приложение

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

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

Первые системы, использующие сетевые графики, были применены в США в конце 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. Выбрав их в качестве стандартных показателей степени, получим функцию, которая относится к классу бета-распределений и имеет следующие параметры:

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

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

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

Алгоритм метода РЕRТ аналогичен анализу сетевого графа с фиксированными значениями продолжительности операций.

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

2. Построить сетевой граф.

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

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

5. Определить критические операции и критический путь.

6. С помощью значений дисперсии для критических операций оценить дисперсию ожидаемой продолжительности всего проекта.

сетевой граф дисперсия планирование

2.4 Задача

Задача1. Компания с ограниченной ответственностью «Jubilee Computer Systems Ltd» выполняет заказ, полученный от ее потребителя. Необходимая информация приведена в таблице 1

Таблица1

Косвенные издержи, связанные с выполнением проекта, составляют 300 ф.ст. в день. В контракте, заключенном с потребителем, оговорено, что если заказ не будет выполнен в течение 15 дней, сумма штрафа составит 100 ф.ст. за каждый последующий день. Требуется:

1. Построить сетевой граф. Каково ожидаемое значение времени выполнения всего проекта? Каково значение соответствующей стоимости?

2. Какой пусть в графе является критическим? Прокомментируйте продолжительности некритического путей.

3. Какая вероятность того, что проект будет завершен без выплаты штрафов?

Решение :

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

Рисунок-2

2. Рассчитываем ожидаемое значение выполнение операций. Для это воспользуемся формулой (1) и рассчитаем сразу же дисперсию дней выполнения проекта по формуле (2). Все данные представим в виде таблице 2.

Таблица 2

По данным в таблице 2 составим сетевой граф и вычислим прямым и обратным ходом ожидаемое время выполнения всего проекта. После вычисление мы получаем граф со следующими данными:

Рисунок-3

на сетевой модели показаны данные. На основании их можно сказать, что ожидаемое выполнение всего проекта составит 19 дней. По данным в таблице 1 можно сказать, сколько будет стоить этот проект.

Стоимость=(1000+1400+2000+1200+900+2500+800+300)+300*19+100*3=16 100

3. Критический путь в сетевой модели является C, F, H. Для сравнения приведем другие пути: A, D, G, H составит 17. B, E, G, H составит 17. Так как разница составляет всего 2 дня то изменение одной операции приведет к увеличению всего проекта.

4. Дисперсия ожидаемого выполнения всего проекта определяется как сумма дисперсий критических путей Следовательно, Стандартное отклонение времени выполнения всего проекта составит:

Вероятность того, что выполнение проекта займет 15 дней, можно найти следующим образом: Пятнадцать дней составляют z стандартных отклонений от среднего, где:

По таблице стандартного нормального распределения находим:

Р (z) =-0,4953.

Следовательно, вероятность того, что выполнение проекта будет завершен без выплат штрафов, равна: -0,4953+0,5=0,0047 или 0,47%

Заключение

Сетевой анализ используется при разработке и планировании проектов. Он предполагает разбиение проекта на отдельные виды работ или операции. Логическая взаимосвязь между операциями изображается с помощью сетевого графа. На основе значений сроков выполнения операций производится расчет общей продолжительности проекта, возможных сроков начала и окончания каждого вида работ и определяются операции, принадлежащие критическому пути. Операции в сетевых графах можно изображать либо с помощью стрелок, либо с помощью узлов. Альтернативным методом изображения сети операций является график Ганта, в котором используется шкала времени. Сроки выполнения операций могут быть подвержены влиянию неопределенности. В этом случае для анализа проекта можно использовать метод оценки и пересмотра проектов, основанный на предпосылке об аппроксимации сроков выполнения операций р-распределением с минимальным значением а, наиболее вероятным значением m и максимальным значением b. Ожидаемая продолжительность операции в методе РЕRТ рассчитывается по следующей формуле:

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

1. В. К. Буторин, В. В. Карпов. Прикладной системный анализ: сетевой анализ и календарное планирование проектов, метод прогнозного графа: Учеб. Пособие, Кемерово, 2002 г.

2. Л. С. Костевич. Математическое программирование, Минск ООО «новое знание», 2003 г. [гл. 8]

3. В. Ш. Трофимова. Исследование операций: методы и модели сетевого планирования и управленияУчеб. Пособие, Магнитогорск, 2009 г.

Приложение

Таблица значений интегральной функции Лапласа