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

005002279

АЛФЕРОВ ВИКТОР ИВАНОВИЧ

Модели и методы распределения ресурсов при управлении проектами дорожного строительства

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

1 7 НОЯ 2011

Воронеж 2011

005002279

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

Научный консультант: доктор технических наук, профессор

Суровцев Игорь Степанович

Официальные оппоненты: доктор технических наук, профессор

Кульба Владимир Васильевич

доктор технических наук, профессор Львович Яков Евсеевич

доктор технических наук, профессор Бабкин Виктор Филиппович

Ведущая организация: Московский автомобильно-дорожный институт

(государственный технический университет)

Защита состоится «25» ноября 2011 г. в 10:00 часов в ауд. 3220 на заседании диссертационного совета ДМ 212.033.03 при Воронежском государственном архитектурно-строительном университете по адресу: 394006, г. Воронеж, ул. 20-летия Октября, 84.

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

Автореферат разослан «24» октября 2011 г.

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:

- федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»;

з

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

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

Достижение цели работы потребовало решения следующих задач:

1. Проанализировать существующие методы и модели управления дорожным строительством.

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

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

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

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

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

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

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

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

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

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

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

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

3. Задача распределения ресурсов в нескольких пунктах сведена к нелинейной распределительной задаче.

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

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

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

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

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

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

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

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

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

Разработанные модели используются в практике работы ОАО «Орелавто-дор» (г. Орел), ООО ПСК «Домострой» (г. Воронеж), ЗАО «Дороги Черноземья» (г. Воронеж), ФГУ ФУ АД «Черноземье» ФДА (г. Воронеж), ФГУ «Управление автомобильной магистрали Москва - Волгоград ФДА» (г. Тамбов), ВФ ООО «Ин-тердорстрой» (г. Богучар Воронежской области), Управления дорогами Брянской области (г. Брянск), ООО «Магистраль» (г. Тула).

Модели, алгоритмы и механизмы включены в состав учебных курсов

«Управление проектами», «Исследование операций при моделировании социально-экономических систем» и «Организационно-технологическое проектирование», читаемых в Воронежском государственном архитектурно-строительном университете.

На защиту выносятся:

- постановка задач календарного планирования с учетом времени перемещения ресурсов между работами и алгоритм определения продолжительности проекта при заданном потоке ресурсов по графу перемещения ресурсов;

- доказательство того, что в оптимальном решении отсутствуют перемещения ресурсов между работами;

- сведение задачи распределения ресурсов в нескольких пунктах к нелинейной распределительной задаче;

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

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

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

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

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

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

Апробация работы. Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях и семинарах, в том числе на 52-64-й научно-технических конференциях во ВГАСУ (г. Воронеж, 1999-2011); международной научно-практической конференции в МАДИ (г. Москва, 2000); научно-техническом семинаре (г. Астрахань,

2000); международной научно-практической конференции в БелдорНИИ (г. Минск,

2001); научно-практическом семинаре «Новые технологии и материалы, применяемые при содержании автомобильных дорог» (г. Ростов-на-Дону, 2002); научно-практической конференции «Инновационные технологии и процессы в секторе реальной экономики РФ» (г. Москва, 2004); научно-практической конференции «Образование, наука, производство и управление» (г. Старый Оскол, 2003, 2009); всероссийской научно-технической конференции «Управление в организационных системах» (г. Воронеж, 2005, 2007, 2009); X международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (г. Воронеж, 2009); 2-й Всероссийской научно-технической конференции «Управление в организационных системах» (г. Воронеж, 2009) и др.

Публикации. По теме диссертации опубликована 51 печатная работа, в том числе 27 работ опубликовано в изданиях, рекомендованных ВАК РФ.

Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: в работах [8], [9], [16], [24], [30], [32], [40], [48] автору принадлежит постановка задач календарного планирования с учетом времени перемещения ресурсов между работами; в работах [1], [2], [6], [36], [49] - алгоритм определения продолжительности проекта при заданном потоке ресурсов по графу перемещения ресурсов; в работах [3], [5], [12], [23], [35], [44], [46] - задача распределения ресурсов для случая независимых работ; в работах [7], [30], [32], [39], [41], [43], [47] - минимизация продолжительности проекта для случая, когда каждая бригада выполняет не более двух работ; в работах [9], [13], [15], [17], [30], [31], [32], [33] - метод ветвей и границ для задачи определения очередности выполнения работ одной бригадой (единицей ресурсов) при учете времени перемещения бригады от работы к работе при симметричной и несимметричной транспортных схемах; в работах [4], [18], [24], [29], [30], [32], [37] - минимизация штрафов за превышение плановых сроков для случаев линейного, кругового, радиального и произвольного расположения объектов; в работах [14], [19], [33], [38], [42], [45] - оптимальное решение для минимизации отклонения от плановых сроков; в работах [10], [11], [24], [28], [32], [33] - задача планирования ремонта участков дороги.

Объем и структура работы. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложений. Она содержит 278 страниц основного текста, 92 рисунка, 98 таблиц и приложения. Библиография включает 215 наименований.

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

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

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

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

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

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

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

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

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

Состояние любой работы »' в момент / характеризуется объемом работы щ(/), выполненной к этому моменту, и скоростью ее выполнения vl(t)=

А

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

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

При рассмотрении процесса выполнения комплекса работ отмечается, что после выполнения одной работы ресурсы перемещаются на другие работы своего класса, образуя поток по множеству работ. Но существуют случаи, когда перемещение ресурсов с одной работы на другую недопустимо по тем или иным причинам (отсутствие транспортных средств, высокая стоимость или невозможность перемещения данного вида ресурсов и т. д.). Описать возможные варианты перемещения ресурсов между работами возможно путем задания графа перемещений ресурсов (рис. 1). Он состоит из к компонент (по числу классов работ). Вершины графа соответствуют работам, от вершины / идет дуга к вершине у, если возможно перемещение ресурсов от /-й нау'-ю работу. Кроме того, каждой дуге (/,_/) ставят в соответствие время ру перемещения ресурсов от ;'-й работы на /-ю.

Л.

А, Л,

Рис. 1. Граф перемещения ресурсов

Будем считать, что задана сетевая модель комплекса из и работ, в которую входят сетевой график; граф перемещений ресурсов; матрица Цд,Д где - время перемещения ресурсов с 1-й работы нау'-ю; объемы работ и зависимости у;=у,(и,) скорости выполнения /-й работы от количества ресурсов соответствующего вида (предполагаем, что у, - неубывающие функции «/); и, - количество ресурсов; количество ресурсов /?уУ-го вида (/ = 1,2,..., к), где к- число классов операций.

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

Рассмотрим случай независимых работ. Имеется п независимых работ и ресурсы в количестве Л. Задана матрица а=(Цу), /' = 0,п, ] = Тм, времен перемещения ресурсов между работами и времен перемещения ресурсов из пункта О их нахождения к пункту у выполнения работы у. Заданы объемы работ Щ и зависимость Д«,-) скорости выполнения работ от количества ресурсов и„ /=7л. Определим граф перемещений ресурсов, состоящий из (п+2) вершин. Вершина О - это вход сети, соответствующая пункту размещения ресурсов, вершины Тп соответствуют работам проекта, вершина 1 - выход - соответствует пункту сбора ресурсов после выполнения всех работ. Пример графа перемещений ресурсов приведен на рис. 1. Длины дуг равны временам перемещения ресурсов (числа без скобок на рис. 1). Времена перемещения ресурсов к пункту сбора 2 не играют роли, нас интересует время завершения всех работ проекта.

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

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

Пусть / (и;) — вогнутые функции и,-, г = 1,п. Для случая, когда времена перемещений равны нулю, ранее были получены известные условия оптимальности распределения ресурсов:

а) все работы заканчиваются одновременно;

б) все работы выполняются с постоянной интенсивностью.

Из этих условий следует уравнение для определения минимальной продолжительности проекта Т:

где (р, - функция, обратная функции

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

Теорема 1. В оптимальном решении задачи все работы выполняются с постоянной интенсивностью и заканчиваются одновременно.

Доказательство. Из условий теоремы следует, что в оптимальном решении отсутствует перемещение ресурсов между работами. Действительно, если часть ресурсов с одной работы / перемещается на другую у, то интенсивность выполнения работ (' и у изменяется, что противоречит условиям теоремы.

Если же перемещается весь ресурс, то работа 1 завершается раньше работы У, что противоречит условиям теоремы.

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

Рассмотрим другой вариант выполнения объемов работ и щ{Л), а

именно, примем, что ресурсы из начального пункта 0 направляются непосредственно на работы / и у. Для выполнения работы / в объеме г,1>,(Л) за время Т требуются ресурсы в количестве

а для выполнения работы у" в объеме щ{Л) за время Г требуется ресурсы в количестве

(1)

(2)

ю

Заметим, что

T-V« =Т,. +/I, +г, >г, + r,, Г-Д,, = r,. + r, + Д„ + Д, >Т, +Т,,

так как

Из последних соотношений имеем

(6)

где а, = -

«г

Из (5), (6) следует, что ц + < а, А + а;Д = 4.

Таким образом, те же объемы работ / и у могут быть выполнены меньшим количеством ресурсов без перемещения ресурсов с работы / на работу у.

Отсюда следует, что при оптимальном календарном плане отсутствуют перемещения ресурсов с работы на работу. Количество ресурсов, требуемое для выполнения ¿-й работы за время Г, равно

т-ц0,

Минимальная продолжительность проекта определяется из уравнения

2fP

7-к

= R.

(7)

(В)

Заметим, что при /Ль—О уравнение (8) переходит в уравнение (1).

Таким образом, для случая вогнутых зависимостей задача распределения ресурсов эффективно решается на основе уравнения (8). К сожалению, в случае выпуклых зависимостей это не так. Если все fi ¡¡=0 (i, j = \,n), то, как известно, оптимальный календарный план состоит в последовательном выполнении работ максимальным количеством ресурсов. Минимальная продолжительность проекта определяется выражением

+ (9)

где

т. =

w,

f№

(10)

Если //,у (/, у = 1,л) велики, то минимальная продолжительность проекта определяется уравнением (8). Решения задачи в промежуточных случаях неизвестны.

м

Пусть имеются несколько пунктов расположения ресурсов, причем в j-м пункте находятся ресурсы в количестве ЛДу = /,«)• Обозначим - минимальное

время перемещения ресурсов из пункта расположения у к пункту выполнения работы Ху- часть /-й работы, выполняемая ресурсами, расположенными в пункте / Очевидно

= /=Гя. (и)

Если Л^- определены, то продолжительность проекта определяется как минимальное Т, удовлетворяющее системе неравенств

2>

А",.

Г-Л,

<Л , у = 1,/я.

(12)

Задача заключается в определении |лг,у = /,я,у=Лт| и Г, удовлетворяющих

ограничениям (11), (12) и минимизирующих Т.

Можно решать обратную задачу: при заданном Т определить Ху и минимизирующие

5U

(13)

при ограничении (11). Эта задача распадается на п независимых задач минимизации

Jjr,

х.< T-V-n

при ограничении

= w,.

(14)

(15)

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

Рассмотрен случай распределения m > 1 единиц ресурса (бригад). Принято, что каждая бригада выполняет не более двух работ. Пусть задана матрица Цг^Ц времен перехода с одной работы i на другую j. Без ограничения общности можно принять, что п = 2т, то есть количество работ в два раза больше числа бригад. Пусть операции i и j выполняются одной бригадой. Время выполнения двух работ составит Г8 = 11ы + г, + fil+rj.

Су = min (Ту; Tji).

Рассмотрен граф с длинами ребер Су. Задача сведена к выделению в этом графе m ребер (по числу бригад), никакие два из которых не имеют общих вершин. Такое множество ребер называется паросочетанием графа. Таким образом, необходимо найти паросочетание Q, для которого величина ц = шах С., минимальна. В основе метода решения задачи лежит алгоритм определения паросочетания

в графе, в котором оставлены только ребра, для которых Минимальное ц,

при котором существует паросочетание с т ребрами, определяет минимальную продолжительность проекта.

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

Предполагается, что заданы времена перемещения бригады от работы к работе и времена перемещения бригады из пункта расположения к месту выполнения каждой работы, т.е. задана матрица (/г,времен, где ^ - время перемещения

бригады с места выполнения работы / в место выполнения работы ], - время перемещения бригады из места ее расположения в место выполнения работы /", //у0 - время перемещения бригады из пункта у в пункт 0.

Обозначим через г,- продолжительность работы /, I,- момент завершения работы /, £» - планируемый срок завершения работы /. В этом случае разность Д, = г, — £>, определяет величину запаздывания завершения работы /' (срыв плановых сроков) или величину резерва, если I, < Ц. В качестве критерия оптимальности расписания примем величину штрафов

С(Д) = ХС,А1[Д(], (16)

где С; - штраф за единицу превышения планового срока; 1 [Л,] = 0 при 4<0,= 1 при ¿¡>0.

Задача заключается в определении очередности выполнения работ, минимизирующей (16).

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

Если временами (щ) пренебрегать нельзя, то задача становится сложной (ИР-трудной) задачей оптимизации.

В следующих пунктах рассматриваются методы решения задачи для различных транспортных схем.

Обозначим Су +Ту, р) = ту + гшп ¡Л^. Рассмотрим оценочную задачу:

определить очередность выполнения работ /Ч, ...,/„), минимизирующую суммарные штрафы за превышение плановых сроков

(17)

I

при продолжительностях работ />,, у = 1, п.

Утверждение 1. Решение оценочной задачи дает оценку снизу величины штрафов.

Доказательство следует из того, что функция (17) меньше или равна функ-

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

ЪргЬ

С,.

(1В)

Рассмотрим применение метода ветвей и границ. Для этого разбиваем множество всех решений на п подмножеств ()({). В подмножестве (¿(¡) работа / выполняется первой. В этом случае

р =Т: + ттЦу, у*/. (19)

Упорядочим работы по возрастанию />у/су. Пусть это упорядочение О'ь Ь,..., ¿„.О- Оценка снизу равна

5(0 = СДг,.-/>,.)1[т,-4.]+ХС,.

У-1

Л

(20)

Из всех подмножеств выбираем подмножество с минимальной оценкой.

Рассмотрим общий шаг алгоритма. Обозначим (}(/,, Ь, ...,/'*)- подмножество решений, в котором зафиксирована очередность выполнения первых к работ (¿1,1*2, ...,/*). Разобьем его на (п-к) подмножеств 0(('и Ь,..., где

ее 0(/|, Ь,

Определяем

1 1 1*0,1, ,12,..,ц 9

Упорядочим оставшиеся («-¿-1) работ по возрастанию отношения Ру/су. Пусть это упорядочение (/|, <2,..., ¡„-к-/). Оценка снизу для этого подмножества равна

¡1 1г

где Г;

Из всех («-/:) подмножеств выбирается подмножество с минимальной оценкой.

Рассмотрены частные случаи задачи, когда все пункты расположены в линию (например, вдоль автострады) (рис. 2).

pJ=TJ+mm(qj-<^и,qj+í-qj), д0=О (22)

о,

Рис. 2. Линейная схема расположения объектов

Описанный подход можно применить к ряду других схем расположения пунктов. Пусть все пункты расположены вдоль кольцевой дороги (рис. 3).

В случае одностороннего движения оценка р, определяются следующим выражением:

О- (23)

В общем случае для множества (КЛ, ь, ..., /<., .у) имеем

Р) = т,+ т'п

1 ' .....' '

Сама оценка определяется выражением (21).

Рис. 3. Кольцевая схема

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

Л=ТУ + „т'п к/ -9,1- (24)

Сама оценка определяется выражением (21).

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

41 Чг Чз 44 45

О, Г>) О, 01

Рис. 4. Линейная схема расположения объектов

В этом случае р, определяется тем же выражением (24), а оценка — выражением (21).

Рассмотрим еще один частный случай, когда транспортная схема является радиальной (рис. 5).

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

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

Таким образом, время перехода бригады от пункта / в пункт у равно

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

В данном случае для подмножества <30° ь |Ч,..., >ь л) величина Pj равна

а сама оценка определяется выражением (21).

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

Построим транзитивное замыкание сети (рис. 6), то есть проведем дуги (/,Д если существует путь из вершины / в вершину У (эти дуги показаны на рис. 4 пунктиром). Очевидно, что переход с работы у на работу I не может быть, если дуга (/, у) присутствует в сети. Поэтому положим / м = », если (/, у)е II (где и -

множество дуг транзитивного замыкания). Далее отметим, что последними могут выполняться только конечные работы (это работы 4 и 5). Наконец, первыми могут выполняться только начальные работы, то есть работы 1 и 2. Далее метод ветвей и границ применяется так же, как для симметричной и несимметричной транспортных схем.

= Д+£*,..

Рис. 5. Радиальная схема

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

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

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

Обозначим через и плановый момент начала <-й работы. Примем, что моменты г,- заданы (а значит, заданы и моменты £).=<, +тД и требуется обеспечить выполнение всех работ минимальным числом бригад. Построим сеть следующим образом. Вершины сети / соответствуют работам проекта.

Вводим две новые вершины - вход 0 и выход 2.

Вход соответствует пункту начального расположения бригад, а выход -пункту их сбора после выполнения проекта. Соединим вход 0 с вершиной если ¿(0( < , вершины I и у соединим дугой (у), если Гу -В1 < . Наконец, вершины /

соединяем с выходом 2. Примем пропускные способности вершин равными 1. Определим допустимый поток {У'у} по сети как поток, удовлетворяющий условиям

7*0.2. (26)

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

Ниже описывается другой подход, в основе которого лежит метод сетевого программирования на основе понятия агрерируемой сети.

Определение 1. Множество вершин называется параллельным, если у них совпадают множества непосредственно предшествующих вершин и совпадают множества непосредственно последующих вершин.

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

Определение 2. Множество вершин называется последовательным, если все вершины, за исключением первой и последней, имеют степени исхода и захода, равные единице (рис. 7).

Рис. 7. Последовательное множество вершин сетевого графика

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

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

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

Имеет место следующая теорема.

Теорема 2. Величина максимальной пропускной способности разреза преобразованной сети является оценкой снизу максимальной пропускной способности разреза исходной сети.

Эта теорема является следствием более общей теоремы для оценочных задач в методе сетевого программирования.

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

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

Из описанного алгоритма следует теорема.

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

На рис. 8 приведена неагрегируемая сеть, а на рис. 9 - преобразованная агрегированная сеть (вершина 3 разбита на две вершины 3.1 и 3.2).

Рис. 8. Сеть без контуров

В нижних половинах кружков указаны пропускные способности вершин. Оптимальное разделение пропускной способности вершины 3 приведено на рис. 9 (О для вершины 3.1 и 1 для вершины 3.2).

Поток минимальной величины (разрез максимальной пропускной способности) для рис. 9 равен 2 и равен потоку минимальной величины (разрезу макси-

мальной пропускной способности) для исходной сети (рис. 8). Заметим, что любое другое разбиение дает оценку сверху. Так, при делении пропускной способности вершины 3 пополам получаем поток минимальной величины в преобразованной сети, равный 2,5, что больше 2.

ной схемы. Сначала проведем некоторые преобразования, упрощающие задачу. Во-первых, увеличим плановые сроки Д на величину Д (время возвращения бригады с работы / в пункт размещения), прибавив величину Д к продолжительности работы г'=т + Д.

Во-вторых, прибавим к продолжительности работы время а, перемещения бригады в пункт /. Смысл этого преобразования в том, что продолжительность работы считается равной времени с момента отправления бригады в пункт / из пункта размещения до момента ее возвращения в пункт размещения после выполнения работы ¡. После сделанных преобразований можно не учитывать времен перемещения бригад, а учитывать только продолжительность работы т'=а, + г, + Д и плановый срок завершения С' = Д+ Д . С учетом сказанного плановый срок завершения работы и ее продолжительность будем обозначать, как и ранее, Д и т; соответственно. Предположим, что каждая работа может выполняться одновременно несколькими бригадами с соответствующим уменьшением продолжительности (если две бригады, то в два раза, если три, то в три, и т.д.). Построим на плоскости систему координат, ось абсцисс которой соответствует моментам времени, а ось ординат - временам выполнения работ. Каждому значению Д оси абсцисс поставим в соответствие точку (/*,, Д), где Л, - суммарная продолжительность работ от 1 до / , то есть О, (считаем, что Д упорядочены по возрастанию, то есть Д <Д <... <Д). Соединяя точки (/', Д) и (/ + 1, Д) горизонтальными линиями, а точки (/, О,), (/, Д+0 вертикальными линиями, мы получим область допустимых состояний комплекса работ. На рис. 10 приведен пример такой области для значений т, и Д, приведенных в табл.

Построим кратчайшую траекторию, соединяющую начало координат с точкой А=фюТ), (Т = ), соответствующей выполнению всех работ за время Д,. (траектории ОВА).

ВС 21,3

Ье максимальный наклон-= — = 1— определяет минимальное количест-

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

Таблица

i 1 2 3 4 5 6

*¡ 2 4 4 4 7 3

А 4 6 8 9 12 16

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

Пусть число бригад равно т. Обозначим через x¡f= 1, если /-я работа выполняется у-й бригадой, x¡j= 0 - в противном случае. Имеем ограничения

£хв = /. i=Tn. (27)

i'l

Для записи целевой функции примем, что D¡ упорядочены по возрастанию, то есть D[< Dj< ...<D„). Запишем неравенства:

k=Tñ,j=Tm. (28)

i'i

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

Заметим, что все работы, выполняемые у-й бригадой, выполняются в очередности возрастания £>,-, то есть в очередности их номеров. Так как x¡j— 1, то *

£Vi определяет момент завершения работы к.

>=■1

Если же -т,у=0, то (28) следует из выполнения этого неравенства для q < к.

Таким образом, задача заключается в минимизации

Д = тахшах

IV,--А

при ограничениях (27).

Для применения метода сетевого программирования зафиксируем Л и рассмотрим следующую задачу: определить {ху,1 = 1,п, у = 1 ,т}, максимизирующие

при ограничениях (28)и

в=25>,г< (30)

I — 1,п. (31)

Разделим систему ограничений на две группы. В первую группу входят в ограничения (31), а во вторую - ограничения (28). Соответственно разделим продолжительности работ 1} на две части _у,уи т, -уу , 1-=\,п, ]=\,т.

Получим две группы оценочных задач. Первая группа: определить ху, j = 1 ,т,

максимизирующие /•;(>>,,) = Л "Р" ограничении ^ < 1.

У .1'

Ее решение очевидно: = шаху, .

]

Заметим, что исходя из требования минимизации оптимальных значений целевых функций оценочных задач следует взять .у,, = >»,- для всех/ В этом случае сумма оптимальных значений оценочных задач первой группы составит

У = ±у,. (32)

/=1

Вторая группа: определить Ху, максимизирующие

(33)

при ограничениях

(34)

м

Заметим, что все т оценочных задач второй группы совпадают. Поэтому мы имеем дело всего с одной задачей (33), (34), где ху можно обозначить через х,.

Обозначим через 2 оптимальную величину (33) в задаче второй группы при заданных {у,-}. Тогда значение целевой функции оценочной задачи равно

Ф(2,у) = тг+У. (35)

Обозначим через {*/} совокупность N допустимых решений системы (34), упорядоченных по убыванию величин:

Двойственная задача заключается в определении 1 и {у,}, минимизирующих (35), при ограничениях

Опишем алгоритм решения двойственной задачи. / шаг. Полагаемого, i = l,n,Z=M\, определяем Ф\=тМ\. 2 шаг. Полагаем Z = Mi. Если М> = Mi, то полагаем Z = М) и т.д. до тех пор, пока при Z = Mq, Mq < Mi. Решаем следующую задачу линейного программирования: найти min при ограничениях

определяем Фч- тМч+Уя, где Уч - оптимальное решение.

Если Фч=Фи то получена оптимальная верхняя оценка критерия (35). Если Фй<Фи то повторяем шаг 2, полагая 1 и т.д.

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

Если полученная верхняя оценка тМ+У<Т, то при данном значении Л решения не существует. В этом случае увеличивается А до появления хотя бы одного нового допустимого решения системы (34).

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

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

Ремонт производится с целью снижения этого показателя до величины, позволяющей вести эксплуатацию данного участка дороги. Если ремонт не производится в текущем плановом периоде, то либо ограничиваются возможности эксплуатации данного участка, либо он вообще закрывается для проезда (определяются объездные пути). Затратив дополнительные средства, можно обеспечить величину степени опасности меньше требуемого нормативного уровня, что приводит как к уменьшению степени опасности, так и к увеличению срока эксплуатации данного участка дороги. Примем, что определена зависимость у; = ¡р,(х,) степени опасности /-го участка дороги после ремонта от величины средств на ремонт. Рассмотрим два вида таких зависимостей - непрерывные и дискретные.

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

+ Z>Mt,k = \,N.

(37)

> М,-Л/=!,<?-1,

(38)

для финансирования ремонта всех участков, требующих ремонта. Как уже отмечалось выше, если ремонт участка не производится в планируемом периоде, то ограничение либо запрещение эксплуатации данного участка приводит к потерям. Обозначим b¡ потери (ущерб) в случае, если ремонт /-го участка не производится в планируемом периоде; d¡ - затраты на уменьшение степени опасности до нормативного уровня.

Тогда суммарный ущерб можно записать в виде

*(б) = 24. (41)

'«У

где Q - множество ремонтируемых участков, а суммарные затраты

DiS)=2d,

ieQ

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

(42)

«у

где С - величина средств на ремонт в планируемом периоде.

Задача 1. Определить множество Q ремонтируемых участков, так, чтобы минимизировать (41) при ограничении (42).

Представим задачу 1 в виде задачи целочисленного линейного программирования в переменных {0,1}. Для этого примем z¡= 1, если участок i включен в план ремонта, и г, = 0 - в противном случае. Тогда критерий (41) запишется в виде

B(x) = ±b,(\-z,) = ±b-±b¡z¡. (43)

/-i /.i ..i

Очевидно, что задача минимизации (43) эквивалентна задаче максимизации

K(z) = £hz, (44)

i=i

при ограничении (42).

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

используется не полностью, то есть Д =C-r£/d¡ >0, где Q - множество участков,

щ)

включенных в план ремонта.

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

Введем новую переменную и, = xrd¡, равную величине дополнительных средств, выделенных для ремонта /-го участка. Функцию <рДх, ) = (р(и + d.) будем обозначать для простоты <£>,(",)■

Задача 2. Определить минимизирующие

при ограничении

£н<Д. (46)

«с

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

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

Пусть ?>,(«,) - выпуклые функции. В этом случае получаем задачу выпуклого программирования, методы решения которой хорошо разработаны. С точки зрения практики можно всегда принять, что функция <рДгл) является кусочно-линейной с отрезками линейности единичной длины. В этом случае существует эффективный алгоритм решения задачи. Обозначим

га = ¥>(*)+1), 0<Л <Д-d, =т1,

где Di -d¡ - максимальная величина дополнительных средств.

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

Если <p,(u¡) являются вогнутыми функции, то задача становится многоэкстремальной, и для ее решения следует применять комбинаторные методы.

Рассмотрим применение метода ветвей и границ для решения задач. Для этого, в первую очередь, необходимо иметь метод получения нижней оценки критерия (45).

Построим выпуклую функцию Ц(и), максимально близкую к функции <р(и). Как легко видеть, это линейная функция.

Если теперь решить задачу минимизации

Ф(и) = ЪЪ(»,) (47)

<9

при ограничении (46), то мы получим нижнюю оценку критерия (45) исходной задачи. Эту оценку можно взять для оценки подмножеств в методе ветвей и границ. Сформулируем ряд простых утверждений о свойствах оптимального решения оценочной задачи (46), (47).

Утверждение 2. Если в решении оценочной задачи для любого / имеет место «¡=0 либо u¡=m¡, то полученное решение является оптимальным для исходной задачи.

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

Утверждение 3. Существует решение оценочной задачи, для которого имеется не более одного /, имеющего 0 <и,< m.

Из утверждения 3 следует естественный способ разбиения множества всех решений на подмножества. А именно, находим номер к, такой, что £><«, <mt, и делим множество всех решений на два подмножества. В первом подмножестве и < а во втором - у > ii . Далее строим оценочные функции в каждом из отрезков [f/Ujt*] и ffi^ и решаем оценочные задачи.

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

Рассмотрим частный случай задачи, когда отрезки [</„£>,] имеют одинаковые длины 8, = Dt - dt =5, ) = Л п.

Пусть Д = р• 5 + s, где 0<s<&.

В этом случае для р участков в оптимальном решении u=â, что соответствует минимальной степени опасности, а для одного участка u=s. Пусть участки пронумерованы в очередности убывания iij=ç,{0) - ç,(â).

Определяем

Обозначим через t номер участка с максимальной величиной ff,(s).

Рассмотрим два случая.

1 случай. Пусть t> р. В этом случае оптимальное решение имеет вид

«( = 8, i = 1, р, и, = s,

остальные и,=0. Доказательство достаточно очевидно следует из того факта, что мы берем р самых больших я, и одну самую большую 7r,(s).

Рассмотрим теперь второй случай, когда t<p. Имеются два варианта.

1 вариант. Определяем участок г с максимальной величиной 7r,(j) среди всех участков с номерами i > р + 1. Берем решение и, =ô,i = \,p, ur=s, остальные и,=0.

2 вариант. Рассматриваем (/т+1) участков и определяем участок с минимальной величиной

xl-x,(s),i = ],p+]. (48)

Пусть это участок с номером к. Берем решение и, = 8,/ = 1, к-1,к + 1,р+1, ut=s, остальные и,=0.

Сравнивая эти два решения, берем лучшее.

Обоснование алгоритма следует из того, что единственный участок с i//=s может быть либо среди участков с номерами, большими чем {р+1), либо среди участков с номерами не больше (р+1). В первом случае это, очевидно, участок с

максимальной величиной гг,(.$), то есть участок с номером г.

Во втором варианте величина (48) определяет увеличение целевой функции, если для участка» взять к, = s вместо и, = <5. Очевидно, следует выбрать участок, для которого это увеличение минимально.

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

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

Согласно плану каждый объект должен быть сдан к определенному сроку. Особенно это касается таких дорожных элементов, как мостовые переходы, примыкания и пересечения, водоотвод и водопропускные трубы. Жесткость срока сдачи объекта будет определяться его важностью для обеспечения движения на дороге. Рассмотрим случай, когда на одной трассе объекты располагаются произвольно и могут быть соединены некоторой замкнутой линией. Такую схему называют кольцевой. Приведена процедура оптимизации календарного плана в данном случае. В качестве примера рассматриваются запланированные на 2008 г. дорожно-строительные работы в Лискинском районе.

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

В качестве примера рассмотрен план работы бригад для выполнения запланированных работ в Лискинском районе на 2008 г.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

обобщающее известное уравнение, в котором время перемещения ресурсов равно нулю.

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

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

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

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

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

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

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

11. Разработанные модели, обеспечивающие рациональное использование производственных ресурсов при их распределении во времени и пространстве с учетом специфики дорожного строительства, используются в практике работы ОАО «Орелавтодор» (г. Орел), ООО ПСК «Домострой» (г. Воронеж), ЗАО «Дороги Черноземья» (г. Воронеж), ФУАД «Черноземье» ФДА (г. Воронеж), ФГУ «Управление автомобильной магистрали Москва - Волгоград ФДА» (г. Тамбов), ВФ ООО «Интердорстрой» (г. Богучар Воронежской области), Управления дорогами Брянской области (г. Брянск), ООО «Магистраль» (г. Тула).

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

Статьи, опубликованные в изданиях, рекомендованных ВАК РФ

1. Алферов, В.И. Механизмы распределения корпоративных заказов / В.И. Алферов, В.Н. Бурков, В.Л. Порядина, В.Н. Шипилов // Вестник Воронеж.

гос. техн. ун-та. - 2008. -Т. 4, № 2. - С. 63-67.

2. Алферов, В.И. Оптимальное размещение проекта во времени / С.А. Баркалов, A.B. Беликов, В.И. Алферов, Д.А. Хвастунов Н Вестник Воронеж, гос. техн. ун-та. - 2008. - Т. 4, №3. - С. 79-83.

3. Алферов, В.И. Методы решения задач максимизации прибыли дохода оператора при условии поставки ресурса в любом периоде / В.И. Алферов, C.B. Володин, Д.А. Хвастунов // Системы управления и информационные технологии. - 2008. - №2.1 (32). - С. 111-114.

4. Алферов, В.И. Неманипулируемые механизмы распределения финансовых ресурсов / В.И. Алферов, А.Е Кравцов, Е.Г. Оноприенко II Системы управления и информационные технологии. - 2008. - №2.1 (32).-С. 114-118.

5. Алферов, В.И. Повышение эффективности деятельности предприятий корпорации на основе механизма обмена ресурсами / В.И. Алферов, В.Н. Бурков, С.А. Пузырев // Системы управления и информационные технологии. - 2008. - X» 2.3(32).-С. 319-322.

6. Алферов, В.И. Игровой анализ моделей системы «поставщик-потребитель» / В.И. Алферов, С.А. Баркалов, В.Н. Бурков, А.Е. Кравцов // Вестник Воронеж, гос. техн. ун-та. - 2008. - Т. 4, № 11. - С. 85 - 89.

7. Алферов, В.И. Решение многоэкстремальных задач распределения ресурсов на основе метода дихотомического программирования / В.И. Алферов, И.В. Буркова, A.B. Никитено, A.B. Сенюшкин // Вестник Воронеж, гос. техн. унта.-2008.-Т. 4, № 12.-С. 166-169.

8. Алферов, В.И. Разработка графиков движения бригад по объектам строительства . / В.И. Алферов, С.А. Баркалов, Г.Д. Юшин // Вестник Воронеж, гос. техн. ун-та. - 2009. - Т. 5, № 1. - С. 30 - 35.

9. Алферов, В.И. Очередность выполнения работ на основе симметричной транспортной схемы / В.И. Алферов, С.А. Баркалов, А.Е. Кравцов // Вестник Воронеж. гос. техн. ун-та. - 2009. - Т. 5, № 2. - С. 99 - 103.

10. Алферов, В.И. Механизмы классификации работ при ремонте мостовых сооружений / В.И. Алферов, В.О. Скворцов // Вестник Воронеж, гос. техн. унта. - 2009. - Т. 5, № 6. - С. 30 - 33.

11. Алферов, В.И. Управление рисками при выполнении мероприятий развития автомобильных дорог / В.И. Алферов, А.Е. Кравцов // Вестник Воронеж, гос. техн. ун-та.. - 2009. - Т. 5, № 6. - С. 41 - 44.

12. Алферов, В.И. Декомпозиционные механизмы согласования экспертных оценок / В.И. Алферов, С.А. Баркалов, В.Н. Бурков II Системы управления и информационные технологии. - 2009. - № 2.2 (36). - С. 217 - 220.

13. Алферов, В.И. Корпоративные механизмы обмена ресурсами / В.И. Алферов, А.Е. Кравцов, Ю.А. Карпов // Системы управления и информационные технологии. - 2009. - № 2.2 (36). - С. 220 - 224.

14. Алферов, В.И. Неманипулируемый механизм согласования экспертных оценок / В.И. Алферов, В.Н. Бурков, Б.В. Тарасов // Вестник Воронеж, гос. техн. ун-та. - 2009. - Т. 5, № 10. - С. 181 - 185.

15. Алферов, В.И. Двухэтапный конкурсный механизм отбора проектов . / В.И. Алферов, С.А. Баркалов, A.B. Сенюшкин, А.Е. Кравцов // Вестник Воронеж.

гос. техн. ун-та. - 2009. - Т. 5, № 11. - С. 144 - 146.

16. Алферов, В.И. Задачи календарного планирования с учетом времени перемещения ресурсов / В.И. Алферов В.И., В.Н. Бурков, А.Е. Кравцов, А.В. Се-нюшкин // Вестник Воронеж, гос. техн. ун-та. - 2009. - Т. 5, № 11. - С. 217 - 220.

17. Алферов, В.И. Определение оптимальной очередности выполнения строительных работ бригадой с учетом времени перемещения ресурсов . / В.И. Алферов, П.С. Баркалов, А.Е. Кравцов // Вестник Воронеж, гос. техн. ун-та. -2009. - Т. 5, № 11. - С. 235 - 237.

18. Алферов, В.И. Задача поиска оптимальной иерархии в зависимости от функции затрат / В.И. Алферов, С.А. Баркалов, И.Ф. Набиуллин, Ю.А. Черенков // Вестник Воронеж, гос. техн. ун-та. - 2009. - Т. 5, № 11. - С. 237 - 240.

19. Алферов, В.И. Механизмы агрегирования последовательных и параллельных моделей на сетевые графики / В.И. Алферов, П.Н. Курочка Н Известия Тул. гос. ун-та. - 2009. - Вып. 13. - С. 222 - 231.

20. Алферов, В.И. Исследование моделей и механизмов управления проектами с учетом топологии / В.И. Алферов II Вестник Воронеж, гос. техн. ун-та. -2011. - Т. 7, № 3. - С. 252-257.

21. Алферов, В.И. Механизмы распределения ресурсов в классификационной модели / В.И. Алферов // Вестник Воронеж, гос. техн. ун-та. - 2011. - Т. 7, № 4.-С. 173-178.

22. Алферов, В.И. Распределение ресурсов типа мощности с учетом времени их перемещения / В.И. Алферов // Вестник Воронеж, гос. техн. ун-та. - 2011. -Т. 7, №4.-С. 229-233.

23. Алферов, В.И. Определение планов анализа и оптимизации комплекса операций при перемещении ресурсов / В.И. Алферов, О.В. Будков, В.Н. Бурков // Вестник Воронеж, гос. техн. ун-та. - 2011. - Т. 7, № 5. - С. 171 -174.

24. Алферов, В.И. Учет времени перемещения производственных ресурсов при подготовки производства / В.И. Алферов, В.Н. Колпачев, И.С. Суровцев // Вестник Воронеж, гос. техн. ун-та. - 2011. - Т. 7, № 8. - С. 206-211.

25. Алферов, В.И. Задачи оптимального распределения ресурсов инновационных проектов / В.И. Алферов // ИнВестРегион. - 2011. - №1. - С. 47 - 51.

26. Алферов, В.И. Определение оптимальной очередности выполнения работ при линейном расположении объектов строительства / В.И. Алферов // Вестник МАДИ. - 2011. - № 2 (в печати).

27. Алферов, В.И. Оптимизация движения бригад при радиальном расположении объектов / В.И. Алферов // Вестник МАДИ. - 2011. - № 2 (в печати).

Монографии

28. Алферов, В.И. Организация экологического и технологического аудита автомобильных дорог / Вл.П. Подольский, B.C. Турбин, В.И. Алферов, А.Н. Ка-нищев. - Воронеж: ВГАСУ, 1999. - 173 с.

29. Алферов, В.И. Модели и механизмы управления недвижимостью / С. А. Баркалов [и др.]. - М.: Уланов-пресс, 2007. - 309 с.

30. Алферов, В.И. Прикладные задачи управления строительными проектами / В.И. Алферов [и др.]. - Воронеж: Центрально-Черноземное книжное издательство, 2008. - 765 с.

31. Алферов, В.И. Модели и механизмы в самоорганизующихся системах / В.И. Алферов [и др.]. - Воронеж: Научная книга, 2008. - 300 с.

32. Алферов, В.И. Управление проектами в дорожном строительстве / В.И. Алферов, С.А. Баркалов, П.Н. Курочка. - Воронеж: Научная книга, 2009. - 340 с.

Методические рекомендации, пособия

33.Алферов, В.И. Основы научных исследований по управлению строительным производством: лаб. практикум / В.И. Алферов [и др.]. - Воронеж: Научная книга, 2011. - 188 с.

Статьи, материалы конференций

34. Алферов, В.И. Повышение надежности автомобильных дорог / В.И. Алферов // Тезисы докладов международной научно-практической конференции. -М: МАДИ, 2000. - С. 189-191.

35.Алферов, В.И. Согласование экспертных оценок методом декомпозиции / В.Н. Бурков, В.И. Алферов, C.B. Володин, Р.Ю. Беляев // Образование, наука, производство и управление: материалы науч.-практ. конф. - Старый Оскол, 2003. -T. III.-С. 119—126.

36.Апферов, В.И. Игровой анализ некоторых моделей системы «поставщик-потребитель» / В.И. Алферов, С.А. Баркалов, В.Н. Бурков, А.Е. Кравцов // Управление в организационных системах: материалы всерос. науч.-техн. конф. - Воронеж, 2005. - С. 57-65.

37.Алферов, В.И. Управление организационной системой при полной информированности и полной централизации планирования / В.И. Алферов, В.Н. Бурков, Т.В. Мещерякова, О.В. Мещеряков // Управление в организационных системах: материалы всерос. науч.-техн. конф. - Воронеж, 2007. - С. 133 - 145

38.Алферов, В.И. Способы агрегирования сетевых графиков для строительного производства / В.И. Алферов, С.А. Баркалов, В.Г. Тельных // Управление в организационных системах: материалы всерос. науч.-техн. конф. - Воронеж, 2009. -T. 1.-С. 114-123.

39.Алферов, В.И. Решение многоэкстремальных задач распределения ресурсов на основе метода дихотомического программирования / В.И. Алферов, И.В. Буркова, В.А. Керусова // Управление в организационных системах: материалы всерос. науч.-техн. конф. - Воронеж, 2009. - Т. 1. - С. 127-131.

40.Алферов, В.И. Модель определения вариантов содержания объектов недвижимости придорожного сервиса / С.А. Баркалов, В.И. Алферов // Инновации в сфере науки, образования и высоких технологий: материалы 64-й всерос. науч.-практ. конф. - Воронеж, 2009. - С. 5-8.

41.Алферов, В.И. Механизм оптимального распределения ресурсов при вогнутых зависимостях скорости работ в задаче календарного планирования / В.И. Алферов, В.Н. Бурков, В.А. Левочкин // Образование, наука, производство и управление: материалы междунар. науч.-практ. конф. - Старый Оскол, 2009. - Т. 2.-С. 217-220.

42. Алферов, В.И. Механизм агрегирования последовательных и параллельных моделей при реализации строительных проектов / В.И. Алферов, С.А. Баркалов,

А.Ю. Стуков И Образование, наука, производство и управление: материалы между-нар. науч.-практ. конф. - Старый Оскол, 2009. - Т. 3. - С. 16 - 22.

43.Алферов, В.И. Алгоритм принятия решения по выбору к производству конкретного товара / В.И. Алферов, П.Н. Курочка, А.Е. Кравцов // Образование, наука, производство и управление: материалы междунар. науч.-практ. конф. -Старый Оскол, 2009. - Т. 3. - С. 22 - 28.

44. Алферов, В.И. Обменные схемы в задачах корпоративного обмена ресурсами / В.И. Алферов, Д.Н. Стеганцев // Образование, наука, производство и управление: материалы междунар. науч.-практ. конф. - Старый Оскол, 2009. - Т. З.-С. 117-122.

45.Алферов, В.И. Построение оптимального календарного плана выполнения всех работ проекта / В.И. Алферов, И.Ф. Набиуллин, Е.А. Сидоренко И Образование, наука, производство и управление: материалы междунар. науч.-практ. конф. - Старый Оскол, 2009. - Т.З. - С. 88 - 91.

46.Алферов, В.И. Оптимальное распределение ресурсов в задачах календарного планирования / В.И. Алферов, С.А. Баркалов, Е.А. Сидоренко И Образование, наука, производство и управление: материалы междунар. науч.-практ. конф. -Старый Оскол, 2009. - Т.З. - С. 88 - 91.

47.Алферов, В.И. Процесс управления системой внешних взаимодействий при функционировании и развитии некоммерческого дорожного фонда / А.С. Амплеев, В.И. Алферов, Н.М. Подвальная // Инновации в сфере науки, образования и высоких технологий: материалы 65-й всерос. науч.-практ. конф. -М., 2010. - С. 45-49.

48.Алферов, В.И. Модель определения вариантов содержания объектов недвижимости / В.И. Алферов, С.А. Баркалов II Инновации в сфере науки, образования и высоких технологий: материалы 65-й всерос. науч.-практ. конф. -М., 2010. -С.49-54.

49.Алферов, В.И. Модель календарного графика с учетом времени перемещений бригад / В.И. Алферов, С.А. Баркалов // Инновации в сфере науки, образования и высоких технологий: материалы 65-й всерос. науч.-практ. конф. - М., 2010.-С. 54-58.

50.Апферов, В.И. Разработка алгоритмов построения двойной сетевой модели проекта / В.И. Алферов // Вестник Воронеж, гос. арх.-строит. ун-та. Серия: Управление строительством. - 2011. - № 3 (в печати).

51. Алферов, В.И. Распределение ресурсов одного вида методом пропорционального растяжения / В.И. Алферов // Вестник Воронеж, гос. арх.-строит. ун-та. Серия: Управление строительством - 2011. - № 3 (в печати).

Подписано в печать 21.10.2011. Формат 60*84 1/16. Усл. печ. л. 2,0.

Бумага лисчад. Тираж 100 экз. Заказ № _

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