Методология сетевого планирования и управления

Интегрирование методом Монте-Карло

Рисунок 1. Численное интегрирование функции детерминистическим методом

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

     Для определения этой площади можно  воспользоваться одним из обычных численных методов интегрирования: разбить отрезок на подотрезки, подсчитать площадь под графиком функции на каждом из них и сложить. Предположим, что для функции, представленной на рисунке 2, достаточно разбиения на 25 отрезков и, следовательно, вычисления 25 значений функции. Представим теперь, мы имеем дело с n-мерной функцией. Тогда нам необходимо 25ⁿ отрезков и столько же вычислений значения функции. При размерности функции больше 10 задача становится огромной. Поскольку пространства большой размерности встречаются, в частности, в задачах теории струн, а также многих других физических задачах, где имеются системы со многими степенями свободы, необходимо иметь метод решения, вычислительная сложность которого бы не столь сильно зависела от размерности. Именно таким свойством обладает метод Монте-Карло.

Обычный алгоритм Монте-Карло  интегрирования

Рисунок 2. Численное интегрирование функции методом Монте-Карло

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

• ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого S_par можно легко вычислить;
• «набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек (N штук), координаты которых будем выбирать случайным образом;
• определим число точек (K штук), которые попадут под график функции;
• площадь области, ограниченной функцией и осями координат, S даётся выражением

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

     Использование выборки по значимости

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

     Program Evaluation and Review Technique (сокращенно PERT) — техника оценки и анализа программ, которая используется при управлении проектами. Была разработана в 1958 году консалтинговой фирмой «Буз, Ален и Гамильтон» совместно с корпорацией «Локхид» по заказу Подразделения специальных проектов ВМС США в составе Министерства Обороны США для проекта создания ракетной системы «Поларис» (Polaris). Проект «Поларис» был ответом на кризис, наступивший после запуска Советским Союзом первого космического спутника.

     Пример  сетевой PERT диаграммы  для проекта продолжительностью в семь месяцев  с пятью промежуточными точками (от 10 до 50) и  шестью деятельностями (от A до F)

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

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

     Самая известная часть PERT — это «Сети PERT» — графики соединённых  между собой временных линий. PERT предназначен для очень масштабных, единовременных, сложных, нерутинных проектов.

     Диаграмма представляет собой множество точек-вершин вместе с соединяющими их ориентированными дугами. Каждая из них как направленный отрезок имеет начало и конец, причем модель содержит только одну из пары симметричных дуг (от вершины 1 к  вершине 2 и от вершины 2 к вершине 1). Всякой дуге, рассматриваемой в  качестве какой-то работы из числа нужных для осуществления проекта, приписываются  определенные количественные характеристики. Это — объемы выделяемых на нее  ресурсов и, соответственно, ее ожидаемая  продолжительность (длина дуги). Любая  вершина интерпретируется как событие  завершения работ, представленных дугами, которые входят в нее, и одновременно начала работ, отображаемых дугами, исходящими оттуда. Таким образом, фиксируется  что ни к одной из работ нельзя приступить прежде чем будут выполнены  все предшествующие ей согласно технологии реализации проекта. Факт начала этого  процесса — вершина без входящих, а окончание — без исходящих  дуг. Остальные вершины должны иметь  и те, и другие. Последовательность дуг, в которой конец каждой предшествующей совпадает с началом последующей, трактуется как путь от отправной  вершины к завершающей, а сумма  длин таких дуг — как его  продолжительность. Обычно начало и  конец реализации проекта связаны  множеством путей, длины которых  различаются. Наибольшая определяет длительность всего этого проекта, минимально возможную при зафиксированных  характеристиках дуг графа. Соответствующий путь — критический и в каждый момент времени контролировать нужно состояние именно тех работ, которые «лежат» на нем.

     Метод графической оценки и анализа (GERT, англ. Graphical Evaluation and Review Technique) — альтернативный вероятностный метод сетевого планирования, применяется в случаях организации работ, когда последующие задачи могут начинаться после завершения только некоторого числа из предшествующих задач, причём не все задачи, представленные на сетевой модели, должны быть выполнены для завершения проекта. 
Разработан в США в 1966 году. 
 Основу применения метода GERT составляет использование альтернативных сетей, называемых GERT-cетями.   Они позволяют более адекватно задавать сложные процессы строительного производства в тех случаях, когда затруднительно или невозможно (по объективным причинам) однозначно определить, какие именно работы и в какой последовательности должны быть выполнены для достижения цели проекта (то есть существует многовариантность реализации проекта). 
 Расчёт GERT-сетей, моделирующих реальные процессы, чрезвычайно сложен, однако программное обеспечение для вычисления сетевых моделей такого типа в настоящее время, к сожалению, не распространено. 
 
 
 
 
 
 
 
 
 

2. Сетевой график

     Сетевой график основан на использовании математической модели - графа. Графом (устаревшие синонимы: сеть, лабиринт, карта и т.д.) математики называют "множество вершин и набор упорядоченных или неупорядоченных пар вершин". Говоря более привычным для студента (но менее точным) языком, граф - это набор кружков (прямоугольников, треугольников и проч.), соединенных направленными или ненаправленными отрезками. В этом случае сами кружки (или другие используемые фигуры) по терминологии теории графов будут называться "вершинами", а соединяющие их ненаправленные отрезки - "ребрами", направленные (стрелки) - "дугами". Если все отрезки являются направленными, граф называется ориентированным, если ненаправленными - неориентированным.⁷

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

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

     В графике могут использоваться пунктирные стрелки - это так называемые "зависимости" (фиктивные работы), не требующие  ни времени, ни ресурсов.

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

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

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

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

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

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

     Особое  значение при составлении сетевого графика имеют два понятия:

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

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

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

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

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

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