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

Размещено на http://www.allbest.ru/

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

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

Дуборкина Ирина Альбертовна, кандидат экономических наук, доцент отделения кафедры экономики и управления,

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

Ключевые слова: логистика, энергетическая цепь, эффективность

Search algorithms OF EFFECTIVE LOGISTICS CHAINS of NETWORK FOR service industry

Sergey Lavrenchenko, PhD in Physico-mathematical sciences, Associate Professor, lawrencenko@hotmail.com,

Irina Duborkina, PhD in Economic sciences, Associate Professor; duborkina2012@yandex.ru

Russian State University of Tourism and Service (Regional Department of Services Studies in Lubertsi),

Lubertsi, Russian Federation

Logistics network arise when a transmission of material substance, material objects or energy, information and finance by links (channels) exist (for example, checked baggage on flights). The article proposes and substantiates the general concept of a logistics network for modeling any kind of service delivered by links between network nodes.

The efficiency of each link of the network is defined as ratio of the volume of useful services at the outlet link to the volume of service, which has been spent at the input (for a certain period of time).

The effectiveness of chain in the network is determined the same - as ratio of the volume of service at the output of chain to the volume of service at its input.

The overall efficiency of the chain is calculated as the product of the efficiencies of its links and the efficiency of chain better, than less in it losses.

The author introduces the concept of unprofitableness of service in such way that the total unprofitableness is equal to the sum of unprofitability chain of unprofitable parts of it, i.e., efficiency of links are multiplied, and their loss added. Thus, the antagonistic couple (efficiency unprofitability) turns out analogous to the pair (reliability, entropy) from communication theory and coding.

The article presents the possible interpretations by the offered logistic model: energy, material, information and financial network. The algorithms for information support of logistics networks are offered: two algorithms for finding the most effective chain from a specified mentioned one node to another, and two algorithms for finding in the network guaranteed a minimum level of service (between any pair of unspecified nodes).

The authors demonstrated an example of the application of the algorithm for finding the most efficient energy chain from the substation to the specified customer in the specific energy network.

Keywords: logistics, energy chain efficiency

Введение

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

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

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

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

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

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

(1) .

Здесь - безразмерная величина,

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

(2) .

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

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

Материальная логистическая сеть

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

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

Энергетическая логистическая сеть

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

Информационная логистическая сеть

Здесь звенья сети представляют каналы связи. Конкретным примером канала связи служит описанный в [9, с. 4] бинарный симметричный канал, на вход которого подается бит, причем вероятность того, что бит передается по каналу правильно, имеет определенное значение (), которое в теории связи (и кодирования) называется надежностью канала. В нашей общей теории логистических сетей мы интерпретируем это значение как эффективность () звена . Тогда получается, что выражает долю текста, в среднем передаваемую правильно по каналу , что согласуется с определением (1).

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

Финансовая логистическая сеть

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

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

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

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

Для решения задачи I мы вместо вводим новые веса дуг, которые будем называть весами Хартли-Шеннона, следующим образом: где - параметр (). В нашем исследовании важную роль играет изоморфизм между аддитивной полугруппой действительных чисел с нейтральным элементом 0 и мультипликативной полугруппой действительных чисел с нейтральным элементом 1: если и , то

(3) или .

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

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

В силу (3), утверждение 1 следует из того, что при функция монотонно убывает на промежутке Хотя в нашей теории непринципиально, по какому основанию брать логарифмы, в случае информационной сети естественнее положить т.е. Поскольку выражает долю текста, в среднем передаваемую правильно по каналу , получается, что в среднем передается правильно один бит из битов. Минимальное количество битов информации, достаточное для выявления этого правильного бита, в точности равно весу Хартли-Шеннона Последнее утверждение есть известная формула Хартли [8], обобщенная Шенноном [10].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

Литература

логистический цепь материальный информационный

1. Логистика: учеб. пособие для бакалавров / Б.А. Аникин [и др.]; ред. Б.А. Аникин, Т.А. Родкина. - М.: Проспект, 2014. - 408 с.

2. Белоусов, А.И., Ткачев, С.Б. Дискретная математика. - М.: МГТУ, 2006. - 744 с.

3. Vildhшj H.W., Wind D.K. Supplementary Notes for Graph Theory I // DTU DATABARS. [Электронный ресурс: URL: http://www.student.dtu.dk/~dawi/01227/01227-GraphTheory.pdf (дата обращения: 15.03.2015).

4. Ключевский, В.О. Русская история: полный курс лекций. - М.: ОЛМА-ПРЕСС Образование, 2004. - 831 с.

5. Левитин, А. Алгоритмы: введение в разработку и анализ. - М.: Вильямс, 2006. - 576 с.

6. Регуляторные аспекты политик энергоэффективности / З. Лонтаи, А. Пал, Г. Бакош, Л. Верринг: учебник INOGATE. - Европейский Союз: ERRA, 2011. - 88 с. [Электронный ресурс: URL: http://www.fstrf.ru/about/activity/inter/2/erra/2/EE_Textbook_FINAL_rus.pdf (дата обращения: 15.03.2015).

7. Peterson B. The problem with airlines and checked baggage // Condй Nast Traveler. -- 18 июня, 2012 г. [Электронный ресурс: URL: http://www.cntraveler.com/stories/2012-06-19/airlines-baggage-luggage-checked-fees-missing-bags (дата обращения: 15.03.2015).

8. Хартли, Р.В.Л. Передача информации / Теория информации и ее приложения. - М.: Физматгиз, 1959.

9. Hoffman D.G., Leonard D.A., Lidner C.C., Phelps K.T., Rodger C.A., Wal J.R. Coding Theory: The Essential. -- New York, Basel: Marcel Dekker Inc., 1991. -- 277 с.

10. Шеннон, К.Э. Математическая теория связи // Работы по теории информации и кибернетике / пер. С. Карпова. - М.: ИИЛ, 1963. - 830 с.

References

1.Logistika: ucheb. posobie dlja bakalavrov [Logistics: Textbook for bachelors]. B.A. Anikin [and so on]. Edited by B.A. Anikin, T.A. Rodkina. Moscow: Prospekt, 2014. 408 p.

2.Belousov, A.I., Tkachev, S.B. Diskretnaja matematika [The discrete mathematics]. Moscow: MGTU, 2006. 744 p.

3.Vildhшj H.W., Wind D.K. Supplementary Notes for Graph Theory I. DTU DATABARS. URL: http://www.student.dtu.dk/~dawi/01227/01227-GraphTheory.pdf (Accessed on March 15, 2015).

4.Kljuchevskij, V.O. Russkaja istorija: polnyj kurs lekcij [Russian history: a complete course of lectures]. Moscow: OLMA-PRESS Obrazovanie, 2004. 831 p.

5.Levitin, A. Algoritmy: vvedenie v razrabotku i analiz [The algorithms: Introduction to the development and analysis]. Moscow: Vil'jams, 2006. 576 p.

6.Reguljatornye aspekty politik jenergojeffektivnosti [Regulatory aspects of energy efficiency policy] / Z. Lontai, A. Pal, G. Bakosh, L. Verring: textbook INOGATE. EU: ERRA, 2011. 88 p. URL: http://www.fstrf.ru/about/activity/inter/2/erra/2/EE_Textbook_FINAL_rus.pdf (Accessed on March 15, 2015).

7.Peterson B. The problem with airlines and checked baggage. Condй Nast Traveler. June 18, 2012. URL: http://www.cntraveler.com/stories/2012-06-19/airlines-baggage-luggage-checked-fees-missing-bags (Accessed on March 15, 2015).

8.Hartli, R.V.L. Peredacha informacii [Information transfer]. Teorija informacii i ee prilozhenija [Theory of information and its applications]. Moscow: Fizmatgiz, 1959.

9.Hoffman D.G., Leonard D.A., Lidner C.C., Phelps K.T., Rodger C.A., Wal J.R. Coding Theory: The Essential. New York, Basel: Marcel Dekker Inc., 1991. 277 p.

Размещено на Allbest.ru