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

Введение

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

Оглавление

- Введение.

- Содержательное описание кзн.

- Основные определения.

- Стандартные методы решения задачи о назначениях.

- Эвристические алгоритмы.

- Модифицированные алгоритмы.

- Реализация алгоритма и численные эксперименты.

- Математическая модель решения задачи.

- Программная реализация алгоритма.

- Заключение.

- Список использованной литературы.

- Листинг программы венгерского алгоритма решения задачи о назначениях С.

Заключение

Рассмотрены стандартные и эвристические методы решения задачи о назначениях и квадратичной задачи о назначениях в постановке (1.1) Такие, как динамическое программирование, метод отсечения, метод ветвей и границ, локальные методы поиска и их улучшения, метод отжига и генетический алгоритм. Кроме того, представлено описание трех модифицированных методов решения квадратичной задачи о назначениях с использованием моделирования поведения муравьиных колоний, нейронных сетей и генетического алгоритма.

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

Список литературы

- Беллман Р. Динамическое программирование М.: ИЛ, 1960. 400 с.

- Лазарев, А.А. Теория расписаний. Задачи и алгоритмы: учебное пособие / А.А. Лазарев, Е.Р. Гафаров. Москва: Изд-во МГУ, 2011. 222 с.

- Загребаев, А.М. Методы математического программирования в задачах оптимизации сложных технических систем: учебное пособие / А.М. Загребаев, Н.А. Крицына, Ю.П. Кулябичев, Ю.Ю. Шумилов. М.: МИФИ, 2007. 332 с.

- Дроздов, С.Н. Комбинаторные задачи и элементы теории вычислительной сложности: учебное пособие / С.Н. Дроздов. Таганрог: Изд-во ТРТУ, 2000. 62с.

- Электронная энциклопедия Wiкiреdiа. Электрон. дан. Режим доступа.

- Кравец, О.Я. Обзор методов структурного синтеза для решения квадратичных задач о назначениях / О.Я. Кравец, А.П. Сафронова // Современная наука: Актуальные проблемы теории и практики: научно-практический журнал. Москва. 2013. 9/10: Сер. Естеств. и техн. науки. С.