Метод сетевого программирования в задачах управления строительным производством

• Автор: Аснина, Наталия Георгиевна
• Шифр специальности: 05.13.10
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Воронеж
• Количество страниц: 126 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

1. МЕТОДЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ.

1.1 Постановка злдлч дискретного программирования

1.2 Методы решения задач дискретного программирования

Методы отсечения.

Комбинаторные методы.

. Метод ветвей и границ.

1.3 Методы математического программирования.

Метод двойственных оценок

Адаптивный метод.

Алгоритм Удзавы
1.4 Генетические алгоритмы
1.5 Метод дихотомического программирования
1.6 Метод сетевого программирования.
1.7 Выводы
2. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ НА ГРАФАХ.
2.1 Основные понятия
2.2 Задача определения циркуляции максимальной величины.
2.3 Задача о минимальном разрезе
2.4 Задача о минимальном разрезе
2.5 Задача о максимальном независимом множестве.
3. ЗАДАЧА О МАКСИМАЛЬНОЙ ЗАГРУЗКЕ.
3.1. Постановка задачи о максимальной загрузке
3.2 Алгоритм в задаче о камнях
3.3 Обобщение метода на случай различных объемов групп
3.4 Априорные оценки
3.5 Непрерывный вариант задачи о загрузке оборудования
4. ФОРМИРОВАНИЕ ОПТИМАЛЬНОЙ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ ПРОЕКТНОСТРОИТЕЛЬНОГО ПРЕДПРИЯТИЯ
4.1 Распределение единиц проектирования между структурными подразделениями
4.2 Определения работ для передачи на субподряд
4.3 Другие критерии распределения работ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Алгоритмы решения задач о максимальной загрузке и о максимальном независимом множестве на основе метода сетевого программирования. Алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования и способ определения априорных оценок для нее. Апробация работы. Международная школа-семинар «Современные проблемы механики и прикладной математики» (Воронеж, г. Орел, г. Математика. Экономика. Образование» (Ростов-на-Дону, г. Математика. Компьютер. Образование» (Москва-Пущино, г. Международная научно-практическая конференция «Теория активных систем» (Москва, г. Научно-техническая конференция «Современные сложные системы управления» (Воронеж, г. Публикации. По теме диссертации опубликовано 8 печатных работ. В работах [], [], [], [] автору принадлежат постановки задач, доказательство основных теорем и алгоритм, основанный на методе сетевого программирования. Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, приложений. Она содержит 3 страницы основного текста, рисунка, таблиц. В первой главе работы дан обзор известных методов решения задач дискретной оптимизации с целью определения круга задач, для решения которых метод сетевого программирования является наиболее предпочтительным. Предложен алгоритм решения задачи о циркуляции максимальной величины, основанный на преобразовании произвольного графа в агрегируемый. Доказана теорема двойственности для агрегируемых графов о совпадении величины максимальной циркуляции и минимальной пропускной размерности разреза. Разработан алгоритм решения задачи о максимальном независимом множестве на основе метода сетевого программирования. В третьей главе предложен алгоритм решения задачи о максимальной загрузке на основе метода сетевого программирования. Разработан алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования. Предложен способ определения априорных оценок для задачи о камнях. Задача обеспечения равномерной загрузки подразделений организации, выполняющих однотипные работы. Эта задача сведена к известной «задаче о камнях» с различными объемами групп, для решения которой ипоьзован метод сетевого программирования. Задача о передаче части работ на субподряд в случае перегрузки основных исполнителей. Задача решается методом динамического программирования. В последнее время дискретные оптимизационные задачи находят широкое применение в различных областях, где используются математические методы для анализа происходящих процессов. Дискретное программирование сформировалась как самостоятельная и важная часть математического программирования в конце -х годов. Еще около двадцати лет назад решение каждой серьезной задачи дискретного программирования было связано с большими трудностями; это решение во многом являлось искусством, хотя многие алгоритмы были уже разработаны. В настоящее время ситуация существенно изменилась. Это связано в основном с двумя обстоятельствами. Во-первых, на порядки увеличилась мощность вычислительной техники. Во-вторых, удалось понять тонкости вычислительной реализации комбинаторных методов и алгоритмов, связанных с особенностями решаемых задач. Тем не менее, трудности, связанные с перебором большого числа вариантов, сохраняются при любой мощности компьютера. В связи с этим, проблема разработки и использования новых методов решения задач дискретной оптимизации по-прежнему является весьма важной. Конечное множество допустимых решений, т. X <Ь1, 1 = 1. О, j = 1. Если п<п, то задача называется частично целочисленной, если П]=п -полностью целочисленной. Задача о ранце. Имеется п предметов, каждый из которых характеризуется стоимостью ^>0 и весом ^>0, ^1,2,,п . Имеется ранец, грузоподъемность которого равна Я>0 . Требуется положить в ранец набор предметов с максимальной суммарной стоимостью. Задача о коммивояжере. Пусть Р=(1,2,,п) - конечное множество точек, сц>0 -«расстояние» от точки до точки ], С=(Су)п*п - матрица «расстояний». Маршрут 2 коммивояжера- это любая перестановка точек из Р , 7=0',, 2, . Пусть 2- множество всех маршрутов.