Алгоритмы поиска эффективных логистических цепей сети процесса для сферы сервиса

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

В логистической сети для каждой дуги указана ее эффективность , определяемая как отношение объема чистого полезного сервиса на выходе дуги к объему затраченного сервиса на ее входе (за конкретный временной интервал). В терминах теории графов такая сеть представляет собой дуго-взвешенный орграф, в котором всем дугам e_k приписаны веса η_k – действительные числа из промежутка (0;1]. Эти веса моделируют эффективности соответствующих дуг. Логистические сети моделируют ситуации, в которых имеет место передача материальной субстанции (или материальных объектов), энергии, информации или финансов по дугам сети. При доставке сервиса по дуге e_k потери прямо пропорциональны объему сервиса на ее входе с коэффициентом 1 - η_k .

Логистическая сеть называется односторонней , если между любыми двумя ее узлами u и v сервис доставляется или только из u в v , или только из v в u , или вообще не доставляется. Сеть называется двусторонней , если из того, что сервис доставляется из u в v , следует, что он также доставляется из v в u , т.е. u и v соединены парой дуг с противоположными направлениями, uv и vu . Сеть, не являющуюся ни односторонней, ни двусторонней, будем называть смешанной . У сети любого из этих видов каждую пару противоположных дуг uv и vu будем заменять на одно неориентированное звено с тем же весом, например, так поступаем с парой дуг ed и de в смешанной сети на первой диаграмме (рис.). Если в двусторонней сети у каждой пары противоположных дуг веса одинаковы, сеть называется симметричной двусторонней сетью и преобразуется к неориентированному графу, причем предполагается, что сервис доставляется в обоих направлениях каждого звена с равными эффективностями.

В разделе 3 данной статьи представлены возможные приложения предлагаемой логистической модели: материальные, энергетические, информационные и финансовые сети. В разделах 4 и 5 решены две задачи (соответственно): I) в данной логистической сети общего вида с выделенной парой конкретных узлов a и z найти цепь из a в z , имеющую максимальную эффективность, и II) для данной связной симметричной двусторонней логистической сети найти гарантированный минимальный уровень эффективности сервиса (между любой парой не указанных конкретно узлов).

2.    Понятие эффективности логистической цепи

Логистическая цепь из узла a в узел z – это последовательность дуг, конец каждой из которых, кроме последней, является началом следующей, причем первая дуга выходит из a , а у последней дуги цепи только один конец – узел z . Эффективность сервиса на одном звене логистической сети определяется как отношение объема чистого полезного сервиса на выходе звена к объему затраченного сервиса на его входе:

Serviceâûõ.

n = f----------n-

Serviceâõîä.

Здесь n - безразмерная величина, 0 <  n ^ 1-

Формула (1) также служит определением общей эффективности сервиса во всей цепи как отношения сервиса на выходе цепи к сервису на ее входе. Нетрудно показать, что общая эффективность сервиса в q -звенной цепи вычисляется как произведение эффективностей ее звеньев [6, с. 17]:

n iau. = П 1 П 2 L n q -

3.    Основные классы логистических сетей

Приведем четыре основных класса логистических сетей, второй из которых представлен в [6, с. 16], а третий – в [9, с. 4].

• 3.1.    Материальная логистическая сеть. Здесь звенья сети представляют транспортировочные магистрали, по которым передается материальная субстанция или материальные объекты, например, зарегистрированный багаж на авиарейсах. Эффективность звена здесь – это отношение количества материальной субстанции (в весовом, объемном или штучном измерениях) на выходе звена к ее количеству на входе. Конкретные примеры: транспортные логистические сети [1], сети централизованного теплоснабжения и сети трубопроводов (жидкости или газа) [6].

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

• 3.3.    Информационная логистическая сеть. Здесь звенья сети представляют каналы связи. Конкретным примером канала связи служит описанный в [9, с. 4] бинарный симметричный канал, на вход которого подается бит, причем вероятность того, что бит передается по каналу ek правильно, имеет определенное значение pk (0 < pk< 1), которое в теории связи (и кодирования) называется надежностью канала. В нашей общей теории логистических сетей мы интерпретируем это значение как эффективность Пк (= Рк) звена ek. Тогда получается, что п выражает долю текста, в среднем передаваемую правильно по каналу e_k , что согласуется с определением (1).

• 3.4.    Финансовая логистическая сеть. Здесь звенья сети представляют каналы транзакций. Если банк взимает комиссионный сбор в размере КСБ % от суммы транзакции, то в качестве эффективности такого канала e_k следует взять величину n_k = 1-КСБ/100.

4.    Нахождение максимально эффективной логистической цепи

Интересный факт отмечен в зарубежных исследованиях [7]: оказывается, в течение 2011 года 26 млн. единиц зарегистрированного багажа во всем мире сбивались с маршрута на международных авиарейсах. Если бы все эти потери случались в одном аэропорту размера Международного аэропорта Филадельфии, то получилось, что в среднем за 2011 год у каждого пассажира терялась одна единица зарегистрированного багажа!

В случае информационной цепи надо сделать оговорку, что формула (2) верна, если под Service_âûõ. понимать объем текста, передаваемого правильно в каждом звене. Если же контролировать правильность передачи бита, например, в двухзвенной цепи, сравнивая лишь его начальное и самое конечное значения, то две ошибки подряд компенсируют друг друга, и итоговый бит получается таким же, как исходный; в такой постановке если эффективности звеньев равны П 1 и 7 2 , то общая эффективность цепи будет не 7 1 7 2 , а уже 7 1 7 2 + ⁽¹ - 7 1 ) ⁽¹ - 7 2 ).

Задача I. В данной логистической сети общего вида с выделенной парой узлов a и z найти цепь из a в z , имеющую максимальную эффективность.

Сразу же отметим, что цепь из a в z с максимальной суммой весов дуг не обязательно будет иметь их максимальное произведение. Например, из пары двухзвенных цепей из a в z , с весами дуг 0,8 и 0,3 у первой цепи, и 0,5 и 0,5 у второй, первая будет иметь бóльшую сумму весов, а вторая большее произведение. Будем считать , что первая цепь больше по сложению (т.е. в аддитивном смысле), а вторая больше по умножению (т.е. в мультипликативном смысле). Однако можно утверждать (см. утверждение 1 ниже), что цепь из a в z с минимальной суммой весов Хартли-Шеннона уже будет цепью с максимальным произведением исходных весов дуг.

Для решения задачи I мы вместо П к вводим новые веса дуг, которые будем называть весами Хартли-Шеннона, следующим образом: i k = | log b (П к )| = - log b (П к ), где b - параметр ( b >  1). В нашем исследовании важную роль играет изоморфизм между аддитивной полугруппой действительных чисел у е [0; + да ) с нейтральным элементом 0 и мультипликативной полугруппой действительных чисел x е (0; 1] с нейтральным элементом 1: если у 1 = | log b ( x i) | и у 2 = | log b ( x 2) | , то

• ⁽³⁾    У 1 ⁺ У 2 =| log b ^{( x} 1 ^x 2)| ^{или l} 1 ^{+ l} 2 =| log b⁽ П 1 П 2)\ .

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

Утверждение 1. Из логистических цепей из узла a в узел z произведение весов (дуг) П к максимально у той, у которой минимальна сумма весов Хартли-Шеннона г ^ .

В силу (3), утверждение 1 следует из того, что при b >  1 функция у = | log b ( x )| монотонно убывает на промежутке (0;1]. Хотя в нашей теории непринципиально, по какому основанию b >  1 брать логарифмы, в случае информационной сети естественнее положить b = 2, т.е. г ^ = | log 2 ( П k )| = - log 2 ( П k ) = log 2 (V П к )• Поскольку П к выражает долю текста, в среднем передаваемую правильно по каналу e_k , получается, что в среднем передается правильно один бит из 1/ П к битов. Минимальное количество битов информации, достаточное для выявления этого правильного бита, в точности равно весу Хартли-Шеннона t ^ . Последнее утверждение есть известная формула Хартли [8], обобщенная Шенноном [10].

Авторами предлагается следующий алгоритм решения задачи I. Он верен в силу утверждения 1.

Алгоритм 1. Вход: логистическая сеть общего вида с выделенной парой узлов a и z . Подготовительная часть: заменить веса дуг на соответствующие веса Хартли-Шеннона. Основная часть: найти цепь из a в z с минимальной суммой весов Хартли-Шеннона. Выход: найденная цепь максимально эффективна.

Рисунок – Решение задачи I при помощи алгоритма 2

Для выполнения основной части можно использовать известный алгоритм Дейкстры [3, с. 13], [5, с. 189]. Изоморфизм (3) вкупе с утверждением 1 и со свойством монотонности функции у = | log ь ( x )| на (0;1] позволяют приспособить алгоритм 1 в терминах исходных весов без перехода к весам Хартли-Шеннона. Для этого надо заменить «0» на «1», « да » на «0», «min» на «max», а также изменить все знаки неравенств на противоположные. В результате получается мультипликативный аналог алгоритма Дейкстры.

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

1-й основной шаг. Из узлов, еще не обведенных в кружок, выбрать тот, у которого наибольший текущий вес и обвести его в кружок. Если таких узлов более одного, обвести в кружок любой один из них.

2-й основной шаг. Для узла v , только что обведенного в кружок, попытаться обновить вес каждого еще не обведенного в кружок узла u , в который есть дуга vu из v , по следующему правилу: если произведение веса узла v на вес дуги vu больше текущего веса узла u , то заменяем вес узла u на это произведение, иначе вес узла u не обновляется. В случае фактического обновления веса узла u текущая история узла u заменяется на текущую историю узла v , к которой справа приписывается символ u .

Алгоритм 2 (мультипликативный аналог алгоритма Дейкстры). Вход: логистическая сеть общего вида с выделенной парой узлов a и z . Подготовительная часть: узлу a присваивается вес 1, а всем остальным узлам вес 0, также узлу a присваивается история, состоящая из одного символа a . Основная часть: к получающейся сети применяются последовательно в чередующемся порядке 1-й и 2-й основные шаги, начиная с 1-го; процесс завершается, как только узел z оказывается обведенным в кружок; процесс также завершается, когда после очередного выполнения 2-го основного шага узел z остается не обведенным, но все необведенные узлы имеют текущий нулевой вес (такая ситуация возникает, когда вообще не существует логистической цепи из a в z ). Выход: история узла z показывает максимально эффективную цепь из a в z , а вес узла z показывает эффективность этой цепи.

В силу (3) и монотонности log очередность обведения узлов в кружок в алгоритме 2 такая же, как в алгоритме 1. Значит, алгоритм 2 верен, потому что алгоритм 1 верен.

Пример 1. От подстанции a энергия доставляется в пункты b , c , d , e и z по смешанной энергетической сети, показанной на 1-й диаграмме рисунка. Для каждой дуги указана ее эффективность. Для подачи энергии от a в z найти цепь максимальной энергоэффективности.

Для решения примера 1 используем алгоритм 2. Работа этого алгоритма иллюстрируется диаграммами на рисунке. На последней диаграмме порядок обведения узлов в кружок следующий: сначала d (после пересчета весов узлов d и z из узла e), затем z (после пересчета веса узла z из узла d ). Ответ к задаче находится на последней диаграмме напротив узла z, а именно: abcdz – самая эффективная цепь, ее энергоэффективность равна 0,93168306.

Заметим, что в примере 1 в процессе работы алгоритма возникает паритет весов у узлов d и e (см. предпоследнюю диаграмму на рисунке). Поэтому альтернативный вариант работы алгоритма состоит в том, что на предпоследней диаграмме в кружок обводится сначала узел d , затем e (потому что у e больший вес, чем текущий вес узла z ) и, наконец, z (после пересчета веса узла z из e без его обновления). Ответ получается такой же.

5.    Нахождение гарантированного минимума эффективности сервиса в сети

Задача II. В данной связной симметричной двусторонней логистической сети найти гарантированный минимальный уровень эффективности сервиса между любой парой не указанных конкретно узлов, т.е. такой уровень η _{ãàð. min}, когда из любого узла в любой другой найдется цепь с эффективностью, не меньшей η _{ãàð. min}. В качестве тривиального решения можно взять нулевой уровень, но авторы заинтересованы в нахождении максимально возможного уровня для η _{ãàð. min}.

Остовным деревом в данном неориентированном графе называется связный подграф, не содержащий циклов и покрывающий все узлы данного графа. Как обосновано в [3, с. 88], если веса всех звеньев графа положительны, остовное дерево с минимальной суммой весов имеет и минимальное их произведение. Доказательство [3, с. 88] можно слегка модифицировать и доказать следующее утверждение.

Утверждение 2. Если веса всех звеньев графа положительны, остовное дерево с максимальной суммой весов звеньев имеет и максимальное их произведение.

В силу утверждения 2 задача II решается адаптацией алгоритма Краскала (изложенного, например, в [2, с. 309], [3, с. 24] и [5]), который отыскивает остовное дерево с максимальной суммой весов звеньев.

Алгоритм 3. Вход: связная симметричная двусторонняя логистическая сеть. Подготовительная часть: текущее множество звеньев устанавливается пустым. Основная часть: последовательно делается следующий основной шаг: из звеньев, которые не принадлежат текущему множеству и добавление которых к текущему множеству не создает в нем цикла, выбирается звено максимально возможного веса и добавляется к текущему множеству; когда число звеньев в текущем множестве становится на единицу меньше, чем общее число узлов в сети, процесс завершается. Выход: текущее множество звеньев определяет остовное дерево с наибольшим произведением весов звеньев Πmax.

Поскольку эффективность каждого звена логистической сети есть величина между нулем и единицей, из формулы (2) следует, что любая цепь в найденном остовном дереве имеет эффективность, не меньшую η _ãàð.min = Π _max. В качестве цепи, соединяющей конкретную пару узлов сети с эффективностью, не меньшей η _{ãàð. min}, достаточно взять цепь в найденном остовном дереве, соединяющую эти узлы.

Алгоритм 4. Вход: такой же, как для алгоритма 3; перебираются все пары узлов сети, и для каждой пары при помощи алгоритма 2 ищется максимальная эффективность сервиса между ними. Выход: наименьшая из найденных эффективностей и будет максимальным уровнем η _ãàð.min.

Отметим, что алгоритм 4 также применим к произвольной логистической сети общего вида, причем всегда дает на выходе максимально возможное значение для η _{ãàð. min}, в то время как алгоритм 3 применим только для связных симметричных односторонних сетей и дает значение, близкое к максимальному, лишь для достаточно разреженных сетей. Однако алгоритм 4 имеет бóльшую вычислительную сложность – время его работы по порядку не менее чем в n ²/log n раз больше времени работы алгоритма 3 даже для густых сетей, где n – число узлов в сети.

Заключение

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

В заключение подчеркнем, что предложенная концепция логистической сети универсальна. В статье показано, как она может служить для моделирования четырех классов сетей: материальных, энергетических, информационных и финансовых. Однако области применимости концепции шире этих четырех классов. Алгоритмы 1 и 2 также могут найти применение в анализе социологических сетей, например, когда пользователь a ищет цепь поручителей, чтобы с максимальной вероятностью добиться принятия «узлом» z нужного для a решения. «Так порука складывалась в цепь поручителей, охватывавшую весь служилый уезд». – Писал еще В.О. Ключевский [4, с. 257].