автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Логическое моделирование систем с последовательно-параллельной структурой

На правах рукописи

БЛИЗНОВА Ольга Владимировна

ЛОГИЧЕСКОЕ МОДЕЛИРОВАНИЕ СИСТЕМ С ПОСЛЕДОВАТЕЛЬНО-ПАРАЛЛЕЛЬНОЙ СТРУКТУРОЙ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Саратов 2004

Работа выполнена в Саратовском государственном техническом университете

Научный руководитель: кандидат технических наук, доцент

Большаков Александр Афанасьевич

Официальные оппоненты: доктор технических наук, профессор

Кушников Вадим Алексеевич

доктор физико-математических наук, профессор

Ушаков Николай Михайлович

Ведущая организация: Институт проблем точной механики

и управления РАН, г. Саратов

Защита состоится 13 апреля 2004 г. в 15 часов 00 минут на заседании диссертационного совета Д 212.242.08 при Саратовском государственном техническом университете (410054, г. Саратов, ул. Политехническая, 77, корп. 2, ауд. 322).

С диссертацией можно ознакомиться в научно-технической библиотеке Саратовского государственного технического университета.

Автореферат разослан «12» марта 2004 г. Ученый секретарь

диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задачи выбора оптимального варианта из конечного набора альтернатив являются важными как в теоретическом,, так и в прикладном значении. К их числу относятся так называемые многоиндексные, в том числе трехиндексные задачи о назначениях, которые до сих пор недостаточно глубоко исследованы. Они принадлежат к классу наиболее трудных с вычислительной точки зрения задач дискретной оптимизации, имеющих экспоненциальную (NP) вычислительную сложность (Емеличев В.А., Ковалев М.М., Кравцов М . М , (1981)). NP-полнота данных задач обусловливает необходимость поиска и разработки приближенных алгоритмов их решения.

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

A.И. Сердюкова (1999), Н.М. Кайрана (2000), Н.М. Коркишко (2003) и др., в которых алгоритмы решения разработаны для задач малой размерности.

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

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

Общие положения и теоретические основы этого метода разработаны

B.И. Левиным (1979) и получили развитие в работах А.Ф. Буланова (1981),

C.А. Лысаха (1983), И.Ю. Мирецкого (1987) и других ученых. Особенность данного метода заключается в необходимости развития и доработки математического аппарата непрерывной логики и логических определителей для конкретного класса задач дискретной оптимизации. Применение структурно-логического метода исследования систем для разработки алгоритмов решения рассматриваемого в данной диссертационной работе класса задач

выражает большую благодарность за плодотворное сотрудничество и научные консультации проф. Левину В.И.

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

Предметом исследования является проблема оптимизации работы последовательно-параллельной системы обслуживания. В терминах и представлениях трехиндексной задачи о назначениях подобная система описывается следующим образом. Последовательно-параллельная система обслуживания представляет собой N параллельно соединенных ветвей, характеризующихся быстродействием, и способных выполнять одновременно N однотипных работ. Каждая ветвь предназначена для последовательного выполнения двух работ и представляет собой цепочку из последовательно соединенных блоков, которые осуществляют операции, составляющие работу. Имеется 2N работ, характеризующихся издержками на их выполнение в ветвях системы. Необходимо выбрать оптимальный порядок подачи работ в ветви системы, минимизирующий общее время выполнения комплекса работ. При этом применяются следующие допущения: 1) абсолютная надежность всех блоков системы обслуживания; 2) для каждой работы задается множество составляющих ее операций, порядок выполнения которых предписывается некоторым заданным отношением порядка; 3) в любой момент времени, каждый блок может выполнять не более одной операции; 4) первые N работ подаются в систему одновременно.

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

Для достижения этой цели необходимо решить следующие задачи.

• Развить математический аппарат непрерывной логики и логических определителей с учетом специфики рассматриваемого класса задач теории расписаний.

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

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

расписаний, теории графов, статистического моделирования, математического программирования и комбинаторного анализа.

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

На защиту выносятся:

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

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

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

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

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

Научная новизна. В ходе выполнения работы получены следующие новые результаты:

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

2. Сформулированы и исследованы связанные с недетерминированностью условия существования задачи при интервальной неопределенности параметров функционирования системы.

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

4. Созданы эффективные алгоритмы синтеза приближенно оптимальных расписаний для задач произвольной размерности.

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

Апробация работы. Основные результаты диссертационной работы были доложены и обсуждены на Всероссийских, международных научно-технических, научно-практических конференциях и совещаниях «Непрерывная логика и ее применение в технике, экономике и социологии» (Пенза, 1994); «Экологическая безопасность и социально-экономическое развитие регионов России» (Саранск, 1994); «New Information Technologies and Systems» (Penza, Russia, 1994); «Непрерывно-логические и нейронные сети и модели» (Ульяновск, 1995); «Непрерывно-логические методы и модели в науке, технике и экономике» (Пенза, 1995); «Информационные технологии и системы» (Воронеж, 1995); «Экологическая безопасность регионов России» (Пенза, 1996); «Применение баз данных» (Пенза, 1997); «Непрерывная и смежная логики в информатике, экономике и социологии» (Пенза, 1997); «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2001); «Математические -методы в технике и технологиях» (Ростов-на-Дону, 2003); «Компьютерное моделирование и информационные технологии в науке, инженерии, образовании» (Пенза, 2003).

Публикации. По теме диссертации опубликованы 13 печатных работ, перечисленных в конце автореферата.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

Анализ литературных данных позволил сформулировать цель и задачи исследования.

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

Рассматривается система обслуживания, состоящая из N параллельно соединенных ветвей, характеризующихся быстродействием и способных выполнять одновременно N однотипных работ. Каждая ветвь предназначена для последовательного выполнения двух работ и представляет собой цепочку из последовательно соединенных блоков, предназначенных для выполнения операций, составляющих работу. Необходимо выбрать оптимальный порядок подачи 2N работ, характеризующихся издержками на их выполнение, в ветви системы, минимизирующий общее время выполнения комплекса работ. При этом применяются следующие допущения: 1) абсолютная надежность всех блоков системы обслуживания; 2) для каждой работы задается множество составляющих ее операций, порядок выполнения которых предписывается некоторым заданным отношением порядка; 3) в любой момент времени каждый блок может выполнять не более одной операции; 4) первые N работ подаются в систему одновременно.

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

переменными :

Ьх V Ь2 V... V Ь„ — \/ Ъ( - тах(6,,Ь2Ь„) - дизъюнкция НЛ;

¿>! л Ь2 л... л Ьп = д ¿>, = тт{Ь{,Ь2,—,Ьп) - конъюнкция НЛ.

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

Для произвольной трехиндексной м а т р г С = | э д я т с я

следующие понятия.

Определение 1. Распределяющей суммой ^'с^ называется сумма

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

Определение 2. л -определителем трехиндексной матрицы С называется выражение вида

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

Имеется п исполнителей и две группы из п работ. Каждый исполнитель может выполнять любую пару работ по одной из каждой группы.

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

Обозначим Сцк издержки на выполнение у-м исполнителем ьй и к-и работ из 1-й и 2-й группы соответственно, тогда

ук

или £? = СЛ=Л =|с&а|Л.

ук

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

Сложность вычисления данного JЮ с помощью непосредственного перебора сумм имеет экспоненциальную оценку:

т\р\п

— 1.

(т-п)\(р-п)\

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

Дана трехиндексная матрица издержек С = [С],С2], где С^Цс)^! -

минимальная, а - максимальная детерми парованная

матрицы издержек, составленные из нижних и вер) РИХ границ замкнутых интервалов С^ = [р!^/^ > с2,уЛ: ]' в которых за лючены фактические значения издержек. Необходимо на множестве всех булевых матриц назначений , удовлетворяющих ограничениям

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

X •' Вх - с№ = "ИП сук

или й = СЛ В = лХ^,

Л

что сводится к вычислению интервального логического определителя.

Однако в связи с ограничениями на сравнимость интервальных величин, находящихся в отношении неравенства, т.е. требованием согласованности (Левин В.Щ1992)), решение данной задачи существует не всегда.

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

рассматриваемой \ ¿д | - трехиндексная матрица

назначений, являющаяся 1-м частным решением задачи í = 1,..., Р;

МСх и МСг - множества всех решений детерминированных задач с постоянными коэффициентами с матрицами издержек

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

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

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

Пусть

множество всех решений

с=[с„с2].

и

Определение 3. Логическим дополнением Сдо элемента С/„

называется трехиндексный логический определитель задачи, матрица которого получается из матрицы задачи удалением аксиальных сечений на пересечении которых находится элемент Теорема 4. л - определитель трехиндексной задачи о назначениях может быть разложен по элементам плоского сечения j = const в виде

Вычисление ЛО с использованием теоремы 4 требует т!р!(и-1)

ТУд/ =-—-----1- тр — 1 операций сравнения, что сокращает их

(т-п)\(р-п)\

число по сравнению с полным перебором в п1е раз.

Определение 4. Минором г-го порядка назовем логический определитель , матрица которого получена из матрицы задачи

выделением наборов аксиальных сечений 1Т,3Г, Кг (1 < г < л)

Пусть означает логический определитель, имеющий матрицу,

полученную из матрицы С = ||с^ | удалением наборов аксиальных сечений /г,Уг,/Гг. Имеет место следующая теорема.

Теорема 5. Логический определитель СА можно разложить по заданному фиксированному набору аксиальных сечений в.виде

Вычисление ЛО с использованием теоремы 5 обеспечивает обозримость процедуры поиска, однако имеет также экспоненциальную оценку сложности.

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

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

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

Алгоритм А приближенного решения трехиндексной задачи о назначениях, основанный на теореме 4, описывается формулой

СЛ +С.Г(2),2,*(2)Ч1)*С1) +С'И)А*тЧ|)1(2)¥(2) + ",+

где, например, - минимальный элемент 2-го аксиального

сечения (у = 2) определителя, полученного удалением из аксиальных сечений / = 5()) и / = кщ

При оценке временной сложности отыскания приближенного решения по этому алгоритму использовались количественные оценки зависимости «сложность задачи - размеры системы», согласно которым она равна

Вероятностный анализ точности решения проводился для решений задачи для случайных входов, определяемых множеством Мп матриц С = Цсдо| размера пхпх П, где элементы С- независимые случайные величины, выбираемые из отрезка , с одинаковой

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

увеличении размерности задачи.

Предполагаемая сложность отыскания оптимального решения

модифицированного алгоритма

NА. (л) = (и-1)л(л+1)/3

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

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

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

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

Одной из практических задач составления расписания движения транспортных средств на маршрутах является назначение заданных транспортных средств на определенные маршруты в соответствии с уже выбранными для них расписаниями.

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

В связи с этим предлагается следующая модель работы автотранспортного предприятия.

Даны N единиц автотранспортных средств, N заказов на перевозки.

Даны С1]к = £ с'ук - суммарные выбросы т загрязняющих веществ при

осуществлении одним автомобилем предполагаемой пары перевозок.

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

(\й1йт\й ] <,п\<,кй р)

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

1-го загрязняющего вещества при осуществлении одним автомобилем предполагаемой пары перевозок с'ук: ""

с'«/* = тпрогр] X Кр + т^ч X Ц] + Пщк + X ,

где ^„рогр/ - удельный выброс /-го загрязняющего вещества при прогреве двигателя автомобиля, г/мин; - время прогрева двигателя, мин; пробеговый выброс /-го загрязняющего вещества автомобиля с относительно постоянной скоростью, г/км; - предполагаемый

пробег при выполнении автомобилем заказов, км; Ю^д - удельный

выброс загрязняющего вещества при работе двигателя на холостом ходу, г/мин; - предполагаемое время работы на холостом ходу.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

1. Близнова О.В. Условия существования задачи интервальной оптимизации решения трехиндексной аксиальной задачи о назначениях// Компьютерное моделирование и информационные технологии в науке, инженерии и образовании: Сборник материалов Междунар. науч. конф. - Пенза, 2003. - С. 18-21.

2. Близнова О.В. Структурный алгоритм решения трехиндексной аксиальной задачи о назначениях// Компьютерное моделирование и информационные технологии в науке, инженерии и образованииг Сборник материалов Междунар. науч. конф.- Пенза, 2003. - С. 16-18.

3. Близнова О.В. Логическая модель принятия решений, в условиях интервальной неопределенности// Непрерывная и смежные логики в технике, экономике и социологии: Сборник материалов Междунар. науч.-техн. конф-Пенза, 1996. - С. 144.

4. Близнова О.В., Большаков А.А., Глазков В.П. Структурный подход к задаче моделирования работы транспортно-экспедиторской компании// Математические методы в технике и технологиях: Сборник трудов 16 Междунар. науч. конф. - Ростов-на-Дону, 2003. - Т.7 - С. 84-86.

5. Близнова О.В., Лягин И.А. Анкетирование пользователей-прикладников экспертных систем оценки результатов измерений. - М., 1995. - 1 1с. Деп. в ВИНИТИ ЮЛ 1.95, № 2992-В95.

6. Левин В.И., Близнова О.В. Объединение детерминированных экспертных оценок на основе априорной информации. - М., 1994. - 7 с. Деп. в ВИНИТИ 22.06.94, № 1547 - В94.

7. Левин В.И., Близнова О.В. Интервальный подход к оптимизации работы автотранспортного предприятия // Непрерывная и смежные логики в информатике, экономике и социологии: Сборник материалов Всерос. науч.-техн. конф. - Пенза, 1997. - С. - 85-86.

8. Левин В.И., Близнова О.В. Система управления планированием перевозок АТП в условиях экологического кризиса// Математические методы и информационные технологии в экономике, социологии и образовании: Сборник материалов Междунар. науч.-техн. конф. -Пенза,2001.-С. 141-142.

P-46J4

9. Лягин И.А., Близнова О.В. Модель предметной области экспертной системы оценки результатов измерений. - М., 1995. - 8 с. Деп. в ВИНИТИ 10.11.95, №2993-В95.

10.Лягин И.А., Близнова О.В. Формализация описания алгоритмов обработки данных - М., 1995. - 5 с. Деп. в ВИНИТИ 14.02.95, №425-В95.

11. Свидетельство об официальной регистрации программы для ЭВМ №2004610418 (Россия). Экспертная система моделирования экологии транспортно-экспедиторской компании / Большаков А.А., Близнова О.В., Левин В.И. Дата реп: 10 февраля 2004г.

12.Bliznova О., Levin V. Application of Priory Information in Knowledge Bases of Expert Systems// New Information Technologies and Systems (NITS' 94): Proceedings of Intern. Conf. of Science and Technology. -Penza, Russia, 1994. - P. 48.

13.Bliznova O., Tuzilov I. On Expert Systems for Simulation of Industrial Ecology// New Information Technologies and Systems (NITS' 94): Proceedings of Intern. Conf. of Science and Technology. - Penza, Russia, 1994. - P. 21-22.

Лицензия ИД № 06268 от 14.11.01

Подписано в печать 09.03.04 Формат 60x84 1/16

Бум.тип. Усл.-печ.л. 0,93(1,0) Уч.-изд. л. 0,9

Тираж 100 экз. Заказ 113 Бесплатно

Саратовский государственный технический университет 410054, г. Саратов, ул. Политехническая, 77 Копипринтер СГТУ, 410054, г. Саратов, ул. Политехническая, 77

ВВЕДЕНИЕ.

1. ОБЗОР РАБОТ ПО МОДЕЛИРОВАНИЮ И ОПТИМИЗАЦИИ ДИСКРЕТНЫХ СИСТЕМ.

1.1. Классификация моделей и методов решения задач дискретной оптимизации.

1.2. Характеристика методов математического программирования^ . 1.3. Описание метода исследования на графах.

1.4. Описание метода ветвей и границ.

1.5 Характеристика статистического моделирования.

1.6 Выводы и постановка задачи.

2. СТРУКТУРНО-ЛОГИЧЕСКИЙ ПОДХОД К АНАЛИЗУ ПОСЛЕДОВАТЕЛЬНО-ПАРАЛЛЕЛЬНОЙ СИСТЕМЫ.

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

2.2. Описание интервального анализа.

2.2.1. Краткое описание принципов сравнения и оптимизации интервальных величин.

2.2.2. Характеристика интервальных логических определителей.

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

2.4 Анализ условий существования решения недетерминированной трехиндексной задачи о назначениях.

2.5. Выводы.

3. СИНТЕЗ ПЛАНА РАБОТЫ ПОСЛЕДОВАТЕЛЬНО -ПАРАЛЛЕЛЬНОЙ СИСТЕМЫ.

3.1 Синтез последовательно-параллельной системы методом ветвей и границ.

3.2. Разработка метода оптимизации, основанного на вычислении логических определителей.

3.3. Создание метода решения задачи в условиях интервальной неопределенности.

3.4. Конструктивный подход к построению приближенно-оптимального решения.

3.5. Анализ алгоритма приближенной оптимизации.

3.6. Выводы.

4. КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ПОСЛЕДОВАТЕЛЬНО-ПАРАЛЛЕЛЬНЫХ СИСТЕМ.

4.1. Процессы управления в транспортно-экспедиторской компании

4.2. Описание требований к системе моделирования.

4.3. Реализация программного комплекса моделирования экологии транспортно-экспедиторской компании.

4.4. Характеристика режимов решения задач с помощью экспертной системы.

4.5. Организация диалога с пользователем на ограниченном естественном языке.

Актуальность темы. Задачи выбора некоторого оптимального варианта из конечного набора альтернатив являются важными как в теоретическом, так и прикладном значении. К их числу относятся так называемые многоиндексные, в том числе трехиндексные задачи о назначениях, которые до сих пор недостаточно глубоко исследованы. Они относятся к классу наиболее трудных с вычислительной точки зрения задач дискретной оптимизации, имеющих экспоненциальную (ИР) вычислительную сложность (Емеличев В.А., Ковалев М.М., Кравцов М.М, (1981)). ЫР-полнота данных задач обусловливает поиск и разработку приближенных алгоритмов их решения.

Наиболее часто используемым для исследования этих задач о назначениях и разработки приближенных схем их решения является метод исследования на графах. Характерными являются работы Гимади Э.Х., Сердюкова А.И. (1999), Кайрана Н.М. (2000), Коркишко Н.М. (2003) и др., в которых алгоритмы решения разработаны для задач малой размерности.

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

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

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

Общие положения и теоретические основы этого метода разработаны В.И. Левиным (1979) и получили развитие в работах А.Ф. Буланова (1981), С.А. Лысака (1983), И.Ю. Мирецкого (1987) и др. ученых. Особенность данного метода заключается в необходимости развития и доработки математического аппарата непрерывной логики и логических определителей для конкретного класса задач дискретной оптимизации. Применение структурно-логического метода исследования систем для разработки алгоритмов решения рассматриваемого в данной диссертационной работе класса задач осуществляется впервые.

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

Предметом исследования является проблема оптимизации работы последовательно-параллельной системы обслуживания. В терминах и представлениях трехиндексной задачи о назначениях подобная система описывается следующим образом. Последовательно-параллельная система обслуживания представляет собой N параллельно соединенных ветвей, , характеризующихся быстродействием, и способных выполнять одновременно N однотипных работ. Каждая ветвь предназначена для последовательного выполнения двух работ и представляет собой цепочку из последовательно соединенных блоков, предназначенных для выполнения операций, составляющих работу. Имеется 2 ТУ работ, характеризующихся издержками на их выполнение в ветвях системы. Необходимо выбрать оптимальный порядок подачи работ в ветви системы, минимизирующий общее время выполнения комплекса работ. При этом применяются следующие допущения: 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 cience and 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 наименований. Приложения содержат акты о внедрении и доказательства теорем.

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

В диссертации разработаны теоретические и практические вопросы оптимизации работы последовательно-параллельной системы { обслуживания терминах и представлениях трехиндексной задачи о ч назначениях.

1. Авен О.И., Ловецкий С.Е., Моисеенко Г.Е. Оптимизация транспортных потоков. М.: Наука, 1985. - 268 с.

2. Алексеев О.Г. Комплексное применение методов дискретнойf „оптимизации. М.: Наука, 1987. - 248 с.

3. Алефельд Г. Хальцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987. - 365 с.

4. Ахо А., Хопкорфт Дж. Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

5. Ахо А., Хопкорфт Дж. Ульман Дж. Структуры данных и алгоритмы. М.: Вильяме, 2000. - 468 с.

6. Беленький A.C., Левнер Е.В. Применение моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте // Автоматика и телемеханика, 1989. №1. С.3-77.

7. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 458 с.

8. Близнова О.В. Логическая модель принятия решений в условиях интервальной неопределенности // Непрерывная и смежные логики в технике, экономике и социологии: Материалы Межд. НТК. Пенза: ПДЗ, 1996.-С.144.

9. Близнова О.В. Структурный алгоритм решения трехиндексной задачи о назначениях // Компьютерное моделирование и информационные технологии в науке, инженерии и образовании: Сборник матер. Межд. научн. конф. Пенза, 2003. - С. 16-18.

10. Близнова О.В., Тужилов И.В. Проблема разработки экспертных систем моделирования экологии предприятий. М., 1994. - 4 с. Деп. в ВИНИТИ 22.06.94 № 1546 - В 94.

11. Близнова О.В., Лягин И. А. Анкетирование пользователей-прикладников экспертных систем оценки результатов измерений. М:., 1995. 5 с. Деп. в ВИНИТИ 10.11.95 № 2992-В95.

12. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль, 1995. 230 с.

13. Венгерова И.И., Финкельштейн Ю.Ю. К вопросу об эффективности метода ветвей и границ //Экономика и математические методы. 1975. Т. XI, №1. С.186-193.

14. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. -М.: Радио и связь, 1981. 328 с.

15. Гимади Э.Х., Коркишко Н.М. Об одном алгоритме решения трехиндексной аксиальной задачи о назначениях на одноциклических подстановках // Дискретный анализ и исследование операций, 2003. -Серия 1. Том 10, №2. С. 56-65.

16. Гимади Э.Х., Сердюков А.И. Аксиальные трехиндексные задачи о назначении и коммивояжера: быстрые приближенные алгоритиы и их вероятностный анализ // Изв. вузов. Математика, 1999. № 12. С.19-25.

17. Гончаров E.H. Математическая модель и метод решения двухуровневой задачи стандартизации // Модели и методы оптимизации Новосибирск: Институт математики СО РАН, 1994. - Т.28 - С. 77-90.

18. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.-М.: Мир, 1982.-416 с.

19. Жаке-Лагрез Э. Применение размытых отношений при оценке предпочтительности распределенных величин // Статистические модели и многокритериальные задачи принятия решений. М.: Статистика, 1979.- С. 168-183.

20. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. — М.: Лаборатория Базовых Знаний, 2002. 288 с.

21. Информационные технологии в транспортной логистике. Составитель А.К. Труханов. М.: КИА центр, 2000. 86 с.

22. Крисевич B.C., Кузьмин Л.А., Шиф A.M. и др. Экспертные системы для персональных компьютеров: методы, средства, реализации: Справ, пособие. Мн.: Выш. Шк., 1990. - 197 с.

23. Конвей Р.В., Маквелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.-360 с.

24. Коркишко Н.М. Трехиндексная аксиальная задача о назначениях на одноциклических подстановках на максимум. Новосибирск, 2003. 18 с.

25. Кочетов Ю.А. Задачи оптимального выбора состава систем технических средств при многоэтапном процессе выполнения работ. Новосибирск, 1987. С.48-58. (Препринт/АН СССР. Сиб. Отд-ние. Ин-т математики; №12)

26. Ларин P.M., Пяткин A.B. Двухуровневая задача о назначениях // Дискретный анализ и исследование операций, 2001. Серия 2, Т.8, №2, -С. 42-51.

27. Левин В.И. Структурно-логический метод комбинаторной оптимизации // Автоматика и вычислительная техника, 1979. №1. -С.45-52.

28. Левин В.И. Структурно-логический метод приближенной комбинаторной оптимизации в задачах распределения вычислительных мощностей // Автоматика и вычислительная техника, 1981. №6. -С.46-53.

29. Левин В.И. Логический метод оптимизации решения задач в вычислительных системах // Автоматика и вычислительная техника, 1982.-№3.-С.55-61.

30. Левин В.И. К планированию работы вычислительных систем. Математический аппарат // Автоматика и вычислительная техника, 1982.- №5. — С.52-58.

31. Левин В.И. Бесконечнозначная логика в задачах кибернетики. — М.: Радио и связь, 1982. 175 с.

32. Левин В.И. К планированию работы вычислительных систем. Анализ плана // Автоматика и вычислительная техника, 1983. №2. -С.64-72.

33. Левин В.И. К планированию работы вычислительных систем. Синтез плана // Автоматика и вычислительная техника, 1983. №3. - С.64 — 70.

34. Левин В.И. Структурно-логические методы исследования сложных систем с применением ЭВМ. М.: Наука, 1987. - 304 с.

35. Левин В.И. Непрерывная логика. Ее обобщения и применения. 1, 2 //автоматика и телемеханика, 1990. №8. - С.3-22 - и - №9. - С. 3-26.

36. Левин В.И. Дискретная оптимизация в условиях интервальной неопределенности // Автоматика и телемеханика, 1992. №7. - с.97-106.

37. Левин В.И. Антагонистические игры с интервальными параметрами // Кибернетика и системный анализ. 1999. №7. С. 100-121.

38. Левин В.И. Оптимизация расписаний в М стадийной системе с неопределенными временами обработки. 1, 2. // Автоматика и телемеханика, 2002. - №1. - с.116-124 - и - №2. - С. 129-136.

39. Левин В.И., Близнова О.В. Объединение детерминированных экспертных оценок на основе априорной информации. М: 1994. . — 7 е.- Деп. в ВИНИТИ 22.06.94, № 1547 - В94

40. Левин В.И., Близнова О.В. Управление процессом планирования перевозок АТП в условиях экологического кризиса // Применение баз данных: Сборник материалов НПС. — Пенза: ПДЗ, 1997. — С. 12-13.

41. Левин В.И., Близнова О.В. Интервальный подход к оптимизации работы автотранспортного предприятия // Непрерывная и смежные логики в информатике, экономике и социологии: Сборник материалов Всеросс. НТК. Пенза, ПДЗ, 1997. - С. - 85-86.

42. Левин В.И., Буланов А.Ф. Логический синтез алгоритма вычислений в пространственной задаче о назначениях. // Применение вычислительных методов в научно-технических исследованиях. -Пенза, 1981.-С. 67-74.

43. Левин В.И., Лысак С.А. Оптимизация порядка следования работ в системе с параллельно-последовательной обработкой // Вычислительная техника в автоматизированных системах контроля и управления. Пенза, 1984. - Вып. 14. - С. 34-37.

44. Левин В.И., Мирецкий И.Ю. Организация процесса обработки заданий в конвейерной вычислительной системе // Вопросы радиоэлектроники. Сер. ЭВТ., 1986. Вып. 8. - С.3-7.

45. Левин В.И., Мирецкий И.Ю. Моделирование и оптимизация работы производственной системы // Механизация и автоматизация производства, 1987. №10. - С. 35-36.

46. Левин Р., Дранг Д., Эделсон Б. Практическое введение в технологию искусственного интеллекта и экспертных систем. М. Финансы и статистика, 1991. - 239 с.

47. Луканин В.Н., Трофименко Ю.В. Промышленно-транспортная экология. М.: Высш. Шк., 2001.-273 с.

48. Луканин В.Н., Буслаев А.П., Яшина М.В. Автотранспортные потоки и окружающая среда 2. - М.: ИНФРАМ, 2001. - 646 с.

49. Лягин И.А., Близнова О.В. Модель предметной области экспертной системы оценки результатов измерений. М:., 1995. — 6 с. Деп. в ВИНИТИ 10.11.95 № 2993-В95.

50. Лягин И.А., Близнова О.В. Формализация описания алгоритмов обработки данных. М:., 1995.- 5 с. Деп. В ВИНИТИ 14.02.95 №425-В95.

51. Максимей И.В. Математическое моделирование больших систем. -Минск: Вышэйшая школа, 1985. 120 с.

52. Марселус Д. Программирование экспертных систем на Турбо-Прологе: Пер. с англ. / М.: Финансы и статистика, 1994. 256 с.

53. Методика определения массы выбросов загрязняющих веществ автотранспортными средствами в атмосферный воздух. М.: НИИАТ, НИИКТП, МАДИ, НИЦИАМТ, 1993.

54. Методика проведения инвентаризации выбросов загрязняющих веществ в атмосферу для автотранспортных предприятий (расчетным методом). М. НИИАТ, 1991.

55. Мирецкий И.Ю. Оценивание возможностей повышения производительности конвейерной вычислительной системы // Вопросы радиоэлектроники. Сер. ЭВТ, 1990. Вып. 9. - С.34-39.

56. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. М.: Наука, 1986. —240 с.

57. Нечеткие множества и теория возможностей. Последние достижения: Пер. с англ. / Под ред. Р.Р.Ягера. М.: Радио и связь, 1986. -408 с.

58. Павлова Е.И. Экология транспорта. М.: Транспорт, 2000. - 248 с.

59. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 510 с.

60. Подчасова Т.П., Португал В.М., Татаров В.А., Шкурба В.В. Эвристические методы календарного планирования. Киев: Техника, 1980.- 140 с.

61. Португал В.М., Писаренко В.М. Экспериментальное исследование алгоритмов случайного поиска для задач календарного планирования // Вопросы разработки территориальных автоматизированных систем управления: Сб. научн. трудов . Кемерово, 1984. - С. 8-12.

62. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.-352 с.

63. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. М.: Мир, 1973. — 304 с.

64. Сергиенко И.В. Математическое модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1985. - 384 с.

65. Стаханов В.Н., Украинцев В.Б. Теоретические основы логистики. Ростов н/Д: «Феникс», 2001. 160 с.

66. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.-280 с.

67. Трубин В.А., Шарифов Ф.А. Простейшая многоэтапная задача размещения на древовидной сети // Кибернетика и системный анализ, 1992. №6. С.128-135.

68. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. - 234 с.

69. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения // Кибернетический сборник. — М.: Мир, Вып. 9.-С. 202-218.

70. Хохлюк В.И. Задачи целочисленной оптимизации. Новосибирск: Новосибирск, ун-т, 1979. - 92 с.

71. Свидетельство об официальной регистрации программы для ЭВМ № 2004610418 (Россия). Экспертная система моделирования экологии транспортно-экспедиторской компании / Большаков А.А., Близнова О.В., Левин В.И. // дата per: 10 февраля 2004г.

72. Adams W.P., and Johnson Т. Improved Linear Programming-based Lower Bounds for the Generalized Assignment Problem. DIMACS Series in Discrete Mathematics and Theoretical Сотр. Science, vol. 16, 1994. Pp. 43-76.

73. Adams W.P. and Sherali H.D. A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems // Management Science, Vol.32, № 10, 1986.- Pp. 1274-1290.

74. Assard A.A. and Xu W. On Lower Bounds for Class of Quadratic 0,1 Programs // Operation Research Letters, vol.4. 1985. Pp.175-180.

75. Azar Y., Naor J. and Rom R. The Competitiveness of On-line Assignment. In Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, 1995. Pp.203-210.

76. Bazaraa M.S. and Kirca, O. A Branch-and-Bound-Based Heuristics for Solving the Generalized Assignment Problem // Naval Research Logistics Quaterly/ vol. 30, № 1, 1983. Pp 287-304.

77. Bellman R. Dynamic Programming. Princeton: Princeton University Press, 1957. - 348 p.

78. Bliznova O., Levin V. Application of Priory Information in Knowledge Bases of Expert Systems // New Information Technologies and Systems (NITS' 94). Proceedings of Intern. Conf. of Science and Technology: Penza, Russia, 1994. P. 48.

79. Bliznova O., Tuzilov I. On Expert Systems for Simulation of Industrial Ecology // New Information Technologies and Systems (NITS' 94). Proceedings of Intern. Conf. of Science and Technology: Penza, Russia, 1994. -P. 21-22.

80. Borodin A. and El-Yanin R. Online Computation and Competitive Analysis/ Cambridge University Press, 1998. 134 p.

81. Borodin A., Nielsen M.N. and Rackoff D. Priority Algorithms. In Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002. Pp. 752-761.

82. Broder A.Z., Frieze A., Lund C. Phillips S. and Reingold N. Balanced Allocations for Tree-like Inputs //Information Processing Letters, №55 (6) 1995.- P. 329-332.

83. Burkard R.E. Locations with Spatial Interactions: The Generalized Assignment Problem // Discrete Location Theory, 1991. P. 387-437.

84. Burkard R.E., and Bonniger T. A Heuristic for Quadratic Boolean Programs with Applications to Quadratic Assignment Problems // European Journal of Operation research, Vol.13, 1983. P. 374-386.

85. Burkard R.E. and Stratmann K.H. Numerical Investigations on Generalized Assignment Problems // Naval Research Logistical Quarterly, vol. 25, № 16 1978. P. 129-148.

86. Carraresi P. and Malucelli F. A New Lower Bound for the Quadratic Assignment Problem // Operation Research, Vol. 40, 1992. P.22-27.

87. Clausen J., and Perregaard M., Solving large Quadratic Assignment Problems in Parallel. DIKU, Dept. of Computer Science, University of Copenhagen, June 30, 1995. P. 134-147.

88. Edmonds J. Matching and a Polyhedron with 0-1 Vertices // J. Res. NBS, 69B, 1965.- P. 125-130.

89. Frieze A.M., and Yadegar J. On the Generalized Assignment Problem // Discrete Applied Mathematics, vol. 5, № 1,1983. P. 89-98.

90. Frumkin M.A., Gens G.V., Hemelevskii J.I., Levner E.V. On Computational Complexity of Optimization Combinatorial Problems. IV Workshop on Combinatorial Optimization // Report №80159. Bonn. University of Bonn, 1980. - 32 p.

91. Gomory R.E. Outline of an Algorithm for Integer Solution to Linear Programs // Bui. Amer. Math. Soc. V.64, № 5, 1958. P. 275-278.

92. Grant T.L. An Evaluation and Analysis of the Resolvent Eequence Method for Solving the Generalized Assignment Problem. Master's Thesis, University of Pennsylvania, 1989.- P. 489-501.

93. Gutin G., Punnen A.P. (Eds.) The Traveling Salesman Problem and its j,. Variations. Dordrecht; Boston; London: Kluwer Acad. Publ., 2002. — 218 p/

94. Hadley S., Rendl F., and Wolkowicz H. Bounds for the Quadratic Assignment Problem Using Continuous Optimization Techniques // Integer Programming and Combinatorial Optimization, University of Waterloo Press, 1990.- P. 237-248.

95. House R.W., Nelson L.D. and Rado T. Computer studies of a certain Class of linear Integer Programs // recent advances in Optimization Techniques, ed. by A. Lavi and T.P. Vogl, New York: John Wiley and Sons, 1965.-340 p.

96. Johnson T.A. New Linear Programming-Based solution Procedures for the Generalized assignment problem. Ph. D. Dissertation, Clemson University, Clemson, SC. 1992.

97. Itaraki I. Integer Programming Formulation of Combinatorial Optimization Problems. Discrete Math., 1976, V.16, №1. P.39-52.

98. Kaku, B.K., Thompson, G.L. An Exact Algorithm for the General Assignment Problem // European Journal of Operation Research, vol. 23, №3, 1986. P. 382-390.

99. Karisch S.E. and Rendl F. Lower Bounds for the Generalized assignment Problem via Triangle Decomposition // Mathematical Programming, Vol 71, №2, 1995. P. 137-152.

100. Kohler W.H., Stieglitz K. Characterization and Theoretical Comparison of1. V

101. Branch-and-Bound Algorithms for Permutation Problems // J. of the ACM. -1974. V.21, №1. - P. 140-156.

102. Koopmans T.C. and Beckmann M.J. Assignment Problems and the Location of Economic Activities // Econometrica, vol. 25, 1957. P. 53-76.

103. Kuhn H.W. The Hungarian Method for the Assignment Problem // Naval Research Logistics Quarterly, №2, 1955. P. 83-97.

104. Lawler E.L. The Cubic Assignment Problem // Management Science, vol. 9, 1963. P. 586-599.

105. Lawler E.L. Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart & Winston, 1976. 260 p.

106. Lenstra J.K., Shimoys D.B. and Tardos E. Approximation Algorithms for Scheduling unrelated P arallel M achines. M ath. Prog., 46, 1 990. P . 2 59271.

107. Li Y., Pardalos P. and Resende M. A Greedy Randomized Adaptive Search Procedure for the cubic assignment Problem, DIMACS Series in Discrete Mathematics and Theoretical comp. Science, vol. 16, 1994. P. 237263.

108. Li Y., Pardalos P., Ramakrishnan K.G., Resende M.G. Lower Bounds for the Quadratic Assignment Problem // Annals of Operation Research, vol. 50, 1994. P. 387-410.

109. Little J.D., M urty K .G. S weeney D.W., Karel C. A n A lgorithm for t he Traveling Salesman problem // Oper. Res. V.l 1,№6, 1963/ P. 972-989.

110. Munkeres M. Algorithms for the Assignment and Transportation Problems // Journal of the Society for Industrial and Applied Mathematics, vol. 5,№ i, 1957. p. 32-38.

111. Nugent C.E., Vollman T.E. and Ruml J. An Experimental Comparison of Techniques for the Assignment of Facilities to Locations // Operations Research, vol. 16, 1968.- P.150-173.

112. Papadimitriou C.H., Yannakakis M. The Complexity of Restricted Spanning Tree Problems // Automata, Languages and Programming, ed. H.A. Maurer. Berlin: Springer-Verlag, 1979. 98 p.

113. Resende M.G.C., Ramakrishnan K.G. and Drezner Z. Computing Lower Bounds for the Generalized assignment Problem with an Interior Point

114. Algirithm for Linear Programming // Operation research, vol.43. Pp. 781791.

115. Roucairol C. A Reduction Method for cubic assignment Problems // Operations research Verfahren. Vol.32. P. 183-187.

116. Shimoys D. and Tardos, E. An Approximation Algorithm for the Generalized Assignment Problem. Mathematical Programming A., 1993. -№62-P.461-474.

117. Szwarc W. Permutation Flow-Shop Theory Revizited // Nav. Res. Log. Quart. 1978. - V. 25, № 3, - P. 557 -570.

118. Tcha D., Lee B. A Brunch-and- Bound Algorithm for the Multi-level Uncapacitated Facility Location Problem // European J. Oper. Res. 1984. -V.18, №1. P. 35-43.1. СПИСОК ПРИЛОЖЕНИИ1. ЙЕ

119. Акты о внедрении результатов диссертационной работы.2. Доказательства теорем.