Иерархия моделей процессов и типовые математические схемы их формализации

Проведем формальное описание архитектуры АСДП, рассматривая взаимодействие внешней среды и элементов системы между собой и обработку заказа каждым из элементов АСДП в виде внешней среды E и сетевой среды N. Каждую из них представим в виде двух сред: среды генерации, или G_E-среды (от англ. «generation» - генерация), среды распространения, или W_E-среды (от англ. «widespread» - распространение), среды взаимодействия, или I_N-среды (от англ. «interaction» - взаимодействие) и среды обработки, или P_N-среды (от англ. «processing» - обработка). Условно предлагаемая иерархия сред показана на рис. 4.10.

 

Рис. 4.10 Предлагаемая иерархия сред элементов АСДП

Выделение G_E-среды должно позволить описать воздействие пользователей на систему, т. е, потоков их заказов на услуги АСДП; W_E-среда должна позволить отразить воздействие внешних препядствующих факторов (сбои случайного характера) на процесс доставки заказа (проблемы с транспортом, поломки оборудования и пр.); I_N-среда даст возможность описать АСДП в целом, как единую систему, взаимодействующую с внешней средой на системном уровне (G_EI_N -уровне); P_N-среда даст возможность описать основные структурные элементы АСДП, обрабатывающие заказ: АСУ, ЦС, ПС, система доставки и т. п. С учетом взаимодействия с внешней средой на реализационном (аппаратно-программном) уровне (W_EP_N –уровне).

Учитывая, что в дальнейшем основное внимание будет уделено управлению ядром АСДП, т. е, АСУ, в котором решаются задачи обработки и доставки заказов в системе АСДП.

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

Представим I_N-среду как некоторую однородную или регулярную системную среду [24], состоящую из ПС, формализуемых в виде многополюсников с тремя типами входов и выходов , , , у которых число входов соответствует числу выходов, так как согласно ЭМВОС все соединения между открытыми системами являются дуплексными.

I_N-среда имеет сложную структуру, позволяющую изобразить иерархию АСДП, т. е. выделять особенности взаимодействия ПС внутри данного уровня иерархии и между соседними уровнями. При этом

,

где i - номер уровня данного многополюсника; п - номер ПС в множестве узлов i -го уровня M_i, i = , п = ; I_n - число уровней иерархии; N_i - число узлов i -ro уровня иерархии. Иногда удобно рассматривать только связи между соседними уровнями ,

а связи с несоседними уровнями изображать с помощью фиктивных узлов

 - множество всех входов и выходов n -го узла уровня i I_N-среды, тогда

 

является подмножеством входов и выходов п -го узла 1-го уровня, соединенных с узлами следующего нижнего уровня, а  - подмножество входов и выходов этого узла, связанных с узлами следующего верхнего j -го уровня. Каждое такое подмножество состоит из элементов М _nk: .

Элементы, т. е. ПС, имеют переменную структуру, а именно: при , , ,  и при этом  (в общем случае

,

 каждый M_jk может принимать значение от 0 до ;  тоже может быть переменным.

В терминах ЭМВОС рассматриваемые узлы I_N-среды являются совокупностями открытых систем, которые подчиняются следующим правилам:

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

Для описания и анализа особенностей I_N-среды предлагается аппарат так называемых иерархических матриц связности [24], которые будем называть H-схемами (от англ. «hierarchical matrix connection»). Структура любой сети (в нашем случае – системы) может быть задана с помощью простой квадратной матрицы связности (МС), размерность «второй определяется числом узлов в сети N _у. В случае СИО такая МС будет иметь большую размерность, к тому же применительно к каждому узлу она содержит много избыточной информации, но в явном виде в ней нельзя отразить факт наличия и особенности некоторых вторичных систем.

Эти недостатки можно устранить, если ввести понятие H-схем, представляющих собой совокупность квадратных и прямоугольных МС. Поясним понятие H-схемы на примере произвольной радиально-кольцевой четырехуровневой АСДП (рис. 3.2), на основе которой построена система автоматизированной доставки продовольствия с различными приоритетами. Характер доставляемых потоков заказозов, их направленность и приоритеты обуславливают упорядочивание ПС, т. е. выделение среди множества региональных ПС { А_х } главного ЦС Ц, для которого требуется обеспечить прямую связь со всеми региональными узлами, что осуществляется путем:

1. Выбора часов оптимальных по разгруженности дорог от автотранспорта, для осуществления сообщения между ЦС и ПС;

 2. Наиболее подхождящего географического расположения, с доступом к скоростному шоссе, которое схематически обозначено на рис. 3.2 как = = = =.

Подобная иерархическая структура, например, обуславливается особенностями функционирования и требованиями к информационным и управляющим потокам данных в крупных АСУ с преобладающим объемом оперативной информации (АСУ крупными транспортными системами - авиационные, морские, железнодорожные и др., АСУ специального назначения, большие Централизованные информационно-справочные системы) [25, 26, 27, 28, 29, 30, 31, 32].

На рис. 4.11 изображены условно четыре категории ПС, соответствующие четырем уровням иерархии. Для удобства дальнейшего рассмотрения фрагмент структуры на рис. 4.11 представлен на рис. 4.12 без учета реальных расстояний и с выделением уровни иерархии в виде концентрических кругов около центрального узла Ц. Данное представление дает возможность увидеть, что на базе первичной сети без каких-либо дополнительных работ по созданию ПСв можно построить сеть обеспечения продовольствием, с ярко выраженной радиальной структурой. Новые физические линии обозначены сплошными линиями, а организованные с целью создания кольцевой структуры виртуальные каналы – штриховыми линиями, т. е. пунктиром обозначены сквозные каналы не на существующих физических линиях, а на базе логических каналов через замыкающий узел верхнего уровня.

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

Конфигурация узлов задается в матричной форме с использованием квадратных матриц связности узлов данного уровня размерностью N_i x N_i где N_i - число узлов соответствующего i -гo уровня, и прямоугольных матриц связности узлов смежных уровней размерностью N_i x N_{i - 1}, где N_{i - 1} - число узлов нижнего уровня. Перечень узлов может быть задан в виде таблицы представительности (табл. 3.1). Матрицы имеют следующий вид

,

где элемент МС узлов уровня имеет вид:

Рис. 4.11 Категории ПС, соответствующие четырем уровням иерархии

 

Рис. 4.12 фрагмент структуры на рис. 4.11, без учета реальных расстояний

Таблица 4.1

Уровни	Узлы коммутации
1	Ц			-
2	А1Ц	А2Ц	АЗЦ	-	-	-
3	Б11	Б21	Б32	...	Б68	Б173
4	В11	В21	В31	…	В1417	В1517

 

Очевидно, в ПС вместо 1 могут стоять обозначения численного значения некоторых параметров, характеризующих соответствующие связи.

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

,                            (4.54)

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

Для отображения связей между узлами соседних уровней составляются прямоугольные матрица связанности (МС) вида

.

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

В некоторых случаях МС можно рассматривать как булевые матрицы и применять к ним аппарат булевой алгебры. Также может быть применен аппарат преобразований булевых матриц и булевых определителей. Некоторые особенности, связанные с интерпретацией сети булевыми матрицами, даны в работе [31].

Покажем, как МС формируется с помощью образующих векторов, содержащих упорядоченные символьные обозначения узлов, находящихся на одном и том же уровне, например, J = (n ₁, n ₂,..., n_Ni), т. е. на уровне i имеется N_i узлов.

Определим вектор связности узла n_k:

,

 

где i - 1, i и i + 1 - соседние уровни иерархии системы.

На определенных таким образом МС, пользуясь некоторыми дополнительными средствами и понятиями, например, понятиями ранга узла, ранга пути, сечением системы и рангом сечения системы, достаточно просто можно организовать поиск оптимального пути доставки, а также проводить оптимизацию структуры системы [1].

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

На рис. 4.12 показана радиально-кольцевая структура, для которой на рис. 4.13 изображены МС. Эти рисунки иллюстрируют механизм формирования МС, т. е. формализацию процесса.

Целесообразно задавать топологию системы таблицей представительности, на основании которой легко можно строить МС. Представительность четырехуровневой системы, изображенной на рис. 3.4, показана в табл. 4.1. Затем составляются МС первичной системы. Связность всех узлов уровня i задается тремя основными МС: , , , а также добавочными МС (если таковые имеются). Добавочные МС отображают связи узлов данного уровня с узлами не соседних уровней  и , , где I_n - число уровней иерархии системы.

Элементы МС первичной системы соответствуют определенным элементам простой МС, в которой перечислены все узлы системы и связи между ними. Сокращение числа элементов при переходе к H-схемам происходит за счет уменьшения числа нулевых элементов простой МС. Если обозначить через  - число элементов простой МС, а через  - число элементов H‑схемы, то

,

где n_i - количество узлов на i -м уровне и

, в общем случае.

Очевидно,  >  >  для всех I_n > 1, причем разница между  и  увеличивается с ростом I_n за счет увеличения вероятности получения нулевых добавочных МС, которые в  не присутствуют.

4.13 Структура матриц связанности (МС) для топологии АСДП

Полные МС образуются присоединением к основным МС добавочных МС, что осуществляется следующим образом. На ЦС, при условии выбора варианта доставки «получение с ЦС», создаются фиктивные узлы со связностью ν = 2 (см. рис. 4.3). Под связностью узла ν понимаем число узлов, с которыми данный узел имеет прямое физическое соединение. Затем производятся операции добавления этих фиктивных узлов к соответствующим основным МС. Операция добавления определяется ниже.

 

Рис. 3.4

Рис. 4.13 Получение вектора связанности (ВС)

 

На рис. 4.13, а для узла а ₁ показано получение вектора связности (рис. 4.14, б), который полностью определяет возможности доставки заказа из конкретного ПС системы.

Рис. 4.14 Вектора связанности

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

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

1. Исключение узла k из уровня i :

, N ’ _i = N_i – 1, , I_n = const,

которое заключается в вычеркивании всех строк и столбцов МС, которых узел k является образующим (например, узел b ₂ рис. 3.6, а).

2. Добавление узла k к уровню i :

, N ’ _i = N_i + 1, , I_n = const,

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

3. Понижение уровня k-го узла уровня i:

, N’_i = N_i, N’_{i- 1} = N_{i- 1} + 1, , I_n = var,

в том случае, если узел верхнего уровня переводят на нижний уровень (рис. 4.15). Например, узел х2 переведен на нижний уровень i-1 (ему присваивается обозначение y5); на рис. 4.14, а показана первая фаза понижения уровня - исключение узла х2 из уровня i и включение узла y5=х2 в уровень i-1; понижение заканчивается удалением строк и столбцов фиктивных узлов на уровне i-1, наличие которых определяется наличием нулевых строк в матрице (строка (y2, х1, у2, х3) на рис. 4.15, б); элементы удаляемых строк и столбцов (образующими для которых являются фиктивные узлы) добавляются к соответствующим элементам новых строк и столбцов, сформированных на первой фазе; на рис. 4,15, в показана законченная операция понижения уровня узла х ₂.

4. Повышение уровня k -го узла уровня i :

, N’_i = N_i, N’_{i+ 1} = N_{i+ 1} + 1, , I_n = var,

когда узел с нижнего уровня переводится на высший уровень. Например, узел на рис. 4.15, а переводится на верхний уровень i + 1 (ему присваивается обозначение х ₃); при этом на рис. 4.15, б показано, что создается один фиктивный узел у ₂, который не имеет связей на уровне i, а значение элемента у ₂₃ получается суммированием элементов (векторов) второй строки матрицы .

Рис. 4.15

 

Одноместные операции исключения и добавления узла будем называть операциями модификации H-схем, а одноместные операции понижения и повышения уровня узла - операциями реконфигурации H-схем. На H-схемах определим также и двухместные реорганизации:

операция наложения :

,  = N_i × N_i, , I_n = const;

операция расслоения :

, ,  = N_i × N_i, , I_n = const.

В простейшем случае операции можно свести к сложению и вычитанию матриц.

Сформируем представление об отдельных структурных элементов P_N-среды, т.е. ПС системы. Задача усложняется разнообразием функциональных и структурных связей внутри открытых систем,

Эта задача достаточно сложна из-за многочисленности и разнообразия функциональных и структурных связей внутри ПС, что не дает возможности воспользоваться предложением о построении однородной P_N-среды на базе простых элементов [31, 24, 160].

Для управления использованием ресурсов АСДП в ПС в соответствии с требуемыми направлениями доставки заказов применяются маршрутные таблицы (МТ), сформированные на основе вектора связности ПС и соответствующих ВМС, описывающих I_N -среду.

Рассмотрим некоторый условный ПС (рис. 4.16), где МТ - маршрутная таблица (табл. 4.2). Столбцы этой таблицы заполняются на базе соответствующих значений вектора связности, строки же соответствуют трем категориям ПС, с которыми данный ПС связывается: 1) ПС верхнего уровня иерархии (кроме ЦС); 2) ПС данного уровня иерархии и 3) ПС нижнего уровня.

Рис. 4.16 МС для условного промежуточного склада

Глава V. МОДЕЛИРОВАНИЕ АСДП

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