Транспортные сети
Наше описание алгоритмов вычисления сетевых потоков мы начнем с идеализированной физической модели, которая наглядно продемонстрирует несколько фундаментальных понятий. Допустим, что имеется система взаимосвязанных нефтепроводных труб различных диаметров, а на соединениях труб установлены вентили, управляющие движением потоков, как показано на
рис.
22.5. Далее мы будем предполагать, что в системе трубопроводов имеется единственный исток (допустим, нефтяное месторождение) и единственный сток (к примеру, нефтеперерабатывающий завод), в который попадают все потоки. В каждом соединении потоки нефти находятся в равновесии: объем поступающей нефти равен объему вытекающей нефти. Мы будем измерять потоки и пропускную способность труб в одних и тех же единицах (например, в галлонах в секунду).
Если общая пропускная способность труб, входящих в каждый вентиль, равна общей пропускной способности выходящих труб, то решать вообще нечего: нужно просто заполнить по максимуму все трубы. Иначе будут заполнены не все трубы, но нефть будет течь по трубам в соответствии с настройками вентилей и свойством, что объем нефти, поступающей в каждое соединение, равен объему вытекающей нефти. А из баланса в соединениях следует и общий баланс в сети: в лемме 22.1 будет показано, что объем нефти, втекающей в сток, равен объему нефти, вытекающей из истока. А, как показано на
рис.
22.6, настройки вентилей на соединениях могут оказывать нетривиальное влияние на потоки в сети. И вот нас интересует следующий вопрос: какие настройки вентилей обеспечат максимальный поток нефти из истока в сток?
Эту ситуацию можно непосредственно смоделировать при помощи сети (взвешенный орграф, согласно определению из
“Кратчайшие пути”
) с одним истоком и одним стоком. Ребра сети соответствуют трубам, вершины соответствуют соединениям труб с вентилями, которые регулируют потоки нефти в исходящие ребра, а веса ребер соответствуют пропускной способности труб. Мы считаем ребра ориентированными, т.е. нефть в каждой трубе может течь только в одном направлении. По каждой трубе проходит определенный поток, который меньше или равен ее пропускной способности, и каждая вершина удовлетворяет условию баланса: входной поток равен выходному потоку.
Рис.
22.5.
Сетевые потоки
Транспортная сеть – это взвешенная сеть, в которой веса ребер интерпретируются как пропускные способности (вверху). Требуется вычислить второе множество весов ребер, ограниченное пропускными способностями, которые мы называем потоками. Внизу показаны наши соглашения относительно вычерчивания транспортных сетей. Ширина каждого ребра пропорциональна его пропускной способности; объем потока в каждом ребре показан заштрихованной частью; поток на наших рисунках всегда направлен из единственного истока вверху в единственный сток внизу; пересечения (как между ребрами 1-4 и 2-3 в рассматриваемом примере) не представляют вершин, если не обозначены как вершины. За исключением истока и стока, в каждой вершине входной поток равен выходному потоку: например, в вершину 2 входят 2 единицы потока (из вершины 0) и выходят 2 единицы потока (1 единица в вершину 3 и 1 единица в вершину 4).
Рис.
22.6.
Управление потоками в сети
Открыв вентили вдоль пути 0-1-3-5, можно инициировать в этой сети поток мощностью 2 единицы (вверху); открыв вентили вдоль пути 0-2-4-5, получим еще 1 единицу потока (в центре). Звездочками отмечены заполненные ребра. Поскольку ребра 0-1, 2-4 и 3-5 заполнены, прямого способа увеличить поток из 0 в 5 не существует, но если еще открыть вентиль в вершине 1, чтобы направить часть потока в ребро 1-4 , то будет задействовано ребро 4-5, благодаря чему будет получен максимальный поток в данной сети (внизу).
Такая абстракция транспортной сети представляет собой полезную модель решения задач, которая непосредственно применима к широкому кругу ситуаций, а косвенно – к еще более широкому кругу. Иногда для наглядности мы представляем нефть, текущую по нефтепроводу, но можно представлять и товары, перемещаемые по каналам распределения, и другие ситуации.
Потоковая модель непосредственно применима к задаче распределения – при этом значения потоков интерпретируются как их интенсивность, и транспортная сеть описывает потоки товаров точно так же, как и потоки нефти. Например, потоки на
рис.
22.5 можно интерпретировать так: два элемента в единицу времени пересылаются из вершины 0 в 1 и из 0 в 2, один элемент в единицу времени – из 0 в 2, один элемент в единицу времени – из 1 в 3 и из 1 в 4 и т.д.
Другой способ интерпретации потоковой модели для задачи распределения – потоки интерпретируются как объемы товаров, и тогда сеть описывает только одноразовую рассылку товара. Например, потоки на
рис.
22.5 можно интерпретировать, как трехэтапную поставку четырех единиц товара из вершины 0 в 5: сначала пересылаются две единицы товара из 0 в 1 и две единицы из 0 в 2, так что в каждой из этих вершин остается по две единицы товара. Далее выполняется пересылка по одной единице товара из 1 в 3, из 1 в 4 , из 2 в 3 и из 2 в 4 , и в каждой из вершин 3 и 4 остается по две единицы товара. Рассылка завершается доставкой двух единиц товара из вершины 3 в 5 и двух единиц из 4 в 5.
Как и в случае использования расстояния в алгоритмах поиска кратчайшего пути, мы вполне можем, когда это удобно, отказаться от любой физической интерпретации, т.к. все рассматриваемые нами определения, леммы и алгоритмы основаны исключительно на абстрактной модели, которая не обязана подчиняться физическим законам. Вообще-то основная причина нашего интереса к модели сетевых потоков в том, что она позволяет решать методом сведения множество других задач – в этом мы убедимся в разделах 22.4 и 22.6. В силу такой универсальности целесообразно дать точные определения терминов и понятий, с которыми мы ознакомились неформально.
Определение 22.1. Сеть с вершиной s, выбранной в качестве истока, и с вершиной t, выбранной в качестве стока, называется st-сетью.
В этом определении слово ” выбранный ” означает, что вершина s не обязательно должна быть истоком (вершина без входящих ребер), а вершина t – стоком (вершина без исходящих ребер), но мы будем рассматривать их именно так, игнорируя в наших рассуждениях (и алгоритмах) ребра, входящие в s, и ребра, исходящие из . Во избежание путаницы в наших примерах мы будем рассматривать сети с одним истоком и стоком, а более общие ситуации рассмотрим в разделе 22.4. Вершины s и t мы будем называть, соответственно, ” истоком ” и ” стоком ” st-сети, поскольку они выполняют в сети именно эти роли. Остальные вершины сети мы будем называть внутренними вершинами.
Определение 22.2. Транспортная сеть (flow network) – это st-сеть с положительными весами ребер, которые мы будем называть пропускными способностями (capacity). Поток (flow) в транспортной сети – это множество неотрицательных весов ребер, которые называются реберными потоками (edge flow) и удовлетворяют условиям: поток в любом ребре не превышает пропускную способность этого ребра, а суммарный поток, входящий в каждую внутреннюю вершину, равен суммарному потоку, выходящему из этой вершины.
Мы будем называть суммарный поток в вершину притоком (inflow) этой вершины, а суммарный поток из вершины – оттоком (outflow) этой вершины. По соглашению потоки в ребрах, входящих в исток, и потоки в ребрах, исходящих из стока, равны нулю, а в лемме 22.1 будет показано, что отток истока всегда равен притоку стока, и этот поток мы будем называть мощностью (value) сети. Имея эти определения, нетрудно дать формальное определение нашей основной задачи.
Максимальный поток. Для заданной st-сети необходимо найти такой поток, что никакой другой поток из в не имеет большего значения. Для краткости будем называть такой поток максимальным потоком (maxflow), а задачу вычисления такого потока в сети будем называть задачей о максимальном потоке. В некоторых приложениях достаточно знать только величину максимального потока, но обычно требуется знать структуру потока (величины каждого реберного потока), обеспечивающего эту величину.
На ум тут же приходят различные варианты этой задачи. Можно ли рассматривать сеть с несколькими истоками и стоками? А как насчет сетей без истоков и стоков? Может ли поток проходить по ребрам в обоих направлениях? Возможны ли ограничения на пропускную способность вершин вместо ограничений на ребра (или наряду с ними)? Для алгоритмов на графах характерно то, что отделение тривиальных ограничений от ограничений, влекущих далеко идущие последствия, само по себе может оказаться трудной задачей. После того, как мы рассмотрим алгоритмы решения фундаментальной задачи, в разделах 22.2 и 22.3 мы исследуем эту задачу и приведем примеры сведения к задаче о максимальном потоке множества других с виду различных задач.
Характерным свойством потоков является условие локального баланса: в каждой внутренней вершине приток равен оттоку. На пропускные способности ребер такое ограничение не накладывается, и вообще-то именно нарушение баланса между суммарной пропускной способностью входящих ребер и суммарной пропускной способностью исходящих ребер и характеризует задачу о максимальном потоке. Условие баланса должно выполняться в каждой внутренней вершине, но оказывается, что это локальное свойство определяет и глобальное перемещение по сети. Однако пока это гипотеза, которую еще нужно доказать.
Лемма 22.1. Любой st-поток обладает тем свойством, что отток из вершины s равно притоку в вершину t.
Доказательство. (Термин st-поток (st-flow), означает ” поток в st-сети ” .) Добавим в сеть ребро из фиктивной вершины в вершину s, с потоком и пропускной способностью, равными оттоку вершины s, и ребро из вершины t в другую фиктивную вершину, с потоком и пропускной способностью, равными притоку вершины t. Теперь по индукции можно доказать более общее свойство: приток равен оттоку для любого множества вершин (без фиктивных вершин).
Применяя это свойство к множеству всех вершин сети, получим, что приток в исток из связанной с ней фиктивной вершины (который равен оттоку истока) равен оттоку из стока в связанную с ним фиктивную вершину (который равен притоку стока).
Следствие. Величина потока объединения двух множеств вершин равна сумме величин каждого из потоков этих двух множеств минус сумма весов ребер, соединяющих вершину одного множества с вершиной другого множества.
Доказательство. Приведенное выше доказательство для множества S и вершины v работает и в том случае, когда мы заменяем вершину v некоторым множеством T (которое не пересекается с S). Иллюстрация этой леммы приведена на
рис.
22.7.
В доказательстве леммы 22.1 можно обойтись и без фиктивных вершин, добавить в любую транспортную сеть ребро из в с пропускной способностью, равной мощности сети, и знать, что приток равен оттоку для любого множества узлов этой расширенной сети. Такой поток называется циркуляцией (circulation), а подобное построение показывает, что задача о максимальном потоке сводится к задаче поиска такой циркуляции, которая обеспечивает максимальный поток в заданном ребре.
Рис.
22.7.
Баланс потоков
Это иллюстрация сохранения баланса потоков при объединении множеств вершин. Два меньших овала соответствуют двум произвольным непересекающимся множествам вершин, а буквы представляют потоки в множествах ребер: A – величина потока в левое множество, кроме притока из правого множества, х – величина потока в левое множество из правого множества и т.д. Если имеет место баланс потоков между двумя множествами, то должно выполняться равенство A + x = B + у для левого множества и C + y = D + x для правого множества. Суммируя эти два равенства и исключая сумму , мы получим A + C = B + D, – т.е. для объединения двух множеств приток равен оттоку.
В некоторых ситуациях подобная формулировка упрощает наши рассуждения. Например, как показано на
рис.
22.8, она приводит к интересному альтернативному представлению потоков как множества циклов.
Если задано множество циклов и величина потока для каждого цикла, то легко вычислить соответствующую циркуляцию: нужно пройти по каждому циклу и добавить указанную величину потока к каждому ребру. Обратное свойство более интересно: можно найти множество циклов (и величину потока для каждого из них), которое эквивалентно любой заданной циркуляции.
Лемма 22.2. (Теорема разложения потока). Любую циркуляцию можно представить в виде потока в некотором множестве из не более чем E направленных циклов.
Доказательство. Этот результат можно получить с помощью простого алгоритма: будем повторять следующий процесс, пока имеются ребра, по которым проходят потоки. Начнем с произвольного ребра с ненулевым потоком, пройдем по любому ребру с ненулевым потоком, исходящему из конечной вершины первого ребра, и продолжаем эту процедуру, пока не попадем в уже посещенную вершину (обнаружен цикл). Выполним обратный обход по обнаруженному циклу, найдем ребро с минимальным потоком, а затем уменьшим потоки в каждом ребре цикла на это значение. Каждое повторение этого процесса обнуляет поток по меньшей мере в одном ребре, поэтому в сети может быть не более E циклов.
Процесс, описанный в доказательстве, показан на
рис.
22.9. В случае st-потоков применение этой леммы к циркуляции, полученной добавлением ребра из в , позволяет сделать вывод, что любой st-поток можно представить в виде потока вдоль множества не более E ориентированных путей, каждый из которых есть либо путь из в , либо цикл.
Следствие. Для максимального потока любой st-сети подграф, индуцированный ненулевыми потоками, является ациклическим.
Доказательство. Циклы, не содержащие ребро , не меняют величину потока, поэтому можно обнулить поток в любом таком цикле, не меняя величину общего потока.
Следствие. Максимальный поток любой st-сети можно представить в виде потока вдоль множества не более чем E ориентированных путей из в .
Рис.
22.8.
Представление в виде циклических потоков
Здесь показано, что приведенную слева циркуляцию можно разложить на четыре цикла , , и с весами, соответственно, 2, 1, 1 и 3. Ребра каждого цикла показаны в соответствующем столбце, а суммирование весов каждого ребра в каждом цикле, в который оно входит (по соответствующей строке), дает его вес в циркуляции.
Рис.
22.9.
Процесс разложения потока на циклы
Чтобы разложить произвольную циркуляцию на множество циклов, мы многократно выполняем следующий процесс: проходим по любому пути, пока не встретим какой-либо узел второй раз, затем находим минимальный вес в обнаруженном цикле, после чего вычитаем минимальный вес из весов каждого ребра обнаруженного цикла и удаляем каждое ребро, вес которого стал нулевым. Например, на первой итерации мы проходим по пути и обнаруживаем цикл , потом вычитаем 1 из весов всех ребер цикла, и в результате удаляем из цикла ребро , так как его вес стал нулевым. На второй итерации мы удаляем ребра 0-1 и 2-0, на третьей – 1-3, 4-2 и 2-1, а на последней итерации удаляем 3-5, 5-4 и 4-3.
Эти свойства позволяют получить представление о природе потоков, что будет полезно при разработке и анализе алгоритмов вычисления максимальных потоков.
С одной стороны, мы можем рассмотреть более общую формулировку задачи вычисления максимального потока в сети с несколькими истоками и стоками. Это позволит использовать наши алгоритмы для более широкого спектра приложений. С другой стороны, мы можем рассмотреть специальные случаи, например, ациклические сети. Это может облегчить решение задачи. Хотя, как мы убедимся в разделе 22.4, по трудности решения эти варианты эквивалентны рассматриваемой нами версии. Поэтому в первом случае мы можем приспособить наши алгоритмы и приложения для более широкой области приложений, а во втором случае вряд ли найдется более легкое решение. В приведенных здесь иллюстрациях мы используем ациклические графы, поскольку легче понять такие примеры, когда направление потока естественное – сверху вниз, но наши реализации допускают существование сетей с циклами.
Для реализации алгоритма вычисления максимального потока мы воспользуемся классом GRAPH из
“Минимальные остовные деревья”
, но с указателями на более сложный класс EDGE. Вместо одного веса, как это было в
“Минимальные остовные деревья”
и
“Кратчайшие пути”
, мы используем приватные члены данных pcap и pflow (пропускная способность и величина потока), а также общедоступные функции-элементы cap() и flow(), которые возвращают их значения. Хотя сети являются ориентированными графами, наши алгоритмы будут проходить по ребрам в обоих направлениях, поэтому мы используем представление в виде неориентированного графа из
“Минимальные остовные деревья”
и функцию-член from, которая позволяет отличить ребро от ребра .
Такой подход позволяет отделить абстракцию, необходимую нашим алгоритмам (ребра идут в обоих направлениях), от конкретной структуры клиентских данных и ставит перед этими алгоритмами простую цель: присвоить элементам flow в ребрах клиента такие значения, которые максимизируют поток через сеть. Критическим моментом наших реализаций является замена абстракции сети, которая зависит от значений потока и реализуется функциями-членами класса EDGE. Мы рассмотрим реализацию класса EDGE в разделе 22.2 (программа 22.2).
Поскольку транспортные сети обычно разрежены, мы воспользуемся классом GRAPH на основе представления списками смежных вершин, как в реализации класса SparceMultiGRAPH из программы 20.5. Но более важно то, что типичные транспортные сети могут содержать параллельные ребра (различной пропускной способности), соединяющие две вершины. Класс SparceMultiGRAPH не требует специальных мер в подобных ситуациях, но в случае представления графа матрицей смежности клиентам придется объединить такие ребра в одно ребро.
В представлениях сетей, описанных в
“Минимальные остовные деревья”
и 21, применялось соглашение, что веса представляются вещественными числами от 0 до 1. В этой главе мы полагаем, что веса (пропускные способности и величины потоков) представляют собой да-разрядные целые числа (от
0 до 2m – 1
). Это сделано по двум основным причинам. Во-первых, нам часто придется проверять на равенство различные линейные комбинации весов, а в случае чисел с плавающей точкой это не всегда удобно. Во-вторых, время выполнения алгоритмов может зависеть от относительных значений весов, а параметр
M = 2m
удобен для ограничения значений весов. Например, отношение наибольшего веса к наименьшему ненулевому весу меньше M. Использование целочисленных весов – лишь один из многочисленных возможных вариантов (см., например, упражнение 20.8) при решении подобных задач.
Иногда удобно рассматривать ребра с неограниченной пропускной способностью, что означает, что мы не сравниваем поток с пропускной способностью такого ребра. В такой ситуации можно воспользоваться сигнальным значением с заведомо большим значением, чем величина любого потока.
Программа 22.1 представляет собой клиентскую функцию, которая проверяет, удовлетворяют ли потоки условию баланса в каждом узле, и если удовлетворяют, то возвращает значение мощности потока. Вызов этой функции можно включить в алгоритм вычисления максимального потока в качестве заключительной операции. Несмотря на все доверие к лемме 22.1, программистская осторожность требует также проверить, равен ли поток, вытекающий из истока, потоку, втекающему в сток. Иногда имеет смысл проверить, что ни в одном ребре поток не превосходит пропускную способность этого ребра и что структуры данных внутренне непротиворечивы (см. упражнение 22.12).
Программа 22.1. Проверка и вычисление мощности потока
Вызов вычисляет разность между входным и выходным потоками в вершине v сети G. Вызов flow(G, s, t) проверяет величины сетевых потоков из истока (s) в сток (t). Если входной поток в некотором внутреннем узле не равен выходному потоку или если величина какого-либо потока меньше нуля, то возвращается 0; иначе возвращается величина потока.
Рис.
22.10.
Транспортная сеть для упражнений
Эта транспортная сеть используется в нескольких упражнениях данной главы.
Рис.
22.11.
Транспортная сеть с циклами
Данная транспортная сеть похожа на сеть, изображенной на
рис.
22.10, только направления двух ребер заменены на обратные, вследствие чего появлились два цикла. Эта транспортная сеть также рассматривается в нескольких упражнениях данной главы.
22.1. Найдите два различных максимальных потока в транспортной сети, изображенной на
рис.
22.10.
22.2. Пусть все пропускные способности выражаются положительными целыми числами, меньшими M. Каков максимально возможный поток для произвольной st-сети с V вершинами и E ребрами? Дайте два ответа, в зависимости от того, допускаются ли параллельные ребра.
22.3. Приведите алгоритм решения задачи о максимальном потоке для случая, когда сеть образует дерево, если удалить сток.
22.4. Приведите семейство сетей с E ребрами и циркуляцией, в которых процесс, описанный в доказательстве леммы 22.2, порождает E циклов.
22.5. Напишите класс EDGE, представляющий пропускные способности и потоки в виде вещественных чисел от 0 до 1 с d цифрами после десятичной точки, где d – фиксированная константа.
22.6. Напишите программу, которая строит транспортную сеть, считывая из стандартного ввода ребра (пары целых чисел в интервале от 0 до V- 1) с целочисленными пропускными способностями. Считайте, что верхняя граница пропускной способности M не превосходит 220.
22.7. Добавьте в решение упражнения 22.6, возможность присваивать вершинам символические имена, а не номера (см. программу 17.10).
22.8. Найдите в интернете крупную транспортную сеть, которую можно использовать для тестирования алгоритмов вычисления потоков. Это могут быть сети перевозки материалов (автомобильные, железнодорожные, авиа), сети связи (телефонные или компьютерные сети передачи данных) или распределительные сети. Если пропускные способности не известны, продумайте подходящую модель для их добавления. Напишите программу, использующую интерфейс программы 22.2 для реализации транспортных сетей с вашими данными – возможно, на основе решения упражнения 22.7. При необходимости разработайте дополнительные приватные функции для очистки данных (см. упражнения 17.33-17.35).
22.9. Напишите генератор случайных разреженных сетей с пропускными способностями от 0 до 220, взяв за основу программу 17.7. Воспользуйтесь отдельным классом для пропускных способностей и разработайте две реализации, одна из которых генерирует равномерно распределенные пропускные способности, а другая – нормально распределенные. Разработайте клиентские программы, которые генерируют случайные сети для обоих типов распределений весов с подобранными значениями V и E, чтобы использовать их для выполнения эмпирических тестов на графах, полученных из различных распределений весов ребер.
22.10. Напишите генератор случайных насыщенных сетей с пропускными способностями от 0 до 220, взяв за основу программу 17.8 и генераторы пропускных способностей ребер из упражнения 22.9. Напишите клиентские программы генерации случайных сетей для обоих распределений весов с подобранными значениями V и E, чтобы использовать их для выполнения эмпирических тестов на графах, полученных из этих моделей.
22.11. Напишите программу, которая генерирует на плоскости V случайных точек, затем строит транспортную сеть с (двунаправленными) ребрами, соединяющими все пары точек, расположенных на расстоянии не более d одна от другой (см. программу 3.20), и устанавливает пропускную способность каждого ребра с помощью одной из случайных моделей, описанных в упражнении 22.9. Определите, как выбрать d, чтобы ожидаемое количество ребер было равно E.
22.12. Добавьте в программу 22.1 проверку, что величина потока каждого ребра не больше его пропускной способности.
22.13. Найти все максимальные потоки в сети, показанной на
рис.
22.11. Приведите представление циклами для каждого из них.
22.14. Напишите функцию, которая считывает величины потоков и циклы (по одному в строке, в формате, представленном на
рис.
22.8) и строит сеть с соответствующим потоком.
22.15. Напишите клиентскую функцию, которая находит представление циклами для потока сети, используя метод, описанный в доказательстве леммы 22.2, и выводит величины потоков и циклы (по одному в строке, в формате, представленном на
рис.
22.8).
22.16. Напишите функцию, которая удаляет циклы из st-потока сети.
22.17. Напишите программу, которая назначает целочисленные потоки каждому ребру в любом заданном орграфе без истоков и стоков, чтобы получилась транспортная сеть, представляющая собой циркуляцию.
22.18. Пусть поток представляет собой товары, которые перевозят на грузовых машинах между городами, при этом под потоком в ребре понимается количество товара, которое нужно доставить из города u в город v в течение дня. Напишите клиентскую функцию, которая выводит график работы для водителей грузовиков: где и сколько погрузить и где и сколько разгрузить. Считайте, что количество грузовиков неограничено, и распределительные пункты не начинают отгрузку, пока не получат весь товар.
1. Объектом работы информационной логистики является информационный поток.
Информационный поток — это совокупность циркулирующих внутри логистической системы, между нею и внешней средой сообщений, необходимых для управления и контроля логистических операций.
Организация информационных потоков — дорогостоящее дело. На их формирование, передачу, прием, хранение, анализ расходуются большие средства.
Информационные потоки протекают в информационном пространстве. Оно обширно и практически охватывает весь земной шар и освоенную часть космоса. Использование этого пространства — дело не простое, оно требует межгосударственных решений по использованию коммуникаций связи на территории каждой страны — транспортных магистралей (железнодорожных, водных, воздушных), средств космической связи, телеграфных и радиорелейных линий и др. Использование названных коммуникаций (например, доставка почты во Францию через территорию Литвы, Польши и Германии) — дорогостоящее дело.
Создание и поддержание в надлежащем состоянии материально-технической базы, обеспечивающей движение информационных потоков, — капиталоемкий и длительный процесс.
Сообщения. составляющие информационные потоки. выполняются на разных носителях.
В логистике выделяют следующие виды информационных потоков в зависимости:
• горизонтальный (информационные потоки, охватывающие сообщения между партнерами по хозяйственным связям одного уровня управления: предприятиями-поставщиками и предприятиями-потребителями материальных ресурсов либо между ними и их посредниками по процессу обращения товаров);
• вертикальный (информационные потоки, охватывающие сообщения, поступающие сверху, из руководящих инстанций в подведомственные им звенья логистической системы: из корпорации холдинга в дочерние предприятия и т. д.);
• внешний (информационные потоки, протекающие в среде, внешней по отношению к логистической системе. Так, горизонтальные информационные потоки сообщений от предприятий — партнеров (других логистических систем) выступают внешними по отношению к тому партнеру, которому они направлены и который их получит);
• внутренний (информационные потоки — сообщения, циркулирующие внутри одной логистической системы (предприятия, оптовой базы и др.). Для логистических подсистем внутренними являются потоки сообщений внутри подсистемы, остальные сообщения для ник внешние);
• входной (информационные потоки представляют собой сообщения, входящие в логистическую систему либо в одну из ее подсистем);
• выходной (информационные потоки — сообщения, выходящие за пределы одной логистической системы либо одной из ее подсистем);
• срочные (соответствующая пометка “срочная” указывается на носителе информации и служит указателем срочности сообщения);
• очень срочные — “молнии” (соответствующая пометка “срочная”, “молния” указывается на носителе информации и служит указателем срочности сообщения);
• содержащие коммерческую тайну (направляются с грифом пометкой о секретности документа);
• содержащие государственную тайну (аналогично). Благодаря этому удается ограничить доступ к такого рода документам и предотвратить утечку важной информации;
• заказные (принимаются с регистрацией, с выдачей отправителю квитанции об их приемке, вручаются адресату под роспись. За своевременность их доставки организации связи ведут контроль полнее, чем простых сообщений);
• ценные (имеют цену компенсации, которую в случае их утери организации связи уплачивают подателю сообщения);
• традиционные (почтовые сообщения);
• быстрые (факсимильная связь, электронная почта, телеграф, телетайп, телефон);
Важную роль среди информационных потоков играют сообщения документального характера, которые оформляются чаще всего на бумажных носителях определенной формы, заполненных в установленном порядке и заверенных подписями и печатью отправителя сообщения. Такие сообщения называются документальными.
2 Информационный поток характеризуется такими показателями. как:
Информационные потоки характеризуют с помощью следующих оценок.
Источники возникновения сообщений могут быть различными от участников логистических цепей и смежных с ними организаций, сообщения которых влияют на перемещение, организацию и приемку потоков. Таковы сообщения, например, паводковой комиссии об аварии моста и его разрушении, сделавшие невозможным проезд по нему и требующие движения по иному маршруту.
По направлению информационные потоки могут быть горизонтальными (туда и обратно) и вертикальными (сверху вниз и обратно). Горизонтальными называют сообщения между участниками логистического процесса одного уровня — равноценными партнерами. Вертикальные информационные потоки протекают между разными уровнями управления: верхним— руководящим и нижним — подчиненным. Таковы, например, сообщения дирекции предприятия руководителям цехов и ответы на них.
Направление информационного потока трактуется и по другому: как прямое и косвенное. Прямое направление партнеру (руководителю) или другому адресату — для исполнения требований, имеющихся в сообщении. Косвенное направление информационного потока — направление копий сообщений для сведения, ознакомления с данным вопросом, без участия в его решении.
Есть и третий вариант определения понятия направление информационного потока— учет географического или территориального адресата его назначения: на Крайний Север, Дальний Восток, Украину и другие страны, либо область (край), город, населенный пункт назначения сообщения.
Объем информационных потоков учитывают несколькими способами. Один из них — учет размеров потока по числу: документов; листов в потоке; страниц в потоке; пачек документов. Этот способ применяют для определения объема больших информационных потоков.
Второй способ учета объема информационных потоков применяют для малых потоков. При нем объем потока определяют числом строк в документе — документо-строк или числом слов в сообщении — телеграммах.
Третий способ — учет числа знаков в сообщении — оценивается в компьютерных системах в особых единицах измерения для учета потребности в магнитных носителях, размещения в памяти ПЭВМ и в других случаях.
Периодичность информационных потоков характеризует частоту их формирования. В логистике многие информационные потоки — разовые, не повторяются и создаются один раз на каждый материальный поток, параллельно с ним, чуть ранее или чуть позже. Но некоторые информационные потоки в логистике оформляют один раз в месяц, ежеквартально и с другой частотой. Такова, например, отчетность по движению материальных ресурсов.
Информационные потоки документального характера проходят при оформлении определенную процедуру согласования. Так, плановые сообщения на предприятиях согласуют с руководителями цехов и членами дирекции предприятия. Для каждого документа обычно устанавливают определенные правила согласования его проектируемого содержания.
Каждое документальное сообщение информационного потока утверждается (подписывается) определенными лицами: генеральным директором, исполнительным директором, их заместителями и т. д. Без соответствующей подписи документ силы не имеет.
Некоторые документы имеют срок действия, за пределами которого они становятся недействительными. Таковы лицензии, квоты, право на место в транспортном средстве, некоторые уведомления о возможности заказа, праве на востребование похищенного груза и др. Такие документы можно использовать лишь в течение срока их действия.
Но большая часть информационных потоков к таким документам не относится и представляет собой уведомительные сообщения, необходимые для управления материальными потоками: раскрывает характеристику этих потоков и состояния их движения к заданному месту доставки.
Различен и порядок хранения сообщений, доставленных в информационных потоках. Некоторые сообщения собирают в отдельные пачки, другие хранят на магнитных носителях и в другой форме.
Срок хранения информации различен: один, два года, пять лет, постоянно (вечно) и др.
3. Управлять информационным потоком можно1.
4. Информационные потоки в логистике формируются в соответствии с материальными. Считается, что каждому материальному потоку соответствует информационный поток. Такое соответствие не всегда бывает изоморфным (полным).
Часто информационные и материальные потоки протекают в разных временных интервалах. Так, материальный поток может прибыть в заданное место, а документы на него сюда могут быть еще не доставлены. Тогда материальный поток считается неотфактурованными поставками, принимается получателем на ответственное хранение и лишь потом, после прибытия документов, проверяется соответствие прибывших материалов этим документам.
Может быть и наоборот: документы на груз прибыли на место назначения, а материальный поток находится еще в пути следования. Такие документы фиксируются как основание для учета “запасов в пути” и после прибытия груза сверяются с его составом и объемом.
Предпочтительнее вариант опережения информационных потоков по сравнению с движением материальных потоков. Это дает возможность лучше подготовиться к приему грузов. Фактически же информационные потоки имеют опережение далеко не всегда.
Информационные потоки должны быть адекватны материальным потокам в части характеристики этих потоков. Но такое соответствие есть не всегда: в ряде случаев оформляются документы, общие для нескольких потребителей-получателей, и тогда в них отражается информация, часть которой избыточна для каждого отдельного получателя данных ресурсов.
Направление потока данных
Как
упоминалось ранее и как показывает
стрелка на приведенном выше рисунке,
поток данных связывания может идти от
цели привязки к источнику привязки
(например, исходное значение изменяется,
когда пользователь изменяет значение
TextBox)
и/или от источника привязки к цели
привязки (например, содержимое TextBox
обновляется при изменениях в источнике
привязки), если источник привязки
предоставляет соответствующие
уведомления.
Возможно,
требуется, чтобы в приложении пользователи
могли изменить данные и передать их
обратно объекту источника.Или может
потребоваться не предоставлять
пользователям возможности обновления
источника данных.Это можно регулировать
с помощью свойства Mode
объекта Binding.На
следующем рисунке показаны различные
типы потоков данных:
- Связывание
OneWay
приводит к изменениям свойства источника
для автоматического обновления свойства
цели, но изменения свойства цели не
передаются обратно к свойству
источника.Этот тип привязки подходит,
если привязка элемента управления
неявно доступна только для чтения.Например,
можно привязаться к источнику, такому
как биржевые сводки, или, возможно,
свойство цели не имеет интерфейса для
внесения изменений, например цвета
фона привязанной к данным таблицы.Если
отсутствует необходимость отслеживать
изменения свойства цели, можно
использовать режим привязки OneWay,
при котором удастся избежать издержек
режима привязки TwoWay. - Тип
связывания TwoWay
вызывает изменения либо свойства цели,
либо свойства источника для автоматического
обновления другого.Этот тип привязки
подходит для изменяемых форм или других
полностью интерактивных скриптов
UI.Большинство свойств являются свойствами
по умолчанию для связывания OneWay,
но некоторые свойства зависимостей
(обычно свойства изменяемых пользователями
элементов управления, такие как свойство
Text
элемента TextBox
и свойство IsChecked
элемента CheckBox)
являются свойствами по умолчанию для
связывания TwoWay.Определить
программный способом, связано ли по
умолчанию свойство зависимостей
односторонним или двусторонним способом,
можно, получив метаданные свойства с
помощью GetMetadata,
а затем проверив логическое значение
свойства BindsTwoWayByDefault. - Связывание
OneWayToSource
является обратным к связыванию OneWay;
оно обновляет свойство источника при
изменении свойства цели.Одним примером
скрипта является пересчет значения
цели из UI. - На
рисунке не показана привязка OneTime,
которая вызывает инициализацию свойства
цели свойством источника, но последующие
изменения при этом не распространяются.Это
означает, что, если в контексте данных
производятся изменения или меняется
объект, это изменение не отражается в
целевом свойстве.Этот тип привязки
можно применять, если для использования
данных подходит снимок или данные
являются статическими.Этот тип привязки
также может использоваться, если
необходимо инициализировать целевое
свойство с некоторым значением из
исходного свойства, и контекст данных
не известен заранее.По существу, это
является простой формой связывания
OneWay,
которая обеспечивает лучшую
производительность в случаях, когда
значение цели не изменяется.
Обратите
внимание, что для обнаружения изменений
в источнике (применимо для связывания
OneWay
и TwoWay),
источник должен реализовывать подходящий
механизм уведомления об изменении
свойства, такой как INotifyPropertyChanged.Пример
реализации класса INotifyPropertyChanged
см. в разделе Практическое
руководство. Реализация уведомления
об изменении свойства.
На
странице свойства Mode
содержатся дополнительные сведения о
режимах привязки и пример того, как
указать направление привязки.
Соседние файлы в папке !
Глава 11. ИНФОРМАЦИОННАЯ ЛОГИСТИКА
В основе процесса управления материальными потоками лежит обработка информации, (информация (экономическая) — совокупность функционирующих в экономических объектах различных сведений (об общественных процессах производства, распределения, обмена и потребления материальных благ и услуг), которые можно фиксировать, передавать, преобразовывать и использовать для осуществления таких функций управления, как планирование, учет, экономический анализ, регулирование и др.) циркулирующей в логистических системах. В связи с этим одним из ключевых понятий логистики является понятие информационного потока.
Информационный поток — это совокупность циркулирующих в логистической системе, между логистической системой и внешней средой сообщений, необходимых для управления и контроля логистических операций. Информационный поток может существовать в виде бумажных и электронных документов.
В логистике выделяют следующие виды информационных потоков (рис. 48):
– в зависимости от вида связываемых потоком систем: горизонтальный и вертикальный;
– в зависимости от места прохождения: внешний и внутренний;
– в зависимости от направления по отношению к логистической системе: входной и выходной.
Рис. 48. Виды информационных потоков в логистике
Информационный поток может опережать материальный, следовать одновременно с ним или после него. При этом информационный поток может быть направлен как в одну сторону с материальным, так и в противоположную:
– опережающий информационный поток во встречном направлении содержит, как правило, сведения о заказе;
опережающий информационный поток в прямом направлении — это предварительные сообщения о предстоящем прибытии груза;
– одновременно с материальным потоком идет информация в прямом направлении о количественных и качественных параметрах материального потока;
– вслед за материальным потоком во встречном направлении может проходить информация о результатах приемки груза по количеству или по качеству, разнообразные претензии, подтверждения.
Путь, по которому движется информационный поток, в общем случае, может не совпадать с маршрутом движения материального потока.
Информационный поток характеризуется следующими показателями:
– источник возникновения;
– направление движения потока;
– скорость передачи и приема;
– интенсивность потока и др.
Формирование информационных систем (рассматриваемых в §§ 11.2-11.4), невозможно без исследования потоков в разрезе определенных показателей. Например, решить задачу оснащения определенного рабочего места вычислительной техникой невозможно без знания объемов информации, проходящей через это рабочее место, а также без определения необходимой скорости ее обработки.
Управлять информационным потоком можно следующим образом:
– изменяя направление потока;
– ограничивая скорость передачи до соответствующей скорости приема;
– ограничивая объем потока до величины пропускной способности отдельного узла или участка пути.
Измеряется информационный поток количеством обрабатываемой или передаваемой информации за единицу времени.
Способы измерения количества информации, содержащейся в каком-либо сообщении, изучаются в разделе кибернетики, который называется теорией информации. Согласно этой теории за единицу количества информации принята так называемая двоичная единица – бит. При использовании электронно-вычислительной техники информация измеряется байтами. Байт – это часть машинного слова, состоящая обычно из 8 бит и используемая как одно целое при обработке информации в ЭВМ.
Применяются также производные единицы количества информации: килобайт и мегабайт.
В практике хозяйственной деятельности информация может измеряться также:
– количеством обрабатываемых или передаваемых документов;
– суммарным количеством документострок в обрабатываемых или передаваемых документах.
Следует иметь в виду, что помимо логистических операций в экономических системах осуществляются и иные операции, так же сопровождающиеся возникновением и передачей потоков информации. Однако логистические информационные потоки составляют наиболее значимую часть совокупного потока информации.
Рассмотрим в качестве примера структуру совокупного информационного потока в крупном магазине продовольственных товаров. Основную часть общего объема обращающейся здесь информации (более 50% ), составляет информация, поступающая в магазин от поставщиков. Это, как правило, документы, сопровождающие поступающий в магазин товар, так называемые товарно-сопроводительные документы, которые в соответствии с вышеприведенными определениями образуют входящий информационный поток.
Логистические операции в магазине не ограничиваются получением товаров от поставщиков. Внутримагазинный торгово-технологический процесс также включает в себя многочисленные логистические операции, которые сопровождаются возникновением и передачей информации, используемой внутри магазина. При этом доля образованной информации, используемой внутри магазина, составляет приблизительно 20%.
В целом примерно 2/3 общего объема обрабатываемой в магазине информации может составлять информация, необходимая для управления и контроля логистических операций. На производственных предприятиях или предприятиях оптовой торговли доля логистических информационных потоков еще значительнее.
В дальнейшем вместо термина «логистический информационный поток» мы будем пользоваться термином «информацнонный поток», не забывая при этом о его логистическом содержании.
