4.3. Анализ вариантов построения топологической структуры асдп

Для АСДП, имеющей пользователей О = {a_i}, i = , можно задать матрицу связности ||H|| = [h_ij], элемент которой

Граф, отображающий топологическую структуру АСДП, должен удовлетворять условиям, описываемым матрицей связности ||Н||, т. е. если h_ij = 1, то должна существовать по крайней мере одна цепь, соединяющая вершины а_i и a_j.

При построении топологической структуры АСДП условиям, накладываемым матрицей ||Н||, может соответствовать некоторое множество различных графов. Поэтому возникает задача отыскания графа, оптимального по некоторому критерию. В схожих, по принципам своей организации, системах, таким критерием чаще всего служит суммарная «длина» (в некоторой метрике) условных путей внутри системы (рёбер). Таким образом, предварительно нужно построить граф, отображающий топологическую структуру АСДП и имеющий минимальную суммарную длину ребер.

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

Фрагментом называется подмножество вершин, связанное прямыми ветвями, каждая из которых соединяет вершины этого подмножества. Изолированной вершиной называется вершина, которая на данном этапе построения сети еще не связана с другими вершинами (фрагментами). Аналогично определяется изолированный фрагмент. Ближайшим соседом вершины (фрагмента) является та, которая находится от данной на минимальном расстоянии.

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

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

Исходными данными для построения кратчайшей связывающей сети является матрица расстояний между вершинами ||L|| = [l_ij], где l_ij - расстояние между вершинами а_i и a_j. В матрице расстояний в каждой строке выделяются минимальные элементы, из числа которых в строках находится наименьший существующий элемент. Пусть таким элементом оказался l_ij = l_ji. Тогда первым ребром дерева минимальной длины будет ребро, соединяющее вершины а_i и a_j. В строках с номерами i и j отыскивается следующий минимальный элемент. Допустим, что им будет элемент l_ik в строке j. Вторым ребром дерева кратчайшей длины будет ребро, соединяющее вершины θ_j и a_k. Далее процедура повторяется для строк с номерами i, j и k. Таким образом, на каждом шаге построения дерева минимальной длины отыскивается ребро минимальной длины, соединяющее еще не соединенные вершины. Связное дерево минимальной длины содержит N - 1 ребро, где N - число вершин графа.

В работе [17] предложен алгоритм построения информационной сети, основывающийся на принципах Р. Прима и позволяющий построить сеть, оптимальную в смысле надежности. В качестве критерия надежности используются средние потери, вызванные отказами ПСв и части автопарка. Рассматривается построение системы доставки, обеспечивающей доставку заказов между центральным пунктом (ЦС) и всеми N остальными пунктами (ПС) с минимальными средними потерями. Авторы работы [17] несколько модифицировали определения Р. Прима, руководствуясь тем, что фрагмент должен обязательно включать в себя центральный узел, что отлично подходит для случая с АСДП. Исходными данными для построения сети, являются матрица связности ||Н|| и матрица [q'_ij], i, j = , где q'_ij - вероятность выхода из строя случайного ПС между вершинами а_i и a_j; q'_ij - вероятность выхода из строя аппаратуры i-го ПС, играющего для исходного склада роль виртуального ЦС или реальным ЦС. Отказы различных элементов системы предполагаются независимыми событиями. Сеть строится в классе структур, обеспечивающих ЦС один вполне определенный путь к каждому из N ПС. В работе [17] доказано, что построение сети, обеспечивающей минимальные средние потери, в этих условиях сводится к построению структуры, в которой каждый ПС связан с ЦС кратчайшим путем (в смысле обеспечения минимума времени, необходимого на доставку и средних потерь заказов).

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

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

Учитывая, что площадь вместимость складских помещений (СП) транзитных ПС обеспечивает достаточно малую вероятность отказа от обслуживания заказа, из-за переполнения СП, можно представить путь доставки заказа, состоящий из n транзитных участков, в виде n-фазной Q-схемы без блокировок [8].

Будем считать, что средние времена обработки заказа на каждом транзитном участке одинаковы и равны . Ставится задача анализа зависимости параметров и С_n от изменения числа транзитных участков n и требований к показателям качества процессов доставки продовольствия, задаваемых для всего пути в целом, где С_n – производительность (пропускная способность) транзитных складов.

При введенных предположениях о характере функций распределения интервалов времени между поступлением некой заявки в АСУ и осуществлением ЛПС доставки соответствующего заказа клиенту, получаем следующую зависимость между средним временем передачи Т⁰ и вероятностью Pr (t > T^Д) при фиксировании T^Д:

(4.11)

(4.12)

Зависимость Т⁰ от T^Д при различных значениях вероятности Pr (t > T^Д) приведена на рис. 4.2. По выражениям (4.11) и (4.12) может быть определена как пропускная способность складов С, обеспечивающая выполнение предъявляемых к показателям качества процессов передачи продовольственных заказов требований, задаваемых в виде Т⁰ либо Pr (t > T^Д).

При наличии между рассматриваемой парой ЦС-клиент транзитных ПСв с учетом введенных предположений получаем, что интенсивность поступления заказов в каждый транзитный КС не зависит от числа транзитных участков, постоянна и равна λ (теорема Бурке [3]). Учитывая предположение о независимости, получаем, что времена передачи заказов по каждому ПС независимы и распределены по экспоненциальному закону с параметром μС_n. Для каждого транзитного участка получаем, что

, (4.13)

где .

Рис. 4.3 Функция распределения времени передачи по n транзитным участкам

Функция распределения времени передачи по n транзитным участкам определяется как композиция функций распределения, соответствующих каждому участку, и с учетом введенных допущений она выражается следующим образом [25]:

, T^Д > 0, (4.14)

где ;

— распределение Эрланга n - 1 порядка (или (n - 1)-фазное распределение Эрланга).

Таким образом, при заданном значении P (t > T^Д) значение определяется из уравнения (4.14). Зависимости P (t > T^Д) при различных значениях n и отношения представлены на рис. 4.4.

Рис 4.4 Зависимости P (t > T^Д) при различных значениях n и отношения

Анализ полученных зависимостей показывает, что при фиксированных значениях T^Д и Pr (t > T^Д) с увеличением значения параметра n значение уменьшается; следовательно, увеличивается пропускная способность транзитного ПС (ЛПС) С_n, которая сможет обеспечить выполнение заданного требования к показателям качества процессов доставки продовольственных заказов клиентской метасистеме.

Введем параметр относительного среднего расчётного времени доставки заказа:

, (4.15)

где - определяется из уравнения (4.14), а Т⁰ - из (4.13).

Нетрудно заметить, что 0 ≤ β ≤ 1. Определение конкретного значения β при фиксированных T^Д, Pr (t > T^Д) и n сводится к решению уравнения вида:

_(4.16)

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

(4.17)

Путём проведения серии компьютерных моделирований АСДП, можно подобрать соответствующий параметр T^Д, чтобы значение параметра Pr (t > T^Д) удовлетворяло условию

Pr (t > T^Д) < 0,1. (4.18)

Используя таблицы гамма-распределения, построим зависимость параметра β при различных значениях вероятности Pr (t > T^Д), удовлетворяющих условию (4.8), и различном числе транзитных участков n (рис. 4.4). Анализируя построенные зависимости, можно сделать следующие выводы. Для выбранных значений Pr (t > T^Д) значения параметра β меняются в достаточно широких пределах. При n ≥ 2 и Pr (t > T^Д) < 0,1 область изменений значений β задается неравенством 0,25 < β < 1.

Проведем анализ влияния изменения параметра β на выбор пропускных способностей транзитных ПС (ЛПС).

Без учета числа транзитных участков пропускная способность ПС, обеспечивающая выполнение требований к среднему времени доставки заказа Т⁰, определяется соотношением

C = (1 + λТ⁰) / (μТ⁰), (4.19)

а при наличии транзитных участков

C_n = (1 + λβТ⁰) / (μβТ⁰) (4.20)

Проводя соответствующие преобразования, получаем

C_n = C + (1 – β) / (βμТ⁰) (4.21)

Значение β в выражениях (4.20) и (4.21) определяется для фиксированного числа транзитных участков n при заданном значении Pr (t > T^Д) из таблиц гамма-распределения или из рис. 3.4.

Рис. 4.5 Функция гамма-распределения β

Введем обозначение ΔC = (1 – β) / (βμТ⁰) и рассмотрим, каким образом будет меняться значение отношения ΔС/С при изменении значений параметров β, Т⁰.

Анализируя полученные зависимости, можно сделать следующие выводы. В первом варианте для значений параметра λ < 20 заказов/сутки и для β < 0,80 (число транзитных участков n ≥ 2) рассматриваемое отношение ΔС/С составляет более 5 %. Можно показать, что при уменьшении значения параметра Т⁰ отношение ΔС/С будет увеличиваться. Следовательно, если в выражении (4.9) положить β = 1, то при расчете пропускных способностей транзитных ПС может быть получена существенная ошибка, которая будет тем меньше, чем меньше будут значения параметров Т⁰ и λ.

Анализ зависимостей, соответствующих второму варианту, показывает, что для β ≥ 0,25, λ ≥ 0,5 сообщений/с отношение ΔС/С составляет менее 3 %. С увеличением значений параметров Т⁰ и λ рассматриваемое отношение уменьшается. В данном случае использование в выражении (4.9) значения β = 1 при определении пропускных способностей транзитных ПСв является допустимым.

В каждом конкретном случае вопрос о необходимости учета параметра β при определении пропускных способностей ПСв, в проектируемой АСДП, должен решаться с учетом конкретного значения параметров T, Pr (t > T^Д), n и области изменения значений параметра λ.

Предположение об экспоненциальном характере времени обслуживания дает несколько завышенные характеристики времени обслуживания заказов и размеров очередей [10, 12]. Однако такая ошибка не оказывает существенного влияния на эффективность проектируемой АСДП, так как адаптивная система управления АСУ обеспечит требуемое качество продуктов, необходимых клиенту. Кроме того, в случае необходимости полученные результаты могут быть скорректированы путем построения более сложных моделей или по средствам подбора, после ряда испытаний по компьютерному моделированию АСДП.

На основании полученных в данном параграфе результатов значение параметра для ПСв, соединяющего узлы a_p и a_k, определяется выражением

, (4.22)

где

Значение β_ij определяется с учетом числа транзитных участков, составляющих путь передачи заказа между a_i и a_j.

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