Информационная логистика. Информационные потоки. Алгоритм Де Мукрона.

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

Основные понятия информационной логистики:

информационный поток;

информационная система;

информационная технология.

Основная задача информационной логистики заключается в доставке информации к системе управления предприятием и от нее. Информационная логистика выполняет функции:

собирает возникающую информацию;

анализирует информацию;

перемещает информацию;

накапливает и хранит информацию;

фильтрует поток информации (отбирает необходимые для того или иного уровня управления данные и документы);

объединяет и разъединяет информационные потоки;

выполняет элементарные информационные преобразования;

управляет информационным потоком.

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

Выделяют виды информационных потоков в зависимости от вида связываемых потоком систем:

горизонтальный

вертикальный

от места происхождения:

внешний

внутренний

он направления потока:

входной 

выходной

от значимости почтовых сообщений:

простые; заказные; ценные.

от скорости передачи:

традиционные (почта); быстрые (факс, эл.почта, телеграф, телефон...).

Информационные потоки в логистике формируются в соответствии с материальными. Но иногда материальный поток может прибыть в заданное место, а документы на него могут быть еще не доставлены. Такой материальный поток считается неотфактурованной поставкой, и принимается получателем на хранение до прибытия документов. Может быть и наоборот: документы прибывают на место назначения раньше самого груза.

Опережение информационным потоком материального предпочтительнее. Это дает возможность лучше подготовиться к приему грузов. Информационные потоки должны быть адекватны материальным потокам в части характеристики этих потоков.

Сущность алгоритма Де Мукрона.

Нам дан ориентированный граф.

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

Все остальные клетки считаются равными нулю.

Если граф не содержит петель, то его главная диагональ заполнена нулями.

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

Для этого используется метод разбиения множества N на слои – подмножества множества N, отвечающие условию:

Все вершины данного слоя имеют предков только в предыдущих слоях, или то же самое – все вершины данного слоя имеют потомков только в последующих слоях.

Разбиение на слои выполняется 2 способами :

- исключением предков;

- исключением потомков.

Рассмотрим второй способ.

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

Приведенный алгоритм формирует слои, начиная с последнего. Исключение предков формирует слои, начиная с первого.

Чтобы определить на первом шаге, какие вершины не имеют потомков, достаточно сложить единицы по строкам матрицы. Там где суммы равны 0 – потомков нет.

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

Алгоритм исключения предков аналогичен, но суммирование производится по столбцам матрицы.

Два этих подхода могут дать неодинаковые результаты.

После упорядочения вершин производится их перенумерация. От слоя к слою нумерация монотонно возрастает.

Пример.

Задан граф, размерностью n=10, k=18. Упорядочить его вершины и пронумеровать их.

Составим матрицу смежности вершин графа, размерностью 10х10, и дополним ее нужным кол-вом столбцов, содержащих суммы для реализации метода исключения потомков, и строк для метода исключения предков.

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