Логическое моделирование систем с последовательно-параллельной структурой тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Близнова, Ольга Владимировна

• Близнова, Ольга Владимировна
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Близнова, Ольга Владимировна

ВВЕДЕНИЕ.

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

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат технических наук Близнова, Ольга Владимировна, 2004 год

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. Доказательства теорем.