Реферат: Воропаев В. И., Гельруд Я. Д. Циклические альтернативные сетевые модели и их использование при управлении проектами


Воропаев В.И., Гельруд Я.Д.

Циклические альтернативные сетевые модели и их использование при управлении проектами.


Введение.

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

проект состоит из определенного комплекса взаимосвязанных работ, завершение которых (всех или некоторого подмножества) означает окончание проекта;

работы частично упорядочены, то есть должны выполняться в некоторой технологической последовательности;

с учетом выполнения этой последовательности работы могут начинаться и заканчиваться независимо одна от другой;

некоторые параметры работ подвержены различным случайным воздействиям, вследствие чего носят вероятностный характер;

сама технологическая последовательность зачастую также может зависеть от случайностей и иметь стохастическую (альтернативную) природу.

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

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

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

Моделирование процессов осуществления проектов является действующим методологическим ядром Управления проектами[1]. От степени адекватности моделей реальным процессам и требованиям решаемых в Управлении проектами задач зависит эффективность принимаемых решений и всей работы систем Управления проектами.

Применяемые до настоящего времени математические методы моделирования процессов реализации проектов (классические сетевые модели[2], обобщенные[3,4], вероятностные[5] и стохастические[6] сетевые модели) не всегда оказываются в достаточной степени адекватными сложным реалиям моделируемого процесса. Причем это относится к каждому методу в отдельности и даже к некоторым комбинациям их друг с другом.

Предлагаемая в настоящей работе модель управления проектами является синтезом обобщенных сетевых моделей (с их богатым спектром возможностей описания организационно-технологической структуры проекта) с вероятностными и стохастическими моделями, в значительной степени учитывающими фактор риска и неопределенности при осуществлении проекта. Данные модели (называемые в дальнейшем циклические альтернативные сетевые модели - ЦАСМ) являются самым гибким и адекватным инструментом для описания процесса управления разработкой сложного проекта. ЦАСМ включают в себя все преимущества обобщенных и стохастических моделей по сравнению с традиционными сетевыми моделями, при этом язык описания ЦАСМ усложняется незначительно. Имеется ввиду пользовательский язык общения, средства, предоставляемые менеджерам проекта (на разных уровнях управления) для описания проекта, для участия в интерактивном режиме формирования календарных планов. Общее описание данных моделей проводилось в ряде докладов[7-8], в настоящей работе приводится подробное описание с обоснованием необходимых условий непротиворечивости, а также алгоритмы ресурсно-временного анализа ЦАСМ.

^ Описание ЦАСМ.

ЦАСМ представляет собой конечный, ориентированный, циклический граф G(,A), состоящий из множества событий  и дуг (i,j) (i,j), определяемых матрицей смежности А={pij}. 0 pij 1, причем pij=1 задает детерминированную дугу (i,j), а 0pij 1 определяет альтернативное событие i, которое с вероятностью pij связано дугой с событием j. Множество дуг подразделяется на дуги-работы и дуги-связи. Первые реализуют определенный объем производственной деятельности во времени, второй тип дуг отражает исключительно логические связи между последними. Событиями могут быть как начала и окончания выполняемых работ, так некоторые их промежуточные состояния.

Обозначим через Тi время свершения i-го события, тогда соотношение между сроками свершения событий, связанных дугой (i,j), задается неравенством:

Тj – Тi  ij , (1)

где ij в общем случае случайная величина, распределенная по некоторому закону в интервале от –  до 0 или от 0 до +.

Кроме того, возможны абсолютные ограничения на момент реализации события i:

li Тi Li. (2)

Соотношения (1)-(2) являются обобщением соответствующих неравенств при описании обобщенных сетевых моделей[3], где параметр ij и матрица смежности А носят детерминированный характер.

Рассмотрим смысловую нагрузку соотношения (1) при вероятностном характере параметра ij.

Если (i,j) есть дуга-работа (или ее часть), то положительно распределенная случайная величина ij задает распределение минимальной продолжительности этой работы (связанной с максимальным насыщением ее определяющим ресурсом). Планируя максимально возможное использование ресурса на работе, мы ожидаем кратчайшее ее исполнение, однако непредвиденные помехи и случайные обстоятельства обуславливают вероятностный характер этого времени, причем, как правило, мода (наиболее вероятное минимальное время выполнения работы) сдвигается вправо относительно математического ожидания. Вследствие этого распределение величины ij является унимодальным и асимметричным, а данным требованиям удовлетворяет бета-распределение, которое интуитивно было введено для оценки продолжительности работ еще в системе PERT, а затем получило аналитические и эмпирические подтверждения[5].

Таким образом, минимальная продолжительность работы есть случайная величина ij=tmin(i,j), распределенная по закону бета-распределения на отрезке [а, b] с плотностью

(t)=С(t – a)p-1(b – t)q-1, (3)

где С определяется из условия ab(t)dt=1.

В [2] показано, что параметры распределения ij – математическое ожидание Мij и дисперсия 2ij приближенно определяются по формулам:

Мij =(aij +4mij +bij)/6, (4)

ij =(bij – аij)/6, (5)

где aij,bij,mij – соответственно оптимистическая, пессимистическая и наиболее вероятная оценки минимальной продолжительности работы (i,j), задаваемые ее ответственными исполнителями (при использовании трехоценочной методики). В случае же двухоценочной методики (предложенной и обоснованной в [5]) плотность распределения имеет вид:

(t)=С(t – a)(b – t)2, (6)

где С=12/(b – а)4, а параметры распределения

Мt=(3а+2b)/5, (7)

m=(2а+b)/3, (8)

Dt=0.04(b – а)2. (9)

Если же случайная величина ij в (1), соответствующая дуге-работе (i,j), распределена в интервале от –  до 0, то –ij=tmax(j,i) задает распределение максимальной продолжительности работы (j,i) (связанной с минимальным насыщением ее определяющим ресурсом). Проведя для этой величины рассуждения, аналогичные вышеизложенным, получим ее распределение вида (3) или (6) и параметры, вычисляемые по формулам (4)–(5) или (7)– (9) соответственно.

Принимая в качестве значений этих случайных величин их наиболее вероятные значения (моды), мы получаем в частном случае известную двухоценочную вероятностную модель (рассмотренную в [5]), где аij=mtmin(i,j), а bij=mtmах(i,j). Таким образом, введение в (1) отрицательно распределенных величин ij для дуг-работ (i,j) существенно расширяет возможности описания временных характеристик работ, делая широко используемую вероятностную модель лишь одним из частных случаев.

Для дуг-связей (i,j) величина ij задает распределение временной зависимости между событиями i и j, причем положительно распределенная величина ij определяет взаимосвязь типа “не ранее” (событие j может наступить не раньше, чем через ij дней после свершения события i), а отрицательно распределенная величина ij определяет взаимосвязь типа “не позднее” (событие i может наступить не позже, чем через –ij дней после свершения события j).

В последнем случае такие связи называют «обратными».

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

Так как сроки свершения событий Тi определяются суммой продолжительностей работ, технологически им предшествующих, то при достаточно большом числе таких работ в соответствии с центральной предельной теоремой распределение случайной величины Тi стремится к нормальному с параметрами – математическое ожидание MТi и дисперсия DТi. Следует ожидать нормальное распределение и от параметра ij, соответствующего «обратным» дугам, что также подтверждается статистическим анализом[5].

Абсолютные ограничения на сроки свершения событий, заданные (2), отражают соответствующие директивные, организационные и технологические ограничения на сроки выполнения работ или их частей, заданные в «абсолютной» (реальной или условной) шкале времени. Абсолютные ограничения также характеризуются типом «не ранее» или «не позднее». В абсолютной шкале времени значения li и Li неотрицательны. Если принять начало отсчета (абсолютное или относительное) за нулевое событие, то можно ввести дуги (0,i) и (i,0) с параметрами 0i=li и i0= –Li соответственно, и тогда (2) примет вид: Тi – Т0  li , Т0 – Тi  –Li. Таким образом, абсолютные ограничения вида (2) являются частным случаем ограничений вида (1) для определенных дуг-связей.

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

Пусть L(i,j) – некоторый путь, соединяющий события i и j.

L(i,j)={i=i0i1i2…iv=j}. (10)

Назовем путь детерминированным, если для всех k[1,v] справедливо pik-1ik=1, и стохастическим, в противном случае. Таким образом, по определению стохастический путь содержит хотя бы одну дугу, вероятность «исполнения» которой строго меньше 1. Здесь под «исполнением» дуги понимается выполнение работы (для дуги-работы) или выполнение требования о временной связности событий (для дуг-связей).

Аналогично определим детерминированный и стохастический контур К(i)={i=i0i1i2…iv=i}. (такие события i назовем “контурными”).

Пусть события i и j соединены путем L(i,j), тогда вероятность свершения события j при условии, что событие i произошло Р(j/i) есть произведение коэффициентов матрицы смежности А, соответствующих дугам связующего пути:

Р(j/i)=vk=1 pik-1ik. (11)

Если события i и j соединены несколькими путями, то выполняется эквивалентное GERT-преобразование данного фрагмента сети в соответствии с формулами, приведенными в [6], вычисляется производящая функция ij(s) и вероятность свершения события j при условии, что событие i произошло, Р(j/i)= ij(0).

Первая производная функции ij(s)/ ij(0) по s в точке s=0 (первый момент 1(j/i)) определяет математическое ожидание М(j/i) времени свершения события j относительно времени свершения события i. Вторая производная функции ij(s)/ ij(0) по s в точке s=0 (второй момент 2(j/i)) позволяет вычислить дисперсию времени свершения события j относительно времени свершения события i по формуле:

2(j/i) =2(j/i) – (1(j/i))2. (12)

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

Р(j)=1– i  j (1 – P(i)pij), (13)

где Р(i) – вероятность свершения i-го события, Р(0)=1 и уже известны Р(i) для всех i, строго предшествующих j (i  j). Из (13) следует, что если событию j предшествует хотя бы один полный детерминированный путь, то Р(j)=1 (одна из скобок в произведении обращается в ноль). Будем называть такое событие детерминированным, в противном случае – стохастическим.

Рассмотрим небольшой числовой пример:

0.3

0.7



0.6

0.4

Здесь Р(0)=Р(1)=Р(2)=1. Для вычисления Р(4) GERT-преобразование не применимо (0.7+0.6=1.3>1). В соответствие с (13):

Р(4)=1 – (1 – 0.7)(1 – 0.6)=0.88.

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

Длина пути L(i,j) есть случайная величина, математическое ожидание которой МL(i,j) есть сумма математических ожиданий длин всех дуг, составляющих данный путь, а дисперсия DL(i,j) равна сумме дисперсий. Математические ожидания длин дуг вычисляются по формулам (4) или (7), а дисперсии по формулам (5) или (9) при трех- или двухоценочной методиках соответственно.

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

5 6 4 2




ji=-20

рис. 1

В данном случае событие j должно свершиться не позднее чем через –ji дней после наступления события i. В отличие от обобщенных сетевых моделей[3], параметр ji носит вероятностный характер, что позволяет более гибко описывать логико-временные связи между событиями.

^ 3. Постановка задач временного анализа ЦАСМ.

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

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

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

Задачи временного анализа ЦАСМ сводятся к нахождению случайного вектора Т=(Т0,Т1,…,Тn), где Тi есть время свершения i-го события, координаты которого удовлетворяют неравенствам (1)-(2) и обращают в экстремум некоторую целевую функцию F(T).

Так как здесь {Тi} суть случайные величины, то задачи временного анализа ЦАСМ характеризуются не только видом функции F(T), но и способом вычисления {Тi} и их параметров.

В силу этого выделим три класса задач временного анализа:

классические, в которых для вычисления {Тi} используются математические ожидания продолжительностей всех дуг;

вероятностные, в которых на основании предельной теоремы Ляпунова или другими аналитическими средствами[5] вычисляются математические ожидания сроков свершения i–х событий – {МТi}, являющиеся аргументами целевой функции F(T);

статистические, в которых для заданного уровня достоверности р по методике[5] определяются р-квантильные оценки эмпирических распределений как сроков свершения i–х событий – {Wp(Тi)}, так и производных от них величин, в том числе и значений целевой функции F(Wp(T)), где Wp(Т)={Wp(Т0),Wp(Т1),…,Wp(Тn)}.

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

^ Понятие непротиворечивости ЦАСМ.

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

Разберем отдельно эти три понятия.

^ 4.1. Классическая непротиворечивость модели.

Математические ожидания продолжительностей всех дуг вычисляются по соответствующей формуле (7), (4) (при двух- или трехоценочной методике) и задают сеть с постоянными длинами дуг. В теории классических сетевых моделей[2] показано, что условием непротиворечивости модели является отсутствие в ней контуров. Учитывая стохастический характер рассматриваемой модели и наличие обобщенных связей, в ЦАСМ после проведенных выше вычислений могут иметь место стохастические и детерминированные контура.

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

Доказательство.

Пусть задан контур K(i) и вероятность прохождения по нему Р(i/i)<1. Вероятность выхода из контура при k-кратном прохождении по нему вычисляется по формуле 1 – Рk(i/i). Отсюда определим количество k возможных проходов по контуру, после которого мы с вероятностью  из него выходим: =1 – Рk(i/i), следовательно

k=ln(1 – )/ lnР(i/i). (14)

Например, при =0.95 и Р(i/i)=0.4 получаем k3, т.е. после трехкратного прохождения по контуру мы выйдем из него с вероятностью 0.95. При определении допустимого (с вероятностью ) срока свершения события j, отождествляемого с выходом из контура, к длине пути, проходящего через событие i до события j, необходимо добавить величину kL(K(i)), где L(K(i)) длина контура K(i).

Лемма 2. Чтобы циклическая альтернативная модель, в которой продолжительности дуг вычислены по классической схеме, была непротиворечивой, необходимо и достаточно, чтобы длины всех детерминированных контуров (при отсутствии стохастических) были не положительны, т.е. L(K(i))0, для всех “контурных” i .

Доказательство.

Если продолжительности дуг вычислены по классической схеме и отсутствуют стохастические контура, то мы получаем обобщенную сетевую модель, для которой доказательство утверждения, содержащегося в лемме 2, проведено достаточно строго в [3].

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

Доказательство теоремы непосредственно следует из совместного применения леммы 1 и леммы 2.

^ 4.2. Вероятностная непротиворечивость модели.

Вычисляем математическое ожидание МТi и дисперсию 2Тi сроков свершения событий по формулам из [5]. Следует отметить, что вычисленные подобным аналитическим способом параметры на 15-20% отличаются по величине от вычисленных классическим способом (по математическим ожиданиям продолжительностей дуг).

Будем говорить о вероятностной непротиворечивости модели в среднем, если полученный таким образом набор удовлетворяет неравенствам (1)-(2), где в качестве значения ij взято ее математическое ожидание.

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

Доказательство.

Пусть K(i) контур и МL(K(i)) математическое ожидание его длины. Тогда производящая функция моментов для контура K(i) есть Мii(s)=еsМL(K(i)). Первая производная Мii(s) по s при s=0 (характеризующая математическое ожидание длины контура) есть функция нечетная относительно знака длины контура. Следовательно, в этом же смысле нечетна и функция ii(s)=рiiМii(s), где рii вероятность «входа» в контур, а рb=1–рii вероятность «выхода» из него. Так как производящая функция эквивалентного фрагмента есть

ij(s)= b(s)/(1 – ii(s)), (15)

то при рii <1 получаем:

рij= ij(0)= b(0)/(1 – ii(0))= (1 –рii)/(1–рii)=1, (16)

т.е. из стохастического контура мы выходим с вероятностью 1.

Для определения математического ожидания длины эквивалентного фрагмента вычислим первый момент от (15) в точке s=0:

1(j/i)= [рb(1– рii)МL(i,j)+ рbрiiМL(K(i))]/(1 –рii)2 =

= МL(i,j)+ МL(K(i))[рii/(1 –рii)]. (17)

Таким образом, для определения среднего срока свершения события j, отождествляемого с выходом из контура, к длине пути, проходящего через событие i до события j, необходимо добавить величину L(K(i)), где L(K(i)) длина контура K(i), а =[рii/(1 –рii)].

Если же контур детерминированный (рii =1), то при положительных значениях ii(s) и ее производной из (17) мы получаем невозможность выхода из контура (бесконечность длины эквивалентного фрагмента). При неположительной длине контура МL(K(i)) мы имеем вероятность выхода из него, равную 1, и длину эквивалентной дуги, лежащую в пределах от МL(i,j) до МL(i,j) + МL(K(i)).

В предположении, что Тi имеют нормальное распределение с параметрами: математическое ожидание – МТi и дисперсия – 2Тi, введем более широкое понятие -вероятностная непротиворечивость модели.

Будем говорить, что ЦАСМ -вероятностно непротиворечива, если существует >0, такое что для всех Тi, удовлетворяющих неравенству Тi – МТi <, справедливы соотношения (1)-(2).

Теорема 3. Для того, чтобы циклическая альтернативная модель была -вероятностно непротиворечивой, необходимо и достаточно, чтобы математические ожидания длин всех детерминированных контуров удовлетворяли соотношению МL(K(i))  –4.

Доказательство.

Пусть K(i) контур и МL(K(i)) математическое ожидание его длины.

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

Мij




ji

рис. 2

Здесь Мij – математическое ожидание «положительной» части контура K(i).

Пусть для Тi и Тj, удовлетворяющих неравенствам:

Тi – МТi <, Тj–МТj<, (18)

справедливы соотношения (1), тогда они справедливы для крайних значений Тi и Тj, минимизирующих левую часть (1), т.е. для Тi =МТi   и Тj=МТj  :

МТj– – (МТi + )Мij и МТi –  – (МТj+)Мji. (19)

Складывая неравенства, получаем

–4  Мij+Мji  МL(K(i)), что доказывает необходимость утверждения теоремы 3.

Для доказательства достаточности положим Тj= Тi +Мij. Неравенство (1) для дуги (i,j) выполнено. Имеем Тi –Тj= –Мij.

Так как Мij+Мji  МL(K(i))  –4, то –Мij4+ Мji Мji, откуда следует справедливость неравенства (1) для дуги (j,i).

Приведем небольшой числовой пример, иллюстрирующий справедливость теоремы 3. Пусть для фрагмента сети, представленного на рис. 2, МТi=50, МТj=100. Примем =1 (один день). Соотношение (1) для дуги (i,j) должно выполняться для всех Тi и Тj, удовлетворяющих неравенствам (18), а значит и для тех, которые минимизируют левую часть в (1), т.е. для Тi=50+1=51 и Тj =100 – 1=99. Отсюда следует, что должно выполняться неравенство Мij  Тj – Тi =99 – 51=48. С другой стороны, рассматривая “обратную” дугу (j,i), и рассуждая аналогично, имеем справедливость (1) для дуги (j,i) при Тi=50 – 1=49 и Тj =100 + 1=101. Следовательно, также должно выполняться неравенство Мji  Тi – Тj =49 – 101= –52. Складывая полученные неравенства, окончательно получаем требуемое соотношение:

Мij+Мji  МL(K(i))  48 – 52= –4 = –4.

Вероятностная непротиворечивость модели в среднем является частным случаем -вероятностной непротиворечивости при =0.

^ 4.3. Статистическая непротиворечивость модели.

При статистическом методе расчета параметров сетевой модели мы имеем дело с их р-квантильными оценками значений, которые являются теоретико-вероятностными аналогами соответствующих показателей[5]. Будем говорить, что циклическая стохастическая модель статистически непротиворечива с вероятностью р, если для каждого события i существуют р-квантильные оценки сроков свершения событий Wp(Тi), удовлетворяющие неравенствам:

Wp(Тj) – Wp(Тi) Wp(ij), (20)

liWp(Тi)Li. (21)

Здесь соотношения (20)-(21) являются вероятностными аналогами (1)-(2), Wp(ij) есть р-квантильная оценка длины дуги (i,j).

Теорема 4. Для того, чтобы циклическая альтернативная модель была статистически непротиворечивой с вероятностью р, необходимо и достаточно, чтобы р-квантильные оценки длин всех детерминированных контуров удовлетворяли соотношению Wp(L(K(i)))  0.

Доказательство.

После вычисления р-квантильных оценок вероятностная модель превращается в обобщенную сетевую модель, а для нее утверждение теоремы 4 справедливо[3].

Наличие альтернативных вершин (с возможным появлением стохастических контуров) в соответствие с леммой 1 не приводит к непротиворечивости сети, следовательно теорема справедлива для любой ЦАСМ.

^ 5. Алгоритмы расчета временных параметров ЦАСМ.

5.1. Планы ранних и поздних сроков.

Для расчета ранних и поздних сроков свершения событий предлагается модифицированный алгоритм «Маятника». Идея модификации заключается в синтезе статистического метода расчета параметров, применяемого для вероятностных сетей[5], и алгоритма «Маятник», используемого в обобщенных сетях[3], и последующего применения его для ЦАСМ.

Принципиальная блок-схема алгоритма для расчета р-квантильных оценок ранних сроков свершения событий приведена на рис. 3.
























Да




Да
















Рис.3. Принципиальная блок-схема алгоритма для расчета

р-квантильных оценок ранних сроков свершения событий.

Блок 1. Ввод исходных данных (коэффициентов матрицы А, параметров распределения ij, уровня достоверности р). Упорядочение сети. Для небольших сетей вычисление Р(j) по формулам GERT-преобразований и (13).

Блок 2. Вычисление необходимого числа «розыгрышей» N для обеспечения заданной точности результатов. Проделанные расчеты показали, что при р=0.95, =0.05 получаем N270.

Блок 3. v:=v+1 (v – номер «розыгрыша).

Блок 4. Розыгрыш v-го варианта случайных величин ij, каждой в соответствии с ее законом распределения, получение констант ij(v) – длина дуги (i,j) при v-м розыгрыше.

Блок 5. Розыгрыш для каждой альтернативной вершины i перехода в смежную вершину j (разыгрывается дискретная случайная величина рij, представленная i-й строкой матрицы смежности А, 0< рij <1 и jрij =1). Выбранная дуга помечается, остальные из графа исключаются. Если в полученном графе образовался контур К(i), содержащий хотя бы одну помеченную дугу, это есть стохастический контур, вычисляем его длину L(v)K(i) и опять для вершины i разыгрываем дискретную случайную величину рij. В соответствие с леммой 1 один и тот же стохастический контур при заданном уровне достоверности р может образоваться не более k раз, где k оценивается по формуле (14). k-кратную длину контура прибавляем к длине дуги, которую мы “разыграли” на (k+1)-м шаге и переходим к анализу другого стохастического контура (если он есть). При этом могут образоваться противоречия в сети (положительные детерминированные контуры), тогда в соответствие с (17) прибавляем -кратную длину контура, оценивая тем самым время свершения “выходного” из контура события в среднем.

Блок 6. Полученную детерминированную обобщенную сеть G(v) разбиваем на две сети G1(v) и G2(v), так, чтобы ни G1(v), ни G2(v)не содержали контуров. Вершины в сети G1(v)упорядочиваем по рангам и в соответствие с ними устанавливаем «правильную» нумерацию. Переносим эту нумерацию на сеть G2(v)и на исходную G(v).

Блок 7. Для всех вершин i сети G1(v) вычисляем ранние сроки свершения

Тi0(v) : =махj{Тi0(v), Тj0(v) + ij(v)}.

^ Блок 8. Проделываем процедуры, аналогичные блоку 7, для вершин сети G2(v).

Блок 9. Если результаты блоков 7 и 8 хоть на одном показателе не совпадают, то возвращаемся к блоку 7 (таких возвратов не более, чем число обратных дуг в G2(v)), иначе блок 10.

^ Блок 10. Если номер розыгрыша v
Блок 11. Для каждой вершины i подсчитываем количество ее наступлений (i). Для детерминированных вершин, естественно, (i)=. Р(i)=(i)/ – статистическая характеристика вероятности наступления события i, полученная методом имитационного моделирования. Из полученной совокупности {Тi0(v)} для каждой вершины i строим вариационный ряд. Фиксируем такое значение Тi0(), что /(i)=р, где – число членов вариационного ряда, меньших Тi0(). Величина Тi0() является искомым р-квантилем раннего срока свершения i-го события – Wp(Тi0). Аналогично, по вариационным рядам {ij(v)} строим р-квантильные оценки длин дуг – Wp(ij).

На вход блока 6 поступает v-й вариант обобщенной сетевой модели G(v), и, собственно, блоки 6 – 9 представляют собой укрупненную блок-схему алгоритма «Маятник» для вычисления ранних сроков свершения событий в ОСМ. Подробно этот алгоритм изложен в [3], там же приведен алгоритм для вычисления поздних сроков свершения событий. Применяя этот алгоритм в блоках 7 и 8, мы получаем Тi1(v)– поздние сроки свершения событий для v-го варианта обобщенной сетевой модели, при этом блок 11 нам дает Wp(Тi1) – р-квантильные оценки поздних сроков свершения событий.

^ 5.2. Планы минимальной продолжительности.

Продолжительность L(Т(v)) любого допустимого плана Т(v)={Тi(v)} v-го варианта сети G(v) определяется по формуле:

L(Т(v))=махij Тi(v) – Тj(v). (21)

Заменяя в блок-схеме на рис. 3 блоки 6 – 9 на блок нахождения минимума функции (21), мы получаем план минимальной продолжительности для сети G(v) (или «сжатый» план). Величина

L(Т*(v))=min махij Тi(v) – Тj(v) (22)

является критическим временем сети G(v). Метод нахождения сжатого плана для ОСМ подробно описан в [3], там же приведены алгоритмы построения четырех разновидностей сжатых планов:

раннего и позднего сжатых планов при раннем завершении проекта:

раннего и позднего сжатых планов при позднем завершении проекта.

Используя в блоках 6-9 метод нахождения сжатого плана для ОСМ и пропуская полученные планы через блок 11, получаем вероятностные р-квантильные оценки сжатых планов.

^ 5.3. Вычисление резервов, коэффициентов напряженности работ, р-квантильных критических, резервных и промежуточных зон.

Резервам времени для работы (i,j) здесь соответствуют их р-квантильные аналоги, вычисляемые по формулам:

Rпp(i,j)= Wp(Тjп) – Wp(Тip) – Wp(ij) для полного резерва, (23)

Rсp(i,j)= Wp(Тjр) – Wp(Тip) – Wp(ij) для свободного резерва. (24)

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

Wp(kн(i,j))=1–Rпp(i,j)/(Wp(Tn0) – Wp(Ткр(i,j))), (25)

где Wp(Tn0)– р-квантильная оценка критического времени выполнения проекта, Wp(Ткр(i,j)) – р-квантильная оценка продолжительности совпадающего с критическим путем
еще рефераты
Еще работы по разное