До сих пор мы рассматривали модели с детерминированной топологией сети. При моделировании сложного проекта нередко наиболее гибкими и полезными оказываются сетевые модели со стохастической структурой. Стохастическую сеть определяют как сеть, содержащую альтернативные узлы (состояния), при этом дуги (работы) характеризуются не только вероятностным распределением продолжительности, но и вероятностью их выполнения. Стохастическая сетевая модель с множеством возможных исходов, являясь дальнейшим развитием традиционных сетей, дает возможность полнее отобразить процесс разработки и создания сложного проекта. Применяемый для анализа стохастических сетевых моделей математический аппарат позволяет вычислять вероятности различных альтернативных исходов, оценивать время их возможной реализации. Стохастическая сетевая модель есть конечный граф G=(Ω,А), где Ω– есть множество детерминированных и альтернативных вершин, отождествляемых с событиями, а технологическая матрица А={pij} задает множество ориентированных дуг, отождествляемых с работами (или связями). Для стохастических сетей 0≤ pij ≤ 1, причем pij =1
161 определяет работу (i,j) аналогично принятым в традиционных сетях определениям, а 0 < pij < 1 соответствует альтернативному событию i, из которого с вероятностью pij «выходит» работа (i,j). Другими словами pij – вероятность того, что работа (i,j) будет выполнена при условии, что узел i выполнен. Пусть ϕ(tij) – плотность распределения времени выполнения работы (i,j). М[х] – математическое ожидание случайной величины х. Вводится условная производящая функция моментов случайной величины tij как Мij(s)=М[еstij], т.е. Мij(s)= ∫ еstijϕ(tij)dtij (для непрерывной случайной величины), ∑ еstijϕ(tij) (для дискретной случайной величины). В частности, Мij(s)=М[еsа] = еsа при tij=а=const, Мij(0)=1. Для каждой дуги (i,j) определяется Ψ–функция как Ψij(s) = pijМij(s). Исходная сеть преобразуется в эквивалентную, используя три базисных преобразования: • последовательные дуги, • параллельные дуги, • петли. Для последовательных дуг (рис.2.4.7) Ψij Ψjk Рис. 2.4.7 Ψik(s) = Ψij(s)Ψjk(s). Для параллельных дуг (рис.2.4.8) Ψa Ψb Рис. 2.4.8 Ψij(s) = Ψa(s) +Ψb(s). Для петель вида (рис. 2.4.9) Ψa Ψb Рис. 2.4.9 Ψij(s) = Ψb(s)/[1 – Ψa(s)]. Комбинируя базисные преобразования, любую сеть можно преобразовать в эквивалентную сеть, состоящую из одной дуги (Е- дуги). Цель временного анализа стохастической сети состоит в вычислении математического ожидания и дисперсии времени выполнения сети (или любого ее фрагмента) и вероятности выполнения заключительного (или любого другого события) сети. iJk i J i J
162 Здесь используется теория замкнутых потоковых графов, где введенная выше Ψ-функция трактуется как соответствующий коэффициент пропускания дуги. Для применения результатов этой теории к открытой сети с искомым параметром ΨЕ(s) вводится дополнительная дуга с параметром ΨА(s), соединяющая конечное событие (сток) с начальным (источником). Затем используется топологическое уравнение для замкнутых графов, известное как правило Мейсона, следующего вида: 1–∑Т(L1)+∑Т(L2)–∑Т(L3) +…+ (–1)m∑T(Lm) + … =0, (2.4.9) где ∑T(Lm) – сумма эквивалентных коэффициентов пропускания для всех возможных петель m-го порядка. Эквивалентный коэффициент пропускания для петли m-го порядка равен произведению коэффициентов пропускания m не связанных между собой петель первого порядка, т.е. T(Lm)=∏m k=1Tk. Непосредственно из правила Мейсона следует, что 1–ΨА(s)ΨЕ(s)=0 или ΨА(s)=1/ΨЕ(s). Используя данный результат, в топологическом уравнении (4.4.9) ΨА(s) заменяется на 1/ΨЕ(s) и затем оно решается относительно ΨЕ(s), тем самым получается эквивалентная Ψ-функция для исходной стохастической сети. Поскольку ΨЕ(s) = pЕМЕ(s), а МЕ(0)=1, то pЕ=ΨЕ(0), откуда следует, что МЕ(s)= ΨЕ(s)/pЕ =ΨЕ(s) /ΨЕ(0). (2.4.10) После получения аналитического выражения для МЕ(s), вычисляют первую и вторую частную производную по s функции МЕ(s) в точке s=0, т.е. μ1E=∂/∂s[МЕ(s)]s=0 (2.4.11) μ2E=∂2/∂s2[МЕ(s)]s=0 (2.4.12) Первый момент μ1E относительно начала координат есть математическое ожидание времени выполнения сети (преобразованной в эквивалентную ей Е-дугу), а дисперсия времени выполнения сети равна разности между вторым моментом μ2E и квадратом первого, т.е. σ2= μ2E – (μ1E) 2. (2.4.13) Таким образом, описанный выше аппарат позволяет вычислять временные параметры любых интересующих пользователя событий стохастической сети, а также определять вероятность их наступления. Используя полученную информацию, можно с помощью неравенства Чебышева оценивать вероятность любых доверительных интервалов времени окончания проекта при произвольных законах распределения времени выполнения отдельных операций. Если время
163 выполнения каждой операции имеет нормальное распределение, то результирующее время также нормально распределено. В этом случае можно получить вероятностные оценки времени выполнения проекта, используя интегральную теорему Муавра-Лапласа. Кроме того, при достаточно большом числе работ в сети и выполнении некоторых условий (в частности, независимость работ) можно использовать предельную теорему Ляпунова и считать результирующее время выполнения проекта нормально распределенной случайной величиной с характеристиками, вычисленными по выше описанной методике. Таким образом, стохастическая сетевая модель включает все случайные отклонения и неопределенность, возникающие непосредственно во время выполнения каждой отдельной работы. В качестве параметра дуги мы рассматривали время выполнения операции (работы). Можно рассматривать также любой характерный параметр, который обладает аддитивностью по дугам любого пути. Это может быть стоимость работы, количество потребного накапливаемого ресурса и т.п. Следует отметить, что до настоящего времени широкое практическое применение нашли только методы детерминированного сетевого моделирования, некоторые эвристические методы оптимального распределения ресурсов и параметрические методы оценки затрат (преимущественно в сфере воздушных и космических полетов). Хотя точное решение стоимостных задач календарного планирования на основе классических сетевых моделей теоретически найдено, но его практическое использование сопряжено с трудностью получения фактических данных о зависимостях «время-стоимость». Каждая из рассмотренных выше моделей имеет свою предметную область, по-своему (более или менее полно) реализует базовые функции управления проектом, и только синтез анализируемых моделей и методов позволяет построить модель, адекватно отражающую процесс реализации сложного проекта в условиях неопределенности, и при этом получить приемлемое в практическом отношении решение сформулированной задачи.
Ви переглядаєте статтю (реферат): «Стохастические сетевые модели» з дисципліни «Математична економіка»
