авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 5 | 6 || 8 |

«Институт проблем управления Университетский Центр им. В.А.Трапезникова РАН Самарии (Москва, Россия) (Ариэль, Израиль) Д.И. ...»

-- [ Страница 7 ] --

Другое направление построения и анализа обобщённых сетевых пла нов представлено в работах Салаха Элмаграби [6.10-6.13]. В то время как Эйснером описаны два типа событий, здесь уже строятся довольно слож ные стохастические сетевые структуры, включающие шесть типов событий (вершин). На входах событий реализуются три вида логических отноше ний: «И», «неисключающее (соединительное) ИЛИ», «исключающее (раз делительное) ИЛИ», а на выходах - «необходимость следования» («И») ли бо «возможность следования» («Исключающее ИЛИ»), что иногда называ ется «ветвлением». Элмаграби разработал метод последовательного экви Стохастические Сетевые Модели Планирования и Управления Разработками валентного преобразования обобщённой сети путем сведения ее фрагмен тов к агрегированным ветвям, заменяющим эти фрагменты. В результате применения набора стандартных правил сеть преобразуется к одной экви валентной для всего проекта ветви, характеристики которой позволяют су дить о параметрах сложного стохастического проекта.

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

1. Разработка алгебры анализа и преобразования обобщённых сете вых планов [6.10]. В работе [6.12] даны правила сведения пяти основных графов к соответствующим элементарным графам. В так называемой «ос новной алгебре» выделены формулы расчёта вероятностей и времён реали зации эквивалентных элементов, являющихся результатом преобразова ния: а) последовательных дуг, б) параллельных дуг (соотношение «И»), в) параллельных дуг с соотношением «соединительное ИЛИ», г) параллель ных дуг с соотношением «разделительное ИЛИ», д) петель (с неограни ченным и ограниченным числом повторений).

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

контур с двумя вершинами, составные контуры в многоконтур ных графах.

2. Разработка метода анализа обобщённых стохастических сетей, основанного на выделении двух типов модулей - неприводимых сетей и пучков.

Будем называть сеть неприводимой, если исключение любой вершины ведёт к тому, что сумма условных вероятностей её конечных вершин (вы ходов) становится меньше единицы. Пучок - это неприводимая сеть, со держащая одну или более вершин типа «И».

Процедура данного метода анализа сводится к трём этапам:

а) для каждой вершины «И» определить связанный с ней пучок, кото рый может включать другие варианты «И» и в котором вероятность свер шения конечных вершин зависит только от его начальных вершин;

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

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

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

Глава 6. Альтернативные стохастические сетевые модели В случае неудачного исхода «контролирующей» работы вся система воз вращается в «стартовое» состояние (причём работы по параллельному на правлению также прерываются и возобновляются с самого начала). При анализе подобной сети Элмаграби вводит понятие статус-вершины («statusnode»), размещаемой на дуге (дугах), развитие по которой является зависимым.

Исследование заключается в сравнении временных и стоимостных оценок двух способов (политик) организации работ: запараллеливание с риском потерь и возвратов к стартовому состоянию и последовательный способ действий, когда комплекс работ зависимого параллельного разви тия выносится за пределы ситуации выполнения «контролирующей», ис пытательной работы. Выгоды и недостатки обеих стратегий проанали зированы как для детерминированных, так и для вероятностных оценок продолжительности работ [6.12].

4. Исследование частного вида сетей с вершинами типа «исключаю щее ИЛИ» [6.11]. Здесь Элмаграби обосновал возможность сведения сете вых моделей данного вида к «графикам потоков сигналов», для которых имеется разработанный математический аппарат.

5. И, наконец, следует отметить использование Элмаграби при расчете параметров сетевого проекта методов преобразования Лапласа и Z преобразования (соответственно для непрерывных и дискретных характе ристик).

Одно из крупных направлений исследования обобщенных стохастиче ских сетевых планов развито разработчиками систем GERT и VERT [6.18 6.22].

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

Обе системы предназначены для анализа сетевых моделей с «исклю чающими ИЛИ», но позволяет также преобразовать другие типы событий (правда, за счет роста объема сети) в подсети с «исключающими ИЛИ».

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

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

б) сбор необходимых данных для описания ветвей (работ) сети;

в) определение эквивалентной функции или функций сети;

г) преобразование эквивалентной функции в следующие две характе ристики отображения сети: вероятность реализации определенной верши ны;

производящая функция момента времени, соответствующего эквива лентной сети;

формулировка (на основании полученной на этапе «г» ин формации) выводов, касающихся исследуемой системы.

Стохастические Сетевые Модели Планирования и Управления Разработками Данный подход объединяет концепции анализа сети типа PERT и по токов в сетях.

Заметим, что с теоретической точки зрения модели GERT и VERT от личаются друг от друга незначительно. Разница состоит лишь в различных структурах пакетов информационных программ, моделей и программ ста тистического моделирования и ряда других аспектов программного обес печения.

Среди исследований в данной области следует отметить построение Г.С. Поспеловым и В.А. Баришполецом стохастической сетевой модели [6.5]. Данная модель включает 7 типов событий с тремя типами входов и выходов вершин, на которых реализуются логические операции «И», «ИЛИ» (неисключающее), «исключающее ИЛИ». Методы и алгоритмы расчёта модели на ЭВМ базируются на аппарате статистического модели рования вероятностных характеристик работ сети и структуры развёрты вания моделируемого процесса. В результате получается гистограмма рас пределения вероятностей и рассчитываются р-квантильные оценки слу чайной величины времени выполнения всего комплекса операций проекта.

Отметим введенный в указанной модели новый тип выхода событий, так называемый «временной различитель». Выход данного типа отражает операцию, близкую к «исключающему ИЛИ», но характерную тем, что выполняемая на выходе работа определяется номером закончившейся ра боты на входе. Другими словами, каждой входящей в событие «временной различитель» работе ставится в соответствие одна и только одна входящая работа. Так, при входе типа «И» x -я работа, окончившаяся последней из всех входящих в событие работ, приведет соответственно только к началу x -й выходящей работы. При входах типа «исключающее (а также «неис ключающее») ИЛИ» x -я наиболее ранняя из всех закончившихся работ приведёт к началу только входящей x -й работы. Для анализа подобных сложных структур в стохастической сети алгоритмом предусмотрено за поминание последовательности свершения работ.

Следует отметить, что все описанные ранее системы PERT, GERT и VERT не носят управляющий характер. Это информационно-советующие системы, для которых не существует управляющих воздействий, которые за счёт лишь внутренних ресурсов управляемой системы осуществляют ускорение хода работ по проекту.

Возникла необходимость создания АСМ, имеющих в своём составе детерминированные точки ветвления и осуществляющих в этих точках принятие решений, т.е. корректировку управления проектом на стадии оперативного управления. В связи с этим в работах автора монографии [6.2-6.3, 6.14-6.16] впервые были рассмотрены управляющие АСМ-модели CAAN и GAAN, описанные ниже, в главе 8 настоящей монографии. В этих работах даётся определение смешанной (детерминировано-стохастичес Глава 6. Альтернативные стохастические сетевые модели кой) сети, включающей как чисто стохастические ситуации ветвления аль тернатив a (неконтролируемые проектировщиком в момент разработки модели процесса), так и точки ветвления детерминированного характера a, в которых может быть произведён управляемый выбор того или иного варианта развития процесса. Каждому из стохастических вариантов, вет вящихся в a, соотносится априорная вероятность его реализации. Управ ляемым альтернативам, исходящим из a, соответствуют единичные веро ятности, что показывает осуществимость этих вариантов независимо от будущих условий их реализации. Подобное дополнительное подразделе ние множества альтернативных вершин стохастического графа на два под множества вершин детерминированного и стохастического типов, на наш взгляд, приводит к большей адекватности такого рода неоднородных сете вых моделей многим важным производственным процессам (например, разработка целой научно-технической проблемы или технической системы и др.) и открывает новые возможности в развитии методов анализа и управления для систем с многовариантными исходами.

Следующим шагом на пути универсализации сетевых моделей в рам ках рассматриваемого направления являются уточнение и разработка но вой терминологии, отражающей различные структурные особенности сложных стохастических сетей и характеризующей тенденцию к декомпо зиции сложной сетевой модели на отдельные составные части, что сущест венно облегчает анализ стохастических сетевых моделей. Сформулируем основные из этих понятий. Разъединительными путями в стохастической сети названы такие, которые в конечном итоге заканчиваются одним из финальных исходов и начиная с первого же по времени альтернативного события (a -события) не имеют точек объединения с аналогичными аль тернативными путями. Соединительными названы такие пути, которые за канчиваются в конечном счёте объединением с одним или несколькими альтернативными путями, проходящими, возможно, через разные a события. Вводятся понятия частичных, полных и совокупных вариантов реализации сети. Частичные варианты альтернативной сети отражают раз личные пути достижения промежуточной локальной цели моделируемого процесса и включают в себя отдельные комплексы работ и мероприятий, возникающих в одном и том же a -событии и конкурирующих на опреде лённой стадии проектируемого процесса. Полные варианты, отражающие способы достижения конечной цели (целей) моделируемой программы, охватывают весь комплекс работ по ее развитию и составлены из последо вательно разложенных во времени частичных вариантов. Реализация кон кретного полного варианта смешанной сети рассматривается как случай ное событие, но в отличие от чисто стохастических сетевых моделей в данном случае имеется возможность определения групп полных вариан тов, охватывающих все стохастические исходы, которые реализуются при определённом выборе направлений в контролируемых альтернативных си Стохастические Сетевые Модели Планирования и Управления Разработками туациях. Считается, что указанные стохастические исходы составляют по терминологии теории вероятностей полную группу событий. Это, естест венно, позволяет выделить в смешанных сетях специальные структуры, которые получили название совокупных вариантов. Таким образом, сово купный вариант, во-первых, представляет собой результат комбинаций решений в управляемых ситуациях a, т.е. является управляемым вариан том, а во-вторых, является комплексным вариантом, включающим ряд внутренних стохастических полных вариантов. По существу совокупные варианты есть отдельные чисто стохастические сетевые проекты реализа ции одного и того же процесса, построенные при различных предположе ниях об основополагающих научно-технических принципах осуществле ния исследуемого процесса. В свою очередь смешанная сетевая модель может рассматриваться как некоторое объединение этих чисто стохастиче ских проектов.

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

Проанализировав исследования в области АСМ [6.1-6.22], можно рас смотреть стандартизированный подход к отображению многовариантной структуры проекта в АСМ. Согласно логическим возможностям событий, в альтернативной сетевой модели используются четыре типа событий, ото браженных в Табл. 6.1 и реализующих на своих входах либо логическую операцию «И», либо логическую операцию «исключающее (разделитель ное) ИЛИ». Логическое отношение «И» на входе означает, что для свер шения события необходимо выполнение всех входящих в него (предшест вующих) работ;

«исключающее ИЛИ» на входе являются указанием того, что для свершения данного события необходимо и достаточно условие вы полнения одной из входящих работ. Событие с логической возможностью «И» на выходе показывает, что после его свершения могут начаться все вместе, а также любая из выходящих (последующих) работ. В результате свершения события, имеющего на выходе «исключающее ИЛИ», может начаться только одна из совокупности выходящих работ. События I типа (обозначение в математической модели - ~ ) имеют на входе и выходе опе x ~ ) – «И» на входе и «исключающее ИЛИ» на выходе;

рацию «И»;

II типа (a ~ III типа ( b ) – «исключающее ИЛИ» на входе, «И» на выходе;

IV типа (g ) – ~ «исключающее ИЛИ» как на входе, так и на выходе. В качестве «особых состояний» альтернативной сети целесообразно выделить начальное и ко нечное события, а также события, моделируемые в сети вершинами типов ~~~ a, b, g. Последние отражают ситуацию ветвления и объединения альтерна Глава 6. Альтернативные стохастические сетевые модели тивных путей осуществления многовариантной программы. Наиболее ~ ~ важную роль в модели играют события типов a и g, соответствующие си туациям возникновения вариантов и называемые в дальнейшем альтерна тивными или a - событиями.

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

А. Однородные детерминированные сети, отображающие чисто де терминированные многовариантные программы [6.17].

Б. Неоднородные (смешанные) детерминировано-стохастические сети, отображающие программы смешанного типа [6.1-6.3, 6.14-6.16].

В. Однородные стохастические сети, отображающие чисто стохасти ческие программы [6.25].

Каждая из указанных групп моделей включает два типа сетей, предна значенных для исследования [6.3]:

ОП – одноцелевых программ, характеризующихся высокой степенью взаимосвязи работ, наличием единой цели и полнотой вариантных путей (последнее означает, что комплексы работ сети G (Y,U ), составляющие от дельные детерминированные фрагменты Gij (Yij,U ij ), включают полную со вокупность работ соответствующей стадии программы);

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

По принадлежности отдельных работ к двум и более конкурирующим вариантам альтернативные модели разделяются на два вида: не вполне разделимые сети, вполне разделимые сети [6.1-6.3].

Альтернативные сетевые модели любых типов имеют две модифика ции, соответствующие одному из следующих способов задания параметров элементарных операций исследуемой программы: детерминированному (однооценочному), при котором величина оцениваемого параметра являет ся фиксированной;

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

Наконец, в соответствии с допускаемыми в сетевой модели топологи ческими конфигурациями и типами используемых событий можно выде лить четыре типа структур альтернативных сетей (для моделей с любым Стохастические Сетевые Модели Планирования и Управления Разработками сочетанием вышеуказанных признаков) [6.2-6.3] (см. табл. 6.2).

Таблица 6. Логические возможности событий альтернативного сетевого проекта Обозначение Тип события дан- Логическое от- Логические воз ного типа в ношение на вхо- Графическое обозначение можности на выхо собы математиче- де события де события тия ской модели «И» - для свер- «И» - после свер шения события шения события мо необходимо вы- гут начаться все ~ I полнение всех вместе, а так же x входящих в него любая из выходя (предшествую- щих (последую щих работ) щих) работ «исключающее ИЛИ» - в результа те свершения собы ~ a тия может начаться II «И»

только одна из со вокупности выхо дящих работ «исключающее ИЛИ» - для свершения собы тия необходимо ~ b III «И»

и достаточно ус ловие выполне ния одной из входящих работ «исключающее «исключающее ~ g IV ИЛИ» ИЛИ»

Таблица 6. Характеристика альтернативных сетевых моделей Вид используемых в Допустимость соединитель- Допустимость нали модели событий ных и разъединительных пу- чия контуров и пе Тип модели тей (+) или только разъедини- тель (+) или недопус ~~~ ~ abg x тельных () тимость () I + + II + + + + III + +++ + IV + +++ + + I. Сетевые структуры без контуров и петель, допускающие наличие ~ только разъединительных путей (используют события видов ~ и a );

x II. Сетевые структуры с контурами и петлями, имеющие только разъе ~ x~ динительные пути на дереве исходов (используют события ~, a и g );

Глава 6. Альтернативные стохастические сетевые модели III. Сетевые структуры без контуров и петель, имеющие как разъеди нительные, так и соединительные пути;

IV. Сетевые структуры наиболее общего вид, допускающие наличие контуров и петель, соединительных и разъединительных путей.

Альтернативные сети III и IV типов используют события всех ви ~ ~ дов: x ~ ~, a, b и g. Следует отметить, что соединительные пути моделируют в альтернативных сетях такие стадии программы, выбор конкретных вари антов осуществления которых не оказывает влияния на дальнейшую структуру процесса.

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

Сетевые модели PERT и PERT-COST [6.16] используют в своем со ставе события I. Они характеризуются детерминированной структурой и случайным характером входящих в сеть операций.

Сетевые модели ОСМ, описанные В.Воропаевым в [6.24, 8.2], отли чаются наличием сложных логических связей. Продолжительность состав ляющих их работ являются постоянной, а модели содержат события I.

АСМ типа GERT, Q-GERT и VERT [6.18-6.22] имеют в своем составе события I и II. Они являются чисто стохастическими АСМ и, подобно мо делям PERT и PERT-COST, не являются управляющими моделями.

Модели типа Decision-CPM [6.7-6.8, 6.23] содержат вершины типа I и III и позволяют осуществлять команды управления. Вместе с тем эти мо дели не являются стохастическими АСМ, и их точки ветвления не носят случайный характер.

Модель CAAN [6.14, 6.16] содержат в своем составе вершины типа I, II и III и носят управляющий характер, причем команды управления реали зуются в детерминированных точках ветвления. Модель CAAN будет де тально описана ниже, в §8.1.

Модель GAAN [6.15] является обобщением модели CAAN и имеет в своем составе события I-IV. Модель также носит управляющий характер и будет описана в §8.2.

Возникло также направление развития АСМ, для которых не сущест вует стохастических ветвящихся вершин, а многовариантные исходы носят исключительно детерминированный характер. Кроустон [6.7-6.8], а в даль нейшем Хастингс и Мелло [6.17] разработали ряд моделей АСМ, не под верженных случайным воздействиям и не включающих вероятностную терминологию. Соответствующие «Decision-CPM» модели просты в при менении и получили распространение (в основном в экономико финансовых проектах).

АСМ SATM являются комбинацией модели GAAN (управляющей де Стохастические Сетевые Модели Планирования и Управления Разработками терминировано-стохастической (смешанной) не вполне разделимой моде ли) [6.24] и обобщенной детерминированной сетевой модели с весьма об ширными логическими связями [8.2]. Описание этой модели, являющейся в на-стоящее время наиболее сложной и обобщенной АСМ, приводятся ниже, в §8.3.

Описываемая в §8.3 циклическая альтернативная сетевая модель ЦАСМ, подобно моделям GERT и VERT, не носит управляющего характе ра и является комбинацией АСМ: PERT, ОСМ и VERT. ЦАСМ не имеет в своем составе детерминированных ветвлений, но отличается более слож ной логикой, нежели модели GAAN [8.3].

Таблица 6. Классификация событий в сложных АСМ с учетом логики и детерминизма Тип события Вход события Название события Выход события I «И» «И» «И»

«И» или «Стохастиче- «И» или «Стохастиче ское исключающее ИЛИ** ское исключающее II ИЛИ» ИЛИ»

«И» или «Детермини- «И» или «Детермини III рованное исключающее ИЛИ* рованное исключающее ИЛИ» ИЛИ»

«И» вместе со «Стохас- «И» вместе со «Стохас тическим исключаю- И + ИЛИ** тическим исключаю IV щим ИЛИ» щим ИЛИ»

«И» вместе с «Детер- «И» вместе с «Детер V минированным исклю- И + ИЛИ* минированным исклю чающим ИЛИ» чающим ИЛИ»

«Стохастическое ис- «Стохастическое ис ключающее ИЛИ» вме- ключающее ИЛИ» вме VI сте с «Детерминиро- ИЛИ* + ИЛИ** сте с «Детерминиро ванным исключающим ванным исключающим ИЛИ» ИЛИ»

«И» вместе со «Стохас- «И» вместе со «Стохас тическим исключаю- тическим исключаю VII щим ИЛИ» и «Детер- И + ИЛИ* + ИЛИ** щим ИЛИ» и «Детер минированным исклю- минированным исклю чающим ИЛИ» чающим ИЛИ»

Типы I – VII вместе с Типы I – VII вместе с типом «Обобщенных типом «Обобщенных ОСМ + И + ИЛИ* + VIII детерминированных детерминированных ИЛИ** сетевых моделей» сетевых моделей»

(ОСМ) (ОСМ) Что касается моделей Эйснера-Элмаграби [6.9-6.13], то они, хотя и не являются АСМ, фактически относятся к чисто стохастическим многовари антным сетям с оригинальной и сложной алгеброй. Они, безусловно, яв ляются предтечами современных АСМ. К этим же моделям следует отне сти стохастические сетевые модели Хеспосa и Штрасманa [6.25].

Классификация альтернативных сетевых моделей (АСМ)* Таблица 6. Глава 6. Альтернативные стохастические сетевые модели * В таблице приняты следующие обозначения: ОП – сетевые модели одноцелевых проектов;

МП – сетевые модели многоцелевых проектов;

ВР – вполне разделимые сети;

НРВ – не вполне разделимые сети;

D – сетевые модели с детерминированными оценками работ;

S – сетевые модели с вероятностными оценками работ;

I, II, III, IV – типы структур альтернативных сетей, соответствующие Стохастические Сетевые Модели Планирования и Управления Разработками Приводим классификацию АСМ с позиций состава и структуры этих моделей (см. табл. 6.4). На наш взгляд, подобная классификация носит наиболее обобщенный характер с точки зрения задач стохастического аль тернативного сетевого планирования.

Перейдем к рассмотрению основных принципов и подходов к анализу стохастических сетей, разработанных в [6.1-6.3]. Задачи исследования аль тернативных сетей решаются большей частью с использованием принципа укрупнения сетей на основе выделения из сети некоторой ветвящейся структуры, отражающей взаимосвязи особых (альтернативных) состояний моделируемого процесса. При этом используется изложенная выше алгеб ра элементарных преобразований исходной сети. В рассматриваемых рабо тах подобная агрегированная структура получила название дерева исходов и обозначение D ( A,V ), где A - множество вершин дерева, отображающих множество альтернативных событий исходного графа, V - множество дуг дерева, представляющий собой результат эквивалентного преобразования целых фрагментов исходной сети. Дерево исходов D ( A,V ) является макро моделью, которая в предельно агрегированном виде показывает характер зависимостей альтернативных путей реализации моделируемого процесса.

Оно отражает развитие процесса, фиксируя прохождение его через ситуа ции, требующие принятия решений о дальнейшем ходе процесса. Заметим, что на дереве исходов D ( A,V ) частичному варианту соответствует отдель ная ветвь, полный вариант отображается разъединительным путем, соеди няющим корневую вершину дерева с одним из финальных исходов, а со вокупный вариант определяется набором полных.

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

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

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

В заключение отметим, что необходимо расширить рамки сущест вующей классификации и разработать ряд новых алгоритмов для стохас тических альтернативных сетей. На наш взгляд, достаточно универсальной и адекватной стохастической сетевой моделью является сеть, в состав ко торой входят следующие события: на выходе эти события, помимо опера ции «И» в не-исключающем смысле, могут реализовать однородные веро ятностные исключающие либо альтернативные детерминированные, либо неоднородные смешанные типы ветвления. На входе же эти события долж ны реализовать как операцию «И» в неисключающем смысле, так и соединительное «ИЛИ». Иными словами, подобные вершины являются со единительно-разделительными, отличаясь существенно большей сложно стью по сравнению с ранее рассмотренными. В гл.8 рассмотрена матема тическая модель для такого рода сети и разработан математический аппа рат анализа и расчета параметров дерева исходов, включая перечень и ха рактеристики возможных путей достижения цели. Последнее дает возмож ность осуществить принятие решений в детерминированных, управляемых точках ветвления.

§6.4 Математическая модель альтернативной сети Приведем общее математическое описание структуры альтернативных сетевых моделей в терминах теории графов. При этом будем использовать здесь и в дальнейшем терминологию и условные обозначения, принятые в работе [6.3].

В общем случае альтернативная сеть представляет собой конечный связный ориентированный граф G = (Y,U ), обладающий следующими свой ствами (независимо от конкретного типа модели):

1. Граф G имеет одну начальную вершину y 0 (вход сети), для кото рой Г -1 у 0 = O;

Гу 0 O. / / 2. Граф G содержит множество Y таких вершин y ' (называемых ко нечными вершинами, или выходами сети), что Гу = O;

Г -1 у O, причем Y 2.

/ / 3. Множество вершин Y графа G неоднородно и состоит из вершин ~ ~~ ~~ ~ ~ типа ~ X и более сложных логических типов a А, b В, g Г (см. Табл.

x 6.2).

4. Множество дуг U графа G разбивается на подмножество U дуг, соответствующих действительным работам моделируемого комплекса, и подмножество U " дуг, отражающих логические взаимосвязи действитель ных работ и соответствующих фиктивным работам.

5. Содержательная информация, характеризующая временные, стои мостные и другие показатели комплекса работ сетевой модели, задается следующим образом: каждой дуге u kl U графа G, отражающей действи Стохастические Сетевые Модели Планирования и Управления Разработками тельную работу, приписан вектор Wkl величин, показывающих время вы полнения работы (t kl ), требуемые финансовые затраты (c kl ) и другие оцен ки ресурсов I рода, а также оценки ресурсов II рода, используемых при вы полнении работы (k, l ) ;

компоненты этого вектора w ( r ) ( r = 1, n, n - число компонент) могут быть представлены детерминированными оценками ли бо случайными величинами с заданной функцией распределения f (w kl ( r ) ) на интервале a(w ( r ) kl ), b(w (r ) kl ), где a(w ( r )kl ) и b(w (r ) kl ) - граничные оценки r ой компоненты вектора Wkl.

6. В случае неоднородной сети множество вершин (А UГ ) разбивается ~~ на подмножества А - альтернативных вершин, показывающих ветвления детерминированных вариантов, и А - альтернативных вершин, отражаю щих ситуации ветвления стохастических вариантов;

таким образом, ~~ А UГ = АU А.

7. Оценка осуществимости отдельных локальных стохастических ва риантов сетевого проекта может быть проведена двумя основными спосо бами.

а) Производится априорная оценка вероятностей ( p ) локальных вари антов, относящихся к каждой альтернативной вершине a А графа G (при этом предполагается заранее известной структура дерева исходов, что воз можно лишь в простейших случаях);

другими словами, каждому альтерна ~ ~ тивному пути, исходящему из вершины i типа a А или g А и ведущему j ni p к исходу j, отнесено неотрицательное число pij 1, такое, что = 1, где ij j = r ij - априорная вероятность перехода от i к j ;

ni - число локальных вари антов, возникающих в событии i ;

заметим, что для случая соединительных путей переходу от i к j может соответствовать несколько альтернативных путей с вероятностями pij 1, а вероятность перехода m pij = p ijn ;

m - число переходов от i к j.

{} n = б) Набор Рij «локальных» вероятностей исходов альтернативной сети (в случае сложной структуры, а также при невозможности задания доста точно обоснованных априорных оценок) может быть вычислен на основе некоторого критерия, связанного с характеристиками локальных вариан тов, например, вероятность Рij можно положить обратно пропорциональ ной стоимости комплекса операций, ведущих из i в j, при соблюдении m Р условия = 1 для каждой альтернативной вершины i.

ij j = Глава 6. Альтернативные стохастические сетевые модели 8. Для всех без исключения вариантов (детерминированных и стохас тических), исходящих из альтернативных вершин (типа a или ~ ), опреде ~ j ляются оценки меры предпочтительности ( р ) каждого локального варианта в соответствующем наборе конкурирующих вариантов (исходящих из од ной и той же альтернативной вершины). При этом оценки {р} подчиняются nj p алгебре вероятностей, т.е. 0 pij 1, = 1, где pij - относительная пред ij j = почтительность выбора перехода от i к j.

Задачи исследования альтернативных сетей решаются с использова нием принципа укрупнения сети и получения графа, отражающего взаимо связи особых состояний планируемого процесса, причем выделение осо бых состояний зависит от постановки задачи и структуры применяемой се ти. За подобным укрупненным графом сохранено название дерево исходов [6.1-6.3].

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

Для одноцелевых сетевых проектов дерево исходов D = ( A,V ) строится на основе операции преобразования альтернативного графа G = (Y,U ).

1. В качестве множества вершин А = {a i } графа D принимается объе динение подмножеств начальной и конечных вершин, а также вершин, яв ляющихся узлами ветвления альтернативных путей графа G = (Y,U ) ;

таким образом, в общем случае имеем:

А = {у 0 }U {у } U {~}U {b }U {g }.

~ ~ a Начальная вершина a 0 = у 0 графа D называется корнем дерева исхо дов, а конечные {a } = {у }- висячими вершинами.

2. Множество дуг V = { ij } графа D получается в результате эквива J лентного преобразования множества подграфов {Gij }, выделяемых из сети G по следующим признакам:

а) начальной вершиной подграфа Gij = (Yij,U ij ) может служить любая вершина a i, за исключением конечных a ;

при этом a i Yij ;

Г -1a i I Yij = O;

/ ) ) б) Yij a, где a = {a i } U a U 2a U... - есть транзитивное замыкание i i i i отображения a i ;

в) конечной вершиной подграфа Gij может быть только a - вершина a i A \ {у 0 } графа G ;

г) все пути вида (a i,......, a j ), связывающие в Gij начальную вершину a i Стохастические Сетевые Модели Планирования и Управления Разработками с конечной вершиной a j подграфа, не содержат других a -вершин, т.е.

Aij = 2, Aij Yij ;

вершины i и j называются смежными a -вершинами гра фа G ;

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

) ) - для a j типа ~ или a - Yij = Гa I Гa, причем (Yij \ {a i,a j }) X ;

здесь ~ ~ x i j ) Гa = { j }U Г -1a U Г -2a j U..... - транзитивное замыкание обратного отображе a j ния a j ;

~ ) ) - для a i типа b или g имеем Yijn = ai I ({a j } U -n ) ;

n = 1, m, где ~ уn Г -1a j ;

m = Г -1a j - число входов события a j ;

как и в первом случае, (Yij \ {a i,a j }) X.

~ Заметим, что подграфы вида Gijv отражают простейший случай соеди нительных путей (см. §6.2), для которых примем термин «элементарный соединительный путь»;

е) количество ni подграфов Gij, связанных с каждой a i A \ Y, опре деляется числом различных путей вида (a i,......., a j ), отличающихся конеч ной a -вершиной и не имеющих других a -вершин, кроме начальной и ко нечной (если { j } имеют тип ~ или a );

в общем случае ni увеличивается ~ a x на количество дополнительных элементарных соединительных путей mij - 1, cсоответствующих смежным a -вершинам i и j (предполагается, что a j имеет альтернативный вход и связана с a i соединительными путя ми, число которых равно mij ).

Для множества подграфов {G k = (Yk,U k )}, k = w (i, j ), k = 1, N (w - оператор преобразования парного индекса, N - число подграфов) альтернативной сети могут удовлетворяться следующие соотношения:

N N N N I X к = O;

IU к = O;

U X к = X ;

UU к = U, где X = Y \ A;

X к = Yк \ Aк.

/ / k =1 к =1 к =1 к = В первом случае при удовлетворении данным соотношениям, когда фрагменты G не пересекаются между собой, альтернативная сеть называ ется вполне разделимой [6.3]. Если же (в противном случае) имеются ком плексы работ, входящие в различные фрагменты Gк (обычно «порожден ные» одной и той же альтернативной ситуацией - a -вершиной), то сеть считается не вполне разделимой. Вернемся к рассмотрению дерева исходов.

Дуга n ij дерева исходов D = ( A,V ) представляет собой результат сведе ния фрагмента Gij (назовем подграф этого типа I/J-фрагментом) сети G = (Y,U ) к одной дуге с началом a i и концом a j, причем дуга n ij (ветвь Глава 6. Альтернативные стохастические сетевые модели дерева исходов [6.3]) эквивалентна I/J-фрагменту Gij = (Yij,U ij ) в смысле ве роятности реализации р, времени выполнения t и других компонентов вектора W, характеризующих дуги подмножества U ij.

Структура и свойства описанного дерева исходов, а также правила его преобразования при выявлении всевозможных финальных исходов и рас чете их параметров, характеризующих глобальные варианты сетевого про екта, определяются конкретным типом топологической структуры альтер нативной сети G = (Y,U ). Количество глобальных вариантов L* в общем случае определяется числом так называемых L -фрагментов (Gl ) сети, со стоящих из набора путей между начальной вершиной y 0 и 1-м финальным исходом y, причем подобный набор путей не включает альтернативных операций, хотя и проходит по альтернативным вершинам. Таким образом, L -фрагмент представляет собой набор последовательно расположенных во времени I/J-фрагментов:

Gi j UGi j U.....UGi j U....UGi j (i0 у0 ;

jh уl;

jq = iq +1, q = 0,h - 1), qq hh 00 причем указанный набор подграфов отражает один из вариантов детерми нированного сетевого графика проведения всего комплекса работ проекта.

Стохастические Сетевые Модели Планирования и Управления Разработками Глава 7. Исследование однородных неуправляемых альтернативных сетей §7.1 Простейшие альтернативные сети с разъединительными пу тями Рассматриваемая альтернативная сетевая модель характеризуется сле дующими определяющими ее тип свойствами:

а) служит для планирования однородных проектов (группы А и В);

б) является вполне разделимой;

в) соответствует одноцелевому проекту;

г) содержит детерминированные оценки работ;

д) относится к I типу альтернативных структур (см. табл. 6.2).

Приведем математическое описание и алгоритм расчета модели на ЭВМ [7.3].

Данная сеть представлена графом G = (Y,U ), входящим в класс альтер нативных сетей и обладающим следующими характеристическими свойст вами.

~~ ~ 1. Множество вершин Y состоит из вершин типа ~ X и a A, т.е., x ~~ ~~ Y = X U A причем X I A =. Множества a -вершин и x -вершин определя ются так:

A = A U Y ' U {y o };

X = X \ (Y ' U {y o }).

~ 2. Граф G не содержит контуров и петель.

3. Если для каких-либо двух вершин y 1 и y 2 существует путь вида (y1,...,a,..., y 2 ), то и любой другой путь вида (y1,..., y 2 ) должен содержать ту ~ ~ же вершину a. Данное свойство, а также отсутствие в модели событий с альтернативным входом исключает возможность наличия соединительных путей в графе G.

4. Для I/J-фрагментов сети - Gij = (Yij,U ij ) - приняты дополнительные ог раничения:

а) если y 0 Yij \ {a i }, а дуга (y1, y 2 ) U, To (y1, y o ) U ij ;

то (y1, y o ) U ij ;

это обстоятельство вытекает из определения типа входов (операции «И») со бытий сети G ;

б) количество ni подграфов Gij, связанных с a i, определяется числом различных путей вида (a i,...,a j ) ;

при этом все пути, не отличающиеся ко нечными вершинами a i, рассматриваются как идентичные и включаются в один тот же подграф Gij.

5. Количество глобальных вариантов реализации сетевого проекта (или L -фрагментов сети) полностью определяется в исследуемой модели числом L* конечных вершин y ' сети G = (Y,U ).

Дерево исходов для исследуемой альтернативной сети есть конечный Глава 7. Исследование однородных неуправляемых альтернативных сетей граф D = ( A,V ), имеющий следующие свойства:

1 ) множество ветвей V = {vij } эквивалентно множеству подграфов {Gij };

множество вершин А = {y0 }U {y ' }U A ;

корневая вершина дерева исходов ~ a 0 y0 ;

2 ) граф D не содержит контуров и петель;

3 ) в каждую вершину a графа D, за исключением корневой a 0, вхо дит одна и только одна ветвь u V, т.е. U a = 1 для всех a A \ {a 0 };

4 ) число ветвей графа D определяется соотношением V = A - 1.

5 ) число исходящих ветвей определяется соотношением 1 при a = a 0 ;

( { }) = n i при a A \ {a 0 } a ' ;

.

+ Ua {} 0 при a a.

' Таким образом, дерево исходов для исследуемой сети является праде ревом [7.3].

Блок-схема алгоритма расчета на ЭВМ описанной модели (для случая детерминированных оценок работ - модификация D ) представлена на рис.

7.1. Приведем некоторые предварительные пояснения к алгоритму.

1. События {y} исходной сети G = (Y,U ) занумерованы произвольным образом, причем нумерация является сквозной, не зависящей от типов со бытий.

2. Информация о характеристиках дуг {U } сети G = (Y,U ) сгруппирова на в Табл. Т1, которая имеет:

T 1 = i n, j n, P n, t n, C n ;

n = 1, n *, где n - порядковым номер работы ;

n * - общее число работ сети G, т.е.

n* U ;

in, j n - номера начального и конечного события работы U n ;

h(in ) ~ тип начального события работы U n ( h = 0 для ~ -вершины, n = 1 для a x вершины);

pn - «локальная» мера предпочтительности работы ( p = 1 для работы с n = 0, 0 p 1 для работы с h = 1 ). Таким образом, здесь оценка предпочтительности pij локального варианта приписывается первой исхо дящей из соответствующей a -вершины дуге (a i, y ), a i A, y (Гa i Гa j ) ;

~ t n - время выполнения работы U n ;

C n - стоимость выполнения работы U n.

3. В блок-схеме расчета исследуемой модели используются обозначе ния:

{y0 } - начальные вершины рассматриваемого фрагмента сети;

Г y0 = ;

- j * = 1 - признак принадлежности дуги контуру;

j1 - множество дуг с j * = 1 ;

Стохастические Сетевые Модели Планирования и Управления Разработками j * = 0 - дуга не входит в состав контура;

j 0 - множество дуг с j * = 0 ;

j * = 2 - подозреваемые на принадлежность контуру дуги;

Рис. 7.1 Блок-схема расчета модели простейшего типа n1 - число дуг множества j1 ;

( ) ( ) G1 = Y 1,U 1 - граф, образованный дугами с j * = 1, U 1 j1 ;

( ) ~ ~ G = Y, U - граф с измененной на противоположную ориентацией дуг;

- j * 0,1, 2 - служебные признаки для запоминания дуг, за которыми следуют контуры;

Глава 7. Исследование однородных неуправляемых альтернативных сетей j 0, j1, j 2 - соответствующие множества дуг;

a 0 - начальная вершина (вход) подграфа Gij = (Yij : U ij ) ;

a ' - конечная вершина (выход) подграфа Gij ;

l* = 1 - признак шага влево;

l* = 2 - признак шага вправо;

l* = 3 - признак рассмотренной дуги;

l0, l1, l 2, l3 - множества дуг с признаком l* = 0, 1, 2, 3, соответствен но;

q - 1 - признак рассмотренной ветви u дерева исходов D = ( A,V ) ;

T * ( y ) - позднее время наступления события y, определенное на дан ном этапе работы алгоритма;

T ( y ) - расчетное время наступления события y ;

A := B - знак операции присвоения переменной A значения перемен ной B.

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

В логических блоках производится проверка какого-либо соотноше ния (неравенства), причем в случае выполнения соответствующего условия вырабатывается ответ «да», которому эквивалентно значение выходного признака, обозначаемого символом wi (либо ji - в §7.2), где i - номер ло гического блока в данной блок-схеме. В случае невыполнения условия, проверяемого в логическом блоке, вырабатывается ответ «нет» и признак w i = 0. Таким образом, значение признака w i определяет направление пе рехода из i -гo блока.

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

Вернемся к описанию блок-схемы, приведенной на рис. 7.1.

Блок 1. Приведение таблицы Т1 к виду T2 = i n, j n, h(in, ) p n, t n, C n, O1, O2, n = 1, n *, где O1 и O2 - столбцы для записи служебных признаков и расчет ных величин.

Блок 2. Присвоение признака j * = 1 всем дугам графа G = (Y,U ), т.е.

получение графа G1 = (Y 1,U 1 ), U 1 = j1.

Блок 3. Выявление начальных вершин {y 0 } графа G 1, т.е. нахождение дуг {(in, jn ) j1}, для которых in jt, t = 1,2,..., n - 1, n + 1,...n1.

Блок 4. Проверка: { y 0 } ? Если «да» ( { y 0 } ), то следует перейти к следующему блоку 5;

если «нет», то перейти к блоку 7.

Стохастические Сетевые Модели Планирования и Управления Разработками Блок 5. Для дуг вида (y, y 0 ), входящих в j1, записать j * = 2.

Присвоить признаки j * = 0 и j * = 1 дугам вида (y 0, y ) (эти дуги исклю чаются из проверки на контуры, но запоминаются, как, возможно, ведущие в контуры).

Блок 6. Осуществляется проверка, имеются ли в сети G дуги с при знаком j * = 1({j1 } ?). Если имеются, то следует возвратиться к блоку 3, если нет - перейти к блоку 22.

Блок 7. Получение сети G = (Y,U ) путем перестановки столбцов in и ~ ~ j n в табл. Т2.

Блок 8. Выявление начальных вершин {y 0 } графа G1 = (Y 1,U 1 ).

~ ~ Блок 9. Проверка: { y 0 } ?. В случае положительного ответа ( ) алгоритм переходит к блоку 10, в случае отрицательного ( = ) - к блоку 11.

Блок 10. Присвоение признака j * = 0 дугам вида (y 0, y ), т.е. получение нового множества j1 = j1 \ j0. Переход к блоку 8.

Блок 11. Получение исходного графа G = (Y,U ), путем изменения ори ентации дуг графа G = (Y,U ).

~ ~ Блок 12. Выбор и запоминание одной ( j ' -й) из вершин с признаком j * = 1 ;

замена признака дуги (in, j ' ) на j * = 2 ;

присвоение: y 0 := j '.

Блок 13. Выбор дуги вида (y, y 0 ) j1 ;

замена признака этой дуги на j * = 2 ;

i := 0 ;

выбранная дуга ( yi, yi +1 ) ( y0, y1 ).

Блок 14. Сравнение номера вершины yi +1 с номерами последователь ности вершин {y p } = ( y 0, y1,...y i ) : y i +1 y p ;

p = 0, i ?. Если ответ положителен (вершина не встречалась), то переходим к блоку 15;

если отрицателен (yi +1 = y p ;

p {0,...i}) - к блоку 18.

Блок 15. Является ли вершина yi +1 тупиковой ([Gy i +1 j1 ] = ) ? Если да, то управление передается блоку 21;

в противном случае - блоку 16.

Блок 16. Запоминание номера yi +1 в последовательности {y p };

i := i + 1;

yi := yi +1.

Блок 17. Из списка дуг вида ( y i, y ) j1 выбирается дуга ( y i, y i +1 ) ;

при знак этой дуги меняется на j * = 2. Переход к блоку 14.

Блок 18. q := i. Путь вида m = (y p, y p +1,... yq, yi +1 ) есть контур длиной q - p + 1. Печать списка дуг, образующих контур m. Исключение последней дуги выявленного контура из рассмотрения [ j * = 0 для (y q, y p ) ].

Блок 19. Все ли начальные вершины (входы) контуров просмотрены ( Y1 = ) ? Если да, то переход к следующему блоку (20), если нет - возврат к блоку 12.

Блок 20. Замена признака j * = 2 дуг сети G на j * = 1 ;

j1 := j1 j 2. Воз Глава 7. Исследование однородных неуправляемых альтернативных сетей врат к блоку 3.

Блок 21. Дуги пути m = ( y0,..., yi +1 ) не входят в состав контуров и поэто му исключаются из рассмотрения, т.е. j1 := 0 для u m. Возврат к блоку 13.

Блок 22. Останов: проверка на контуры завершена;

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

Блок 23. Чистка столбцов Т2 - O1 и O2 для признака l* и величины T * ( y ) : O1 := 0 ;

O2 := 0.

Блок 24. Определение количества ( A* ) a -вершин сети G :

A* = L* + a * + 1, где L* - число конечных вершин, т.е. количество строк Т2, ~ для которых j n it, t = 1,2,..., n - 1, n + 1,...n *, a * - число вершин типа a, т.е. ко личество строк Т2 с признаком h = 1, уменьшенное на число повторений таких строк с одинаковым номером in.

Блок 25. Резервирование поля памяти для таблицы T3 порядка * A - 1 6.

Блок 26. Засылка исходных параметров цикла по заполнению Т3;

,номер ранга вершин дерева исходов - R := 0 ;

начальная вершина рассмат риваемого I/J-фрагмента - a 0 := y0 ;

номер строки T3 - r := 0 ;

число a -вершин ранга R := 0, N1 := 1 ;

число альтернативных ветвей, исходящих из a 0 y0 - N 2 := 1 ;

рассматриваемая дуга - ur = (a 0, y1 );

y1 Гa 0 ;

оценка меры ' предпочтительности - P r := 1.

' Блок 27. Последовательный перебор дуг пути (y 1, y 2 ), (y 2, y 3 ),…, (y k, a ) вплоть до появления смежной a -вершины;


запоминание номера этой вер шины: a ' := a.

Блок 28. Рассмотрение фрагмента сети G (a 0 - a ' ) = {m k = (a 0,...,a ' )} с помощью алгоритма лабиринта Тарри:

1) нахождение времени реализации фрагмента - T = T (a 0 - a ' ) ;

2) пометка дуг, пройденных алгоритмом, l* := 2.

Блок 29. Получение стоимостной характеристики I/J-фрагмента:

C (a - a ' ) = C r = С n по дугам u l2. Изменение признака дуг u l2 на l* := 3. Занесение в Т3 строки вида: ( iG = a 0, j r = a ', pr = pr ', Tr = T, G r, q r* = 0 ).

Блок 30. Проверка на конец просмотра альтернативных ветвей, исхо дящих из a 0 (N 2 = 0 ) ?. Если таких ветвей нет (N 2 = 0), то переходим к блоку 32;

в противном случае (N 2 0) - к блоку 31.

Блок 31. Выбор дуги ur ' = (a 0, y1 ) l0 (не пройденной алгоритмом Тар ри);

запоминание P r ;

r := r + 1. Возврат к блоку 27.

' Стохастические Сетевые Модели Планирования и Управления Разработками Блок 32. Проверка на конец просмотра a -вершин ранга R : N1 = 0 ?

При положительном ответе - переход к блоку 34, при отрицательном ( N1 0 ) - к блоку 33.

Блок 33. Выбор в Т3 первой ( r ' -й) непомеченной (с q = 0 ) строки:

a 0 := j r. Определение количества альтернативных путей: N 2 = (ua ). Помет- + ка r ' -й строки (ветви Vr ) признаком q * = 1. Переход к блоку 31.

' Блок 34. Номер ранга - R := R + 1. Определение количества подлежа щих рассмотрению a -вершин ранга R : N1 = N - N 1, где N - число непоме ченных (q * = 0) строк Т3;

N 1 - число a -вершин j r строк Т3 с q * = 0, не имеющих исходящих дуг (u ir = ). + Блок 35. Проверка на конец построения дерева исходов: все ли вер шины ранга R конечные ( N = N ' )? Если w35 = 1 - переход к блоку 36;

в про тивном случае - (w35 = 0 ) - возврат к блоку 33.

Блок 36. Расчет (на основании Т3) характеристик финальных исходов ~ ~ сети G : Pl = П p ;

Tl = Tr ;

Cl = Cr по всем v r m l ;

l = 1, L* ;

где m1 - путь на r дереве исходов D, соединяющий корневую вершину с финальным исхо дом;

vr - ветвь дерева исходов.

Блок 37. Выбор оптимального варианта, т.е. такого L -фрагмента с но мером l * (финального исхода a l' ), для которого F1 (l * ) = max [F1 (l )]. Здесь * l =1, L* функция F1 есть функция (критерий) полезности исхода с учетом времени ~ ~ исхода Tl, стоимости Cl и вероятности исхода P l. Печать состава опти мального L -фрагмента (перечня соответствующих дуг сети G = (Y,U ) и их параметров), а также характеристик l * -ого исхода.

Блок 38. Останов.

В рассматриваемом алгоритме можно выделить следующие укруп ненные участки:

1) выявление контуров и петель - блоки 2-21;

данный yчaсток должен входить в процесс расчета любого типа альтернативной сети;

2) анализ информации о выявленных контурах - блок 22;

в случае расчета моделей типа II и IV (табл. 6.1), допускающих контуры, следует подключить сюда алгоритм замены контуров эквивалентными ду гами, после работы которого осуществляется обработка сети, не имеющей контуров;

3) определение структуры дерева исходов и расчет характеристик вет вей - блоки 24-35;

вид данного участка определяется принадлежностью се ти к типам I и II или III, IV, а также способом задания исходной информа ции;

4) расчет характeристик финальных исходов (блок 36);

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

Глава 7. Исследование однородных неуправляемых альтернативных сетей 5) выбор оптимального варианта осуществления проекта - блок 37;

мы здесь рассмотрели простейший случай перебора вариантов и оценки их в баллах в зависимости от расположения соответствующих характеристик исходов в последовательности вида {xn (li )}.

Рис.7.2 Модифицированный алгоритм лабиринта Тарри В алгоритм входит один укрупненный блок 28, в котором осуществ ляется упорядоченный обход дуг I/J-фрагментов сети G = (Y,U ) на основе использования алгоритма лабиринта Тарри, модифицированного с учетом специфики альтернативных сетевых графов.

Алгоритм блока 28 целесообразно оформить в виде стандартного уча стка (рис. 7.2), входными данными для которого служат номера начальной ( a 0 ) и конечной ( a ' ) вершин фрагмента, а также таблица Т2;

результатами работы участка являются время Т и набор помеченных дуг I/J фрагмента (в Т2). В алгоритм лабиринта Тарри входят блоки:

Блок 1 - записать y j := a '.

Блок 2 - определить возможность выполнения шага влево из вершины y j : есть ли дуги вида (y, y j ), для которых l* = 0, (т.е. {( y, y j ) l 0 }?). Если такие дуги имеются, то перейти к блоку 3, если нет - к блоку 4.

Блок 3 - выбрать дугу (yi, y j ) l0, присвоить ей признак l* = 1 (в столб це O1 Т2);

положить y j := y j и перейти к блоку 2.

Блок 4 - определить возможность выполнения шага вправе из верши ны y j (т.е. {( y, y j ) l1 }, или y j a ' ?). При наличии такой возможности перейти к блоку 5, в противном случае - к блоку 10.

Блок 5 - найти дугу вида (y j, yk ) l1 и присвоить ей признак l* = 2.

Блок 6 - определить T ( y k ) = T * (y j ) + t (y j, y k ), где t (y j, yk ) - есть t n соот Стохастические Сетевые Модели Планирования и Управления Разработками ветствующей дуги Т2;

T * (y j ) есть заранее найденное значение T для дуг вида (y, y j ).

Блок 7 - провести сравнение: T ( yk ) T * ( yk )? При выполнении неравен ства перейти к блоку 9, при невыполнении - к блоку 8.

Блок 8 - записать новое значение T * := T ( y k ) для всех дуг Т2 вида ( y, y k ) в столбце O2.

Блок 9 - положить y j := yk ;

перейти к блоку 2.

Блок 10 - положить время реализации фрагмента G = (a 0 - a ' ) равным T := T * ( y j = a ' ).

Более подробное описание таблиц алгоритма приводится в §§7.1-7. работы [7.3].

§ 7.2. Анализ альтернативных сетей с соединительными путями В настоящем параграфе продолжается рассмотрение одноцелевых, вполне разделимых сетей группы А (модификация D), структура которых отражает другой важный с практической точки зрения случай - наличие соединительных путей, что характерно для сетевых структур типов III и IV. Соединительные пути соответствуют таким этапам планируемого про цесса, по которым возможны различные варианты осуществления, но ре зультатом реализации вариантных путей развертывания данного этапа яв ляется достижение одной общей цели этапа, причем в дальнейшем ход мо делируемого процесса не зависит от того, каким из альтернативных путей процесса прошел данный этап.

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

~ ~ События с альтернативными входами (типа b и g ), которые отража ют слияние нескольких соединительных альтернативных путей, целесооб разно назвать соединяющими событиями. Введем также понятие « M фрагмент» сети G = (Y,U ), под которым будем понимать совокупность аль тернативных путей, заключенных между альтернативным событием a ~ ~ ~ ~ (типа a или g ) и соединяющим cсобытием a 2 (типа b и g ), т.е. путей ви да m = (a1,...,a 2 ) на сетевом графе G = (Y,U ), проходящих в общем случае че рез различные a -вершины. M -фрагмент обозначается через G = (a1 - a 2 ) и состоит из двух и более соединительных путей.

Заметим, что соединительный путь является путем (в терминах теории графов) лишь на дереве исходов D = ( A,V ). Для первоначальной альтерна тивной сети G = (Y,U ) соединительный путь между a1 и a 2 интерпретиру ется как множество путей {m} вида (a1,...,a 2 ), проходящих через один и тот же набор a -вершин и не включающих альтернативных операций, так что {m} отражает детерминированный по составу работ вариант осуществления Глава 7. Исследование однородных неуправляемых альтернативных сетей соответствующего этапа (стадии или набора последовательных стадий проектируемого процесса).

В рассматриваемой альтернативной сети G = (Y,U ) могут встретиться соединительные пути следующих видов.

1. Элементарные соединительные пути (v ) - соединяют a -вершины i и j дерева исходов D = ( A,V ) ветвями vijS ), кратность которых равна числу ( (S v ) путей вида (a i,...,a j ) на графе G = (Y,U ), не имеющих «внутренних» (от личных от a i и a j ) a -вершин и представляющих различные локальные ва рианты реализации перехода процесса в особое состояние a j (напомним, что в рассматриваемых моделях в качестве особых состояний приняты ~~~ вершины типов a, b, g, а также начальная и конечные вершины).

Элементарные соединительные пути (n -пути) имеют две разновидно сти:

а) пути v соединяют a -вершины двух соседних рангов (или поколе ний) дерева исходов D = ( A,V ) ;

6) пути v соединяют a -вершины i и j несоседних поколений дерева исходов, т.е. r (a j ) - r (a i ) 1, где r (a ) - номер поколения (ранга) вершины a.

Множество элементарных соединительных путей между a i и a j со ставляет M -фрагмент G = (a1 - a 2 ), соответствующий определенному в [7.3] и в §7.1 подграфу Gij = (Yij,U ij ).

В случае соединительных путей целесообразно уточнить понятие I/J фрагмента, исходя из того, что каждому I/J-фрагменту сети G = (Y,U ) должна быть поставлена в соответствие одна ветвь дерева исходов D = ( A,V ). Рассмотрим две ситуации:

а) конечная вершина a j подграфа Gij = (Yij,U ij ) не относится к соеди няющим событиям;

тогда I/J -фрагмент совладает с подграфом Gij и опре деляется следующим образом:

) ) Yij = a i -a j, (7.2.1) ) где ai = {ai } ai 2ai K - транзитивное замыкание отображения a i ;

) -a j = {a j } -1a j -2a j K - транзитивное замыкание обратного отображе ния a j ;

U ij = {( y k, y l ) \ ( y k, y l ) Yij, y l Yij }, (7.2.2) причем (Y \ {a, a }) X, ~ (7.2.3) ij i j ~ где X - множество вершин типа ~ сети G = (Y,U ) ;

x б) если a j соответствует соединяющему событию, подграф Стохастические Сетевые Модели Планирования и Управления Разработками Gij = (Yij,U ij ). разбивается на mij I/J-фрагментов GijS ), отражающих элементар ( ные соединительные пути;


при этом s -й I/J-фрагмент определяется сле дующим образом:

) ) Yij( S ) = ai ({a i } - y s ) ;

s = 1, s v mij, (7.2.4) ) ) где y s ( -a j -1a j ) - начальная вершина одной из дуг, входящих в a j и лежащих на пути вида (a i,...,a j ) ;

) mij m j = -a j, (7.2.5) где m j - общее число альтернативных входов события a j.

Множество дуг Y ( S )ij I/J-фрагмента удовлетворяет соотношению вида (7.2.2), т.е.

U ijS ) = {( y k, y l ) / ( y k, y l ) U, y k Y ( S ) ij, y l Y ( S ) ij }, ( а вершины I / J - фрагмента, за исключением ai и a j, относятся к типу ~ x (соотношение 7.2.3).

Неравенство (7.2.5) означает возможность наличия более сложных со единительных путей, входящих в вершину ai.

2. Обходной соединительный путь ( l ) отражается в сети G = (Y,U ) I/J фрагментом, начальная (a i ) и конечная ( a j ) вершины которого относятся к двум несоседним поколениям вершин дерева исходов, причем вершина a j является соединяющей, и в a j входит еще хотя бы один соединительный путь вида (a i,...,a j ), включающий внутренние a -вершины. В графе D = ( A,V ) пути типа l соответствует одна ветвь vij.

3. Составные соединительные пути (n ) проходят по вершинам не скольких поколений дерева исходов (т.е. имеют внутренние a -вершины) и включают в себя конечный набор последовательных I/J-фрагментов типа Gij или G ( S )ij. Таким образом, в графе D путь типа n, заключенный между a k и a l, представлен простым путем вида m = (i0 a k, i1,..., iq,..., i qv a l ), где iq - номер a -вершины, по которой проходит составной соединитель ный путь;

qv - номер конечной вершины пути n, равный длине этого пути на графе D.

В сети G = (Y,U ) соединительный путь v(a k,a l ) соответствует объеди нению подграфов следующего вида:

(S ) (S ) v(a k,a l ) = Gi( Sj ) Gi( Sj ) K Gi j = q =1Gi j, (7.2.6) R Q q 1 11 22 QQ qq j q = j q +1 ;

q = 1, Q - 1, (7.2.7) где i1 a k - начальная вершина составного соединительного пути;

jQ a l - конечная вершина составного соединительного пути;

Глава 7. Исследование однородных неуправляемых альтернативных сетей Q qv - число I/J-фрагментов или длина соединительного пути на де реве исходов;

(S ) Gi j - q -й I/J -фрагмент, по которому проходит данный соединитель q qq ный путь n ;

S q - номер входа соединяющей вершины jq I/J-фрагмента ( S q = 0 для ~ jq типа ~ или a ).

x Составные соединительные пути имеют две разновидности:

а) путь n включает в себя I/J-фрагменты типа Gij, соединяющие a вершины соседних поколений и элементарные соединительные пути типа n;

б) путь n может включать также обходные соединительные пути и элементарные соединительные пути типа n.

Соотношение (7.2.6) требует пояснения, так как оно показывает один соединительный путь типа n, а число путей nv, заключенных между a k и a l, всегда больше или равно двум. Для определения nv необходимо мно жество соединительных путей вида (a i,...,a j ) разбить на подмножества, в каждое из которых входят соединительные пути, проходящие через один и тот же набор a -вершин. При этом полученные подмножества путей можно отнести к типу n или n. Длина соединительных путей типа n равна разно сти номеров поколений r (a i ) - r (a j ), а количество таких путей определяется числом M -фрагментов, включающих элементарные соединительные пути, и числами Sn путей в каждом таком M -фрагменте. Количество путей типа n определяется аналогично, а длина путей n всегда меньше разности r (a i ) - r (a j ).

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

1. Соединительный путь может заканчиваться только в соединяющем ~ ~ событии (типа b или g ).

2. M -фрагмент альтернативной сети, содержащий обходный соедини тельный путь l, должен включать также по крайней мере один составной соединительный путь n.

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

4. Если M -фрагмент G (a k - a i ), r (a i ) - r (a k ) 1, не содержит «внутрен них» обходных путей, т.е. таких, начальная или конечная вершина которых Стохастические Сетевые Модели Планирования и Управления Разработками относится к внутренним для данного M -фрагмента вершинам, а число внутренних a -вершин какого-либо составного соединительного пути v (a k,a l ) равно c, то число входящих в путь n элементарных соединитель ных путей (h ) удовлетворяет соотношению c - 1 h c + 1.

При построении дерева исходов D = ( A,V ) для рассматриваемой аль тернативной сети G = (Y,U ) будем исходить из очевидного предположения, что просмотр путей, начинающихся в различных выходах альтернативных событий (a, g ) и заканчивающихся в различных входах соединяющих со ~ бытий (b, g ), позволит нам (при условии учета всех особых состояний про ~~ цесса) выявить полную структуру графа D = ( A,V ).

Алгоритм выявления дерева исходов строится, таким образом, на принципе нахождения всех I/J-фрагментов сети G и замены этих фрагмен тов эквивалентными ветвями.

Рассмотрим работу участка алгоритма построения графа D = ( A,V ) для сети G = (Y,U ) с соединительными путями (блок-схема приведена на рис.7.3). Предполагается, что перед работой данного участка были выпол нены следующие операции:

Рис. 7.3 Блок-схема алгоритма построения дерева исходов D = ( A,V ) для сети G = (Y,U ) с соединительными путями 1) проверка сети G на контуры;

выявление ошибок;

2) замена (если в сети G допускаются контуры) контуров эквива лентными дугами;

3) пометка a -вершин.

Информация о сети G = (Y,U ) задана таблицей вида Глава 7. Исследование однородных неуправляемых альтернативных сетей T 1 = i n, j n, h(i n ), g ( j n ), D(in ), D( j n ), O1, w n1),...,w n p ), n = 1, n *, ( ( где h(in ) - тип выхода начального события дуги U n ;

h {0,1};

g ( j n ) - тип входа события jn, g {0,1} ;

D(in ), D( jn ) - признаки a -вершины для событий in и jn, соответственно;

O1 - столбец для записи служебного признака w {0,1,2} ;

wn1),...,wn p ) - характеристики (временные, ресурсные) работы U n.

( ( Искомая таблица информации о дереве исходов должна иметь вид:

T 2 = im, j m, O (1),..., O ( p ), O1, O2 ;

m = 1, m *, где im, jm - коды начала и конца ветви vm ;

m* - общее число ветвей графа D (m* = V );

O1 - столбец для записи вероятности реализации, рассчитываемой на основании характеристик соответствующего I\J-фрагмента (для групп Б и В сетевых обобщенных моделей - рис. 7.4);

O2 - столбец для записи служебного признака;

O (1),...,O ( p ) - столбцы для записи характеристик ветви w m.

В приведенной на рис. 7.3 блок-схеме не рассматриваются вопросы расчета характеристик ветвей, так как принципы расчета не зависят от ти па альтернативной сетевой модели.

Рис. 7.4 Дерево исходов D = ( A,V ) альтернативной сети с соединитель ными путями Опишем по блокам операции, выполняемые алгоритмом построения дерева исходов D = ( A,V ) (отметим, что в блок-схеме на рис. 7.3 признак условного перехода обозначается символом ji ).

Блок 1. Осуществляет изменение ориентации дуг в сети G = (Y,U ), в результате чего получаем граф G = (Y,U ), каждая дуга которого (k, l ) U со ~ ~ ~ Стохастические Сетевые Модели Планирования и Управления Разработками ответствует дуге (l, k ) U графа G.

~ Блок 2. Выбор и запоминание конечной вершины j1 сети G ( y' =, y' y0 ;

y0 - начальная вершина сети G ). Засылка начальных значе ний рабочих переменных y1 и m (номер ветви графа D ): y1 := y ' ;

m := 1.

Блок 3. Выбор дуги, не пройденной шагом влево, т.е. дуги (y j, yi ) w0.

Шаг влево из вершины yi заключается в нахождении дуги вида ( y, yi ), вхо дящей в данную вершину, и пометке этой дуги признаком w * ( y, yi ) = 1. За пись: w * (y j, yi ) = 1.

Блок 4. Определяет, является ли yi a -вершиной (при D(y j ) = 1 выраба тывается признак j 4 = 1 ;

при D(y j ) = 0 обозначение j 4 = 0 ).

Блок 5. Запоминается следующая просматриваемая вершина:

yi := y j.

Блок 6. Запись дуги (y ', y j ) в таблицу информации о дереве исходов T 2 : im := y1;

jm := y j. Изменение номера ветви в T 2 : m := m + 1.

~ Блок 7. Определяет, является ли y j начальной вершиной графа G (т. е.

конечной вершиной y ' графа G ). Если -1 y j =, то j7 = 1 ;

при -1 y j = при знак j7 = 0.

Блок 8. Выясняет, относится ли y j к типам a и g. При h( y i ) = 0 обо ~ ~ значение j = 0 ;

при h( y i ) = 1 обозначение j g = 1.

~ Блок 9. Определяет, имеется ли в сети G хотя бы одна дуга вида (y, y j ) (w1 w2 ) ;

при этом предполагается, что y j относится к типу b, j9 = 0, ~ если {( y, y j ) \ ( y, y j ) (w1 w2 )} =, и j9 = 1 - в противном случае.

~ Блок 10. Определяет, имеются ли в сети G дуги путей, не пройденных алгоритмом. Если {( y, y j ) \ ( y, y j ) w0 } =, то j10 = 0 ;

в противном случае j10 = 1.

Блок 11. Засылает очередные исходные значения рабочих перемен ных: y1 := y j ;

yi := y j.

Блок 12. Выполнение шага вправо из вершины y j по дуге, пройденной до этого шагом влево, т.е. выбор дуги (y j, yk ) w1, и запись:

w * ( y j, yk ) : = 2.

Блок 13. Выясняет, является ли yk a -вершиной, и вырабатывает при знак j13 = 1, если D( yk ) = 1, и j13 = 0 при D( yk ) = 0.

Блок 14. Запоминается очередная вершина: y j := yk.

~ ~ Блок 15. Определяет, относится ли a -вершина yk к типам a и g, и вырабатывает j15 = 1 при h( yk ) = 1 либо j15 = 0 при h( yk ) = 0.

Блок 16. Выясняет, имеются ли непросмотренные альтернативные вы Глава 7. Исследование однородных неуправляемых альтернативных сетей ходы вершины yk. Если {( y, yk ) / ( y, yk ) w0 } =, то j16 = 0, в противном слу чае j16 = 1.

Блок 17. Засылает исходные значения рабочих переменных:

y1 := yk ;

yl := yk.

~~ Блок 18. Выясняет, относится ли a -вершина yk к типам b, g. Если g ( yk ) = 1, то j18 = 1, если же g ( yk ) = 0, то логический признак j18 = 0.

Блок 19. Засылает исходные значения рабочих переменных для про смотра соединяющей вершины: y 0 := yk ;

yq := yk.

Блок 20. Определяет, имеются ли непросмотренные альтернативные входы вершины y 0, и вырабатывает j 20 = 0, если {( y 0, yk ) / ( y0, y ) w0 }, и j 20 = 0 - в противном случае.

Блок 21. Выбор дуги (yq, yl ) w0, не пройденной алгоритмом, и выпол нение шага вправо с записью признака: w * (yq, yl ):= 2.

Блок 22. Проверяет, является ли yl a -вершиной;

при этом j22 = 1 для D( yl ) = 1, j 22 = 0 для D( yl ) = 0.

Блок 23. Осуществляет переход к очередной вершине: yq := yl.

Блок 24. Запись в таблицу Т2 дуги (yl, y 0 ) : im := yl ;

jm := y 0. Изменение номера дуги: m := m + 1.

Блок 25. Засылает значение рабочей переменной: y j := y 0.

~ Блок 26. Определяет, является ли yk конечной вершиной графа G, т.е.

начальной вершиной y0 графа G. При yk y0 вырабатывается j26 = 0, и ра бота алгоритма продолжается. Если yk y0, то j26 = 1 и можно считать, что просмотр сети закончен и структура дерева исходов D = ( A,V ) выявлена полностью (т. е. построена таблица T 2 = i m, j m,0,... ;

m = 1, m * ).

Блок 27. Засылает значение рабочей переменной: y j := yh.

Как ранее отмечалось, соединительные пути в альтернативной сетевой модели показывают последовательности стадий проектируемого процесса (в графе G = (Y,U ) ). Эти последовательности отражаются соответствующи ми M -фрагментами, выбор конкретных вариантов осуществления которых (т.е. выбор соединительных путей) не оказывает влияния на характер даль нейшего развертывания процесса.

В то же время следует подчеркнуть то важное обстоятельство, что для определения параметров, характеризующих моделируемый процесс (по времени реализации, стоимости и т.п.), вовсе не безразлично, каким соеди нительным путем «прошел» процесс в ситуацию, отражаемую тем или иным соединяющим событием. Поэтому действительное число ( L* ) фи нальных исходов планируемого процесса не определяется (в случае нали чия соединительных путей) количеством конечных вершин сети G = (Y,U ) Стохастические Сетевые Модели Планирования и Управления Разработками или, что то же самое, количеством конечных вершин дерева исходов D = ( A,V ).

В связи с этим целесообразно различать несколько - по количеству альтернативных входов соединяющего события - событий в составе a, а дерево исходов D = ( A,V ) следует привести к виду ветвящейся структуры D = (A,V ), отображаемой графом типа прадерева [7.З].

~~ Предположим, что в результате работы алгоритма преобразования се ти G = (Y,U ) (см. рис. 7.3) получено дерево исходов D = ( A,V ), изображенное на рис. 7.4. Допустим также, что рассчитаны характеристики (временные, ресурсные, оценки предпочтительности) ветвей дерева исходов D.

В дереве исходов, показанном на рис. 7.4, можно выделить три M фрагмента, включающие довольно сложные соединительные пути:

G (3 - 16 ) ;

G (4 - 14 ) ;

G (2 - 15). Для удобства исследования графа D a вершины расположены по поколениям.

Укажем примеры описанных ранее видов соединительных путей:

1) в составе M -фрагмента G (3 - 16 ) :

v -пути - G7,12, m12 = 2 ;

G12,16, m12,16 = 2 ;

G8, 3, m8, 3 = 2.

v -пути - G6,16, m6,16 = 2 ;

l -пути - G3,16, m3,16 = 2 ;

u -пути - G3, 7,12,16, m3, 7,12,16 = 4 ;

G3,8,13,16, m3,8,13,16 = 2 ;

u -пути - G3, 6,16, m3, 6,16 = 2 ;

2) в составе M -фрагмента G (4 - 14 ) :

v -пути - G4, 9, m4,9 = 2 ;

G10,14, m10,14 = 2 ;

v -пути - G4, 9,14, m4,9,14 = 2 ;

G4,10,14, m4,10,14 = 2 ;

3) в составе M -фрагмента G (2-15):

v -пути - G11,15, m11,15 = 3 ;

l -пути - G2,11, m2,11 = 1 ;

G5,15, m5,15 = 1 ;

u -пути - G2, 5,11, m2, 5,11 = 1 ;

G5,5,11, m5,5,11 = 3 ;

G2, 5,11,15, m2, 5,11,15 = 3 ;

u -пути - G2, 5,15, m2,5,15 = 1 ;

G2,11,15, m2,11,15 = 3.

Количество финальных исходов, показанное графом D = ( A,V ) на рис.

7.4 и равное четырем (19, 20, 17, 18), не отражает, как уже отмечалось, фактического набора конечных состояний планируемого процесса, одно родных в смысле достижения общей единой цели, но различающихся зна чениями параметров, которые характеризуют «качество» достижения цели.

Для расчета общего числа ( L* ) финальных исходов необходимо знать количество альтернативных путей, связанных с каждой конечной верши ной графа D = ( A,V ). Введем понятие « K -фрагмент», под которым мы бу Глава 7. Исследование однородных неуправляемых альтернативных сетей дем понимать совокупность путей на дереве исходов D, соединяющих корневую вершину с какой-либо конечной вершиной ( p -й) и проходящих через одну и ту же последовательность a -вершин. Обозначим K -фрагмент через G (a 0 - a1 - La r ), где a 0 - корень дерева исходов;

a1 - L - a r -1 - a - вер шины, по которым проходят пути K -фрагмента;

a r = a ( p ) - p -я конечная вершина графа D.

Очевидно, K -фрагмент может включать только элементарные соеди нительные пути (n -пути).

Введем следующие обозначения:

K * ( p ) - число K -фрагментов, связанных с p -й конечной вершиной;

P* Y ' - число конечных вершин графа D с соединительными путями;

k - индекс K -фрагмента;

Qk - количество участков в k -м K -фрагменте, включающих n -пути;

S k (q ) - количество n -путей на q -м участке (q = 1, Qk ) K -фрагмента.

Теперь можно записать формулу расчета (исходя из вида графа D ) количества L* глобальных вариантов проекта:

p* K * ([( ] [( ]) ) ) L = W1 Gk a 0 - a ( p ) / Qk 1 + W 2 Gk a 0 - a ( p ) / Qk = 0, (7.2.8) * p =1 k = g (a - a ( ) ) символ где k 0 k -ого K -фрагмента, связанного с конечной верши p ной a ( p ) ;

[( ] ) W1 Gk a 0 - a ( p ) / Qk 1 - функция, вычисляемая на K -фрагменте, содер жащем элементарные соединительные пути (n );

рассчитывается по фор муле Qk W1 = S k (q ) ;

(7.2.9) q = [( ] ) W 2 Gk a 0 - a ( p ) / Qk = - функция, вычисляемая на K -фрагменте, не включающем -путей;

равна всегда единице.

Например, на рис. 7.4 можно выделить следующие K -фрагменты:

G (1 ® 2 ® 3 ® 6 ® 16 ® 19), G (1 ® 2 ® 3 ® 7 ® 12 ® 16 ® 19), G (1 ® 2 ® 3 ® 8 ® 13 ® 16 ® 19 ), G (1 ® 2 ® 3 ® 16 ® 19 ) - для a (1) = 19 ;

те же фрагменты - для a (2 ) = 20 ;

G (1 ® 2 ® 4 ® 9 ® 14 ® 17 ), G (1 ® 2 ® 4 ® 10 ® 14 ® 17 ) - для a (3 ) = 17 ;

G (1 ® 2 ® 5 ® 18), G (1 ® 2 ® 5 ® 11 ® 15 ® 18), G (1 ® 2 ® 11 ® 15 ® 18) для a (4 ) = 18.

Число финальных исходов по формулам (7.2.8-7.2.9) составит:

L* = (2 + 2 2 + 2 + 1) + (2 + 2 2 + 2 + 1) + (2 + 2) + (1 + 3 + 3) = 29.

Задача выявления полного набора финальных исходов и вместе с тем соответствующих L -фрагментов сети, характеризующих глобальные вари анты реализации рассматриваемого одноцелевого проекта, может быть решена путем построения вышеназванного графа D = (A,V ), который дол ~ ~~ Стохастические Сетевые Модели Планирования и Управления Разработками жен иметь свойства дерева исходов сетевой модели типа I (см. § 7.1).

Предложим следующую процедуру преобразования графа D = ( A,V ), состоящую из двух укрупненных этапов.

Этап I. Осуществляет преобразование соединительных путей в разъе динительные и включает следующие операции.

1) Расположим вершины {a } графа D = ( A,V ) по поколениям, т.е. ка ждой a поставим в соответствие номер поколения r (a ) = Y;

Y {0,1,..., Y* }, где Y = 0 - номер старшего поколения;

Y* - номер младшего поколения, равный длине наидлиннейшего пути, идущего в конечную вершину графа D. На рис. 7.4 a -вершины размещены по поколениям, причем r (a ) = 0 при a a 0 ( a 0 - корень дерева исходов);

( ) r (a ) = Y + 1 для a ГA Y \ Г 2 AY Г3 AY K Г Y - Y AY, * где AY = { j / r (a j ) = Y} - множество a -вершин Y -ого поколения;

a Y* Y = A.

UA Y = 2) Каждой вершине a графа D приписываем начальные значения индексов p (a ) = 1, в результате чего a -вершине будет соответствовать пара [a, p (a )]. Поставим в соответствие каждому номеру a число p max (a ) = 1, ха рактеризующее максимальное значение индекса p (a ).

Рассмотрение a -вершин будем вести, начиная со старшего поколе ния, т.е. положим вначале Y = 0, AY = { j }Y = {a 0 }, и далее будем просматри a вать множества a -вершин последовательных поколений - AY, AY +1,K, c це лью выявления вершин с соединяющим альтернативным входом (типа ~~ ~~ b B или g Г ).

3) Очередную вершину вида a Y B Г разобьем на число (m j ) вер ~~ j шин, равное числу входов a Y, после чего перенумеруем входящие в a Y j j ветви дерева исходов D = ( A,V ) следующим образом:

· номера начальных вершин a i ветвей uij остаются без изменения {[a i, p (a i )]}, a i Г -1a Y ;

j · конечная вершина одной из дуг uij также остается с прежним но мером a Y, p (a Y ), а остальным вершинам присваиваются новые значения j j индекса p :

[a ] () Y, p max a Y + X, X = 1, m j - 1.

j j Таким образом, оказались занумерованы по-новому (m j - 1) ветвей, входящих в a Y. Запишем новое значение p max для вершины a Y :

j j p max (a j ) := p max (a j ) + (m j - 1).



Pages:     | 1 |   ...   | 5 | 6 || 8 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.