Помощь в учёбе, очень быстро...
Работаем вместе до победы

Логическое моделирование систем с последовательно-параллельной структурой

Диссертация: Логическое моделирование систем с последовательно-параллельной структурой
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • 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 &bdquo-оптимизации. М.: Наука, 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. Свидетельство об официальной регистрации программы для ЭВМ № 2 004 610 418 (Россия). Экспертная система моделирования экологии транспортно-экспедиторской компании / Большаков А. А., Близнова О. В., Левин В. И. // дата 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 № 80 159. 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. 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 59 271.
  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. 237 263.
  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. 781 791.
  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. Акты о внедрении результатов диссертационной работы.2. Доказательства теорем.
Заполнить форму текущей работой

Пора сдавать?