Содержание к диссертации
Введение
1. Методы дискретной оптимизации 9
1.1 Постановка задач дискретного программирования 9
1.2 Методы решения задач дискретного программирования . 11
Методы отсечения
Комбинаторные методы 12
\Метод ветвей играниц
1.3 Методы математического программирования 19
Метод двойственных оценок 20
Адаптивный метод 24
Алгоритм Удзавы 29
1.4 Генетические алгоритмы 34
1.5 Метод дихотомического программирования 39
1.6 Метод сетевого программирования 42
1.7 Выводы 43
2. Оптимизационные задачи на графах 46
2.1 Основные понятия 46
2.2 Задача определения циркуляции максимальной величины 48
2.3 Задача о минимальном разрезе 61
2.4 Задача о минимальном разрезе 73
2.5 Задача о максимальном независимом множестве 80
3. Задача о максимальной загрузке 85
3.1. Постановка задачи о максимальной загрузке 85
3.2 Алгоритм в задаче о камнях 87
3.3 Обобщение метода на случай различных объемов групп 91
3.4 Априорные оценки 95
3.5 Непрерывный вариант задачи о загрузке оборудования 98
4. Формирование оптимальной производственной программы проектно-строительного предприятия 106
4.1 Распределение единиц проектирования между структурными подразделениями 106
4.2 Определения работ для передачи на субподряд 111
4.3 Другие критерии распределения работ 113
Заключение 116
Литература 117
Приложения 124
- Методы решения задач дискретного программирования
- Задача определения циркуляции максимальной величины
- Алгоритм в задаче о камнях
- Определения работ для передачи на субподряд
Введение к работе
Актуальность темы. Проблема совершенствования развития строительного производства заставила расширить исследования в области разработки и внедрения новых форм управления. Под строительством понимается процесс возведения зданий и сооружений - объектов строительства. Возведение объекта связано с выполнением следующих работ:
проведение различных видов инженерных изысканий, а также технико-экономического обоснования на возведение объекта;
разработка проектно-сметной документации (архитектурное проектирование, конструкторское проектирование, проектирование организации строительства на различных стадиях возведения объекта);
работа предприятий строительной индустрии и промышленности строительных материалов и последующая комплектация объекта;
собственно возведение объекта ( строительно -монтажные работы, монтаж оборудования, опытная эксплуатация).
Задачи управления строительным производством включают в себя задачи применения новых прогрессивных технологий производства проектных работ, а так же методов управления строительным производством.
Сказанное выше определяет актуальность темы диссертационного исследования, посвященного разработке новых алгоритмов решения задач дискретной оптимизации в управлении строительным производством- на основе метода сетевого программирования.
Цель и постановка задач исследования. Целью диссертации является разработка эффективных методов решения ряда прикладных задач дискретной оптимизации, применяемых для решения проблем в управлении строительным производством. Достижение поставленной цели потребовало решения следующих задач:
Провести анализ известных методов решения задач дискретной оптимизации с целью определения круга задач, для решения которых метод сетевого программирования является наиболее предпочтительным.
Поставить ряд прикладных задач, моделируемых при помощи графов:
задача о циркуляции максимальной величины;
задача о разрезе минимальной пропускной способности;
задача о максимальном независимом множестве.
Разработать алгоритмы решения поставленных задач на основе метода сетевого программирования.
Поставить задачу о загрузке оборудования, как задачу о камнях с различными объемами групп.
Разработать алгоритм решения поставленной задачи на основе метода сетевого программирования.
Разработать методику определения априорных оценок целевой функции дискретной задачи на основе сведения ее к непрерывной и разработать алгоритм решения непрерывной задачи.
7 Применить разработанные методы к решению практических задач.
Методы исследования: В диссертации используются методы
исследования операция, теории графов, теории активных систем, дискретной оптимизации.
Научная новизна роботы состоит в следующем:
Введено понятие агрегируемого графа и доказано, что агрегируемый граф допускает сетевое представление вида дерева.
Предложен алгоритм решения задачи о циркуляции максимальной величины, основанный на преобразовании произвольного графа в агрегируемый.
Доказана теорема двойственности для агрегируемых графов о совпадении величины максимальной циркуляции и минимальной пропускной размерности разреза.
Предложен алгоритм решения задачи о максимальной загрузке на основе метода сетевого программирования.
Разработан алгоритм решения задачи о максимальном независимом множестве на основе метода сетевого программирования.
Разработан алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования.
Предложен способ определения априорных оценок для задачи о камнях.
Разработан эффективный метод решения соответствующей непрерывной задачи на основе декомпозиции системы ограничений.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами. Они подтверждены расчетами на примерах, производственными экспериментами и многократной проверкой при внедрении в практику управления.
Практическая значимость работы и результаты внедрения. Практическая значимость состоит в том, что разработанные методы позволяют повысить эффективность решения широкого класса прикладных задач. Внедрение ряда алгоритмов при планировании проектных работ и оптимизации управления строительными проектами подтверждает высокую прикладную значимость работы.
Разработанные алгоритмы и модели на практике используются в работе предприятия ООО УК «Жилпроект» и 000 «Агрокс-2».
Модели и алгоритмы, разработанные в диссертационной работе, включены в состав учебных курсов и дисциплин: «Теория экономических и информационных систем», «Теория систем и системный анализ», «Оптимизационные задачи в экономике», читаемых в Воронежском государственном архитектурно - строительном университете.
На защиту выносится: Алгоритм решения задачи о циркуляции максимальной величины, основанный на преобразовании произвольного графа в агрегируемый.
Доказательство теоремы двойственности для агрегируемых графов о совпадении величины максимальной циркуляции и минимальной пропускной размерности разреза.
Алгоритмы решения задач о максимальной загрузке и о максимальном независимом множестве на основе метода сетевого программирования.
Алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования и способ определения априорных оценок для нее.
Апробация работы. Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях, симпозиумах и научных совещаниях в 2004-2005 гг, в том числе
Международная школа-семинар «Современные проблемы механики и прикладной математики» (Воронеж, 2004г.)
27-я международная школа семинар «Системное моделирование социально-экономических процессов» (Орел, 2004г.)
13-я международная конференция «Математика. Экономика. Образование» (Ростов-на-Дону, 2005г.)
12-я международная конференция «Математика. Компьютер. Образование» (Москва-Пущино, 2005г.)
Международная научно-практическая конференция «Теория активных систем» (Москва, 2005г.);
Научно-техническая конференция «Современные сложные системы управления» (Воронеж, 2005 г.);
Публикации. По теме диссертации опубликовано 8 печатных работ.
Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: В работе [54] автору принадлежат: математическая модель и вывод достаточного условия совместности системы линейных уравнений
дубльтранспортного типа. В работах [55], [56] автору принадлежат математические модели различных задач, сводящихся к задачам дубльтранспортного типа, а также алгоритмы, основанные на идее декомпозиции. В работах [57], [58], [61], [62] автору принадлежат постановки задач, доказательство основных теорем и алгоритм, основанный на методе сетевого программирования.
Объем и структура работы. Диссертация состоит из введения, четырех
глав, заключения, списка литературы, приложений. Она содержит 123 страницы
основного текста, 52 рисунка, 35 таблиц. Библиография включает 63
наименования
В первой главе работы дан обзор известных методов решения задач дискретной оптимизации с целью определения круга задач, для решения которых метод сетевого программирования является наиболее предпочтительным.
Во второй главе введено понятие агрегируемого графа и доказано, что
агрегируемый граф допускает сетевое представление вида дерева. Предложен
алгоритм решения задачи о циркуляции максимальной величины, основанный
на преобразовании произвольного графа в агрегируемый. Доказана теорема
двойственности для агрегируемых графов о совпадении величины
максимальной циркуляции и минимальной пропускной размерности разреза.
Разработан алгоритм решения задачи о максимальном независимом множестве
на основе метода сетевого программирования.
В третьей главе предложен алгоритм решения задачи о максимальной
загрузке на основе метода сетевого программирования. Разработан алгоритм
решения задачи о камнях с различными объемами групп на основе метода
сетевого программирования. Предложен способ определения априорных
оценок для задачи о камнях. Разработан эффективный метод решения
соответствующей непрерывной задачи на основе декомпозиции системы
ограничений
В четвертой главе решаются практические задачи формирования оптимальной производственной программы проектно - строительного предприятия:
Задача обеспечения равномерной загрузки подразделений организации, выполняющих однотипные работы. Эта задача сведена к известной «задаче о камнях» с различными объемами групп, для решения которой ипоьзован метод сетевого программирования.
Задача о передаче части работ на субподряд в случае перегрузки основных исполнителей. Задача решается методом динамического программирования.
Методы решения задач дискретного программирования
Основная идея данного метода предложена Гомори [1] и состоит в сведении нерегулярной задачи к решению конечной последовательности регулярных задач. Применительно к задаче целочисленного линейного программирования идея регуляризации позволяет свести решение этой задачи к решению последовательности специальным образом построенных линейных задач. Если полученное решение удовлетворяет условию целочисленности, то процесс окончен. В противном случае к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами: - полученный нецелочисленный план не удовлетворяется; - любой целочисленный план удовлетворяется;
Решается задача с дополнительно введенным ограничением, процесс повторяется до получения целочисленного решения. Недостатки метода Идея отсечения приводит к трем проблемам: - нахождение универсального правила формирования отсечений; - доказательство конечности процесса отсечений; - борьба с чрезвычайным «разрастанием» размерности задач при добавлении ограничений; Методы отсечения не нашли широкого применения при решении прикладных задач по следующим причинам: - определение того, какое отсечение есть сильнейшее, есть сложная в вычислительном отношении задача; - методы отсечения приспособлены в основном для решения целочисленных задач; - методы отсечения не приспособлены для решения задач со слабо заполненной матрицей; Комбинаторные методы
Основная идея комбинаторных методов состоит в использовании конечности множества допустимых решений и замене полного их перебора сокращенным. Если каким-либо образом удается показать, что подмножество (/ cG не может содержать оптимальных решений, то в дальнейшем задача решается на множестве х є G \ G . Таким образом, главную роль в сокращении перебора играют оценка и отбрасывание подмножеств, заведомо не содержащих оптимальных решений. К комбинаторным методам относят методы: - метод ветвей и границ: - метод динамического программирования; - аппроксимационно-комбинаторные методы и другие. Комбинаторный подход для задач теории расписаний сводится к целенаправленной взаимной перестановке групп работ в некоторой исходной последовательности, пока не будет получено оптимальное (приближенно оптимальное) решение.
Основополагающей работой по этой теме является работа С. Джонсона [2], положившая начало исследованиям в области конвейерных систем. В ней, а также в [3,4], был предложен полиномиальный алгоритм минимизации длины расписания в конвейерной системе с двумя приборами, основанный на взаимной перестановке требований, и доказана его оптимальность. Этот алгоритм приведен в [5,6], где также выведены неравенства, являющиеся достаточными условиями того, что одно требование предшествует другому. Е.Н. Хоботовым [7] сделаны замечания по поводу транзитивности этих неравенств в случае, когда у некоторых требований длительность обслуживания первым прибором совпадает с длительностью обслуживания вторым прибором..
В [5,8] как один из наиболее значительных и интересных аналитических результатов теории расписаний отмечают следующий. Как уже упоминалось, при поиске оптимального по быстродействию расписания для га-стадийного конвейера достаточно рассмотреть (п!)т 2 расписаний, согласно которым устанавливается одинаковый порядок работ для первых двух приборов и одинаковый порядок для последних двух приборов. Следовательно, для конвейера с числом стадий не более трех достаточно исследовать только множество перестановочных расписаний. Если же число стадий больше трех, то количество потенциально оптимальных расписаний резко возрастает. В этом случае методы, применимые к конвейерным системам, обычно используют специальные предположения и либо являются неэффективными с вычислительной точки зрения, либо дают только приближенное решение.
Приведенные результаты являются классической иллюстрацией использования методов комбинаторного анализа применительно к задаче построения оптимального расписания функционирования конвейерной системы. В работе [5] отмечается, что комбинаторные исследования направлены в основном и дают интересные результаты при рассмотрении вырожденных и частных случаев, а также показывает чрезвычайную широту их применения к конкретным задачам.
Задача определения циркуляции максимальной величины
При этом максимальная величина циркуляции в исходном графе равна максимальной величине циркуляции в агрегированном графе плюс А. Определение 2.2.3 Граф G называется агрегируемым, если, применяя описанные выше операции агрегирования, его можно свести к графу из двух вершин. Задача определения циркуляции максимальной величины в агрегируемом графе эффективно решается. Действительно, каждый раз, когда встречается параллельный подграф, определяется циркуляция по соответствующему контуру, содержащему соответствующую пару вершин (если такой контур существует). Сумма величин таких циркуляции, очевидно, равна максимальной величине циркуляции исходного графа G. Сама оптимальная циркуляция в графе G определяется методом «обратного хода», а точнее путем дезагрегирования полученного агрегированного графа из двух вершин. Пример 2.2.1. Рассмотрим граф, приведенный на рис. 2.2.3 (пропускные способности указаны у соответствующих дуг). Рис. 2.2.3 Структура агрегирования приведена на рис. 2.2.4
Фактически структура рис. 2.2.4 является структурой сетевого представления ограниченной задачи, а описанный выше алгоритм не что иное, как метод сетевого программирования, поскольку структура сетевого преставления имеет вид дерева. На рис. 2.2.4 в квадратных скобках у вершин указаны пропускные способности дуг после агрегирования. Величины А циркуляции при агрегировании параллельных подграфов указаны также у вершин, соответствующих агрегированию таких подграфов.
Поступая аналогичным образом, можно любой граф преобразовать в агрегируемый. Утверждение 2.2.4. Максимальная величина циркуляции в преобразованном (агрегированном) графе не превышает максимальной величины циркуляции в исходном графе. Доказательство следуем из достаточно очевидного факта, что любой циркуляции в агрегируемом графе однозначно соответствует циркуляция той же величины в исходном графе. Утверждение 2.2.5 (теорема двойственности). Существует разбиение пропускных способностей разделенных дуг исходного графа, такое, что максимальная величина циркуляции преобразованного графа равна максимальной величине циркуляции исходного графа. Доказательство. Пусть Х - циркуляция максимальной величины в исходном графе. Ей однозначно соответствует циркуляция той же величины в преобразованном графе. Определим пропускные способности разделенных дуг так, чтобы они были не менее суммарных величин циркуляции по этим дугам. Это всегда можно сделать, поскольку суммарная циркуляция по любой дуге не превышает ее пропускной способности. Утверждение доказано. Таким образом, задача определения циркуляции максимальной величины свелась к определению оптимального разбиения пропускных способностей разделенных дуг графа. Эту задачу назовем оценочной задачей. 2.3 Задача о минимальном разрезе. Определить разрез, имеющий минимальную пропускную способность. Утверждение 2.3.1. Величина любой циркуляции не превышает пропускной способности любого разреза.
Задачи о циркуляции максимальной величины и разрезе минимальной пропускной способности в графе в определенной степени подобны задачам о максимальном потоке и разрезе минимальной пропускной способности в сети. Однако в последнем случае имеет место известная теорема двойственности Форда -Фалкерсона[48].: максимальная величина потока равна минимальной пропускной способности разреза.
Доказательство. Для случая графа из двух дуг теорема очевидна. Пусть теорема справедлива для графа из п дуг. Докажем ее для графа из (n + 1) дуг. Поскольку граф агрегируемый, то найдется подграф, представляющий собой либо последовательную цепочку (путь), либо несколько параллельных дуг, либо элементарный контур из двух дуг. В первом случае можно провести операцию агрегирования, заменив последовательную цепь одной дугой, пропускная способность которой равна минимальной из пропускных способностей дуг цепочки. Получили граф с меньшим числом дуг, для которого по предположению теорема имеет место. Следовательно, теорема справедлива и для исходного графа.
Во втором случае также уменьшаем число дуг, заменяя параллельные дуги одной дугой, пропускная способность которой равна сумме пропускных способностей параллельных дуг.
Рассмотрим третий случай. Уменьшаем число дуг, заменяя контур одной дугой, пропускная способность которой равна модулю разности пропускных способностей дуг контура, а направление определяется дугой (i, j) с большей пропускной способностью.
Алгоритм в задаче о камнях
Одной вершине поставим в соответствие часть веса у;, а второй - (aj-у;). Вторая задача сводится, как и ранее, к одной задаче о ранце с дополнительными условиями (3.3.1). Обозначим через Q={Qj} множество векторов х, удовлетворяющих (3.2.7) и (3.3.1) и упорядоченных по убыванию Mj. Далее решение оценочной задачи происходит аналогично описанному выше.
Пример 3.3.1. Возьмем данные Примера 3.2.1. Будем считать, что камни 5 и 6 фиктивные, то есть Т] = 36, Т2= 18, Тз= 17. Выписываем множества Qj до тех пор, пока каждый камень не войдет хотя бы в одно множество. Возьмем Т = 37. Имеем Q1 = (1,3,4),Q2=(4,7),Q3 = (1,2,3),Q4=(3,7), Q5=(2,7),Q6=(4,6),Q7=(4,5).
Заметим, что для множества Q7 имеем М7=32. Поэтому величину Т следует взять не менее 38. Следующее множество с величиной М 37 существует при Т = 40. Таких множеств два: Qi = (1, 2, 5) и Q2= (5,7).
Итак, мы получили оценку 110, что больше чем 108. Можно попытаться ее еще уменьшить, добавляя множество Q со значениями М 33. Можно поступить другим способом. Учитывая, что оценка больше объема всех работ, попробуем получить решение на основе полученных множеств. Для этого следует выбрать три множества, так, чтобы каждый камень принадлежал бы одному из них. В данном примере решение определяется легко. Действительно, шестой камень входит только в одно множество Q = (4,6). Пятый камень входит в два подмножества (1, 2, 5) и (5, 7). Соответственно, определяются два оптимальных решения: Первое состоит из множеств Qb Q6 и Q8, а второе - Q2, Q5 и Qg. Перегрузка составляет не более 4 для каждого подразделения. Более точно, в обоих решениях перегружено второе подразделение и недогружены первое и третье.
Имеем Q, = (5,6), М, = 37, Q2=(l,3,4), М2=37, Q3=(4,7), М3 = 36, Q4=(2,7), М4=35, 05 = (3,7), М5 = 35. Получили 5 множеств, таких, что каждый камень входит хотя бы в одно из них. Поэтому, не получая верхней оценки, можно попытаться получить оптимальное решение на основе полученных множеств, решая задачу о покрытии двудольного графа. Если минимальное число равно числу подразделений (в нашем случае 3), что задача решена. Граф G(X,Y) для рассматриваемого примера приведен нарис. 3.3.1
В данном случае решение очевидно. Действительно, множество Q2 необходимо взять, так как только оно содержит камень 1. Аналогично необходимо взять множество Qi (только оно содержит камни 5 и 6) и множество Q4 (только оно содержит камень 2). Получили решение, в котором первое подразделение выполняет работы 5 и 6, второе - работы 3 и 4, а третье работу 7. Загрузка первого подразделения составляет 37, второго - 27, а третьего - 22. (табл. 3.2.2)
Для задачи (3.1.6)-( 3.1.8) с Tj=T и различными значениями Т, можно получить получить априорные оценки, если отбросить требование целочисленности. Оптимальное значение целевой функции непрерывной задачи очевидно будет нижней границей оптимального значения для дискретной задачи.
В таком виде она, кроме того, может служить моделью задачи распределения производственной программы по календарным периодам или задача оптимизации распределения работ проекта с фиксированными инвестициями [55,56,57] Анализ задачи с применением метода декомпозиции
Рассмотрим систему уравнений (3.5.4), (3.5.5), (3.5.7). Эта система уравнений представляет собой систему ограничений для транспортной задачи, и, как известно, для того, чтобы эта система была совместна необходимо и достаточно выполнения следующего условия баланса.
Управляющая Компания «Жилпроект» образовалась в результате слияния самостоятельных организаций: изыскателей, архитекторов и проектировщиков, зарегистрирована в сентябре 2001 года. Сегодня компания - это динамично развивающееся предприятие, которое осваивает новые технологии, обучает кадры, совершенствует производственно-техническую базу, формирует систему качества, участвует в областных конкурсах и рейтингах проектно-изыскательских организаций России.
Особенностью компании является возможность в минимальные сроки выполнять проектные работы под «ключ» в любой конструктивной схеме (сборный каркас, монолитный каркас, кирпич, панельное домостроение), выполнять инженерные изыскания, осуществлять геодезическую и картографическую деятельность, для этого в организации имеются различные виды технического сопровождения.
Определения работ для передачи на субподряд
Как следует из таблицы 4.1.2 общий объем работ равен 10100 чел.-смен. В соответствии с планом работы необходимо выполнить за 90 дней. Однако при наличии 90 проектировщиков имеем общее количество человеко-смен Q = 8100. Т.е. проектировщики работают с перегрузкой а = тах(1: —)=1,25.
Поэтому часть работ предлагается передать на субподряд. При этом объем работ выполненный собственными силами должен быть равен 7500 чел.-смен, а передаваемых на субподряд 2600 чел.-смен. Будем передавать на субподряд работы, имеющие наименьшую стоимость при максимальном объеме.
Получили классическую задачу о ранце. Будем решать эту задачу методом динамического программирования, который в данном случае наиболее предпочтителен.
На рисунке 4.2.1 представлен фрагмент сети динамического программирования, который содержит оптимальное решение. По горизонтальной оси указаны номера проектов в порядке неубывания отношения Cj/aj, по вертикальной оси - свободный объем работ в сотнях чел.смен.
Оставшиеся после передачи на субподряд проекты можно вновь распределить между группами проектировщиков. Поскольку остается всего шесть проектов на пять групп проектировщиков, очевидно, то распределить целые проекты равномерно не представляется возможным. Поэтому разрешили делить проекты между группами, то есть будем решать непрерывную задачу. В этом случае можно добавить еще один критерий - равномерность распределения по стоимости.
При этом группы проектировщиков I, II, III выполняют по 2 проекта и только IV и V по 3 проекта. Таким образом, достигнута абсолютная равномерность по трудоемкости и стоимости.
Достоинство рассмотренного алгоритма состоит в его простоте, так как для получения решения надо произвести 2m+n-2 операции. Кроме того, последовательное заполнение столбцов матрицы решения можно произвести в любом порядке, то есть можно получить т! оптимальных решений, которые, впрочем, могут повторяться.
По результатам решения практических задач можно сделать вывод, что метод сетевого программирования оказался весьма эффективным. Если же возможен переход к непрерывным задачам, то можно использовать метод декомпозиции решения задач дубльтранспортного типа.
В диссертационной работе получены следующие основные результаты: 1. разработаны эффективные методы решения прикладных задач дискретной оптимизации :задачи о циркуляции максимальной величины; задачи о разрезе минимальной пропускной способности; задачи о максимальном независимом множестве на основе метода сетевого программирования. 2. Дана постановка задачи о загрузке работами подразделений, как задачи о камнях с различными объемами групп, и разработан алгоритм решения поставленной задачи на основе метода сетевого программирования. 3. Выведены априорные оценки целевой функции дискретной задачи с помощью сведения ее к непрерывной и разработан алгоритм решения непрерывной задачи, основанный на идее декомпозиции системы ограничений. 4. разработанные методы применены к решению задачи оптимального распределения проектных работ между группами проектировщиков по критерию равномерности загрузки; задачи оптимального выделения части работ для передачи на субподряд; задачи распределения проектных работ по группам проектировщиков по двум критериям одновременно (критерий равномерности загрузки и финансирования).
