автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Метод сетевого программирования в задачах управления строительным производством

На правах рукописи

Ленина Наталия Георгиевна

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

Специальность 05.13.10 - управление в социальных и экономических системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Воронеж 2006

Работа выполнена в Воронежском государственном архитектурно-строительном университете

Научный руководитель:

доктор технических наук, профессор Баркалов Сергей Алексеевич

Научный консультант:

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

Официальные оппоненты:

доктор технических наук, профессор Леденева Татьяна Михайловна

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

Ведущая организация:

Воронежская государственная лесотехническая академия

Защита состоится 16 марта 2006 г. в Ю00 часов на заседании диссертационного Совета К 212.033.01 при Воронежском государственном архитектурно-строительном университете по адресу: 394006, г. Воронеж, ул. 20-летия Октября, 84., а. 3220.

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

Автореферат разослан 14 февраля 2006 г.

Ученый секретарь диссертационного совета

Чертов В.А.

Ми?бА

зт

Общая характеристика работы

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

проведение различных видов инженерных изысканий, а также технико-экономического обоснования на возведение объекта;

разработка проектно-сметной документации (архитектурное проектирование, конструкторское проектирование, проектирование организации строительства на различных стадиях возведения объекта);

работа предприятий строительной индустрии и промышленности строительных материалов и последующая комплектация объекта;

собственно возведение объекта (строительно-монтажные работы, монтаж оборудования, опытная эксплуатация).

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

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

Цель и постановка задач исследования. Целью диссертации является разработка эффективных методов решения ряда прикладных задач дискретной оптимизации, применяемых для решения проблем в управлении строительным производством. Достижение поставленной цели потребовало решения следующих задач:

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

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

Разработать алгоритмы решения поставленных задач на основе метода сетевого программирования. —--------

Поставить задачу о загрузке оборудования, как задачу о камнях с различными объемами групп.

Разработать алгоритм решения поставленной задачи на основе метода сетевого программирования.

Разработать методику определения априорных оценок целевой функции дискретной задачи на основе сведения ее к непрерывной и разработать алгоритм решения непрерывной задачи.

Применить разработанные методы к решению практических задач.

Методы исследования: В диссертации используйся методы исследования операций, теории графов, теории активных систем, догадфетной оптимизации.

Научная новизна работы состоит в следующем:

Введено понятие агрегируемого графа и доказано, что агрегируемый граф допускает сетевое представление вида дерева.

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

Доказана теорема двойственности для агрегируемых графов о совпадении величины максимальной циркуляции и минимальной пропускной способности разреза.

Предложен алгоритм решения задачи о максимальной загрузке на основе метода сетевого программирования.

Разработан алгоритм решения задачи о максимальном независимом множестве на основе метода сетевого программирования.

Разработан алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования.

Предложен способ определения априорных оценок для задачи о камнях.

Разработан эффективный метод решения соответствующей непрерывной задачи на основе декомпозиции системы ограничений.

Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами. Они подтверждены расчетами на примерах, производственными экспериментами и многократной проверкой при внедрении в практику управления.

Практическая значимость работы и результаты внедрения. Практическая значимость состоит в том, что разработанные методы позволяют повы-

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

Разработанные алгоритмы и модели на практике используются в работе предприятия ООО УК «Жилпроект» и ООО «Агрокс-2».

Модели и алгоритмы, разработанные в диссертационной работе, включены в состав учебных курсов и дисциплин: «Теория экономических и информационных систем», «Теория систем и системный анализ», «Оптимизационные задачи в экономике», читаемых в Воронежском государственном архитектурно - строительном университете.

На защиту выносится: Алгоритм решения задачи о циркуляции максимальной величины, основанный на преобразовании произвольного графа в агрегируемый.

Доказательство теоремы двойственности для агрегируемых графов о совпадении величины максимальной циркуляции и минимальной пропускной размерности разреза.

Алгоритмы решения задач о максимальной загрузке и о максимальном независимом множестве на основе метода сетевого программирования.

Алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования и способ определения априорных оценок для нее.

Апробация работы. Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях, симпозиумах и научных совещаниях в 2004-2005 гг,: Международная школа-семинар «Современные проблемы механики и прикладной математики» (Воронеж, 2004г.); 27-я международная школа семинар «Системное моделирование социально-экономических процессов» (Орел, 2004г.); 13-я международная конференция «Математика. Экономика. Образование» (Росгов-на-Дону, 2005г.); 12-я международная конференция «Математика. Компьютер. Образование» (Москва-Пущено, 2005г.); Международная научно-практическая конференция «Теория активных систем» (Москва, 2005г.); Научно-техническая конференция «Современные сложные системы управления» (Воронеж, 2005 г.);

Публикации. По теме диссертации опубликовано 8 печатных работ.

Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: В работе [1] автору принадлежат: математическая модель и вывод достаточного условия совместности системы линейных уравнений дубльтранс-портного типа. В работах [2], [3] автору принадлежат математические модели различных задач, сводящихся к задачам дубльтранспортного типа, а также алгоритмы, основанные на идее декомпозиции. В работах [4], [5], [7], [8] автору принадлежат постановки задач, доказательство основных теорем и алгоритм, основанный на методе сетевого программирования.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Она содержит 123 страницы основного текста, 52 рисунка, 35 таблиц. Библиография включает 63 наименования.

Содержание работы

Во введении обосновывается актуальность, описываются цели и задачи исследования, научная новизна и практическая значимость.

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

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

При этом, если структура сетевого представления является деревом, то мы получаем эффективный алгоритм решения задачи, последовательно решая задачи в вершинах сетевого представления.

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

Во второй главе введены основные понятия теории графов, в том числе:

Циркуляцией в графе в называется множество неотрицательных чисел х(ц) заданных на контурах цеМи удовлетворяющих условиям

(1)

Где и,,- множество контуров, содержащих дугу ( У).

Величиной циркуляции называется —

Ф(х)= £х(ц) (2)

цеМ

Разрезом графа в называется множество дуг V, таких, что частичный граф с множеством дугЦ\У не имеет контуров. Величина

<ХУ)= I Су (3)

называется пропускной способностью разреза.

Паросочетаниями графа в называется множество ребер таких, что никакие два ребра не имеют общей вершины.

Дана постановка задачи определения циркуляции максимальной величины.

Рассмотрим частный случай задачи», для которого существует эффективный алгоритм решения.

Определение. 1 Последовательным подграфом называется путь в графе, такой, что степени захода и исхода всех промежуточных вершин пути равны единице.

Последовательный подграф можно агрегировать в одну дугу, пропускная способность которой равна минимальной из пропускных способностей дуг пути.

Определение 2 Параллельным подграфом называется подграф из двух вершин, соединенных несколькими дугами (рис. 1)

Рис. 1 7

Пусть С^ к = 1... т пропускная способность к -ой дуги (У)

Пусть 1 = 1... п пропускная способность 1 -ой дуги (у)

ш . п .

Обозначим: в,, = I С* 8И = ХС1-- ; Д = пппф ¡;8;,) к=1 4 1=1 ;

Утверждение 1 Максимальная величина циркуляции параллельного подграфа равна Л.

Учитывая Утверждение 1, параллельный подграф можно агрегировать в подграф, состоящий из тех же вершин ¡, ] и не более одной дуги.

При этом Су = - в^ , а при Бу = дуга отсутствует.

При этом максимальная величина циркуляции в исходном графе равна максимальной величине циркуляции в агрегированном графе плюсд.

Определение 3 Граф в называется агрегируемым, если, применяя описанные выше операции агрегирования, его можно свести к графу из двух вершин.

Задача определения циркуляции максимальной величины в агрегируемом графе эффективно решается. Действительно, каждый раз, когда встречается параллельный подграф, определяется циркуляция по соответствующему контуру, содержащему соответствующую пару вершин (если такой контур существует).

Сумма величин таких циркуляций, очевидно, равна максимальной величине циркуляции исходного графа в. Сама оптимальная циркуляция в графе в определяется методом «обратного хода», а точнее путем дезагрегирования полученного агрегированного графа из двух вершин

Пример I. Рассмотрим граф, приведенный на рис. 2. (пропускные способности указаны у соответствующих дуг).

Структура агрегирования приведена на рис. 3.

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

Рассмотрим задачу определения циркуляции максимальной величины для произвольного сильно связного графа. Сначала приведем два простых утверждения в ряде случаев позволяющее уменьшить число вершин графа.

Утверждение 2 пусть существует вершина ¡, которой инцидентна одна заходящая дуга (к, |) и некоторое множества и,+ исходящих дуг (¡, 3), причем:

В этом случае вершину \ можно исключить, положив Сь = С;, для VI*,

Ч и

таких, что .¡) е и?".

Утверждение 3. Пусть существует вершина ¡, которой инцидентна одна исходящая дуга (¡,к) и некоторое множество V; заходящих дуг 0,1), причем

Ф= 2 + 2 + 3 + 6 = 13.

Рис. 3

ск! > £ Сц

(4)

СъЬ I с^ (5)

В этом случае вершину 1 можно исключить, положив С^ = С^, для V ]

таких, что 0,1) б и|".

Для решения задачи в общем случае преобразуем граф к агрегируемому путем разделения ряда вершин.

Утверждение 4 Максимальная величина циркуляции в преобразованном (агрегируемом) графе не превышает максимальной величины циркуляции в исходном графе.

Утверждение 5 (теорема двойственности).

Существует разбиение пропускных способностей разделенных дуг исходного графа, такое, что максимальная величина циркуляции преобразованного графа равна максимальной величине циркуляции исходного графа.

Утверждение 6. Величина любой циркуляции не превышает пропускной способности любого разреза.

Задачи о циркуляции максимальной величины и разрезе минимальной пропускной способности в графе в определенной степени подобны задачам о максимальном потоке и разрезе минимальной пропускной способности в сети. Однако в последнем случае имеет место известная теорема двойственности Форда -Фалкерсона: максимальная величина потока равна минимальной пропускной способности разреза.

В случае циркуляции и разреза в сильно связанных графах это, в общем случае, не имеет места.

Тем не менее, для агрегируемых графов аналог теоремы Форда-Фалкерсона имеет место

Теорема 1 (двойственности). Для агрегируемых графов максимальная величина циркуляции равна минимальной пропускной способности разреза.

Будем считать, что путем разделения ряда вершин (и соответственно, пропускных способностей этих вершин) исходный граф преобразован в агрегируемый.

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

ных дуг, принадлежащих к - ому разрезу (к= 1 ,р где р - число различных разрезов минимальной пропускной способности).

Выписываем систему неравенств.

I Сц+ I 80>Ф, к = 1^ (6)

(Ч)е<3к (у)бЯк

Где Ф- максимальная величина циркуляции. Заметим, что величина Бу удовлетворяет условиям ' 1

Е 8в=С|а, (М)еУ, (7)

где V- множество дуг исходного графа, которые разделены, Рь- множество дуг, полученных от разделения дуг (к,б) исходного графа.

Утверждение 7 Необходимым и достаточным условием оптимальности полученной циркуляции является отсутствие решений системы (6), (7). Описание алгоритма

Первый шаг Проводим операции агрегирования, если это возможно.

Второй шаг Проверяем выполнение условий Утверждения 2 и 3. Если они выполняются для какой-либо вершины, исключаем эту вершину, в соответствии с соответствующим утверждением. Если нет, то переходим к следующему шагу.

Третий шаг. Выбираем любую вершину и разделяем ее и соответствующие дуги. Целесообразно выбирать вершины с минимальным числом заходящих, либо исходящих дуг. Далее повторяем шаги 1, 2 и 3, пока не получим граф без контуров, либо простейший граф из двух вершин. Заметим, что при разделении пропускных способностей дуг проводится локальная оптимизация. Так, если разделенная дуга входит в последовательную цепочку дуг (путь), то ее пропускную способность нецелесообразно брать больше, чем минимальная пропускная способность остальных дуг этого пути.

Четвертый шаг Определяем все разрезы минимальной пропускной способности и решаем систему (6),(7). На основе полученного решения корректируем пропускные способности разделенных дуг. С новыми пропускными способностями повторяем шаги 1,2,3. Если система (6),(7) не имеет решения, то получена циркуляция максимальной величины.

Перейдем к исследованию задачи о минимальном разрезе.

Постановка задачи: "

Определить разрез V, такой, что его пропускная способность С(У)= £ Сц

минимальна.

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

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

Задача о максимальном независимом множестве.

Задача заключается в выборе множества объемов максимальной суммарной ценности при ограничениях на несовместимость пар объектов. Для решения этойзадачи применяется метод сетевого программирования.

Рассмотрим граф С(Х,и), где X - множество вершин, и- множество ребер. Для каждой вершины определен ее вес С, > 0 1 = 1,п.

Определение 3 Независимым множеством вершин называется подмножество У с X, такое, что никакие пары вершин этого подмножества не смежны. Постановка задачи.

Определить независимое множество с максимальной суммой весов вершин.

Обозначим х, = 1,если 1 е У, противном случае.

Задача заключается в определении {х,}, удовлетворяющих условиям х, + xJ < 1, V 0,.¡) е У и максимизирующих С(Х) = £ х;с,

I

Для решения задачи методом сетевого программирования представим граф в в виде двух частичных графов: С?(Х, V) и Я(Х, Где множество ребер V графа О является паросочетанием, а множество ребер = Ц\ V.

Вес каждой вершины также разделим на две части V, и так что:

У. + ЛУ.-С,

Решим задачу о максимальном независимом множестве для графа О и графа Я. Обозначим А(у) и В (\у) сумму весов в оптимальных решениях этих задач.

Теорема 2. Величина Ф(у, w) = A(v) + B(w) является оценкой сверху для оптимального решения исходной задачи.

Следствие Если оптимальные решения обеих задач совпали, то полученное общее решение является оптимальным решением для графа G.

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

Пусть в организации имеются ш подразделений, располагающих мощностями ресурсов одного вида. Обозначим Т, объем работ, который может выполнить j-e подразделение, а, - объем i-ой работы, i = 1,п. Требуется распределить работы между подразделениями, так, чтобы загрузка подразделений (или их перегрузка) была максимально равномерной.

Математическая модель задачи примет вид:

¿Ху=1 i = ü (8)

J=1

max(5>,xjj _ Tj) —> min (9)

J ' «-

Решение этой задачи для случая, когда все Tj равны, то есть Т, = Т, j= 1,т было рассмотрено И.В. Бурковой и М.В. Попком и основано на методе сетевого программирования. В этом случае задача сводится к «задаче о камнях»

Дадим обобщение описанного метода на случай, когда Tj различны. Определим Т = maxTj и добавим к имеющимся п камням еще m фиктивных камней, J

вес которых равен а; = Т-Т,_п, i = n +1,n + m. Мы получили «задачу о камнях» с дополнительными условиями

n+m

£ Хц =1 (Ю)

i=n+l

Суть этих условий в том, что в каждый ящик можно поместить один и только один фиктивный камень. Разделим каждую вершину сетевого представления также на две вершины.

Одной вершине поставим в соответствие часть веса у„ а второй - (а,-у,). Вторая задача сводится, как и ранее, к одной задаче о ранце с дополнительными условиями (10). Обозначим через Q = {Q,} множество векторов х, удовлетво-

ряющих К/^ = £х,а, <Т и (10) и упорядоченных по убыванию Мг Далее решение оценочной задачи происходит аналогично случаю, когда Т^ = Т. Априорные оценки. Для задачи

Еа.х^Тз. (11)

1ху=1,1 = 1Я . (12)

)

Т = тах^-яшп (13)

можно получить априорные оценки, если отбросить требование целочисленно-сти. Оптимальное значение целевой функции непрерывной задачи очевидно будет нижней границей оптимального значения для дискретной задачи.

1 п

Для случая Т,=Т оценка очевидна Ттт = тах(таха,;— )

т1=1

Заметим, что если щ целые числа, а Тт1П - дробное число, то оценку можно уточнить Т = [Ттш ] +1

Если все Т, различны, то для получения оценки задачу (11)-(13) преобразуем к следующему виду.

Тф-максимальное значение объема. Предполагаем, что все объемы одинаковы, однако подразделения имеют различную производительность, т.е., если

То

ая работа попадает в j-oe подразделение, то ее объем становится равным aj

Ti

В теории расписаний эта задача известна как задача для m приборов различной производительности. Ее математическая модель имеет вид: m m _

IbiTij=ai> i = l.n

j=l j=l

£т0<Т j = l3i i=l

T—>min Ti

Здесь bj =—, t,j доля объема i-ой работы выделенная j-ому подразде-т0

лению.

Спецификой данной задачи является то, что для нее можно сразу выписать нижнюю оценку Т:

Т = тах

тах 1£р<т-1

р п

1а, 1а,

¡=1 1=1

Р ' т

>1

(14)

Где ^ и а, упорядочены следующим образом Ь[ > Ь2...> Ьт и

В работе доказано, что Тт;п > X

В четвертой главе решаются практические задачи формирования оптимальной производственной программы проектно - строительного предприятия:

- Задача обеспечения равномерной загрузки подразделений организации, выполняющих однотипные проектные работы. Эта задача сведена к известной «задаче о камнях» с различными объемами групп, для решения которой предложен метод сетевого программирования.

— Задача о передаче части работ на субподряд в случае перегрузки основных исполнителей. Задача решается методом динамического программирования.

Указанные задачи решались на основе исходных данных ООО УК «Жил-проект»

Предприятие ООО Управляющая компания «Жилпроект» осуществляет разработку проектно - сметной документации для строительных предприятий Воронежского региона.

Данные о трудоемкости каждого проекта и его стоимости приведены в таблице 1. Во второй строке таблицы а, приведены сведения о трудоемкости проектов в чел.-см., в третей строке стоимости в тыс. рублей.

Таблица 1

1 1 2 3 4 5 6 7 8 9

а, 700 1000 1300 600 700 1100 2700 1300 700

С, 654 1010 1283 565 713 1034 2627 1259 689

Общая трудоемкость составляет 10100 чел.-см.

Компания имеет 90 специалистов, объединенных в пять групп по 10, 15, 20 и 25 человек. При распределении проектов по группам по критерию равномерности загрузки получены результаты, приведенные в таблице 2.

Как следует из таблицы 2 общий объем работ равен 10100 чел.-смен. В соответствии с планом работы необходимо выполнить за 90 дней. Однако при наличии 90 проектировщиков имеем общее количество человеко-смен О =

Уа:

8100. Т.е. проектировщики работают с перегрузкой а = шах(1: =1,25. Поэтому часть работ предлагается передать на субподряд. При этом объем работ выполненный собственными силами должен быть равен 7500 чел.-смен, а передаваемых на субподряд 2600 чел.-смен. Будем передавать на субподряд работы имеющие наименьшую стоимость при максимальном объеме.

Таблица 2

№ группы I II ш IV V

1 проект 700

2 проект 1000

3 проект 1300

4 проект 600

5 проект 700

6 проект 1100

7 проект 1600 1100

8 проект 1300

9 проект 700

Объем работ 2900 2400 2100 1600

Идеальный объем загрузки 2800 2300 2200 1700 1100

Перегрузка +100 +100 -100 -100 0

% перегрузки 3,6% 4,5%

Математическая модель полученной задачи является классической задачей о ранце. Указанная задача решается методом динамического программирования, который в данном случае наиболее предпочтителен.

Расчеты показали, что на субподряд следует предать 1,4 и 8 работы общей стоимостью 2478 тыс. руб.

Основные результаты работы

Перечислим основные результаты работы:

1. Разработаны эффективные методы решения прикладных задач дискретной оптимизации :задачи о циркуляции максимальной величины; задачи о разрезе минимальной пропускной способности; задачи о максимальном независимом множестве на основе метода сетевого программирования.

2. Дана постановка задачи о загрузке работами подразделений, как задачи о камнях с различными объемами групп, и разработан алгоритм решения поставленной задачи на основе метода сетевого программирования.

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

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

V

терию равномерности загрузки; задачи оптимального выделения части работ для передачи на субподряд; задачи распределения проектных работ по группам проектировщиков по двум критериям одновременно (критерий равномерности загрузки и финансирования).

Основные результаты диссертационной работы изложены в следующих публикациях:

1. Ленина А .Я. О некоторых свойствах системы линейных уравнений дубльтранспортного типа/ А.Я Ленина, Н.Г. Ленина, Н.В. Нистратова // Современные проблемы механики и прикладной математики. Сборник трудов международной школы-семинара / Воронеж, гос. ун-т - Воронеж, 2004. - С.41-44. (Лично автором выполнено 3 стр.).

2. Ленина А.Я. Оптимизация распределения планового задания по календарным периодам с фиксированной загрузкой двух видов работ/ А.Я Ленина, Н.Г. Ленина, Ю.С. Попченкова// Системное моделирование социально-экономических процессов: тезисы докладов и сообщений 27-й международной

школы-семинара. - M: ЦЭМИ РАН, 2005. - С. 16-22. (Лично автором выполнено 5 стр.).

3. Аснина А.Я. Управление проектом в условиях фиксированных инвестиций по календарным периодам / А.Я Аснина, Н.Г. Аснина // XIII международная конференция «Математика. Экономика. Образование»: Тезисы докладов.- Ростов-на-Дону: Изд-во ООО «ЦВР», 2005. - С.131. (Лично автором выполнено 0,5 стр.).

4. Аснина Н.Г. Двойственность в задачах дискретной оптимизации/ Н.Г. Аснина, Н.В. Буркова, П.А. Колесников, Н.В. Попок// Теория активных систем: Труды международной практической конференции. - М: ИПУ РАН, 2005. -С.15. (Лично автором выполнено 0,5 стр.).

5. Аснина Н.Г. Задача о максимальной циркуляции для агрегируемых графов/ Н.Г. Аснина, С.А. Баркалов, И.В. Буркова // Вестник Воронежского государственного технического университета. - Воронеж: ВГТУ, 2006. Т. 2, №2. -С. 35-42. (Лично автором выполнено 4 стр.).

6. Аснина Н.Г. Задача о максимальном независимом множестве/ Н.Г. Аснина // Вестник Воронежского государственного технического университета. Воронеж, 2006. Т. 2, №2. - С. 20-25.

7. Аснина А.Я Модели, алгоритмы, оценки в задаче оптимизации загрузки / А.Я Аснина, Н.Г. Аснина, И.В. Буркова, И.В. Попок// Вестник Воронежского государственного технического университета. -Воронеж, 2006. Т. 2, №2 С. 3-16. (Лично автором выполнено 8 стр.).

8. Аснина Н.Г. Выбор оптимального набора продуктов/ Н.Г. Аснина, C.B. Серенько, Г .Д. Юшин// Современные сложные системы управления: Сборник трудов научно-практической конференции. - Воронеж: ВГАСУ, 2005.Т. 2. - С. 123-125. (Лично автором выполнено 2 стр.).

Подписано в печать 09.02.2006 г. Формат 60x84 1/16 Уч. - изд. л. 1,0 Усл.-печ. 1,1 л Бумага писчая Тираж 100 экз. Заказ №73

Отпечатано в отделе оперативной полиграфии Воронежского государственного архитектурно-строительного университета 394006, г. Воронеж, ул. 20-летия Октября, 84.

m?-

- 34 47

ВВЕДЕНИЕ.

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 Другие критерии распределения работ.

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

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

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

Цель и постановка задач исследования. Целью диссертации является разработка эффективных методов решения ряда прикладных задач дискретной оптимизации, применяемых для решения проблем в управлении строительным производством. Достижение поставленной цели потребовало решения следующих задач:

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

2. Поставить ряд прикладных задач, моделируемых при помощи графов:

- задача о циркуляции максимальной величины;

- задача о разрезе минимальной пропускной способности;

- задача о максимальном независимом множестве.

3 Разработать алгоритмы решения поставленных задач на основе метода сетевого программирования.

4 Поставить задачу о загрузке оборудования, как задачу о камнях с различными объемами групп.

5 Разработать алгоритм решения поставленной задачи на основе метода сетевого программирования.

6 Разработать методику определения априорных оценок целевой функции дискретной задачи на основе сведения ее к непрерывной и разработать алгоритм решения непрерывной задачи.

7 Применить разработанные методы к решению практических задач.

Методы исследования: В диссертации используются методы исследования операция, теории графов, теории активных систем, дискретной оптимизации.

Научная новизна роботы состоит в следующем:

1. Введено понятие агрегируемого графа и доказано, что агрегируемый граф допускает сетевое представление вида дерева.

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

3. Доказана теорема двойственности для агрегируемых графов о совпадении величины максимальной циркуляции и минимальной пропускной размерности разреза.

4. Предложен алгоритм решения задачи о максимальной загрузке на основе метода сетевого программирования.

5. Разработан алгоритм решения задачи о максимальном независимом множестве на основе метода сетевого программирования.

6. Разработан алгоритм решения задачи о камнях с различными объемами групп на основе метода сетевого программирования.

7. Предложен способ определения априорных оценок для задачи о камнях.

8. Разработан эффективный метод решения соответствующей непрерывной задачи на основе декомпозиции системы ограничений.

Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами. Они подтверждены расчетами на примерах, производственными экспериментами и многократной проверкой при внедрении в практику управления.

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

Разработанные алгоритмы и модели на практике используются в работе предприятия ООО УК «Жилпроект» и ООО «Агрокс-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. разработаны эффективные методы решения прикладных задач дискретной оптимизации :задачи о циркуляции максимальной величины; задачи о разрезе минимальной пропускной способности; задачи о максимальном независимом множестве на основе метода сетевого программирования.

2. Дана постановка задачи о загрузке работами подразделений, как задачи о камнях с различными объемами групп, и разработан алгоритм решения поставленной задачи на основе метода сетевого программирования.

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

4. разработанные методы применены к решению задачи оптимального распределения проектных работ между группами проектировщиков по критерию равномерности загрузки; задачи оптимального выделения части работ для передачи на субподряд; задачи распределения проектных работ по группам проектировщиков по двум критериям одновременно (критерий равномерности загрузки и финансирования).

1. Финкелыитейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования/ Финкелыитейн Ю.Ю. - М.: Наука, 1976

2. Johnson S.M. Optimal Two and The Stage Production Schedules with Set Up Times Included / S.M. Johnson // Nav. Res. Log. Quart.-1954.- V.l, №1.-P. 61-68.

3. Bellman R. Some Combinatorial Problems Arising in the Theory of Multistage Processes / R. Bellman, O. Gross // J. Soc. Indust. and Appl. Math. 1954. -V.2,№3.-P. 175-183.

4. Bellman R. Mathematical Aspects of Scheduling Theory / R. Bellman // J. Soc.Indust and Appl. Math. 1956. - V.4, №3. - P. 168-205.

5. Конвей P.B. Теория расписаний / P.B. Конвей, B.JI. Максвелл, JI.B. Миллер. -М.: Наука, 1975.

6. Танаев B.C. Теория расписаний. Многостадийные системы / B.C. Танаев, Ю.Н. Сотсков, В.А. Струсевич М.: Наука, 1989.

7. Хоботов Е.Н. Некоторые замечания к теореме Джонсона / Е.Н. Хоботов// Автомат. И телемех.-1995.-№ 10.-С. 186-187.

8. Исследование операций. Т.2. / Под ред. Моудера Дж., Элмаграби С. М.: Мир, 1981.

9. ВагнерГ. Основы исследования операций/ Г. Вагнер-Т. 1,2.-М. :Мир, 1973.

10. Беллман Р. Прикладные задачи динамического программирования /Р. Беллман, С. Дрейфус-М.: Наука, 1965.

11. Хореев В.И. Итеративные алгоритмы определения расписаний в информационно-вычислительных системах / В.И. Хареев // Автоматика и вычислит, техника. 1987.-№4. С.8-14.

12. Муравьев В.И. Использование метода переменного базиса для решения непрерывного аналога задачи Джонсона / В.И. Муравьев, И.В. Романовский // Исследование операций и статист. Моделирование.- Л., 1974.-Вып. 2.-С.27-37.

13. Gilio R.J. Approximate Solutions to the Three- Machine Scheduling Problems / R.J Gilio, H.M. Wagner // Oper. Res. 1964. -V.12 №2.-P. 305-324.

14. Story A.E. Computational Experience with Integer Programming for Job-Shop Scheduling / A.E. Story, H.M. Wagner Englewood Cliffs, N.J.: Prentice-Hall,1963.-Ch. 14.

15. Ленина А.Я. Приближенные методы решения задач теории расписаний на основе двойственных оценок / А.Я. Аснина // Экономико-математические модели и методы: Сб. науч. трудов. Воронеж: ВГУД989. - С. 162-368.

16. Аснина А.Я. Об опыте решения задач Джонсона с произвольным числом станков / А.Я. Аснина, Р.А. Тищенкова // Системный анализ и моделирование социально-экономических процессов: Тр. II Всесоюз. семинара. -М.,1981.

17. Аснина А.Я. Оптимизация гибкого производства БИС на основе модели календарного планирования / А.Я. Аснина, Т.О. Толстых // Модели и алгоритмы оптимизации сложных систем. Воронеж, 1985.

18. Аснина А.Я. Об одном алгоритме решения задачи Джонсона / А.Я. Аснина, Г.Д. Чернышева //Тр. 4-й Междунар. конференции женщин-математиков, Волгоград, 27-31 мая 1996. Н.Новгород, 1997. - Т.4, вып.1-С. 82-86.

19. Ворожеева СВ. Вероятностный алгоритм формирования поисковых функций при решении задач условной оптимизации / СВ. Ворожеева, Г.Д. Чернышева // Алгоритмы моделирования и оптимизации автоматизированных систем. Воронеж, 1990. - С. 115-121.

20. Мину М. Математическое программирование. Теория и алгоритмы. / М. Мину -М.: Наука, 1990.

21. Ленина А.Я. О двух модификациях задачи Беллмана Джонсона: модели и алгоритм решения / А.Я. Ленина, СЮ. Балашева // Вестник ВГТУ. Серия «САПР и системы автоматизации производства» - Воронеж: ВГТУ, 2001.-Выпуск 3.1 -С 34-39.

22. Goldberg D. Е. Genetic algorithms in search, optimization, and machine learning. Reading/ Goldberg D. E. // MA: Addison-Wesley. 1989.

23. Holland J. H. Adaptation in natural and artificial systems./ Holland J. H. //Ann Arbor: University of Michigan Press. 1975.

24. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации./ Еремеев А.В. // Дисс. канд.физ.-мат.наук. Омск, 2000.

25. Александров Н.И. Моделирование организации и управления решением научно-технических проблем./ Н.И. Александров, Н.И. Комков, // М.: Наука, 1988. -216 с.

26. Алтаев В.Я., Теория сетевого планирования и управления/ В.Я. Алтаев, В.Н.Бурков, А.И. Тейман // Автоматика и Телемеханика. 1966. № 5.

27. Баркалов С. А.Минимизация упущенной выгоды в задачах управления проектами/ С.А. Баркалов, В. Н. Бурков, Н.М. Гилязов, П. И. Семенов., -М.: 2001.

28. Баркалов П.С., Задачи распределения ресурсов в управлении проектами./ П.С Баркалов., И.В. Буркова, А.В. Глаголев, В.Н. Колпачев// М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН), 63 с

29. Бурков В.Н. Прикладные задачи теории графов./ В.Н. Бурков, И.А. Горгидзе, С.Е.Ловецкий // -Тбилиси: Мецниереба, 1974. 234 с

30. Арнольд В.И. О функциях трех переменных./ В.И. Арнольд// ДАН СССР, 1957, №2

31. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных./ А.Н. Колмогоров //-ДАН СССР, 1956, 108, №2

32. Баркалов С.А. Прикладные модели в управлении организационными системами./ С.А. Баркалов, В.Н. Бурков, и др.// ИПУ РАН, ВГАСУ, ТГУ, Тула. 2002.

33. Баркалов С.А., Методы агрегирования в управлении проектами./ С.А, Баркалов, В.Н. Бурков, Н.М. Гилязов // М.: ИПУ РАН, 1999. 55 с.

34. Баркалов П.С. Задачи распределения ресурсов в управлении проектами/ П.С. Баркалов, В.Н. Бурков, А.В, Глогольев, В.Н. Колпачев // Москва, ИПУ РАН, 2002г. 52с.

35. Баркалов П.С. Эвристические алгоритмы календарного планирования при управлении проектом/ П.С. Баркалов, В.Н. Бурков, В.Н. Колпачев// Современные сложные системы: сборник трудов Международной конференции,- Воронеж, 2003г. Том1 С.204-207.

36. Бурков В.Н. Теория графов в управлении организационными системами. /В.Н. Бурков, А.Ю. Заложнев, Д.А. Новиков.- М.: СИНТЕГ, 2001. 124 с.

37. Бурков В.Н. Методы решения экстремальных задач комбинаторного типа (обзор)./ В.Н. Бурков, С.Е. Ловецкий // Автоматика и телемеханика 1968, № 11.

38. Бурков В.Н., Методы решения экстремальных комбинаторных задач (обзор)./В.Н. Бурков, С.Е. Ловецкий //Техническая кибернетика-1968, № 4.

39. Бурков В.Н., Буркова И.В. Задачи дихотомической оптимизации. -Материалы международной научно-технической конференции «Системные проблемы качества, математического моделирования, информационных и электронных технологий», Радио и связь, 2003. С. 2328.

40. Басакер Р., Конечные графы и сети. / Басакер Р., Саати Т. М: Наука, 1973. - 368 с.

41. Берж К. Теория графов и ее применения. / Берж К.- М.: Иностранная литература, 1962. 319 с.50.

42. Оре О. Теория графов/ О. Ope.- М: Наука.-1968.-350с.

43. Голыптейн Е.Н. Задачи линейного программирования транспортного типа./ Е.Г. Голыптейн, Д.Б, Юдин.-М.: Наука, 1969

44. Танаев B.C. Теория расписаний. Одностадийные системы./ B.C. Танаев, B.C. Гордон, Я.М. Шафранский. М.: Наука, 1984. - 230 с.

45. Аснина Н.Г. Двойственность в задачах дискретной оптимизации/ Н.Г. Аснина, Н.В. Буркова, П.А. Колесников, Н.В. Попок// Теория активных систем: Труды международной практической конференции. М: ИПУ РАН, 2005.-с. 15

46. Ленина Н.Г. Задача о максимальной циркуляции для агрегируемых графов/ Н.Г. Ленина, С.А. Баркалов, И.В. Буркова // Вестник Воронежского государственного технического университета. -Воронеж: ВГТУ, 2006. том 2, №2 с. 35-42

47. Ленина А .Я. О существовании неотрицательных решений систем линейных уравнений и неравенств специального вида/ Л.Я. Ленина// Вопросы оптимального программирования в производственных задачах. -Воронеж: Изд-во ВГУ, 1980.-С.23-32

48. Ленина Н.Г. Задача о максимальном независимом множестве/ Н.Г. Ленина // Вестник Воронежского государственного технического университета. -Воронеж: ВГТУ, 2006. том 2, №2 с. 20-25

49. Ленина А.Я Модели, алгоритмы, оценки в задаче оптимизации загрузки / А.Я Ленина, Н.Г. Ленина, И.В. Буркова, И.В. Попок// Вестник Воронежского государственного технического университета. Воронеж: ВГТУ, 2006. том 2, №2 с. 3-16

50. Ленина Н.Г. Выбор оптимального набора продуктов/ Н.Г. Ленина, С.В. Серенько, Г.Д. Юшин// Современные сложные системы управления: Сборник трудов научно-практической конференции. Воронеж: ВГАСУ, 2005.-том 2, стр. 123-125

51. Ленина Н.Г. Оптимальная модель последовательности выполнения проектов/ Н.Г. Ленина, И.В. Бурков, A.M. Котенко // Сборник трудов научно-практической конференции. Воронеж: ВГАСУ, 2005.-том 1, стр. 89-941. УТВЕРЖДАЮ1. АКТ

52. Настоящим подтверждаем, что результаты кандидатской диссертации Лениной Н.Г.:----

53. Модель загрузки оборудования, приводящаяся к задаче о камнях с различными объемами групп;

54. Моделирование системы управления в виде графа, имеющего контуры, обнаружение этих контуров и их ликвидация с минимальными потерями;

55. Декан факультета автоматизации и информационных систем, доцент1. Д.К. Проскурин1. УТВЕРЖДАЮнеральный директор1. АКТ19 декабря 2005 г.г. Воронеж

56. О результатах внедрения законченной научно-исследовательской работы по разработке методических рекомендаций по применению моделей эффективнойорганизации проектных работ

57. В период с 5 сентября 2005 г. по 16 декабря 2005 г. в ООО «Агрокс 2» проводилась научно-исследовательская работа по совершенствованию процесса планирования производственной деятельности предприятия.

58. Результатом работы явилась разработка ряда методических материалов по созданию и практическому использованию моделей и методов, основанных на применении методов математического программирования.1. В их числе:

59. Модель загрузки оборудования, приводящаяся к задаче о камнях с различными объемами групп;

60. Моделирование системы управления в виде графа, имеющего контуры, обнаружение этих контуров и их ликвидация с минимальными потерями;

61. Модель выбора множества объектов максимальной суммарной ценности при ограничении на несовместимость пар объектов.

62. Результаты работ получили поддержку и одобрение на заседаниях техник ческого совета.1. Начальник ПТО26 декабря 2005 г.1. АКТг. Воронеж

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

64. Модель загрузки структурных подразделений, приводящаяся к задаче о камнях с различными объемами групп;

65. Модель выбора множества объектов максимальной суммарной ценности при ограничении на несовместимость пар объектов.

66. Результаты работ получили поддержку и одобрение на заседаниях технического совета.1. Начальник ПТО