Содержание к диссертации
Введение
1. Обзор работ по моделированию и оптимизации дискретных систем 11
1.1. Классификация моделей и методов решения задач дискретной оптимизации и
1.2. Характеристика методов математического программирования^
1.3. Описание метода исследования на графах 20
1.4. Описание метода ветвей и границ 30
1.5 Характеристика статистического моделирования 39
1.6 Выводы и постановка задачи 47
2. Структурно-логический подход к анализу последовательно-параллельной системы 51
2.1. Краткая характеристика математического аппарата непрерывной логики и логических определителей 52
2.2. Описание интервального анализа 57
2.2.1. Краткое описание принципов сравнения и оптимизации интервальных величин 58
2.2.2. Характеристика интервальных логических определителей 62
2.3 Разработка формально-логической модели последовательно-параллельной системы обслуживания в задачах о назначениях 65
2.4 Анализ условий существования решения недетерминированной Трехиндексной задачи о назначениях 67
2.5. Выводы 69
3. Синтез плана работы последовательно - Параллельной системы 71
3.1 Синтез последовательно-параллельной системы методом ветвей И границ 71
3.2. Разработка метода оптимизации, основанного на вычислении логических определителей ; 77
3.3. Создание метода решения задачи в условиях интервальной Неопределенности $5
3.4. Конструктивный подход к построению приближенно-оптимального решения 89
3.5. Анализ алгоритма приближенной оптимизации 94
3.6. Выводы 98
4. Компьютерное моделирование последовательно- Параллельных систем 100
4.1. Процессы управления в транспортно-экспедиторской компании
4.2. Описание требований к системе моделирования 104
4.3. Реализация программного комплекса моделирования экологии транспортно экспедиторской компании 107
4.4. Характеристика режимов решения задач с помощью экспертной системы 112
4.5. Организация диалога с пользователем на ограниченном естественном языке 116
Заключение 120
Список литературы 122
Список приложений 134
- Описание метода исследования на графах
- Краткая характеристика математического аппарата непрерывной логики и логических определителей
- Разработка метода оптимизации, основанного на вычислении логических определителей
- Реализация программного комплекса моделирования экологии транспортно экспедиторской компании
Введение к работе
Задачи выбора некоторого оптимального варианта из конечного набора альтернатив являются важными как в теоретическом, так и прикладном значении. К их числу относятся так называемые многоиндексные, в том числе трехиндексные задачи о назначениях, которые до сих пор недостаточно глубоко исследованы. Они относятся к классу наиболее трудных с вычислительной точки зрения задач дискретной оптимизации, имеющих экспоненциальную (NP) вычислительную сложность (Емеличев В.А., Ковалев М.М., Кравцов М.М, (1981)). NP-полнота данных задач обусловливает поиск и разработку приближенных алгоритмов их решения.
Наиболее часто используемым для исследования этих задач о назначениях и разработки приближенных схем их решения является метод исследования на графах. Характерными являются работы Гимади Э.Х., Сердюкова А.И. (1999), Кайрана Н.М. (2000), Коркишко Н.М. (2003) и др., в которых алгоритмы решения разработаны для задач малой размерности.
В связи с этим актуальной является разработка новых методов решения трехиндексной задачи о назначениях. Для этого предлагается использовать подход, с последующим применением методов теории расписаний.
Теория расписаний представляет собой специальное направление прикладной математики, изучающее модели и методы организации комбинаторных вычислений для составления расписаний, т.е. распределения во времени ограниченных ресурсов, предназначенных для выполнения различных видов работ (операций, заданий, процессов, и т. д.) и построения оптимального расписания (плана) выполнения их заданной совокупности. Объектом изучения этой теории являются системы обслуживания, представляющие собой определенное множество блоков, объединенных некоторым множеством связей, предназначенные для выполнения заданной совокупности работ.
Одним из способов решения проблемы. оптимального расписания (плана), и связанной с ней большой размерности является применение структурно-логического метода исследования систем. Этот подход заключается в использовании математического аппарата непрерывной логики (НЛ) и логических определителей (ЛО) (своеобразных экстремальных числовых характеристик прямоугольных матриц). Это позволяет разработать эффективные полиномиальные алгоритмы невысокой степени, позволяющие заменять полный перебор всех вариантов частичными переборами меньших объемов и проводить оптимизационные исследования системы, т.е. осуществлять качественный анализ получаемых решений.
Общие положения и теоретические основы этого метода разработаны В.И. Левиным (1979) и получили развитие в работах А.Ф. Буланова (1981), С.А. Лысака (1983), И.Ю. Мирецкого (1987) и др. ученых. Особенность данного метода заключается в необходимости развития и доработки математического аппарата непрерывной логики и логических определителей для конкретного класса задач дискретной оптимизации. Применение структурно-логического метода исследования систем для разработки алгоритмов решения рассматриваемого в данной диссертационной работе класса задач осуществляется впервые.
Все это обусловливает актуальность диссертационной темы, выбор подхода к исследованию, а также определяет его цели и задачи.
Предметом исследования является проблема оптимизации работы последовательно-параллельной системы обслуживания. В терминах и представлениях трехиндексной задачи о назначениях подобная система описывается следующим образом. Последовательно-параллельная система обслуживания представляет собой N параллельно соединенных ветвей, , характеризующихся быстродействием, и способных выполнять одновременно N однотипных работ. Каждая ветвь предназначена для последовательного выполнения двух работ и представляет собой цепочку из последовательно соединенных блоков, предназначенных для выполнения операций, составляющих работу. Имеется 2N работ, характеризующихся издержками на их выполнение в ветвях системы. Необходимо выбрать оптимальный порядок подачи работ в ветви системы, минимизирующий общее время выполнения комплекса работ. При этом применяются следующие допущения: 1) абсолютная надежность всех блоков системы обслуживания; 2) для каждой работы задается множество составляющих ее операций, порядок выполнения которых предписывается некоторым заданным отношением порядка; 3) в любой момент времени каждый блок может выполнять не более одной операции; 4) первые N работ подаются в систему одновременно.
Целью работы создание адекватных математических моделей функционирования последовательно-параллельной системы обслуживания, сформулированной в виде трехиндексной задачи о назначениях как при детерминированных, так и при недетерминированных (интервальных) параметрах функционирования системы, исследование с помощью этих моделей задачи синтеза оптимальных и приближенно-оптимальных расписаний (планов), разработка эффективных приближенных алгоритмов решения задачи.
Для достижения этой цели необходимо решить следующие задачи:
• Развить математический аппарат непрерывной логики и логических определителей с учетом специфики рассматриваемого класса задач теории расписаний.
• Разработать приближенный метод оптимизации формальнологических моделей системы и применить его к построению эффективных приближенно оптимальных алгоритмов решения задачи произвольной размерности. Методы исследования. В работе использовались методы алгебры непрерывной логики и логических определителей, теории множеств, теории алгоритмов, исследования операций, в том числе теории расписаний, теории графов, статистического моделирования, математического программирования и комбинаторного анализа.
Достоверность и обоснованность научных положений и результатов исследований подтверждаются корректностью применения апробированного математического аппарата непрерывной логики и логических определителей, а также аппарата теории вероятностей, математической статистики и согласованностью результатов теоретических расчетов с данным, полученными экспериментальным путем автором и другими исследователями.
На защиту выносятся:
1. Формально-логические модели, которые представляют собой матричные структуры и позволяют адекватно описать функционирование последовательно-параллельных систем в терминах и представлениях трехиндексной задачи о назначениях.
2. Метод, основанный на непрерывной логике и логических определителях, который позволяет эффективно проводить оптимизационные исследования задачи как при детерминированных, так и при недетерминированных (интервальных) параметрах функционирования системы на основе единого подхода.
3. Условия существования решения недетерминированной трехиндексной задачи о назначениях, связанные с недетерминированностью параметров системы, а также структура множества всех решений рассматриваемой задачи с интервальной матрицей коэффициентов.
4. Методика оптимизационных исследований рассматриваемых систем как при детерминированных, так и при недетерминированных (интервальных) параметрах ее функционирования, основанная на анализе разработанных формально-логических моделей систем.
5. Эффективные алгоритмы получения приближенно оптимальных решений задачи произвольной размерности.
Научная новизна. В ходе выполнения работы получены следующие новые результаты:
1. Разработаны формально-логические модели функционирования последовательно-параллельной системы в терминах и представлениях трехиндексной задачи о назначениях как при детерминированных, так и при недетерминированных (интервальных) параметрах ее функционирования, позволяющие адекватно представлять заданную о системе информацию в компактной, обозримой форме, что важно для решения проблемы большой размерности при исследовании системы и разработки оптимизационных алгоритмов.
2. Сформулированы и исследованы связанные с недетерминированностыо условия существования задачи при интервальной неопределенности параметров функционирования системы.
3. Разработаны оригинальные аппарат и метод оптимизационных исследований рассматриваемой системы, основанные на анализе разработанных формально-логических моделей, позволяющие осуществлять качественный анализ решений при варьировании исходных данных.
4. Созданы эффективные алгоритмы синтеза приближенно оптимальных расписаний для задач произвольной размерности.
Практическая ценность. Использование предлагаемых методик и теоретических разработок расширяет круг решаемых оптимизационных задач. Полученные аналитические результаты позволяют строить легко реализуемые на ЭВМ эффективные алгоритмы получения приближенно-оптимальных решений трехиндексной задачи о назначениях как при детерминированных, так и при недетерминированных (интервальных) параметрах, которые могут использоваться, в частности, при создании оптимизационных модулей экспертных систем. Реализующая данные алгоритмы экспертная система моделирования экологии транспортно-экспедиторской компании используется в Пензенском областном Ці управлении инкассации, внедрена в учебный процесс Пензенской государственной сельскохозяйственной академии.
Апробация работы. Основные результаты диссертационной работы были доложены и обсуждены на 1-й Всероссийской конференции «Непрерывная логика и ее применение в технике, экономике и социологии» (Пенза, 22-23 сентября 1994); научно-практической конференции «Экологическая безопасность и социально-экономическое развитие регионов России» (Саранск, 14-16 декабря 1994); International Conference of S cienceand Technology «New Information Technologies and Systems» (Penza, Russia, 21-29 Dec. 19.94); Международной научно-технической конференции «Непрерывно-логические и нейронные сети и модели» (Ульяновск, 23-25 мая 1995); Международной научно-технической конференции «Непрерывно-логические методы и модели в науке, технике и экономике» (Пенза, 19-20 октября 1995); Всероссийской конференции «Информационные технологии и системы» (Воронеж, 16-19 октября 1995); научно-практическом семинаре «Экологическая безопасность регионов России» (Пенза, 25-26 апреля 1996); научно-практическом семинаре «Применение баз данных» (Пенза, 26-27 ноября 1997); Всероссийской научно-технической конференции «Непрерывная и смежная логики в информатике, экономике и социологии» (Пенза, 30-31 октября 1997); Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 22-23 ноября 2001); 16-й Международной научной конференции «Математические методы в технике и технологиях» (Ростов-на-Дону, 27-29 мая 2003); Международной конференции «Компьютерное моделирование и информационные технологии в науке, инженерии, образовании» (Пенза, 2003).
Публикации. По теме диссертации опубликованы 13 печатных работ, перечисленных в конце автореферата.
Структура работы. Диссертация общим объемом 141 страница состоит из введения, четырех глав, заключения и приложений, содержит 8 рисунков, 12 таблиц, список литературы из 119 наименований. Приложения содержат акты о внедрении и доказательства теорем.
Описание метода исследования на графах
Решение комбинаторных оптимизационных задач основывается на использовании, прежде всего, конечности множества G и специфики J решаемой задачи. Многие из задач этого типа могут быть сведены к задачам целочисленного программирования, однако такое сведение не гарантирует того. Что можно добиться существенного уменьшения сложности решения задачи. Скорее наоборот, задачу. Записанную в терминах целочисленного программирования, будет решить еще сложнее, так как она может иметь большую размерность и, кроме того, уже нельзя будет эффективно воспользоваться ее комбинаторными свойствами. В теоретическом плане в [104] установлены достаточные условия сводимости комбинаторных оптимизационных задач к задачам ЦЛП, а }, а также показано, что не существует общего метода такого сведения.
Многие ученые подчеркивают важность комбинаторного V представления определенных классов дискретных оптимизационных задач. Комбинаторные модели могут быть применены для представления оптимизационных задач, возникающих при оптимальном размещении на графах. Рассмотрим задачу о взвешенном паросочетании [62], в которой задан граф G = (V,E) и каждому ребру [v,,v;Je сопоставимо число wfy 0, называемое весом ребра vj,v,-. Предлагается найти паросочетание в(?с наибольшей возможной суммой весов. Пападимитриу X., Стайглиц К. утверждают, что в данной формулировке задачи о взвешенном паросочетании можно убрать граф G, приняв соглашение, что этот граф всегда полный, и, полагая веса тех ребер, которых нет в графе G равными нулю. Кроме того, всегда можно считать, что число вершин четно - в противном случае можно добавить новую вершину и положить веса всех ребер, инцидентных этой вершине, равными нулю. Если рассматривается двудольный случай этой задачи, также можно считать, что граф представляет собой полный двудольный граф с двумя множествами вершин одинаковой мощности. Оптимальные решения J обязательно будут полными паросочетаниями (так как w 0 ),следовательно, можно формулировать эти задачи как задачи минимизации, { v рассматривая стоимости Сц = W - w , где W больше, чем все w .
Задача о взвешенном паросочетании в двудольном графе известна еще и как задача о назначениях, поскольку ее можно применять для вычисления наилучшего назначения работ рабочим в предположении, что известна величина TV«, производимая і-м рабочим при выполнении j-й работы. Задачу о назначениях можно описать как упрощенную задачу линейного программирования, являющуюся частным случаем задачи Хичкока, и поэтому ее можно решать, используя прямо-двойственный метод, называемый в этом случае венгерским методом.
Линейная задача о назначениях. Имеется п должностей и и исполнителей, причем задана «цена» Сц назначения /-го исполнителя на j-ю должность (і,7=1,...,и). Каждый исполнитель назначается на одну из должностей
При получении временной оценки алгоритма отмечаем, что возможно не более п +1 этапов, так как каждый этап, за исключением последнего, увеличивает паросочетание на одно ребро. Для анализа каждого этапа необходимо рассмотреть сложность поиска и модификации двойственных переменных по отдельности. Поиск осуществляется за 0{п ) операций, поскольку никакая вершина не включается в очередь второй раз на одном и том же этапе и удаление вершины из Q - множества вершин, обходится в 0{п) операций. С другой стороны, при каждой модификации двойственных переменных либо помечается новая вершина v є V, либо производится увеличение, после чего этап заканчивается. Поэтому на каждом этапе возможно самое большее п модификаций двойственных переменных. Каждая модификация требует 0{п) операций.
Следовательно, каждый этап требует 0{п ) операций, следовательно, венгерский алгоритм Г.Куна корректно решает задачу о назначениях для полного двудольного графа с 2п вершинами, используя 0(п ) арифметических операций. В отличие от двухиндексного случая трехиндексная задача о назначениях NP-трудна [26].
Гимади и Сердюков [18] предлагают для решения задачи (1.3.4)..(1.3.5) приближенный алгоритм с временной V сложностью От I. Алгоритм основан на таком согласованном преобразовании подстановок п и (У, которое почти всегда (с вероятностью, стремящейся к 1 при я- со) приводит их (а также подстановку я у) к одноциклическому виду (выполняется требование одноцикличности для каждой из трех подстановок где Рп - множество одноциклических подстановок степени и).
Для отыскания исходной подстановки с используется точный алгоритм решения задачи о назначении на специально сформированной квадратной матрице порядка п. Данный алгоритм не применим для случая числа индексов, большего трех.
В [17] предлагается алгоритм, который всегда строит допустимое решение задачи и имеет существенно меньшую временную сложность. Гимади и Коркишко утверждают, что идею этого алгоритма можно, в принципе, применить и для большего числа индексов. Данные авторы утверждают, что трехиндексная задача о назначениях на одноциклических подстановках степени п разрешима (т.е. для нее существуют подстановки
Для отыскания одноциклической подстановки у используется не точный, а приближенный метод, основанный на выборе минимального элемента в текущей строке с учетом дополнительного требования одноцикличности подстановки
Краткая характеристика математического аппарата непрерывной логики и логических определителей
Множество всех булевых функций, рассматриваемых совместно с Д) операциями конъюнкции и дизъюнкции и отрицания, называется булевой алгеброй. Сфера действия булевой алгебры ограничена лишь изучением "V" процессов, принимающих два значения. Левин [29] построил аналог булевой алгебры, для чего обобщил двузначные логические операции (2.1.1 - 2.1.3) на случай, когда и переменные исходные величины, и результат операции принимают значения из бесконечного (непрерывного) множества и перешел от двузначной к непрерывной логике (НЛ).
Для того, чтобы получить нужное обобщение, отметим, что операция (2.1.1) означает выбор меньшего из двух двоичных чисел, операция (2.1.2) - выбор большего из этих чисел, а операция (2.1.3) - замену имеющегося числа на симметричное с ним относительно середины отрезка [ОД]. Итак, если С = [А, В] - некоторый замкнутый и ограниченный интервал множества всех вещественных чисел. Этот интервал образует непрерывное (бесконечное) множество чисел. Середине этого интервала соответствует точка Определение 2.2. Функцией НЛ называется произвольная функция, которая 1) совместно со своими аргументами принимает значения из множества С = [Л,Б]; 2) может выражаться через свои аргументы формулой в виде суперпозиции операций дизъюнкции, конъюнкции и отрицания НЛ и, возможно, обычных алгебраических операций. Множество всех функций НЛ, рассматриваемых совместно с операциями дизъюнкции, конъюнкции и отрицания НЛ (и, возможно, обычными алгебраическими операциями) называется алгеброй НЛ. Назовем распределяющей суммой сумму элементов матрицы С, удовлетворяющих ограничению: любые слагаемые суммы имеют различные первые индексы і, различные вторые индексы j и различные третьи индексы к. Другими словами, в сумму входит ровно по одному элементу из каждого аксиального сечения матрицы, определяемого уравнениями і - const, j = const,к = const. Такие суммы будем обозначать
Вычисление логического определителя, т.е. отыскание его численного значения по заданным числовым значениям его элементов осуществляется путем прямого перебора всех сумм. Понятие вычисления ЛО в широком смысле включает также отыскание поэлементного состава минимальной
Оптимизация систем с детерминированными параметрами с математической точки зрения, если иметь в виду характеристики систем типа функций, параметры которых являются детерминированными и постоянными величинами есть отыскание экстремумов этих функций. На практике в большинстве случаев приходится иметь дело с системами с не полностью определенными параметрами. Происходит это по следующим причинам: 1. Многим реальным процессам свойственна неопределенность; 2. Параметры большинства систем задаются неточно из-за погрешности вычислений или измерений; 3. Часто возникает необходимость исследования целого семейства однотипных систем, различающихся лишь значениями параметров; 4. Некоторые системы имеют параметры, изменяющиеся во времени. Оптимизация таких систем с математической точки зрения есть отыскание экстремумов функций, параметры которых — недетерминированные величины
Случайные, нечеткие, интервальные и.т.д. Такая оптимизация значительно сложнее традиционной детерминированной, т.к. для нее необходимо [38]: 1. Обобщение понятия экстремума функции; 2. Выяснение условий существования экстремума, связанных с недетерминированностью параметров функций; 3. Разработка специальных методов поиска экстремума таких функций. Методически целесообразно, чтобы оптимизация в условиях неопределенности строилась на базе детерминистской оптимизации с постоянными параметрами путем введения необходимых корректировок.
В работе [38] предлагается общий подход к решению таких задач, базирующийся на непрерывной логике и интервальном анализе [3] и позволяющий сводить задачу с интервальными параметрами к двум аналогичным задачам с детерминированными (точными) параметрами. Этот подход оказался эффективным при исследовании двухоперационных и трехоперационных последовательных систем, параллельных систем, а также другим задачам оптимизации с недетерминированными параметрами [38 - 40], позволив выявить в них случаи существования оптимальных решений и указав простые правила нахождения этих решений.
Выбор неопределенности интервального типа обусловлен тем, что интервальные оценки неизвестных параметров оптимизируемых систем являются наиболее простыми и доступными для получения
Разработка метода оптимизации, основанного на вычислении логических определителей
В соответствии и разработанной в главе 2 формально-логической модели параллельно-последовательной системы, ассоциированной с трехиндексной задачей о назначениях, решение задачи при детерминированных параметрах по критерию минимума сводится к вычислению логического определителя (2.1.21). Логические определители (2.1.21), (2.1.22) для высокоразмерной матрицы С невозможно вычислить непосредственно по определению, т.е. перебором. Поэтому возникает необходимость разложения логических определителей. Рассмотрим ЛО СА с размерами матрицы С (3x3x3). Изобразим матрицу С с помощью аксиальных сечений j = \,j = 2,j — 3:
Выражение в каждой квадратурной (3.2.2) является логическим определителем, матрица которого получена их матрицы задачи удалением трех плоских сечений j = у,,i = il,k = kl, где г,,j\,к{ - координаты элемента сі\пк\ " слагаемого перед рассматриваемой квадратурной скобкой. Например, если имеем первое слагаемое с123, то к нему в квадратурных скобках прибавляется ЛО, матрица которого получена из матрицы Определение 3.1, Логическим дополнением Q элемента c!rs называется логический определитель, матрица которого получается из матрицы задачи удалением сечений і = l,j = г,к =s, на пересечении которых находится элемент cIrs. В этих обозначениях формула (3.2.2) принимает вид:Теорема 3.1. Трехиндексный логический определитель задачи о назначениях может быть разложен по элементам аксиального сечения j = const в виде
Данная теорема показывает, что оптимальное по эффективности распределение т заданий первого типа и р заданий второго типа между п исполнителями есть наилучшее среди п распределений, у-е из которых получается прикреплением некоторого і-то задания первого типа и к-то задания второго типа к j -му исполнителю и оптимальным распределением оставшихся m -1 заданий первого типа и р — \ заданий второго типа между всеми п исполнителями с учетом того, что /-1 исполнитель уже загружен двумя заданиями (работой, состоящей из двух операций).
Аналогично [45] целесообразно использовать разложение (3.2.4) повторно, разлагая на следующем шаге логические дополнения С к и т.д., пока не получится выражение, содержащее достаточно простые определители небольших размеров, которые можно вычислить перебором. Производя в (3.2.4) последовательное разложение логических дополнений получаем структурно-логический алгоритм вычислений в трехмерной задаче о назначениях:
При оценке сложности вычислений по формуле (3.2.4), с учетом того, что матрица логического дополнения С к, имеющая размеры элементарных операций при вычислении по формуле (3.2.4) меньше числа п элементарных операций при вычислении по формуле (3.2.1) в — раз.
Общее число миноров г-го порядка при фиксированном наборе Jг и при всевозможных различных наборах сечений /,. и Кг равно Crm Сr. Пусть далее Dfj к означает логический определитель, имеющий матрицу, полученную из матрицы С = с,-д удалением наборов аксиальных сечений IriJr,Kr. Имеет место следующая теорема.
Таким образом, логическое построение решения трехиндексной задачи о назначениях по формулам (3.2.4), (3.2.5), (3,2.7), основанное на применении аппарата НЛ и ЛО позволяет сокращать число операций в алгоритме поиска оптимального решения. При этом прослеживается обозримость процедуры поиска; используемые приемы наиболее эффективны при рассмотрении высокоразмерных дискретных систем с последовательно-параллельной структурой.
Вследствие того, что понятие вычисления логического определителя включает не только вычисление минимальной распределяющей суммы (нахождения длины кратчайшего пути из корня в вершину в дереве последовательного разложения Л О), а также отыскание ее поэлементного состава, то есть идентификацию этого пути по составу входящих в него вершин-элементов, .использование данного метода позволяет проводить оптимизационные исследования системы, т.е осуществлять качественный анализ решений при варьировании исходных данных.
Реализация программного комплекса моделирования экологии транспортно экспедиторской компании
Программный комплекс экспертной системы моделирования экологии транспортно-экредиторской компании предназначен для ввода, хранения и анализа первичной, бухгалтерской и статистической информации компании. Главной целью создания системы является обеспечение принятия решений в соответствии с современными экологическими требованиями с целью минимизации суммарного экологического ущерба, наносимого деятельностью компании, а также обеспечения целостности взаимосвязи между различными подразделениями компании для повышения информированности (в том числе и об экологическом ущербе, наносимом ежедневной деятельностью компании), уменьшения трудозатрат на обработку заказов, в конечном итоге обеспечивающем более качественное управление транспортно-экспедиторской компанией и совершенствование ее структуры.
Каждое подразделение транспортно-экспедиторской компании является модулем, который принимает входящую и посылает исходящую информацию. При этом входящая информация подвергается обработке в зависимости от задач конкретного подразделения. По своему характеру вся информация подразделяется на руководящую и извещающею. Руководящая информация содержит в себе указание к действию, которое необходимо выполнить, а извещающая - несет в себе данные о совершенных действиях или наступающих событиях. Применительно к деятельности транспортно-экспедиторской : компании руководящей информацией можно считать заказ от клиента на перевозку или складское хранение или указание составить определенный отчет (например, указание на составление экологического паспорта компании), а извещающей — выполнение по поступившему указанию отчет или подготовленный пакет первичных документов, подлежащих дальнейшей обработке (например, сведения о выбросах ЗВ от подвижных источников за определенный период или на перспективу).
Каждое подразделение сообразно выполняемым задачам способно воспринимать строго определенный набор входящих запросов, выполняя при этом требуемые запросом действия. В результате работы подразделения формируется также строго определенный поток исходящей информации, которая необходима для функционирования других служб компании. Таким образом, формируется замкнутая целостная структура, обеспечивающая успешное выполнение производственного цикла. Основным условием нормальной работы этой структуры транспортно-экспедиторской компании в целом является четкая регламентация действий каждого подразделения и своевременное выполнение всех запросов и предопределенных задач. Функции регламентации деятельности конкретных модулей (настройку системы под предприятие) осуществляет администратор системы. При этом настройка производится с учетом имеющихся модулей системы, то есть в зависимости от конкретного набора рабочих мест, выбранного клиентом.
Исходя из целей и задач ЭС МЭТЭК была сформирована структура знаний системы, выбран способ их представления и определена общая структурная схема системы (рисунок 4.2). Транспортно-экспедиторская компания объединяет множество транспортных средств, относящихся к нескольким типам и сериям. Каждое транспортное средство определенного типа и серии характеризуется весом груза, перевозимого за один рейс, временем, необходимым для этой перевозки, и временем, необходимым для подготовки транспортного средства к перевозке очередного вида груза, а также расстоянием до пункта назначения. Транспортные средства требуется направить по ряду возможных направлений с целью выполнения заказов на перевозки двух видов: т заказов на перевозки товаров от производителя на склад и р заказов на перевозки со склада до потребителя. Каждый заказ характеризуется jX , количеством груза, которое требуется перевезти и экологическими издержками на осуществление данной перевозки, которые зависят от "д- категории транспортных средств, структуры парка по грузоподъемности, типа двигателя транспортного средства, используемого топлива, коэффициента загрузки, организации контроля содержания вредных веществ в отработанных газах, периодов года. Периоды года (теплый, переходный, холодный) определяются по величине среднемесячной температуры.
Расчет экологических издержек основан на использовании удельных показателей, т.е. выбросов загрязняющих веществ, приведенных к единице времени, оборудования, массы получаемой продукции или расходуемых материалов. Удельные показатели выделения загрязняющих веществ от различных производственных участков ТЭК основаны на результатах исследований и натурных наблюдений, проводимых различными научно-исследовательскими и проектными организациями, вследствие этого могут иметь вид замкнутых интервалов. При расчете выбросов загрязняющих веществ от подвижных источников учитываются удельные выбросы вредных веществ при і - . прогреве двигателя, при работе двигателя на холостом ходу, пробеговые выбросыВ соответствии и разработанной в главе 2 формально-логической модели параллельно-последовательной системы, ассоциированной с трехиндексной задачей о назначениях, решение задачи при детерминированных параметрах по критерию минимума сводится к вычислению логического определителя (2.1.21). Логические определители (2.1.21), (2.1.22) для высокоразмерной матрицы С невозможно вычислить непосредственно по определению, т.е. перебором. Поэтому возникает необходимость разложения логических определителей. Рассмотрим ЛО СА с размерами матрицы С (3x3x3). Изобразим матрицу С с помощью аксиальных сечений j = \,j = 2,j — 3: Выражение в каждой квадратурной (3.2.2) является логическим определителем, матрица которого получена их матрицы задачи удалением трех плоских сечений j = у,,i = il,k = kl, где г,,j\,к{ - координаты элемента сі\пк\ " слагаемого перед рассматриваемой квадратурной скобкой. Например, если имеем первое слагаемое с123, то к нему в квадратурных скобках прибавляется ЛО, матрица которого получена из матрицы Определение 3.1, Логическим дополнением Q элемента c!rs называется логический определитель, матрица которого получается из матрицы задачи удалением сечений і = l,j = г,к =s, на пересечении которых находится элемент cIrs. В этих обозначениях формула (3.2.2) принимает вид:Теорема 3.1. Трехиндексный логический определитель задачи о назначениях может быть разложен по элементам аксиального сечения j = const в виде
