Методика минимизации структурной избыточности системы

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

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

где M_ij (s) = fe^syijf (y_ij)dy_ij — условная производящая функция моментов случайной величины у у с плотностью распределения Ду_|;), рассчитывать вероятность выполнения отдельных участков сети, а также математическое ожидание и дисперсию случайной величины У, выступающей аналогом у у, но характеризующей систему в целом.

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

Таблица 6.1

Моменты и производящие функции моментов.

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

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

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

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

Отметим, что начальный узел сети выполняет только выходную функцию, в то время как конечный узел — только входную. Существуют три типа входных функций.

Тип 1. Узел выполняется, если выполнены все дуги, входящие в него.

Тип 2. Узел выполняется, если выполнена любая дуга, входящая в него.

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

Выходные функции обычно делят на два типа.

Тип 1. Все дуги, выходящие из узла, выполняются, если этот узел выполнен. Данная функция называется детерминированной выходной функцией.

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

На рисунке 6.1 представлено два типа узлов, которые применяются при построении моделей организации в данной книге:

• • узлы с третьим типом входной функции и детерминированной выходной функцией;
• • узлы с третьим типом входной функции и вероятностной выходной функцией.

Именно сети, содержащие только эти два типа узлов, и называют GERT-сетями.

Рис. 6.7. Типы GERT-узлов:

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

Рис. 6.2. Пример GERT-сети.

GERT-сеть обладает рядом свойств, представляющих интерес с вычислительной точки зрения. Для изучения этих свойств мы рассмотрим три частных случая:

• • GERT-сеть из двух последовательных дуг;
• • GERT-сеть из двух параллельных ветвей;
• • GERT-сеть из одной ветви и одной петли.

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

Рис. 6.3. Последовательные ветви и их эквивалентное представление.

Исходные ветви имеют W-преобразования VVy (s) = PyMy (s), Wjk (s) = Pj_kMjk (s). W-функция для эквивалентной ветви (г, /с) имеет вид W_lk(s) = p_ikM_ik(s).

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

то.

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

Рассмотрим теперь сеть из двух параллельных ветвей а и Ь. Эти ветви также могут быть заменены эквивалентной ветвью. Пусть (i, j) — такая ветвь. По определению, W^-(s)=PyMy (s). В этом случае Ру =р_а+р_ьи

Поэтому.

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

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

Рис. 6.4. Сеть с петлей и ее эквивалентное представление.

ПО.

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

Рис. 6.5. Представление петель в виде параллельных и последовательных дуг.

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

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

Действительно, пусть (i, j) — ветвь, эквивалентная сети, изображенной на рисунке 6.4. Из соотношений (6.2) и (6.3) следует, что W-функция ветви (i, j).

ш.

Данное выражение, в котором мы временно опустили аргументы W-функций, можно упростить, зная, что биномиальный ряд (1 — Wq)¹ раскладывается следующим образом:

Следовательно, окончательно имеем:

и сеть, изображенная на рисунке 6.4, сводится к единственной эквивалентной ей ветви, для которой W-функция.

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

Рис. 6.6. Потоковый граф с петлями.

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

Действительно, в соответствии с определением, приведенным выше, петля второго (третьего) порядка — это множество, состоящее из двух (трех) не связанных между собой петель первого порядка. Поэтому в рассматриваемом нами графе петли L, и 1₂ образуют петлю второго порядка, а петли L_v L₂ и L₃ — петлю третьего порядка.

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

Рис. 6.7. Петли первого порядка в замкнутом потоковом графе.

Рис. 6.8. Петли второго порядка в замкнутом потоковом графе.

Рис. 6.9. Петля третьего порядка замкнутом потоковом графе.

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

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

Пусть L_n, L₂₁, …, L_nl — п не связанных между собой петель первого порядка для исходной петли порядка п. Поскольку для каждой петли первого порядка эквивалентный коэффициент пропускания равен произведению коэффициентов пропускания ветвей, принадлежащих этой петле, т. е.

где tjj — вес дуги (у), т. е. характеристика потока, проходящего по ней (в нашем случае это значение W-функции), то для петли порядка п эквивалентный коэффициент пропускания составит величину.

где произведения организуются по дугам, входящим в соответствующую петлю.

Полученный по формуле (6.5) результат применяется для моделирования процессов и систем, которые могут быть описаны GERT-сетями. Цель такого моделирования состоит в вычислении математического ожидания и дисперсии общего параметра сети (чаще всего — времени выполнения или связанного с ним ресурса), а также вероятности выполнения стока (или стоков) сети, т. е. достижения определенной цели системы или наступления определенной ситуации.