Метод анализа логистических моделей

Введение. В настоящее время, в связи с развитием информационно-вычислительных систем, возникает возможность управлять большими и сложными логистическими системами. Возрастающая сложность логистических систем делает необходимым совершенствование математических инструментов, упрощающих процесс разработки таких систем. Большинство существующих инструментов базируются на представлении систем в виде графов. Преимущества отображения исследуемых моделей в виде графов изложены во многих работах, в том числе в [2, 3]. В настоящее время существуют методы для решения таких задач, как нахождение кратчайшего пути, поиск остова наименьшей цены, нахождение максимального потока и др., однако не всегда данные методы могут быть применены к современным логистическим системам, так как попытки их применения прводят к неприемлемо большим объемам вычислений.

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

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

Определения

Графом G называется пара множеств ( V , E ), где V – непустое конечное множество, а E – произвольное множество, образованное произвольными парами элементов из V . Элементы множества V будем называть вершинами графа, а элементы множества E – ребрами графа.

Вершины v и v' называются смежными (инцидентными), если образуемая ими пара ( v , v′ _{) ∈} E .

Петлей называется ребро, соединяющее вершину саму с собой.

Кратными называются различные ребра, соединяющие две данных вершины.

Простой граф – граф, не содержащий в себе петель и кратных ребер.

Степень вершины v – число ребер, инцидентных с вершиной v , обозначается deg( v ) .

Маршрутом в графе G называется чередующаяся последовательность вершин и ребер v₀ , 6i , ^i ,…, v_t-l , ^et , ^vt _, в которой ^ei =( ^i-1 , Vi ), где (1≤ i ≤ t ) .

Длиной маршрута называют количество содержащихся в нем ребер.

Цепь – маршрут без повторяющихся ребер.

Вершины v и v′ называются связанными , если существует маршрут такой, что ^vo = и ^vt = ′ . Отметим очевидное следствие данного определения. Пусть V , V ′ _, V′′ – вершины графа, при этом если пары вершин ( V , V ^′ ) и ( V ′ _, V′′ ) являются связанными, то вершины V , V′′ также являются связанными.

Матрица Кирхгофа [1] – одно из представлений графа с помощью матрицы. Пусть G простой граф с | V ( G )|= n , тогда матрица Кирхгофа К =( , ) n _× n ,

{deg( vi )    если I= где

-1         если ( Vi , Vj ) ∈ E ( g )

0           иначе .

Определитель матрицы A =( , )     равен ∑ 7=i (-1)¹⁺¹ ×   , ×    ,

Дополнительный минор , – определитель матрицы, полученной из исходной путем вычеркивания i -й строки и j -го столбца.

Алгебраическим дополнением , матрицы A называется число, равное (-1) ^l+'^ij , где ^Mij – дополнительный минор.

Полюсы и срезы в графах

Введем вспомогательное понятие – срез вершины графа . Фиксируем произвольную вершину V графа G . Множество всех смежных вершин для v назовем первым срезом графа G для вершины v . Обозначим это множество ^l ( V ) . Во второй срез ^2 ( V ) включим все смежные вершины из ^l ( V ) , исключая саму вершину V и вершины из ^l ( V ) . Далее продолжаем описанный процесс и формируем очередной срез из смежных вершин предыдущего среза, исключая саму вершину V и все вершины, включенные в какой-либо из ранее сформированных срезов. Процесс формирования срезов естественно заканчивается, когда не останется ни одной не включенной в срезы вершины. Множество всех срезов для вершины V графа G обозначим S ( V ) . По аналогии | S ( V )| – количество срезов для вершины V .

Полный массив всех срезов для всех вершин графа обозначим M и разберем подробнее его структуру. Первый индекс структуры M нумерует список срезов для каждой вершины. Срезы упорядочены в соответствии с вышеприведенным определением, то есть первым идет ^l ( ^vi ) , вторым ^2 ( ^vi ) и т.д., где i – индекс текущей строки в структуре M .

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

Полюсом графа по выбранной шкале весов назовем вершину с минимальным значением индекса по-люсности.

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

Веерные остовы

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

Определим следующие функции:

• 1.    f 1( s ( v ), к , n ) – возвращает множество ребер, инцидентных с n -й вершиной в к -м срезе объекта S ( v ) и вершинами, расположенными в срезе к -1 объекта S ( v ) .

• 2.    f 2( S ( v ), i ) – возвращает число вершин в i -м срезе объекта S ( v ) .

• 3.    f 3( S ( v ), к )=∏ n= ^{( (v} ), ) f 1( S ( V ), к , n ) – возвращает прямое произведение множеств, полученных при помощи функции f 1 для всех вершин, расположенных в к -м срезе объекта S ( v ) .

• 4.    f 4( S ( v ))=∏ k= |_s(v)| f 3( s ( v ), к ) – возвращает прямое произведение множеств, полученных при помощи функции f 3 для всех срезов объекта S ( v ) , кроме первого.

Для графа G ( V , E ) определим T ( v )= f 4( S ( v )) , где V ∈ V , тогда элемент t ∈ T ( v ) является последовательностью ребер графа G , то есть t ⊆ E . Определим множество P , такое, что v′ _∈ P ↔( V ′ _, V′′ ) _∈ t , где ( V ′ _, V ′′ _∈ V ) ∧ (( V ′ _, V′′ ) ₌ ( V ′′ _, V^′ )) .

Теорема. Граф ^̅( p , t ) , остов графа G ( V , E ) для ∀ t ∈ T ( v ) и ∀ v ∈ V , где G – неориентированный связный граф.

Доказательство теоремы сводится к доказательству следующих утверждений:

• 1.    P =   .

• 2.    v^′ и V′′ являются связанными для любых V ′ _, V ′′ _∈ p .

• 3.    Граф ^̅ не содержит циклов.

Доказательство утверждения 1. Предположим, что p ≠ V . В силу определения множества P , P ≠ V ↔( ∃ v′ ∈ V ∧ v′ ∉ P ) , что равносильно утверждению P ⊂ V , и не одно ребро, инцидентное вершине v′ , не содержится в t . Для любой вершины, включенной в объект S ( v ) , в t содержится как минимум одно ребро, инцидентное с ним. В силу определения объекта S ( v ) в него входят все вершины графа при условии, что граф связный. Таким образом, мы приходим к противоречию между утверждениями V′ ∉ S ( V ) ∧ V′ ∈ V и ∀ a ∈ V → a ∈ S ( v ) .

Доказательство утверждения 2. Данное доказательство следует из доказательства первого утверждения. Пусть v′ и V′′ – произвольные вершины графа G . Очевидно, что V′ _∈ V , v ′′ _∈ V , v′ _∈ P , V ′′ _∈ p , V′ _∈ S ( V ) , V ′′ _∈ S ( V ) . В силу конструктивного определения t , данное множество ребер обеспечивает связность любой вершины, расположенной в i -м срезе объекта S ( v ) , с какой-либо вершиной из i -1 среза, где i ∈ {2,3,…,| S ( v )|} . Таким образом, множество ребер t обеспечивает связность любой вершины с вершиной V (вершиной, расположенной в первом срезе объекта S ( V ) ). Из связности графа G следует, что если любая вершина связана с вершиной v , то связаны любые вершины. Что и требовалось доказать.

Доказательство утверждения 3. Предположим, что граф ^̅ содержит циклы. Из этого следует, что в t ⊃ { e ′ _, e ^′′ } , такие, что ( e^′ =( v ′ _, v^′′′ )) ∧ ( e^′′ = =( v ′′ _, v ^′′′ )) ∧ ({ e ′ _, e^′′ } ⊂ E ) ∧ ({ v ′ _, v ′′ _, V ^′′′ } ⊂ V ) ∧ ( V′ _≠ V ′′ _≠ V^′′′ ) , при этом V′′′ расположено в i -м срезе объекта S ( V ) , а V′ и V ′′ в i -1 срезе. Что противоречит описанию функции f 3 , используемой при формировании t . Результатом вычисления функции f 3 в рассматриваемой ситуации будет множество, содержащее в себе объекты t′ ⊇ e′ и t ′′ ⊇ e′′ , при том, что t′ _∩ t^′′ == ∅ . Таким образом, утверждение 3 доказано.

Объединение доказательств утверждений 1, 2, 3 является доказательством теоремы.

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

В     соответствии     с     графическим     представлением     определим     множества

V = {vl, v2, v3,v4, v5, v6, v7, v8, v9, vl0} и E = {rl, r2, r3, r4, r5, r6, r7, r8, r9, rl0,rll,rl2,rl3} , где rl = (vl,v2) , r2 = (vl, v3) , r3 = (v2,v4) , r4 = (v3,v4) , r5 = (v3,v6) , 66 = (v4?v7) , 77 = (v2,v5) , r8 = (v5, v9) , r 9 = (v6, v7) , r10 = (v7,v8) , r11 = (v6,v8) , rl2 = (v8, vl0) , r13 =

( 9, 10). При этом будем считать ( ,  ′)=( ′, ). Построим множество веерных графов относительно вершины vl. В качестве исходных данных необходимо определить объект 5(vl).

4 7

5(vl) = vl ^v„ v5 v8 vl0 3   _{6  9}

Таким образом:

T (vl) = /3(5(vl), 5) x /3(5(vl), 4) x /3(5(vl), 3) x /3(5(vl), 2) . f 3(5(vl), 5) = /l(5(vl), 5,l) = {rl2,rl3} x 0 = {(rl2), ( rl3)} . f 3(5(vl), 4) = /l(5(vl), 4,l) x /l(5(vl), 4,2) x /l(5(vl), 4,3) = {r6, r9} x x {rl0,rll} x {r8} = {(r6,rl0, r8), (r6,rll,r8), (r9, rl0,r8), (r9, rll,r8)} . f 3(5(vl), 3) = /l(5(vl), 3,l) x /l(5(vl), 3,2) x /l(5(vl), 3,3) = {r3, r4} x {r7} x x {r5} = {(r3, r7, r5), (r4, r7, r5)} .

f 3(5(vl), 2) = /l(5(vl), 2,l) x /l(5(vl), 2,2) = {rl} x {r2} = {(rl, r2)}

T (vl) = {(rl2), (rl3)} x {(r6, rl0,r8), (r6, rll, r8), ( r9, rl0, r8), ( r9, rll,r8)} x x {(r3,r7,r5), (r4, r7, r5)} x {(rl, r2)} = {(rl2, r6, rl0, r8,r3,r7, r5, rl, r2), ( rl2,r6,rl0, r8, r 4,r7,r5,rl,r2), (rl2,r6,rll,r8,r3,r7,r5,rl,r2), ( rl2,r6,rll,r8,r4,r7,r5,rl,r2), ( rl2, r 9, rl0, r8, r3, r7, r5, rl, r2), (rl2, r9, rl0, r8, r4, r7, r5, rl, r2), ( rl2, r9, rll, r8, r3, r7, r5, rl, r 2), (rl2, r9, rll, r8, r4, r7,r5,rl, r2), (rl3,r6, rl0, r8, r3, r7,r5, rl, r2), (rl3, r6, rl0, r8, r4, r 7,r5,rl,r2), (rl3,r6,rll,r8,r3,r7,r5,rl,r2), ( rl3,r6,rll,r8,r4,r7,r5,rl,r2), (rl3,r9, 10, 8,  3, 7, 5,  1, 2 〉 , 〈 13, 9,  10, 8, 4,  7,  5,  1, 2 〉 , 〈 13, 9,  11, 8,  3, 7,  5,  1, 2 〉 ,

(rl3, r9, rll, r8, r4, r7, r5, rl, r2)}

Сформировать множество P на основе любого элемента из Т( vl) не представляет трудности. В результате получается 16 остовов.

Заключение

Представленный метод не формирует множество всех остовов графа. Для понимания этого факта можно рассмотреть результат вычисления Т( v6) . Формирование Т( v6) производится на основе 5( v6) = 3  1

v6 v7 v4 ^v„ v5 , так как вершины v7 и v8 расположены в одном срезе, ни один элемент из T(v6) не бу- 8 10 ⁹

дет содержать в себе ребро rl0. Также на основе рассматриваемого графа построим остов G(V,E} где ̅={ 2, 3, 5, 6, 7, 8, 9, 12, 13}. Данный остов не будет являться элементом множества, образо ванного объединением множеств веерных остовов, для всех вершин графа. Для полноты представления приведем расчет алгебраического дополнения к элементу матрицы Кирхгофа, которое, согласно теореме Кирхгофа-Трента[1], равно числу всех возможных остовов в графе. Матрица Кирхгофа для рассматриваемого графа имеет следующий вид:

2 -1 -1 0 0 0 0 0 0 0 -1 2 0 -1 -1 0 0 0 0 0 -1 0 3 -1 0 -1 0 0 0 0 0 -1 -1 3 0 0 -1 0 0 0 ()= 00 -1 0 0 -1 0 0 2 0 0 3 0 -1 0 -1 -1 0 00 . 0 0 0 -1 0 -1 3 -1 0 0 0 0 0 0 0 -1 -1 3 0 -1 0 0 0 0 -1 0 0 0 2 -1 0 0 0 0 0 0 0 -1 -1 2 Алгебраическое дополнение к элементу ,  = (-1) × , =68. Таким образом, мощность мно жества всех возможных остовов равна 68. Это значит, что при анализе коммуникационной компоненты модели, соответствующей графу, рассмотренному в примере, нами не рассматривались 76 % возможных комбинаций. Именно исключение из рассмотрения комбинаций, заведомо не содержащих решения поставленной задачи, является одним из главных принципов предлагаемой концепции. В последующих работах будут приведены алгоритмы решения таких задач, как нахождение кратчайшего пути, поиск остова наименьшей цены, нахождение максимального потока, с применением композиции веерных остовов, а также их сравнение с уже известными алгоритмами решения указанных задач. Изложение этих алгоритмов и моделей в одной работе просто невозможно в связи с ограничениями, предъявляемыми редакциями научных журналов.