Пусть I = 0 и U = S (U – последняя из вершин с неизменной меткой).

Пусть I = I + 1. Для каждой вершины V, кроме вершин с неизменной меткой:

M = min (L (V), L (U) + W (U, V)).

Если M < L (V), то L (V) = M и R (V) = U.

Среди всех вершин V, которые непомечены неизменной меткой, найти вершину W с наименьшей меткой (если таких вершин несколько, то можно взять любую и них). Положить P (W) = 1 и U = W.

Если I < N – 1, идти к пункту 3.

Все кратчайшие пути найдены. Метки вершин представляют собой длины кратчайших путей. V, R (V), R (R (V)), …, S есть вершины кратчайшего ориентированного S-V пути. (см. рис 3.11).

Рис 4. Реализация алгоритма Дейкстры для решения задач нахождения кратчайших путей и задачи построения маршрутов.

Расчеты Дейкстры дают сложность его алгоритма как O (N2) или даже O (N * log(N)), однако, расчеты Д. Б. Джонсона показали, что сложность алгоритма Дейкстры при некоторой модификации его (возможность отрицательных длин ребер графа) может достигать O (N3) а в худшем случае O (N * 2N).

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

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

Предложена схема реализации распределенной информационной системы. Также проведен анализ существующих технологий распределенной работы информационной системы. Была показана необходимость применения компонентной структуры распределенной информационной системы на основе архитектуры распределенного взаимодействия элементов (технология CORBA) (Рис 5).

Рис 5. Схема работы распределенной информационной системы.

Проведен анализ принципов обмена информацией, как между компонентами системы, так и для ввода и вывода данных, также выполнен анализ средств преобразования информации и форматов ее разметки для основных видов запросов пользователей информационной системы.

Анализ современных технологий представления данных показал, что в качестве формата передаваемых данных для вышеуказанных целей наилучшим является использование языка разметки XML, а для представления результатов работы в виде различных отчетов следует использовать язык преобразований XSLT (Рис. 6).

Рис. 6. Схема преобразования и передачи информации в системе.

Такими компонентами в данной реализации являются:

Сервера системы управления основной базой данных. На этих серверах находится главное хранилище информационной системы.

-Сервера системы управления дополнительными базами данных. На этих серверах находятся СУБД принимающие информацию и СУБД, хранящие конечные срезы планов и маршрутов.

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

Веб-сервера. Эти сервера обеспечивают обработку запросов пользователей и выдачу ответов на их запросы.

Описаны основные компоненты такой системы: Сервера системы управления основной базой данных. На этих серверах находится главное хранилище информационной системы: сервера системы управления дополнительными базами данных, а также сервера обработки и преобразования информации. Схема взаимодействия серверов реализации информационной системы «Поставки продукции» представлена на рис.7.

Для принятия решения была собрана информация о наиболее популярных системах управления базами данных и произведён сравнительный анализ технических характеристик рассматриваемых систем.

Проведен выбор комплекса технических средств и топологии локальной вычислительной сети предприятия.

Рис. 7. Схема данных хранилища.

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

Основные результаты работы

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

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

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

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

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

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

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

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

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

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

Предложена схема реализации распределенной информационной системы. Описаны основные компоненты такой системы: Сервера системы управления основной базой данных. На этих серверах находится главное хранилище информационной системы: сервера системы управления дополнительными базами данных, а также сервера обработки и преобразования информации.

Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения в ОАО «Асфальтобетонный завод №1» г. Москва, ЗАО НПВФ «СВАРКА» г. Чебоксары,. а также используются в учебном процессе в МАДИ(ТУ).

Основные положения и результаты диссертационной работы отражены в следующих публикациях: