WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     | 1 |   ...   | 4 | 5 || 7 |

«Д.И. Голенко-Гинзбург СТОХАСТИЧЕСКИЕ СЕТЕВЫЕ МОДЕЛИ ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ РАЗРАБОТКАМИ Воронеж Научная книга 2010 УДК 621.39:519.2 ББК 65.291.217 Г 60 Рецензенты: д.т.н., профессор ...»

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

Глава 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.9-6.13], то они, хотя и не являются АСМ, фактически относятся к чисто стохастическим многовариантным сетям с оригинальной и сложной алгеброй. Они, безусловно, являются предтечами современных АСМ. К этим же моделям следует отнести стохастические сетевые модели Хеспосa и Штрасманa [6.25].

* В таблице приняты следующие обозначения: ОП – сетевые модели одноцелевых проектов; МП – сетевые модели многоцелевых проектов; ВР – вполне разделимые сети; НРВ – не вполне разделимые сети; 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 ' (называемых конечными вершинами, или выходами сети), что 3. Множество вершин Y графа G неоднородно и состоит из вершин типа ~ X и более сложных логических типов a А, b В, g Г (см. Табл.

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 А и ведущему r ij - априорная вероятность перехода от i к j ; ni - число локальных вариантов, возникающих в событии i ; заметим, что для случая соединительных путей переходу от i к j может соответствовать несколько альтернативных путей с вероятностями pij 1, а вероятность перехода б) Набор Рij «локальных» вероятностей исходов альтернативной сети (в случае сложной структуры, а также при невозможности задания достаточно обоснованных априорных оценок) может быть вычислен на основе некоторого критерия, связанного с характеристиками локальных вариантов, например, вероятность Рij можно положить обратно пропорциональной стоимости комплекса операций, ведущих из i в j, при соблюдении Глава 6. Альтернативные стохастические сетевые модели 8. Для всех без исключения вариантов (детерминированных и стохастических), исходящих из альтернативных вершин (типа a или ~ ), опредеj ляются оценки меры предпочтительности ( р ) каждого локального варианта в соответствующем наборе конкурирующих вариантов (исходящих из одной и той же альтернативной вершины). При этом оценки {р} подчиняются алгебре вероятностей, т.е. 0 pij 1, = 1, где pij - относительная предij почтительность выбора перехода от i к j.

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

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

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

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

Начальная вершина 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... - есть транзитивное замыкание отображения a i ;

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

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

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

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

уn Г -1a j ; m = Г -1a j - число входов события a j ; как и в первом случае, Заметим, что подграфы вида Gijv отражают простейший случай соединительных путей (см. §6.2), для которых примем термин «элементарный соединительный путь»;

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

В первом случае при удовлетворении данным соотношениям, когда фрагменты 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-фрагментов:

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

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

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

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

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

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

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

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

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

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

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

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

4. Для I/J-фрагментов сети - Gij = (Yij,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 ; корневая вершина дерева исходов 2 ) граф D не содержит контуров и петель;

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

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

5 ) число исходящих ветвей определяется соотношением Таким образом, дерево исходов для исследуемой сети является прадеревом [7.3].

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

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

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

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

где 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 } - начальные вершины рассматриваемого фрагмента сети;

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

Стохастические Сетевые Модели Планирования и Управления Разработками 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.

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 ; замена признака этой дуги на Блок 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 в последовательности Блок 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* и величины Блок 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 порядка Блок 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) характеристик финальных исходов дереве исходов D, соединяющий корневую вершину с финальным исходом; vr - ветвь дерева исходов.

Блок 37. Выбор оптимального варианта, т.е. такого L -фрагмента с номером l * (финального исхода a l' ), для которого F1 (l * ) = max [F1 (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). В алгоритм лабиринта Тарри входят блоки:

Блок 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.

Блок 10 - положить время реализации фрагмента G = (a 0 - 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 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 и определяется следующим образом:

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

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

причем где X - множество вершин типа ~ сети G = (Y,U ) ;

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

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

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

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

(соотношение 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, представлен простым путем вида где iq - номер a -вершины, по которой проходит составной соединительный путь; qv - номер конечной вершины пути n, равный длине этого пути на графе D.

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

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

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

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

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

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

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

а) путь n включает в себя I/J-фрагменты типа Gij, соединяющие a вершины соседних поколений и элементарные соединительные пути типа б) путь 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 всегда меньше разности Из рассмотренных конфигураций соединительных путей могут быть построены любые достаточно сложные альтернативные сети исследуемого класса. Сформулируем некоторые очевидные свойства соединительных путей альтернативных сетевых моделей.

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 ) удовлетворяет соотношению При построении дерева исходов 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. Исследование однородных неуправляемых альтернативных сетей где h(in ) - тип выхода начального события дуги U n ; h {0,1};

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

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

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

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

где 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. Запоминается следующая просматриваемая вершина:

Блок 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, Блок 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, и запись:

Блок 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. Засылает исходные значения рабочих переменных:

Блок 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 для Блок 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 ) :

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

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

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* глобальных вариантов проекта:

ной a ( p ) ;

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

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

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

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

Задача выявления полного набора финальных исходов и вместе с тем соответствующих 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 - корень дерева исходов);

где AY = { j / r (a j ) = Y} - множество a -вершин 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 целью выявления вершин с соединяющим альтернативным входом (типа 3) Очередную вершину вида a Y B Г разобьем на число (m j ) верj шин, равное числу входов a Y, после чего перенумеруем входящие в a Y ветви дерева исходов D = ( A,V ) следующим образом:

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

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

Глава 7. Исследование однородных неуправляемых альтернативных сетей 4) Каждую исходящую из вершин a Y дугу вида (a Y,a k ) записываем столько раз, на сколько вершин была разбита a j ; при этом конечным вер- Y шинам новых ветвей a k присваивается индекс p (a k ), равный соответствующему индексу начальной вершины - p (a Y ). Таким образом, получаем j множества дуг:

теристики дуг множества V (a k ) одинаковы и соответствуют характеристикам ветви (a j,a k ). Находим величины p max (a k ) = max [p (a k )] для всех a k Гa jY.

5) Проверяем, имеется ли в графе D вершина вида a Y B Г. Если такая вершина имеется, то определяем ее номер a Y и возвращаемся к опеj рации 3). В противном случае переходим к рассмотрению a -вершин множества AY +1.

Здесь выполняется проверка на конец работы I-го этапа процедуры:

сравниваются номера (Y + 1) и Y*. Если (Y + 1) = Y *, то мы считаем, что I-й этап преобразования графа D закончен, получено дерево исходов D1 = (A1,V 1 ) с разъединительными путями и можно переходить ко II-му этапу. При (Y + 1) Y *, переходим к следующей операции.

6) Полагаем Y = Y + 1 и возвращаемся к операции 5).

В результате работы I-го этапа рассматриваемой процедуры преобразования графа D = ( A,V ), изображенного на рис. 7.4, получаем граф D1 = (A1,V 1 ), показанный на рис. 7.5, где значения p (a ) показаны верхними индексами номеров вершин.

Этап II заключается в перестройке графа D1 = (A1,V 1 ) таким образом, что новый граф D 2 = (A2,V 2 ) отражает только ветвления моделируемого процесса, т.е. исключаем a -вершины, не отражающие ситуаций принятия решений (по выбору вариантов). Результатом работы данного этапа является получение искомого дерева исходов, т.е. D 2 = (A2,V 2 ) D = (A,V ).

Приведем следующий алгоритм обхода графа D1 и получения графа D2.

1) Рассмотрение графа D1 = (A1,V 1 ) начнем с a -вершины первого поколения: a i := a Y =1. Ветвь (a 0,a ) оставляем без изменения. Переходим далее к выявлению a -вершин 2-ого поколения графа D 2 = D.

2) Находим вершину вида a j Гa iY и проверяем, является ли a j ветвящей или конечной вершиной.

Если a j A Г A', где A' - множество конечных вершин графа D1, то дугу (a i,a j ) записываем без изменения, указав лишь номер поколения (Y + 1) вершины a j, и переходим к рассмотрению следующей вершины Стохастические Сетевые Модели Планирования и Управления Разработками a Гa jY ; при a j B / A' выполняем следующую операцию.

Рис. 7.5 Преобразованное дерево исходов D1 = (A1,V 1 ) 3) Выбираем a Гa jY и выясняем, к какому типу относится a j. При Глава 7. Исследование однородных неуправляемых альтернативных сетей a j1 B выбираем следующую вершину a j 2 Гa j1 и т.д., пока a j 2 не окажется ветвящей или конечной вершиной.

4) Мы определили вершину a j A Г A '. Заменим в выявленный в графе D1 путь (a i,a j,a j, K,a j ) одной дугой (a i,a j ) с характеристиками, равными соответствующим характеристикам комплекса дуг пути (a i,...,a j ).

Вершине a j присваиваем номер поколения (Y + 1) и переходим к рассмотh рению следующей вершины, принадлежащей Y -му поколению - операция 2).

Заметим, что пройденные алгоритмом дуги помечаются специальным признаком.

Если все исходящие из вершин {a iY } дуги рассмотрены, то, полагая Y = Y + 1, переходим к рассмотрению ветвей, исходящих из следующего поколения вершин, до тех пор, пока не дойдем до конечных вершин самого младшего поколения графа D 2 = (A2,V 2 ).

Окончательный вид дерева исходов D = (A,V ) для нашего иллюстрирующего примера показан на рис. 7.6, где a -вершины размещены по поколениям, а число финальных исходов, равное 29, подтверждает формулу 7.2.8.

Рассмотренные алгоритмы выявления и преобразования дерева исходов с соединительными путями могут использоваться для моделей с любыми типами вариантных путей (т.е. для всех групп моделей - А, Б, В) при условии принадлежности этих моделей к одноцелевым и вполне разделимым сетям.

Как будет показано в гл. 8, модели А, Б и В различаются только при последующем математическом анализе структуры графа D = (A,V ).

§ 7.3 Альтернативные сети с пересекающимися I/J-фрагментами Пересекающимися I/J-фрагментами назовем такие подграфы Gij (либо GijS ) в сетях с соединительными путями) альтернативной сети G = (Y,U ), для которых начальные вершины a i совпадают и множества вершин (Yij ) и дуг (U ij ) взаимно пересекаются (другими словами, альтернативная сеть G является не вполне разделимой [7.3]).

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

Допущение в альтернативных сетях логических структур типа «пересекающиеся I/J-фрагменты» предполагает более свободную интерпретацию выходов альтернативных событий (вида a и g ), при которой между выходящими из альтернативных событий дугами может существовать не Стохастические Сетевые Модели Планирования и Управления Разработками Рис. 7.6 Окончательный вид дерева исходов D = ( A,V ) только логическая возможность «исключающее ИЛИ», но и возможность «И»; последняя реализуется, например, между дугой, принадлежащей нескольким I/J-фрагментам, и дугой, входящей только в один из I/JГлава 7. Исследование однородных неуправляемых альтернативных сетей фрагментов. На рис.7.7 изображены два локальных варианта, включающих общую операцию, которой соответствует дуга (1,5) ; между дугами (1,2 ) и (1,5), а также дугами (1,3) и (1,5) реализуется логическое отношение «И».

Рис.7.7 Пример пересекающихся I/J-фрагментов Рассмотрим виды пересекающихся I/J-фрагментов для различных структур одноцелевого проекта.

1. Альтернативная сеть с разъединительными путями может иметь исходящие из вершин a (a i A Г ) пересекающиеся I/J-фрагменты Gij = (Yij ,U ij ),...,Gij = (Yij,U ij ), характеризующиеся следующими свойствами:

2. В альтернативных сетях с соединительными путями могут встретиться следующие случаи пересечения I/J-фрагментов:

а) пересечение подграфов, отражающих элементарные соединительные пути типа n ;

б) пересечение обходного соединительного пути и исходящего из той же a -вершины I/J-фрагмента.

Рассмотрим один из алгоритмов анализа на ЭВМ альтернативной модели довольно общего вида с пересекающимися I/J-фрагментами. На рис.7.8 приведена блок-схема участка данного алгоритма, характеризующего процедуру выявления структуры дерева исходов D = ( A,V ), основанную на последовательном использовании метода перемешивания дуг сети.

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

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

Перейдем к описанию алгоритма.

1) Исходная информация о сети G = (Y,U ) задана в таблице 2) Рабочая таблица имеет вид где D1 - признак a -вершины для in, D1 {0,1} ;

D 2 - признак a -вершины для jn, D 2 {0,1};

n - порядковый номер дуги;

O1 - столбец для записи l* {0,1, 2}.

Рис.7.8 Блок-схема алгоритма выявления структуры дерева исходов D = ( A,V ) для не вполне разделимой сети Глава 7. Исследование однородных неуправляемых альтернативных сетей 3) Искомая таблица дерева исходов имеет вид где ir, j r - коды начала и конца r -й ветви;

O1, O2, O3, On - столбцы для записи меры предпочтительности pr, времени tr стоимости Cr и признака q * {0,1}, соответственно.

Алгоритм включает в себя следующие блоки (рис. 7.8):

Блок 1. Изменение ориентации дуг в сети G = (Y,U ), т.е. получение графа G = (Y,U ). Положить: L := 0.

Блок 2. Выбор конечной вершины сети G : y1 y0 (начальная вершина графа G ); y = ; запись: yi := y1.

Блок 3. Выбор дуги, не пройденной шагом влево (с l* = 0 ), т.е. дуги (y j, yi ) l0 ; запись: l* (y j, yi ) := 1.

Блок 4. Выясняет, является ли вершина y j a -вершиной. В случае положительного ответа вырабатывается признак w4 = 1, по которому осуществляется переход к блоку 6. При отрицательном ответе w4 = 0, и переход производится к блоку 5.

Блок 5. Запомнить: yi := y j и возвратиться к блоку 3.

Блок 6. Проверка: имеется ли в ТЗ строка вида (yi, y j ). Если да, то переход к блоку 8; в противном случае - к блоку 7.

Блок 7. Запись дуги (yi, y j ) в таблицу TЗ и подсчет числа найденных алгоритмом ветвей - L := L + 1.

Блок 8. Проверка: является ли y j начальной вершиной графа G = (Y,U ) (т.е. одним из финальных исходов сети G )? Если да, то перейти к блоку 10, в противном случае - к блоку 9.

Блок 9. Положить: y1 := y j, yi := y j ; и возвратиться к блоку 3.

Блок 10. Выбор дуги, пройденной шагом влево, (y j, yi ) l1 - и выполнение шага вправо по этой дуге, т.е. запись: l* (y j, yi ) := 2.

Блок 11. Проверка: является ли вершина yi a -вершиной? Если да перейти к блоку 13, если нет - к блоку 12.

Блок 12. Записать: y j := yi и возвратиться к блоку 10.

Блок 13. Проверка: является ли вершина yi конечной вершиной графа G ? Если да - перейти к блоку 17, если нет - к блоку 14.

Блок 14. Выясняет, имеются ли в сети G дуги вида ( y1, yi ) l0 - не пройденные шагом влево. Если имеются - перейти к блоку 15, если нет - к блоку 16.

Блок 15. Положить: y1 := yi и возвратиться к блоку 3.

Блок 16. Положить: y j := yi и возвратиться к блоку 10.

Стохастические Сетевые Модели Планирования и Управления Разработками Блок 17. Определяет, были ли найдены алгоритмом на данном этапе его работы новые ветви дерева исходов (L 0). Если да, то перейти к перемешиванию дуг (блок 18); в противном случае рассматриваемый алгоритм заканчивает свою работу и передает управление следующему этапу расчета сетевой модели.

Блок 18. Засылка исходных характеристик цикла по перемешиванию дуг сети G : количество неперемешанных дуг сети N := n* ; шаг перемешивания H := 1/N ; номер рассматриваемой строки T 2 - k := 1.

Блок 19. Нумерация числами от 1 до N дуг сети, расположенных в строках Т2, начиная от k -й и кончая n* -й.

Блок 20. Выработка значения x случайной величины x, равномерно распределенной на интервале [0,1].

Блок 21. Нахождение номера i -гo интервала, в который попадает x k :

Блок 22. Запись строки с номером i на место k -й строки Т2 и перемещение содержимого R -й строки на место освободившейся строки (с номером i ).

Блок 23. Проверка на окончание перемешивания: k = n* - 1. Если да, то осуществляется переход к блоку 25, если нет - к блоку 24.

Блок 24. Положить: N := N - 1 ; k = k + 1 ; H := 1/N, и перейти к обработке следующей строки (блок 19).

Блок 25. Чистка столбца Т2 для признака l* : l0 = U. Запись L := 0 и возврат к блоку 2.

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

Глава 8. Управляемые альтернативные сетевые модели Глава 8. Управляемые альтернативные сетевые § 8.1 Смешанные вполне разделимые управляющие АСМ класса CAAN.

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

1. Является конечным, связным, ориентированным графом;

2. Содержит одну корневую вершину и не менее двух висячих вершин;

3. Описывает одноцелевой проект;

4. Дерево исходов содержит только вершины типа g (сеть вполне разделимая);

5. Дерево исходов может содержать как управляемые альтернативные вершины (множество А ), так и неуправляемые (множество А );

6. В дереве исходов допускается наличие как разъединительных, так и соединительных путей;

7. Оценки для работ сети имеют детерминированный характер.

В предыдущих параграфах глав VI и VII были рассмотрены основные понятия и определения частичного, полного и совокупного вариантов для смешанной стохастической сетевой модели. Нетрудно показать, что совокупный вариант может быть выделен из исходного графа путем «закрепления» определенных направлений в управляемых взаимосвязанных вершинах a и отсечения незакрепленных направлений. Иначе говоря, каждый совокупный вариант может рассматриваться как один из управляемых вариантов реализации проекта, представляющий из себя однородную стохастическую сетевую модель и имеющий ряд возможных стохастических конечных состояний. Предположим, что для каждой a -вершины задано несколько направлений. Будем считать, что они пронумерованы по часовой стрелке последовательными натуральными числами. Направление соответствует реализации одного из возможных вариантов события. Каждой дуге, выходящей из a -вершины, соответствует некоторое направление h, причем несколько дуг, выходящих из одной вершины, могут иметь одно направление.

Как и для любой альтернативной сети, дерево исходов D ( A,V ) модели CAAN [6.1-6.3, 6.14] содержит в своем составе корневую вершину a 0, все висячие вершины a и все ветвящиеся вершины a. Каждая работа u ij дерева исходов, (i, j ) A, эквивалентна определенному фрагменту Gij исходной модели G (Y,U ). Поскольку модель CAAN является вполне разделимой Стохастические Сетевые Модели Планирования и Управления Разработками сетью, различные фрагменты Gij не пересекаются. Сеть CAAN содержит все четыре логических типа вершин (см. табл. 6.1), хотя дерево исходов содержит только вершины g. Пример дерева исходов, которым мы будем использовать на протяжении всего раздела, представлен на рис. 8.1.

На рис. 8.1 все дуги дерева исходов (i, j ), выходящие из вершин a i или a i, нумеруются по часовой стрелке индексами hij = 1, 2, K, ni, где ni есть число ветвлений (выходов) вершины a i. Направление дуги vij приравнивается соответствующему индексу hij. В качестве примера, дуги, выходящие из вершины 1, имеют следующие направления:

h12 = 1, h19 = 2, h13 = 3 ; дуги, выходящие из вершины 3 :

Следует отметить, что в дереве исходов дуга vij соответствует частному варианту; путь, соединяющий корневую вершину a 0 с одной из висячих вершин a ', соответствует полному варианту.

Определение.

Набор a -вершин и направлений выходящих из них дуг, который однозначно определяет совокупный вариант, мы будем называть допустимым планом [8.5-8.9].

Рис. 8.1 Пример дерева исходов Пусть A = {a 1, a 2,... a n } - множество a - вершин дерева исходов D ( A,V ).

Каждый совокупный вариант S характеризуется выбором определенных направлений в некоторых из этих вершин, то есть некоторым набором Такой набор (8.1.1) называется допустимым планом. В нашем примере для получения допустимого плана надо выбрать непротиворечивые направления в выбранных взаимосвязанных вершинах дерева исходов, например, 1 ® 2, 2 ® 4, 6 ® 10, 7 ® 12, представляют собой непротиворечивые направления в вершинах 1, 2, 6, 7. Такой совокупный вариант изображен на рис. 8.2.А, а соответствующий ему допустимый план имеет вид:

{1,1; 2,1; 6,1; 7,1}.

Глава 8. Управляемые альтернативные сетевые модели Рис. 8.2 Совокупный вариант (а) и подсеть (б) Оптимальная задача на модели CAAN.

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

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

Таким образом, оптимальная задача решается на следующих трех этапах:

Стохастические Сетевые Модели Планирования и Управления Разработками Этап 1. Выделить из дерева исходов все совокупные варианты и допустимые планы. Процесс начинается при t = 0, то есть до начала реализации проекта.

Этап 2. Определить для каждого из совокупных вариантов значения целевой функции и ограничений (обычно в виде математических ожиданий).

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

Пусть, например, при t = 0 для дерева исходов на рис. 8.1 в качестве оптимального совокупного варианта выбрана сеть, представленная на рис.

8.2а. В момент t = 0 следует направить проект по направлению 1 ® 2 и исключить все альтернативные направления, а именно 1 ® 3 и 1 ® 9 со всеми следующими дугами (3,5), (3,9), (3,8), (3,16 ), (9,16), (9,17 ), Когда проект достигнет вершины 2, необходимо повторить процесс оптимизации, но уже для сокращенной, оставшейся части сети, изображенной на рис. 8.2б. Заметим, что в процессе реализации проекта возможны изменения в параметрах модели, например значений tij, cij, pij и т.д., поскольку для долговременного проекта могут иметь место случаи изменения рыночной конъюнктуры, и др. Например, не исключено, что в точке 2 мы выберем направление 2 ® 5 в качестве оптимального направления, а не ранее выбранное в момент t = 0 направление 2 ® 4. Таким образом, управление носит динамический характер.

Математическая формулировка задачи оптимизации [8.7].

Определить совокупный вариант S *, оптимизирующей математическое ожидание значения целевой функции с ограничениями где: W - набор полных вариантов, входящих в S -й совокупный вариант;

- набор совокупных вариантов, входящих в сеть CAAN;

pis - вероятность осуществления i -го полного варианта в S -м совокупном варианте;

F (p is ) - значение целевой функции для i -го полного варианта в S -м совокупном варианте;

Н (p is ) - значение ограничения для i -го полного варианта p is в S * -м совокупном варианте;

Глава 8. Управляемые альтернативные сетевые модели H - заранее заданный уровень ограничения целевой функции.

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

Входная и выходная информация для алгоритма. Входной информацией для работы алгоритма является граф G, описывающий исходную альтернативную сетевую модель. Граф задается в виде массива G, состоящего из записей одинаковой структуры. Каждая запись описывает одну дугу графа (vi v j ) и содержит номер начальной вершины i, направление hi из начальной вершины, номер конечной вершины j, вероятность Pij реализации дуги, вектор Wij характеристик дуги. Тип начальной вершины определяется значением hi : если hi 0, то вершина является альтернативной, если hi = 0 - не является.

Структура одной записи исходного массива представлена так:

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

1) для всех дуг, выходящих из какой-либо a -вершины i, значение hi не равно 0 ;

2) a -вершины i принадлежат множеству А тогда и только тогда, когда все Pij равны 1.

Выходной информацией, получаемой в результате работы алгоритма, являются оптимальный совокупный вариант, соответствующее ему значение критерия оптимальности и управление, приводящее к этому совокупному варианту. Оптимальный совокупный вариант задается в виде массива дуг, идентичных (8.1.4). Оптимальное управление задается в виде массива пар ( a i, hi ), указывающих последовательность управляемых a -вершин a i A, и выбираемые в них направления. В процессе расчета допускается выдача всех совокупных вариантов и соответствующих управлений, а также значения критерия оптимальности. Детализированный алгоритм описан в [8.5, 8.7].

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

Блок 1. Осуществляется ввод информации от исходной сетевой модели. Входная информация содержит описок всех дуг, их характеристики и коды вершин.

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

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

Рис. 8.3 Укрупненная блок-схема алгоритма Блок 4. Построение очередного максимального пути. Выбирается очередной в лексикографическом порядке максимальный путь в a -остове.

Блок 5. Построение совокупного варианта. Выбранный максимальный путь в a -остове порождает совокупный вариант. Для его нахождения строится подграф дерева исходов, содержащий все пути, ведущие из a вершин в заданных направлениях.

Блок 6. Расчет совокупного варианта. Для построенного совокупного варианта вычисляется значение целевой функции по формуле (8.1.2).

Глава 8. Управляемые альтернативные сетевые модели Блок 7. Запоминание лучшего варианта. Значение целевой функции для последнего построенного варианта сравнивается с результатами предыдущих расчетов, и запоминается наилучший вариант.

Блок 8. Анализ максимального пути. Последний построенный максимальный путь анализируется на возможность его преобразования в очередной максимальный путь. Если это возможно, осуществляется переход к блоку 4 для продолжения перебора, если нет - к блоку 9.

Блок 9. Печать результатов. Выдается информация о построенном оптимальном совокупном варианте и его характеристиках.

Блок 10. Конец реализации алгоритма.

Процедуры реализации блоков 1, 6-10 носят тривиальный характер и не встречают принципиальных трудностей. Гораздо более сложными являются алгоритмы блоков 2-5. Детализированная блок-схема программы блока 2 - построения дерева исходов – представлена в [8.5, 8.7].

Процедура блоков 3-5, особенно в случае моделей CAAN большого объема, требуют нетривиальных решений. Опишем три подалгоритма - подалгоритм I расчета a -остова, подалгоритм II построения максимальных путей и подалгоритм III определения совокупных вариантов и допустимых планов. Все три подалгоритма организованы так, что выходная информация каждого подалгоритма является входной для последующего. Для подалгоритма I входной информацией является описанное выше дерево исходов [8.4-8.7].

Под a -остовом мы будем впредь понимать набор всех возможных четверок a i, hik, a j, Pijk. Здесь a i и a j - a -вершины дерева исходов, hik - направление ветвления, а Pijk - означает вероятность реализации пути из a i в d j в направлении hik, причем в этом пути между вершинами a i и a j имеются только вершины a со стохастическим ветвлением. Такого рода путь называется a -простым [8.7]. На рис. 8.1 имеются, например, два a простых пути из вершины 2 в вершину 7 : ( 2, h24 = 1, 7, 0.2 ) и ( 2, h25 = 2, 7, 0.52 ), два a -простых пути между вершинами 1 и 16, и т.д. Идея подалгоритма I [8.7] состоит в сортировке всех a -вершин (включая висячие вершины) и из каждой их них a j осуществляется движение назад (в обратном направлении) до тех пор, пока не встретиться либо корень a 0, либо какая-либо из a -вершин. Строятся триады a i, hik, a j, оцениваются вероятности Pijk и, в случае наличия мультиграфа (в случае нескольких одинаковых триад a i, hik, a j с различными Pijk ) последние суммируются.

Например, есть два a -простых пути ( 1, h13 = 3, 8, 0.05 ) и ( 1, h13 = 3, 8, 0.40 ), соответственно, через вершины ( 1, 3, 5, 8 ) и ( 1, 3, 8 ). В данном случае четверка ( a 1, h13 = 3, 8, 0.45 ) имеет место. a -остов для сети на рис. 8.1 представим в табл. 8.1.

Стохастические Сетевые Модели Планирования и Управления Разработками Идея подалгоритма II состоит в том, что все триады a -остова «достраиваются» до максимальных путей, которые в дальнейшем сортируются в лексикографическом порядке. Два различных максимальных пути сравниваются между собой. Если несколько пар в обоих путях a a и a m, hab и hmn, и т.д. совпадают, а в паре различных элементов значение элемента в X 1 меньше соответствующего значения в X 2, то X 1 предшествует X 2 лексикографически. В табл. 8.2 представлены значения максимальных путей в дереве исходов (см. рис. 8.1). Подалгоритм II построения максимальных путей описан в [8.7].

Подалгоритм III построения совокупных вариантов и допустимых планов реализуется на трех различных стадиях [8.7].

Стадия III А имеет следующую блок-схему:

Таблица 8.1 a -остов Таблица 8.2 Максимальные пути в дереве исходов Блок 1. Из списка максимальных путей исключить все висячие вершины.

Блок 2. Исключить все «укороченные» пути, которые являются частью «укороченных» максимальных путей. Например, пути X 15 и X 16 после исключения висячих вершин являются частью пути X 14 (см. табл. 8.2).

Блок 3. Если несколько «укороченных» путей после блока 1 совпадают, оставить только один из них (пути X 9 и X 10 в табл. 8.2).

Стадия III Б. Основана на лексикографическом сравнении и близка по идее к подалгоритму II. Она состоит из двух блоков:

Блок 1 реализует процедуру построения первого непротиворечивого «укороченного» максимального пути (то есть, первого допустимого плана);

Блок 2 реализует процедуру перехода к очередному непротиворечивому «укороченному» максимальному пути (то есть, к очередному допустимому плану).

Два «укороченных» различных максимальных плана носят название противоречивых, если они содержат общую альтернативную вершину a f c взаимоисключающими направлениями h fp и h fq.

Блок 1 работает следующим образом. Выбирается первый укороченный максимальный путь {, h12 = 1, 2, h24 = 1, 6, h6,10 = 1}. Второй укороченный путь {, h12 = 1,2, h24 = 1,6, h6,11 = 2} противоречит первому ( h6,10 = 1, h6,11 = 2 ), в отличие от третьего {, h12 = 1,2, h24 = 1,7, h7,12 = 1} максимального укороченного пути. Выбираем из третьего пути «непротиворечивое» звено ( 7, h7,12 = 1 ) и добавляем его к первому пути. Получаем «наращенный» допустимый план В дальнейшем просматриваем все остальные укороченные максимальные пути и проверяем, можно ли добавить какое-либо новое звено (a v, hv, w ) к «наращенному» допустимому плану (8.1.6), не нарушая его непротиворечивости.

Блок 2 анализирует очередной «наращенный» допустимый план, к которому никакое новое звено добавлено быть не может. Исключаем его последнее звено (a i, hi q ) и проверяем, можно ли «нарастить» оставшийся допустимый план до максимального, с тем, однако, чтобы этот план не совпадал ни с каким из ранее полученных. Если да, то управление передается блоку 1. В противном случае исключаем еще одно звено слева a i, hi q, q, и снова пытаемся этот оставшийся план «нарастить» до нового максимального, и т.д. Работа стадии III Б прекращается, когда очередной Стохастические Сетевые Модели Планирования и Управления Разработками последовательно «укорачиваемый» допустимый план делается пустым.

Список допустимых планов для нашего примера представлен в табл. 8.3.

Таблица 8.3 Список допустимых планов {W } W7 = 1, { },2, {2},7, {2},8, { } Стадия III В подалгоритма III осуществляет построение совокупных вариантов дерева исходов. Входной информацией при этом является список допустимых планов {W } и дерево исходов D ( A,V ). Учитывая, что совокупный вариант S, соответствующий очередному допустимому плану W, должен быть:

1. Подграфом дерева исходов D ( A,V ).

2. Содержать все вершины, входящие в W, но не содержать никаких других вершин.

3. Содержать висячие вершины a, которые являются висячими вершинами дерева исходов D ( A,V ).

Делается вывод, что S должен быть максимальным подграфом, отвечающим условиям 1-3.

Отсюда вытекает алгоритмизация стадии III В [8.7], основанная на следующем: для каждого a i W строится подграф D ( A,V ), содержащий все максимальные a -простые пути, выходящие из вершины a i в направлении hik W. Комбинация объединения всех этих подграфов содержит в своем составе и совокупный вариант S. Построение совокупного варианта осуществляется отсечением части дуг таким образом, чтобы любой максимальный путь в оставшемся подграфе окончился либо вершиной, принадлежащей W, либо висячей вершиной a.

Решим оптимизационную задачу (8.1.2-8.1.3) на примере дерева исходов, представленной на рис. 8.1. Информация о дереве исходов представлена в табл. 8.4.

Продолжительность работы (i, j ) - t ij - дается в месяцах, а стоимость работы Cij - в тысячах условных единиц. Необходимо минимизировать математическое ожидание продолжительности выполнения проекта при условии, что средняя стоимость проекта не должна превышать 23000 у.е. Необходимо разработать для менеджера проекта оптимальное управление, т.е. выбрать оптимальное направление разработки проекта для всех точек ветвления a i, которые будут достигнуты в процессе выполнения проекта.

Глава 8. Управляемые альтернативные сетевые модели В таблице 8.5 представлены результаты расчета средних значений продолжительности проекта Т s и среднего значения стоимости проекта Cs для всех входящих в дерево исходов совокупных вариантов.

Таблица 8.4 Информация о дереве исходов Таблица 8.5 Характеристика совокупных вариантов Примечание: * - оптимальный вариант Число последних равно 13, причем лишь два из них, S12 и S10, удовлетворяют ограничениям (8.1.3). Для обоих из них C s 23000. Выбрав из допустимых вариантов совокупный вариант с наименьшим Т s, получаем оптимальное решение для S = 10, Т 10 = 5,12 и C10 = 22,22. Совокупный вариант S10 представлен на рис. 8.4:

Таким образом, менеджеру проекта предлагается осуществить оптимальное управление проектом следующим образом:

А. В начале реализации проекта ( t = 0 ) в вершине 1 надо выбрать операцию ( 1,3 ).

Б. Если в результате хода работ по проекту будет достигнута вершина 7, а сеть не претерпит изменений своих параметров, следует выбрать наСтохастические Сетевые Модели Планирования и Управления Разработками правление ( 7 ® 12 ), то есть реализовать операцию ( 7,12 ).

В. Если в результате хода работ по проекту будет достигнута вершина 8, следует реализовать операцию ( 8,14 ).

Г. Вершины 3, 5 и 9 совокупного варианта не носят управляющего характера.

Рис. 8.4 Оптимальный совокупный вариант S В заключение отметим, что вся изложенная выше методика может быть использована и для случайных величин tij и Cij. При этом на этапе алгоритма решения задачи (8.1.2-8.1.3) следует, в целях оценки Т s и Cs, использовать аппарат статистического моделирования.

§ 8.2 Универсальная смешанная управляющая альтернативная модель GAAN [8.8] В предыдущем параграфе главы нами была описана вполне разделимая смешанная АСМ, которая позволяет осуществлять оптимальное управление в детерминированных точках ветвления. В настоящем разделе мы опишем смешанную АСМ более общего вида, в частности, допускающую наличие вершин, из которых могут одновременно выходить несколько операций различных типов. Напомним, что все вершины, входящие в CAAN, могут относиться либо к классу ~, либо к детерминированному a или g, либо к стохастическому a или g, но никогда не к нескольким классам одновременно. Именно последнее имеет место в модели GAAN, что делает эту модель не вполне разделимой АСМ.

Модель GAAN есть конечный, ориентированный, сетевой граф со следующими свойствами:

Глава 8. Управляемые альтернативные сетевые модели 1. GAAN имеет одну корневую вершину и не менее двух висячих вершин.

2. Каждая операция АСМ класса GAAN (i, j ) относится к одному из трех типов, а именно:

Тип I. Операция (i, j ) есть операция сети PERT, то есть реализует логическую операцию «И» на выходе вершины i и на входе вершины j.

Обозначим эту операцию индексом «РА».

Тип II. Операция (i, j ) есть альтернативная стохастическая реализация, то есть реализует «исключающее или» на выходе точки i. Эту операцию обозначим индексом ASA [8.8-8.9]. Каждой операции (i, j ) класса ASA соотносится вероятность 0 pij 1, причем из вершины i выходит не менее двух операций ASA, c pij = 1.

Тип III. Операция (i, j ) есть детерминированная альтернативная реализация с «исключающим или» в точке i. Эту операцию обозначим ADA.



Pages:     | 1 |   ...   | 4 | 5 || 7 |
 

Похожие работы:

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Государственное образовательное учреждение высшего профессионального образования Казанский государственный технологический университет Н.А. МУКМЕНЕВА, С.В. БУХАРОВ, Е.Н. ЧЕРЕЗОВА, Г.Н. НУГУМАНОВА ФОСФОРОРГАНИЧЕСИКЕ АНТИОКСИДАНТЫ И ЦВЕТОСТАБИЛИЗАТОРЫ ПОЛИМЕРОВ МОНОГРАФИЯ КАЗАНЬ КГТУ 2010 УДК 678.03;678.04;678.4;678.7 ББК (Г)24.237 Фосфорорганические антиоксиданты и цветостабилизаторы полимеров. Монография / Н.А. Мукменева, С.В. Бухаров, Е.Н. Черезова, Г.Н....»

«Р.В. КОСОВ ПРЕДЕЛЫ ВЛАСТИ (ИСТОРИЯ ВОЗНИКНОВЕНИЯ, СОДЕРЖАНИЕ И ПРАКТИКА РЕАЛИЗАЦИИ ДОКТРИНЫ РАЗДЕЛЕНИЯ ВЛАСТЕЙ) ИЗДАТЕЛЬСТВО ТГТУ Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования Тамбовский государственный технический университет Р.В. КОСОВ ПРЕДЕЛЫ ВЛАСТИ (ИСТОРИЯ ВОЗНИКНОВЕНИЯ, СОДЕРЖАНИЕ И ПРАКТИКА РЕАЛИЗАЦИИ ДОКТРИНЫ РАЗДЕЛЕНИЯ ВЛАСТЕЙ) Утверждено Научно-техническим советом ТГТУ в...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И ФИНАНСОВ КАФЕДРА ЦЕНООБРАЗОВАНИЯ И ОЦЕНОЧНОЙ ДЕЯТЕЛЬНОСТИ Т.Г. КАСЬЯНЕНКО СОВРЕМЕННЫЕ ПРОБЛЕМЫ ТЕОРИИ ОЦЕНКИ БИЗНЕСА ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ ББК 65. К Касьяненко Т.Г. К 28 Современные проблемы теории оценки бизнеса / Т.Г....»

«А.С.ЛЕЛЕЙ ОСЫ-НЕМКИ ФАУНЫ СССР И сопрЕ~ЕльныIx СТРАН '. АКАДЕМИЯ НАУК СССР ДАЛЬНЕВОСТОЧНЫй НАУЧНЫй ЦЕНТР БИОЛОГО-ПОЧВЕННЫй ИНСТИТУТ А. С. ЛЕЛЕЙ ОСЫ-НЕМКИ (HYMENOPTERA, MUTILLIDAE) ФАУНЫ СССР И СОПРЕДЕЛЬНЫХ С'ТРАН Ответстпеппыи редактор В. и. ТОБИАС ЛЕНИНГРАД ИЗДАТЕЛЬСТВО НАУКА ЛЕНИНГРАДСКОЕ ОТДЕЛЕНИЕ УДК 595.794.2(47+57). фауны СССР и сопредельных MutiIlidae) Л елей А. С. Осы-немки (Hymenoptera, стран. - Л.: Наука, 1985....»

«УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ИМ. А.А. ДОРОДНИЦЫНА РАН Ю. И. БРОДСКИЙ РАСПРЕДЕЛЕННОЕ ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ СЛОЖНЫХ СИСТЕМ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ИМ. А.А. ДОРОДНИЦЫНА РОССИЙСКОЙ АКАДЕМИИ НАУК МОСКВА 2010 УДК 519.876 Ответственный редактор член-корр. РАН Ю.Н. Павловский Делается попытка ввести формализованное описание моделей некоторого класса сложных систем. Ключевыми понятиями этой формализации являются понятия компонент, которые могут образовывать комплекс, и...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Сибирская государственная автомобильно-дорожной академия (СибАДИ) МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ РАБОЧИХ ПРОЦЕССОВ ДОРОЖНЫХ И СТРОИТЕЛЬНЫХ МАШИН: ИМИТАЦИОННЫЕ И АДАПТИВНЫЕ МОДЕЛИ Монография СибАДИ 2012 3 УДК 625.76.08 : 621.878 : 519.711 ББК 39.92 : 39.311 З 13 Авторы: Завьялов А.М., Завьялов М.А., Кузнецова В.Н., Мещеряков В.А. Рецензенты:...»

«MINISTRY OF NATURAL RESOURCES RUSSIAN FEDERATION FEDERAL CONTROL SERVICE IN SPHERE OF NATURE USE OF RUSSIA STATE NATURE BIOSPHERE ZAPOVEDNIK “KHANKAISKY” VERTEBRATES OF ZAPOVEDNIK “KHANKAISKY” AND PRIKHANKAYSKAYA LOWLAND VLADIVOSTOK 2006 МИНИСТЕРСТВО ПРИРОДНЫХ РЕСУРСОВ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНАЯ СЛУЖБА ПО НАДЗОРУ В СФЕРЕ ПРИРОДОПОЛЬЗОВАНИЯ ГОСУДАРСТВЕННЫЙ ПРИРОДНЫЙ БИОСФЕРНЫЙ ЗАПОВЕДНИК ХАНКАЙСКИЙ...»

«Е.А. Урецкий Ресурсосберегающие технологии в водном хозяйстве промышленных предприятий 1 г. Брест ББК 38.761.2 В 62 УДК.628.3(075.5). Р е ц е н з е н т ы:. Директор ЦИИКИВР д.т.н. М.Ю. Калинин., Директор РУП Брестский центр научно-технической информации и инноваций Государственного комитета по науке и технологиям РБ Мартынюк В.Н Под редакцией Зам. директора по научной работе Полесского аграрно-экологического института НАН Беларуси д.г.н. Волчека А.А Ресурсосберегающие технологии в водном...»

«В.Б. БЕЗГИН КРЕСТЬЯНСКАЯ ПОВСЕДНЕВНОСТЬ (ТРАДИЦИИ КОНЦА XIX – НАЧАЛА XX ВЕКА) МОСКВА – ТАМБОВ Министерство образования и науки Российской Федерации Московский педагогический государственный университет Тамбовский государственный технический университет В.Б. БЕЗГИН КРЕСТЬЯНСКАЯ ПОВСЕДНЕВНОСТЬ (ТРАДИЦИИ КОНЦА XIX – НАЧАЛА XX ВЕКА) Москва – Тамбов Издательство ТГТУ ББК Т3(2) Б Утверждено Советом исторического факультета Московского педагогического государственного университета Рецензенты: Доктор...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ, СТАТИСТИКИ И ИНФОРМАТИКИ Кафедра Иностранных языков Лингводидактический аспект обучения иностранным языкам с применением современных интернет-технологий Коллективная монография Москва, 2013 1 УДК 81 ББК 81 Л 59 ЛИНГВОДИДАКТИЧЕСКИЙ АСПЕКТ ОБУЧЕНИЯ ИНОСТРАННЫМ ЯЗЫКАМ С ПРИМЕНЕНИЕМ СОВРЕМЕННЫХ ИНТЕРНЕТ ТЕХНОЛОГИЙ: Коллективная монография. – М.: МЭСИ, 2013. – 119 с. Редколлегия: Гулая Т.М, доцент...»

«Сергей Павлович МИРОНОВ доктор медицинских наук, профессор, академик РАН и РАМН, заслуженный деятель науки РФ, лауреат Государственной премии и премии Правительства РФ, директор Центрального института травматологии и ортопедии им. Н.Н. Приорова Евгений Шалвович ЛОМТАТИДЗЕ доктор медицинских наук, профессор, заведующий кафедрой травматологии, ортопедии и военно-полевой хирургии Волгоградского государственного медицинского университета Михаил Борисович ЦЫКУНОВ доктор медицинских наук, профессор,...»

«Д. В. Зеркалов ПРОДОВОЛЬСТВЕННАЯ БЕЗОПАСНОСТЬ Монография Электронное издание комбинированного использования на CD-ROM Киев „Основа” 2012 УДК 338 ББК 65.5 З-57 Зеркалов Д.В. Продовольственная безопасность [Электронний ресурс] : Монография / Д. В. Зеркалов. – Электрон. данные. – К. : Основа, 2009. – 1 электрон. опт. диск (CD-ROM); 12 см. – Систем. требования: Pentium; 512 Mb RAM; Windows 98/2000/XP; Acrobat Reader 7.0. – Название с тит. экрана. ISBN 978-966-699-537-0 © Зеркалов Д. В. УДК ББК 65....»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ КИЕВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ И. М. Гераимчук Теория творческого процесса Киев Издательское предприятие Эдельвейс 2012 Министерство образования и науки, молодежи и спорта Украины Национальный технический университет Украины Киевский политехнический институт И. М. Гераимчук Теория творческого процесса Структура разума (интеллекта) Киев Издательское предприятие Эдельвейс УДК 130.123.3:11....»

«A POLITICAL HISTORY OF PARTHIA BY NEILSON C. DEBEVOISE THE ORIENTAL INSTITUTE THE UNIVERSITY OF CHICAGO THE U N IV E R SIT Y OF CHICAGO PRESS CHICAGO · ILLINOIS 1938 РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ИСТОРИИ МАТЕРИАЛЬНОЙ КУЛЬТУРЫ Н. К. Дибвойз ПОЛИТИЧЕСКАЯ ИСТОРИЯ ПАРФ ИИ П ер ево д с ан гли йского, научная редакция и б и б л и о г р а ф и ч е с к о е п р и л о ж ен и е В. П. Н и к о н о р о в а Филологический факультет Санкт-Петербургского государственного университета ББК 63.3(0) Д Д ибвойз...»

«Российская академия наук Кольский научный центр Мурманский морской биологический институт Н. М. Адров ДЕРЮГИНСКИЕ РУБЕЖИ МОРСКОЙ БИОЛОГИИ к 135-летию со дня рождения К. М. Дерюгина Мурманск 2013 1 УДК 92+551.463 А 32 Адров Н.М. Дерюгинские рубежи морской биологии (к 135-летию со дня рождения К. М. Дерюгина) / Н.М. Адров; Муман. мор. биол. ин-т КНЦ РАН. – Мурманск: ММБИ КНЦ РАН, 2013. – 164 с. (в пер.) Монография посвящена научной, организаторской и педагогической деятельности классика морской...»

«Российская Академия Наук Уфимский научный центр Институт геологии В. Н. Пучков ГЕОЛОГИЯ УРАЛА И ПРИУРАЛЬЯ (актуальные вопросы стратиграфии, тектоники, геодинамики и металлогении) Уфа 2010 УДК 551.242.3 (234/85) ББК 26.3 П 88 Пучков В.Н. Геология Урала и Приуралья (актуальные вопросы стратиграфии, тектоники, П 88 геодинамики и металлогении). – Уфа: ДизайнПолиграфСервис, 2010. – 280 с. ISBN 978-5-94423-209-0 Книга посвящена одному из интереснейших и хорошо изученных регионов. Тем более важно, что...»

«Н.П. ЖУКОВ, Н.Ф. МАЙНИКОВА МНОГОМОДЕЛЬНЫЕ МЕТОДЫ И СРЕДСТВА НЕРАЗРУШАЮЩЕГО КОНТРОЛЯ ТЕПЛОФИЗИЧЕСКИХ СВОЙСТВ МАТЕРИАЛОВ И ИЗДЕЛИЙ МОСКВА ИЗДАТЕЛЬСТВО МАШИНОСТРОЕНИЕ-1 2004 УДК 620.179.1.05:691:658.562.4 ББК 31.312.06 Ж85 Рецензент Заслуженный деятель науки РФ, академик РАЕН, доктор физико-математических наук, профессор Э.М. Карташов Жуков Н.П., Майникова Н.Ф. Ж85 Многомодельные методы и средства неразрушающего контроля теплофизических свойств материалов и изделий. М.: Издательство...»

«Южный федеральный университет Центр системных региональных исследований и прогнозирования ИППК ЮФУ и ИСПИ РАН Южнороссийское обозрение Выпуск 56 Барков Ф.А., Ляушева С.А., Черноус В.В. РЕЛИГИОЗНЫЙ ФАКТОР МЕЖКУЛЬТУРНОЙ КОММУНИКАЦИИ НА СЕВЕРНОМ КАВКАЗЕ Ответственный редактор Ю.Г. Волков Ростов-на-Дону Издательство СКНЦ ВШ ЮФУ 2009 ББК 60.524.224 Б25 Рекомендовано к печати Ученым советом Института по переподготовке и повышению квалификации преподавателей гуманитарных и социальных наук Южного...»

«Хадарцев А.А., Еськов В.М., Козырев К.М., Гонтарев С.Н. МЕДИКО-БИОЛОГИЧЕСКАЯ ТЕОРИЯ И ПРАКТИКА Тула – Белгород, 2011 Европейская Академия Естественных Наук Отделение фундаментальных медико-биологических исследований Хадарцев А.А., Еськов В.М., Козырев К.М., Гонтарев С.Н. МЕДИКО-БИОЛОГИЧЕСКАЯ ТЕОРИЯ И ПРАКТИКА Под редакцией В.Г. Тыминского Тула – Белгород, 2011 УДК 616-003.9.001.004.14 Хадарцев А.А., Еськов В.М., Козырев К.М., Гонтарев С.Н. Медикобиологическая теория и практика: Монография / Под...»

«Национальный технический университет Украины Киевский политехнический институт И.М. Гераимчук Философия творчества Киев ЭКМО 2006 4 Национальный технический университет Украины Киевский политехнический институт И.М. Гераимчук Философия творчества Киев ЭКМО 2006 5 УДК 130.123.3:11.85 ББК ЮЗ(2)3 Г 37 Рецензенты: д-р филос. наук, проф. Б.В. Новиков Гераимчук И.М. Г 37 Философия творчества: Монография / И.М. Гераимчук – К.: ЭКМО, 2006. – 120 с. ISBN 978-966-8555-83-Х В монографии представлена еще...»





 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

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