Следующим сообщением я отправлю тебе фрагмент текста научной диссертации. Ты должен…
- User
Следующим сообщением я отправлю тебе фрагмент текста научной диссертации. Ты должен принять, обработать и изучить всю полученную информацию. После чего мы продолжим. Напиши “хорошо”, если ты все понял. А потом напиши “принял”, когда получишь и обработаешь сам текст
- Assistant
Хорошо.
- User
СОДЕРЖАНИЕ В в е д е н и е .......................................................................................................................................... 4 1. АНАЛИЗ МОДЕЛЕЙ УПРАВЛЕНИЯ ПРОЕКТАМИ ЛИНЕЙНО-ПРОТЯЖЕННОГО СТРОИТЕЛЬСТВА..............................................16 1.1. Автомобильные дороги как объект управления..................................................... ]6 1.2. Организационно-технологическое проектирование линейно-протяженных объектов.............................................................................................22 1.3. Методы решения организационно-управленческих задач при строительстве автомобильных дорог............................................................................36 1.4. Методы решения задач дискретной оптимизации...................................................40 1.5. Методы сетевого и дихотомического программирования....................................51 1.6. Выводы и постановка задач исследования.................................................................56 2. ИССЛЕДОВАНИЕ МОДЕЛЕЙ И МЕХАНИЗМОВ УПРАВЛЕНИЯ ПРОЕКТАМИ С УЧЕТОМ ТОПОЛОГИИ...............................59 2.1. Исследование двойной сетевой модели ......................................................................59 2.2. Разработка классификационной модели объектов строительства по топологическому признаку................................................................................................69 2.3. Механизмы распределения ресурсов в классификационной модели ..............74 2.4. Задачи календарного планирования с учетом времени перемещения ресурсов.......................................................................... 97 3. ЗАДАЧИ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ОЧЕРЕДНОСТИ ВЫПОЛНЕНИЯ РАБОТ......................................................................................................104 3.1. Постановка задач ..............................................................................................................104 3.2. Линейная транспортная схема .....................................................................................119 3.3. Метод ветвей и границ....................................................................................................120 3.4. Оптимизация календарного графика для радиальной транспортной схемы..................................................................................125 3.5. Определение оптимальной очередности выполнения работ для произвольного сетевого графика ..................................................................................126 4. ПОСТРОЕНИЕ ОПТИМАЛЬНЫХ РАСПИСАНИЙ ДЛЯ НЕСКОЛЬКИХ БРИГАД.......................................................................................129 4.1. Постановка задачи...........................................................................................................129 4.2. Задача минимизации числа бригад при заданных сроках начала работ 129 4.3. Геометрический подход к задаче минимизации числа бригад для радиальной транспортной схемы............................................................................... 138 4.4. Метод дихотомического программирования.........................................................140 5. МЕТОДЫ ОПТИМИЗАЦИИ ПЛАНОВ РЕМОНТА УЧАСТКОВ АВТОМОБИЛЬНОЙ ДОРОГИ...........................................................149 5.1. Постановка задачи...........................................................................................................149 5.2. Методы решения задачи минимизации ущерба....................................................152 5.3. Методы решения задачи минимизации суммарной степени опасности участков дороги...........................................................162 3 5.4. Методы решения задачи минимизации линейной свертки степени опасности и ущ ерба...........................................................164 5.5. Современные принципы содержания и эксплуатации мостовых сооружений............................................................................170 5.6. Классификация работ по содержанию мостовых сооружений........................177 5.7. Существующие стратегии содержания и эксплуатации мостовых сооружений............................................................................185 5.8. Планирование работ по содержанию мостов........................................................195 5.9. Модель определения вариантов содержания мостовых сооружений 202 5.10. Задачи формирования производственной программы....................................214 5.11. Методы решения задачи минимизации ущерб...................................................216 6. ФОРМИРОВАНИЕ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ ДОРОЖНО-СТРОИТЕЛЫЮГО ПРЕДПРИЯТИЯ.............................................238 6.1. Определение оптимальной очередности при линейном расположении объектов строительства.............................................238 6.2. Оптимизация календарного плана работы предприятия при кольцевой системе расположения объектов строительства............................244 6.3. Оптимизация движения бригад при радиальном расположении объектов.......................................................................252 Заключение................................................................................................................................256 Л и т е р а т у р а ................................................................................................................................. 2 5 9 Приложения...............................................................................................................................280
7 Методы исследования. В работе использованы методы моделирова ния организационных систем управления, системного анализа, математиче ского программирования. Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
- Дана постановка задач календарного планирования с учетом време ни перемещения ресурсов между работами, и предложен алгоритм определе ния продолжительности проекта при заданном потоке ресурсов по графу пе ремещения ресурсов.
- Решена задача распределения ресурсов для случая независимых ра бот. Доказано, что в оптимальном решении отсутствуют перемещения ресур сов между работами. Получено уравнение для минимальной продолжитель ности проекта, обобщающее соответствующее уравнение В.Н. Буркова, в ко тором время перемещения ресурсов равно нулю.
- Задача распределения ресурсов в нескольких пунктах сведена к не линейной распределительной задаче.
- Решена задача минимизации продолжительности проекта для слу чая, когда каждая бригада выполняет не более двух работ. Задача сведена к последовательному определению паросочетаний в графе.
- Задача определения минимального числа бригад при заданных сро ках начала работ сведена к задаче о потоке минимальной величины. Предло жен новый подход к определению потока минимальной величины, в основе которого лежит понятие агрегированных сетей. Доказана теорема двойствен ности о равенстве максимальной пропускной способности разрезов для ис ходной и преобразованной (агрегированной) сетей.
- Предложен метод ветвей и границ для задачи определения очеред ности выполнения работ одной бригадой (единицей ресурсов) при учете вре мени перемещения бригады от работы к работе при симметричной и несим метричной транспортных схемах и для случаев линейного, кругового, ради ального и произвольного расположения объектов, минимизирующий штрафы
за превышение плановых сроков. 7. Предложен геометрический подход к оценке оптимального решения минимизации отклонения от плановых сроков для случая, когда число бригад больше одной, а транспортная схема является радиальной. 8. Получено точное решение задачи минимизации отклонения от пла новых сроков для радиальной транспортной схемы и нескольких бригад ал горитмом ветвей и границ с получением оценок на основе метода сетевого программирования. 9. Поставлена и решена задача планирования ремонта участков дороги при различного вида зависимостях степени опасности участка дороги от ве личины средств на ремонт. Достоверность научных результатов. Научные положения, теорети ческие выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами. Они подтверждены расче тами на примерах, производственными экспериментами и многократной про веркой при внедрении в практику управления дорожным строительством. Практическая значимость и результаты внедрения. На основании выполненных автором исследований разработаны методы и модели, опреде ляющие рациональное расположение и использование производственных ре сурсов при реализации проектов в дорожной отрасли. Использование разработанных в диссертации методов и моделей по зволяет многократно применять разработки, тиражировать их и осуществ лять их массовое внедрение с существенным сокращением трудозатрат и средств. Разработанные модели используются в практике работы ОАО «Орелав- тодор» (г. Орел), ООО ПСК «Домострой» (г. Воронеж), ЗАО «Дороги Черно земья» (г. Воронеж), ФУАД «Черноземье» ФДА (г. Воронеж), ФГУ «Управ ления автомобильной магистрали Москва - Волгоград ФДА» (г. Тамбов), ВФ ООО «Интердорстрой» (г. Богучар Воронежской области), Управления доро гами Брянской области (г. Брянск), ООО «Магистраль» (г. Тула).
Модели, алгоритмы и механизмы включены в состав учебных курсов «Управление проектами», «Исследование операций при моделировании со циально-экономических систем» и «Организационно-технологическое проек тирование», читаемых в Воронежском государственном архитектурно- строительном университете. На защиту выносятся: • постановка задач календарного планирования с учетом времени пе ремещения ресурсов между работами и алгоритм определения продолжи тельности проекта при заданном потоке ресурсов по графу перемещения ре сурсов; • доказательство того, что в оптимальном решении отсутствуют пе ремещения ресурсов между работами; • сведение задачи распределения ресурсов в нескольких пунктах к нелинейной распределительной задаче. • решение задачи минимизации продолжительности проекта для слу чая, когда каждая бригада выполняет не более двух работ; • новый подход к определению потока минимальной величины и дока зательство теоремы двойственности о равенстве максимальной пропускной способности разрезов для исходной и преобразованной (агрегированной) сетей; • алгоритм решения задачи определения очередности выполнения работ одной бригадой (единицей ресурсов) при учете времени перемещения бригады от работы к работе при различных транспортных схемах; • геометрический подход к оценке оптимального решения минимиза ции отклонения от плановых сроков для случая, когда число бригад больше одной, а транспортная схема является радиальной; • точное решение задачи минимизации отклонения от плановых сро ков для радиальной транспортной схемы и нескольких бригад; • модель планирования ремонта участков дороги при различного ви да зависимостях степени опасности участка дороги от величины средств на ремонт.
10 Апробация работы. Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях и семинарах, в том числе на 52-64 научно-технических конфе ренциях в Воронежском ГАСУ (г. Воронеж, 1999-2011); международной на учно-практической конференции в МАДИ (г. Москва, 2000); научно- техническом семинаре (г. Астрахань, 2000); международной научно- практической конференции в БелдорНИИ (г. Минск, 2001); научно- практическом семинаре «Новые технологии и материалы, применяемые при содержании автомобильных дорог» (г. Ростов-на-Дону, 2002); научно- практической конференции «Инновационные технологии и процессы в сек торе реальной экономики РФ» (г. Москва, 2004); научно-практической кон ференции «Образование, наука, производство и управление» (г. Старый Ос кол, 2008); всероссийской научно-технической конференции «Управление в организационных системах» (г. Воронеж, 2008); X международной научно- технической конференции «Кибернетика и высокие технологии XXI века» (г. Воронеж, 2009); 2-й Всероссийской научно-технической конференции «Управление в организационных системах» (г. Воронеж, 2009) и др. Публикации. По теме диссертации опубликовано 51 печатная работа, в том числе 27 работ опубликовано в изданиях, рекомендованных ВАК РФ. Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: в работах [8], [16], [17], [30], [32], [40], [48] автору принадлежит постановка задач календарного планирования с учетом времени перемещения ресурсов между работами; в работах [9], [10], [14], [36], [49], [50] - алгоритм определения продолжительности проекта при заданном потоке ресурсов по графу перемещения ресурсов; в работах [5], [11], [13], [20], [35], [44], [46] - задача распределения ресурсов для случая независимых работ; в работах [15], [30], [32], [39], [41], [43], [47] - минимизация продолжительности проекта для случая, когда каждая бригада выполняет не более двух работ; в работах [17], [21], [23], [30], [31], [32], [33] - метод ветвей и границ для задачи определения очередности выполнения работ одной бригадой (единицей ресурсов) при
11 учете времени перемещения бригады от работы к работе при симметричной и несимметричной транспортных схемах; в работах [8], [12], [26], [29], [30], [32], [37] - минимизация штрафов за превышение плановых сроков для слу чаев линейного, кругового, радиального и произвольного расположения объ ектов; в работах [22], [27], [33], [38], [42], [45] - оптимальное решение для минимизации отклонения от плановых сроков; в работах [8], [19], [28], [32], [33] - задача планирования ремонта участков дороги. Объем и структура работы. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложений. Она содержит 278 стра ниц основного текста, 92 рисунка, 98 таблиц и приложения. Библиография включает 215 наименований. Во введении обосновывается актуальность, описываются цели и зада чи исследования,.его научная новизна и практическая значимость. В первой главе показано, что область строительного производства функционирует по всем признакам, характерным для технологии управления проектами. Дорожное строительство представляет собой одну из специфиче ских сфер деятельности строительных фирм. Произведен анализ современного состояния дорожной отрасли в целом по России, выявлены проблемы, стоящие перед дорожным хозяйством, и возможные пути их решения. На основе выявленных особенностей линейно-протяженного строи тельства (перемещение фронта работ в пространстве (следовательно, необхо димо осуществление перебазировки линейной бригады вслед за фронтом ра бот); достаточно ограниченная, по сравнению с обычными объектами, но менклатура работ, подлежащих выполнению; наличие преобладающего ма териального ресурса, используемого при производстве работ; отсутствие са мостоятельного производственно-экономического значения; сезонность) произведен анализ моделей организации и управления данной отраслью. Было установлено, что основным инструментом управления проектами в дорожной сфере является календарный план, принимающий три основные
12 формы представления расписания работ: линейную, циклограммную и сете вую, включая обобщенную, модели. Определены достоинства и недостатки каждой из моделей, выявлен двойственный характер процесса производства вообще и строительного производства в частности, когда календарный план может рассматриваться, с одной стороны, как расписание работ, подлежащих выполнению, а с другой - как график потребления ресурсов некоторого вида. Показано, что учет этой двойственности может быть полноценно обеспечен только на основе сетевых моделей. В связи с этим были проанализированы известные методы и алгоритмы решения задач распределения ресурсов на основе теории графов. В итоге анализа было установлено, что, несмотря на существование определенного методологического обеспечения для определения объемов ра бот по строительству, ремонту и содержанию автомобильных дорог, отсутст вуют какие-либо рекомендации относительно расположения ресурсов пред приятия с целью успешной реализации своей производственной программы с учетом рассредоточенного характера объектов, включенных в неё. Таким образом, можно сделать вывод о том, что в основе эффективного управления отраслью дорожного строительства в условиях дефицита финан совых средств должны лежать современные методы и модели, адаптирован ные к отраслевым особенностям и обеспечивающие повышение объективной составляющей в процессе принятия управленческих решений. Следовательно, цель диссертационной работы определяется необходи мостью разработки моделей, определяющих рациональное расположение, использование и техническое оснащение производственных подразделений предприятий, функционирующих в дорожной отрасли. Во второй главе приводится описание двойной сетевой модели, со стоящей из двух сетей. Первая показывает зависимости между работами, вторая - потребления ресурсов. Задачи календарного планирования рассматриваются, как правило, без учета времени перемещения ресурсов между работами. Постановка задач ка
13 лендарного планирования с учетом времени перемещения ресурсов была сделана В.Н. Бурковым еще в 60-х годах прошлого века. Однако до сих пор методы решения задач с учетом времени перемещения ресурсов слабо разра ботаны. Это, безусловно, объясняется комбинаторной сложностью их реше ния. Так, простейшая задача выполнения независимых работ одной бригадой эквивалентна задаче коммивояжера, которая относится к классу ЫР-трудных задач, не имеющих эффективных алгоритмов решения. Рассмотрим поста новку задачи календарного планирования с учетом времени перемещения ре сурсов. При рассмотрении процесса выполнения комплекса работ отмечается, что после выполнения одной работы ресурсы перемещаются на другие рабо ты своего класса, образуя поток по множеству работ. Но существуют случаи, когда перемещение ресурсов с одной работы на другую недопустимо по тем или иным причинам (отсутствие транспортных средств, высокая стоимость или невозможность перемещения данного вида ресурсов и т.д.). Описать возможные варианты перемещения ресурсов между работами возможно пу тем задания графа перемещений ресурсов. Возникает задача определения потока ресурсов по графу перемещений ресурсов, минимизирующему время выполнения комплекса операций. Полученные результаты позволяют определить оптимальное распреде ление ресурсов при вогнутых зависимостях скорости работ от количества ре сурсов. В третьей главе рассматриваются задачи определения очередности выполнения работ одной бригадой (единицей ресурсов) при учете времени перемещения бригады от работы к работе. Такие задачи, как правило, возни кают в случае проведения или ремонтных или строительных работ, располо женных на расстояниях от места расположения бригады и друг от друга, сравнимых с временем выполнения работ. Предполагается, что заданы времена перемещения бригады от работы к работе и времена перемещения бригады из пункта расположения к месту вы
14 полнения каждой работы для различных транспортных схем (симметричных и несимметричных) и при различном расположении объектов (линейном, ра диальном, круговом и произвольном). Все задачи сведены к оптимальным за дачам на графах, для решения которых предлагается использование метода ветвей и границ. В четвертой главе рассматривается ряд постановок задач определения расписаний для нескольких бригад и предлагаются эффективные методы ре шения таких задач. Для определения минимального числа бригад, обеспечивающих вы полнение проекта при заданных сроках начала работ, предлагается свести исходную задачу к задаче определения потока минимальной величины, на сыщающего все вершины графа при заданных пропускных способностях вершин. Предлагается геометрический подход к оценке оптимального реше ния минимизации отклонения от плановых сроков для случая, когда число бригад больше единицы, а транспортная схема является радиальной. Нако нец, рассматривается точное решение задачи минимизации отклонения от плановых сроков для радиальной транспортной схемы и нескольких бригад. В пятой главе рассматривается случай, когда степень опасности (ожи даемого ущерба) достигает определенной величины (участок дороги подле жит ремонту). Ремонт производится с целью снижения этого показателя до величины не менее некоторой нормативной, при которой возможна нормаль ная эксплуатация данного участка дороги. Если ремонт не производится в те кущем плановом периоде, то либо ограничиваются возможности эксплуата ции данного участка, либо он вообще закрывается для проезда (определяются объездные пути). Затратив дополнительные средства, можно обеспечить ве личину степени опасности меньше требуемого нормативного уровня, что приводит как к уменьшению степени опасности, так и к увеличению срока эксплуатации данного участка дороги. Рассмотрен ряд задач формирования плана ремонтных работ. Если ве личина ущерба от того, что ремонт участка не включен в план, существенно
15 выше, чем дополнительный выигрыш при уменьшении степени опасности ниже нормативного уровня, то основной задачей становится задача миними зации ущерба. Задача 1. Определить множество ремонтируемых участков, так чтобы минимизировать суммарный ущерб при ограничении на величину выделен ных средств. Если, наоборот, дополнительный выигрыш от уменьшения степени опасности ниже нормативного уровня существенно выше, чем ущерб от того, что данный участок не вошел в план ремонта, то основной задачей становит ся минимизация суммарной степени опасности. Задача 2. Минимизировать суммарная степень опасности участков до роги при ограничении на величину выделенных средств. Задача 3. Минимизировать линейную свертку степени опасности и ущерба при бюджетном ограничении. Поставленные задачи являются, как правило, многоэкстремальными задачами для непрерывных зависимостей или задачами дискретной оптими зации для дискретных зависимостей. В шестой главе рассматриваются способы применения разработанных методов и моделей при решении практических задач ресурсного планирова ния.
- Assistant
Принял.
- User
продолжим. я буду отправлять тебе такие фрагменты дальше, а ты отвечай "принял" когда получишь и обработаешь
- Assistant
Понял, продолжайте отправлять фрагменты, и я буду подтверждать получение с "принял".
- User
- АНАЛИЗ МОДЕЛЕЙ УПРАВЛЕНИЯ ПРОЕКТАМИ ЛИНЕЙНО-ПРОТЯЖЕННОГО СТРОИТЕЛЬСТВА 1Л. Автомобильные дороги как объект управления По уровню развития автомобильного транспорта и сети автодорог Россия в значительной степени отстает от развитых стран. Доля грузооборота, прихо дящегося на автомобильный транспорт, непропорционально низка и почти в 20 раз меньше, чем во Франции, в 3-5 раз меньше, чем в США, Германии, Канаде и др. странах. Средняя дальность поездки на автомобиле составляет всего 42 км, что в 2-3 раза меньше, чем в США, Канаде и других близких по размераги территории странах. Протяженность автомобильных дорог в России составляет 927,0 тыс. км, из них 750 тыс. км имеют твердое покрытие. Кроме этого, существуют еще грунтовые автомобильные дороги, проезд по которым в период весенне- осенней распутицы может полностью или частично прекращаться. Официаль ная статистика эти дороги не учитывает. Около трети магистральных дорог перегружены движением. Средняя скорость автомобилей вдвое ниже, чем на аналогичных зарубежных дорогах, что приводит к значительным экономическим потерям. Из-за бездорожья в сельской местности под колесами автомобилей гибнет до 15 % сенокосов и до 5 % зерновых. В целом по России в 2000 г. за счет средств дорожных фондов введено в эксплуатацию 69609 км автомобильных дорог общего пользования, в том числе федеральных дорог - 10436 км (113,1 % к уровню 1999 года); территориальных - 5917,3 км (129,3 % к уровню 1999 года). Опорную территориальную сеть составляют дороги третьей и четвертой категории. Наличие на сети автомобильных дорог общего пользования грунтовых участков (2,3% от общей протяженности), несоответствие между интенсивно стью движения и техническими параметрами значительной части дорог с твер 17 дым покрытием (не соответствуют требованиям действующих нормативов 65% дорог), их низкие транспортно-эксплуатационные качества, неудовлетвори тельное состояние многих мостов и путепроводов (38 %), недостаточный уро вень обустройства и отсутствие необходимого количества объектов дорожного сервиса свидетельствуют о том, что эта сеть не соответствует предъявляемым к ней требованиям. Все это обусловлено, в первую очередь, недостаточным фи нансированием. Минимально необходимое финансирование позволяет удерживать суще ствующую сеть дорог в работоспособном состоянии, но не позволяет довести содержание дорог до требований стандартов, обеспечить ровность покрытий, обустройство дорог, качественную работу и нормативное состояние искусст венных сооружений. Ремонт дорог является следующим за содержанием приоритетным на правлением дорожных работ. Основным видом ремонта является восстановле ние верхних слоев дорожных покрытий с учетом требований ровности и шеро ховатости. Из-за недостатка денежных средств в бюджете ТДФ основная масса денег идет на содержание автомобильных дорог в допустимом состоянии. В связи с таким положением дел в области складывается сложная ситуация с ре монтными работами. Ежегодно в стране капитально ремонтируется 45— 50 тыс. км дорог, что составляет 5— 7 % общей протяженности дорог с твердым покрытием. Ре монтом ежегодно охватывается около 120— 140 тыс. км дорог. Расходы на ремонт и содержание дорог в стране в 1,5 раза превышают затраты на строи тельство новых и составляют от 60 до 80 % всех затрат на дорожное хозяй ство. К примеру, на дорожной сети, обслуживаемой ФУАД «Черноземье» за период с 1996 г. по 2003 г. на работы по строительству и реконструкции было израсходовано 332840 тыс. руб., на капитальный ремонт - 86855 тыс. руб., а на ремонт - 490820 тыс. руб. Объемы работ за этот же период составили:
- строительство и реконструкция - 65,49 км; - капитальный ремонт - 12,38 км;
18 -ремонт-783,01 км. Из графика на рис. 1.1.1 видно, что на федеральной автомобильной дороге «Черноземье» в среднем в год ремонтируется 120 км, не считая спада в 1997- 2000 г., обусловленного экономическим кризисом в стране. Очевидно, что за счет повышенного качества ремонта при использовании прогрессивных технологий имеется возможность увеличения межремонтных сроков и снижения количества ремонтов за год. км Рис. 1.1.1 .Объемы работ по ремонту, км, выполняемые на федеральной автомобильной дороге «Черноземье» Эффект от выполнения дорожно-ремонтных работ выражается в повыше нии транспортно-эксплуатационных качеств дороги, удобства, скорости и безо пасности движения автомобилей и, как следствие, в снижении себестоимости перевозки. Реконструкция автомобильных дорог связана с повышением технических параметров дорог и дорожных сооружений. Она проводится в целях увеличения пропускной способности, повышения безопасности движения на сети дорог общего пользования и ликвидации узких мест (горловин) и планируется исходя из условий аварийности и интенсивности движения автотранспорта.
19 Таким образом, можно прийти к заключению, что финансирование работ по ремонту и содержанию дорог и искусственных сооружений происходит по остаточному принципу. Однако определение тех или иных приоритетов в расходовании средств должно осуществляться в соответствии с набором критериев. Основным критерием является обеспечение безопасности движения. С данной точки зрения вложение средств в содержание автодорог является опти мальным. С другой стороны, обеспечение безопасности движения не исчерпы вается набором мероприятий, входящих в статью «Содержание дорог». Поэто му остающиеся на ремонт и строительство средства должны распределяться за казчиком также с точки зрения обеспечения максимальной безопасности. Из-за неудовлетворительных дорожных условий совершается от 10 до 25% ДТП. По данным ГИБДД, 70 % дорог не удовлетворяет реальной интен сивности движения, которая ежегодно возрастает на 3-4 %. Следующим по значимости критерием для определения направления рас ходования бюджетных средств должен быть экономический критерий. Проблема оценки эффективности инвестиций является одной из важней ших проблем функционирования и развития автодорожной отрасли. Во многом это связано с такими особенностями, как большая капиталоемкость, продолжи тельность жизненного и инвестиционного цикла. Сложность решения этой про блемы в настоящее время усугубляется особенностями инвестиционного кли мата экономики России и изменениями в налоговой системе. Применительно к автомобильным дорогам необходимость разработки но вых методических положений по оценке эффективности инвестиций обуслов лена следующими обстоятельствами:
- неадекватностью существующих методических положений и рекомен даций по оценке эффективности инвестиций в области дорожного хозяйства, ориентированных на централизованно управляемую систему, современные ус ловия хозяйствования;
20
- невозможностью прямого использования применяемых в мировой прак тике методов оценки эффективности инвестиций, ориентированных на стацио нарную рыночную экономику;
- особенности функционирования дорожного хозяйства России в услови ях перехода к рынку. Что касается зарубежного опыта, сходные задачи решаются и такими ме тодами, как исследование операций и системный анализ, то есть исходя из принципа учета и сопоставления всех возможных последствий оцениваются и сравниваются варианты дорожных проектов. Для оценки эффективности проекта определяются: результаты реализа ции проект, затраты, связанные с его реализацией, расчетный период, эффект, получаемый при реализации. Эффективность - это разность выраженных в стоимостной форме резуль тата и затрат. Показатели эффективности делятся на внутренние и внешние, первые из которых относятся к непосредственным участникам автодорожного проекта, а вторые к более широкому кругу лиц или организаций, на которых может ока зывать воздействие рассматриваемый проект. Обязательными показателями эффективности являются:
- Все виды затрат ресурсов, связанных с инвестициями в дорожные проек ты:
- капитальные затраты на строительство;
- эксплутационные затраты на содержание и ремонт автодорог; капитальные затраты на приобретение дорожных машин и оборудова ния.
- Путевое время - экономия времени поездок или перевозок - важная часть экономического эффекта от дорожного строительства. 3. Безопасность.
- Непосредственное воздействие на местную окружающую среду.
21 Первые две группы показателей эффективности можно отнести собствен но к внутритранспортным. Безопасность, определяемая последствиями дорож но-транспортных происшествий, может считаться внутритранспортным показа телем эффективности только в части, касающейся участников дорожного дви жения. Экологические последствия дорожного строительства - классический пример внешнего (в западном понимании) показателя эффективности. В качестве дополнительных предлагается учитывать следующие типы показателей эффективности: 5. Развитие экономики региона, обслуживаемого рассматриваемой автомо бильной дорогой. 6. Глобальные экологические показатели эффективности. 7. Степень соответствия проекта стратегической политике, принятой госу дарством. Все эти показатели эффективности относятся к категории внешних, сте пень их учета на практике зависит от наличия данных и целей конкретного ана лиза автодорожного проекта. Внутритранспортные затраты измеряются общепринятыми показателями, имеют традиционные составляющие и оцениваются непосредственно в рыноч ных ценах. Внешние (внетранспортные) показатели эффективности требуют более детального рассмотрения с точки зрения возможности их измерения или «кос венной» денежной оценки. При принятии решения о формировании показателей эффективности нельзя опираться исключительно на экономические показатели, так как оценка дорожных работ в этом случае получится достаточно односторонней. В задачах оценки инвестиционных проектов часто возникает ситуация, когда некоторые критерии являются качественными и могут быть оценены только экспертно. Бывают ситуации, когда может быть получена и количест венная оценка, но сбор информации для ее расчета чрезвычайно трудоемок, да
22 и полученная таким образом оценка не может быть однозначно переведена в денежную. В условиях дорожного строительства такими качественными критериями будут экологический ущерб, степень соответствия проекта стратегической по литике, принятой государством, социальный риск и т.п. Основной проблемой всех подрядных организаций является формирова ние портфеля заказов. Подрядчик зачастую вынужден соглашаться на выпол нение работ на заведомо для него невыгодных условиях (с нулевой рентабель ностью и т.п.). Это привело к тому, что подрядчики (по их информации) прак тически не имеют прибыли, а следовательно, и средств для развития, создания запасов материалов, приобретения техники. Устойчивое финансовое положение подрядных организаций важно для дорожной отрасли, так как порядка 35-40 % средств, направляемых в дорожное хозяйство, возвращается в бюджеты всех уровней в форме соответствующих налоговых платежей предприятий и организаций дорожного хозяйства. До 70 % затрат предприятий и организаций дорожного хозяйства направляется на при обретение материально-технических ресурсов, другими словами, на финанси рование сопряженных отраслей экономики/ 1.2. Организационно-технологическое проектирование линейно-протяженных объектов Строительство линейно-протяженных объектов, как и всякое строитель ство вообще, связано с отвлечением больших объемов денежных средств на достаточно значительный срок. В связи с этой особенностью возникает необхо димость тщательного обоснования проектов, принятых к реализации. Причем, так как объекты линейно-протяженного строительства зачастую не имеют са мостоятельной потребительской ценности (например, никому не нужна дорога, по которой нечего перевозить), обоснование необходимости реализации такого проекта должно быть тесно увязано с потребностями экономической жизни со ответствующего региона.
23 Сам процесс строительства носит в какой-то степени двойственный ха рактер: с одной стороны, осуществляется работа по возведению некоторого объекта, достаточно сложного с технической стороны, причем работы ведутся специализированными организациями, действия которых необходимо коорди нировать, с другой - деятельность специализированных фирм осуществляется непрерывно, в динамике, и работы по возведению данного объекта являются только производственным эпизодом для организаций - участниц строительства, то есть соответствующие предприятия должны быть подготовлены для выпол нения конкретных работ в определенные сроки. Таким образом, подготовка к реализации проекта, связанная с возведени ем линейно-протяженного объекта, сводится к трем стадиям [1]: • общая подготовка строительного производства; • подготовка к строительству объекта; • подготовка генподрядных строительных организаций. Общая подготовка производства включает в себя предпроектную стадию проведения работ, заключающуюся в экономическом обосновании необходи мости строительства и его увязки с комплексной программой развития региона и разработке проектно-сметной документации на проектируемый объект. Подготовка к строительству объекта предполагает определение номенк латуры возводимых объектов, сроков их возведения и последовательности рас пределения капитальных вложений и объемов строительно-монтажных работ, потребности в материально-технических и трудовых ресурсах. Все эти пробле мы решаются в проекте организации строительства (ПОС). Как известно, проект организации строительства включает в себя: • комплексный укрупненный график и разработанный на его основе ка лендарный план строительства отдельных объектов с распределением объемов капитальных вложений и строительно - монтажных работ по этапам строитель ства; • стройгенгшан;
24 • организационно-технологические схемы сооружения объектов с распре делением линейных подразделений вдоль предполагаемого фронта работ; • решения по рекультивации плодородного слоя почвы с указанием границ участков, временно отводимых под строительство; • ведомость объемов работ с разбивкой по объектам; • графики потребности в строительных материалах, машинах и меха низмах, рабочих кадров. ПОС служит основой для разработки проекта производства работ (ППР), который включает в себя следующие документы: • календарный план возведения объекта с указанием номенклатуры, по следовательности и сроков проведения работ; • стройгенплан; • привязанные к конкретным участкам трассы генпланы временных строительных баз с решениями по выбору площадок, временному отводу и ус ловиям восстановления земель; • схематический план трассы с указанием мест переходов через прегра ды и грунтовых условий; • технологические карты; • график потребности в материалах, машинах и рабочих кадрах. Таким образом, проектирование организации производственных процес сов строительства линейно-протяженных объектов включает в себя решение следующего перечня управленческих задач: • уточнение численности линейных бригад и предприятий, задейство ванных в реализации конкретного строительного проекта; • организация движения линейных подразделений вслед за фронтом работ; • определение рациональной транспортной схемы; • проектирование рациональной схемы материально-технического снабжения с использованием теории управления запасами; • оперативное планирование и контроль.
25 Так как для строительства характерны все особенности, свойственные теории управления проектами, то вполне закономерно будет использование технологий, принятых в этой теории. Теория управления проектами предполагает осуществление горизонталь ных связей, направленных на реализацию проекта и объединяющих деятель ность различных предприятий, участвующих в выполнении проекта, и верти кальных связей, обеспечивающих полноценное функционирование данных предприятий как в рамках этого проекта, так и за его пределами. Роль горизонтальных связей выполняют проекты организации строитель ства и проекты производства работ. В качестве вертикального связующего эле мента, обеспечивающего эффективную деятельность строительной фирмы в те чение некоторого промежутка времени, используется проект организации работ (ПОР), составляемый на один год (реже на два года ) и состоящий из следую щих документов: • графика производства строительно-монтажных работ с разбивкой по месяцам и по объектам; • данных о дислокации линейных бригад, баз и разгрузочных площа док; • графика перебазирования линейных подразделений в процессе вы полнения запланированных объемов работ; • графика потребности в материалах и их поставки; • графика потребности в строительных машинах и механизмах; • расчета потребности в рабочих кадрах по основным профессиям на принятый к выполнению объем работ. Таким образом, основной управленческой задачей при подготовке строи тельства линейно-протяженного объекта является построение календарного плана производства работ на объекте. Построение календарных планов осуществляется на основе организаци онно-технологической модели (ОТМ) процессов реализации строительного проекта. Основной задачей при этом является составление расписания работ.
26 Различные организационно-технологические документы, предусмотренные СНиПами, отличаются только степенью детализации составляемого расписа ния. При этом следует учесть, что календарный график строительства должен быть увязан с имеющимися в распоряжении строительного предприятия ресур сами, удовлетворять принятым решениям по технологии и организации работ на объекте, укладываться в директивные сроки, обусловленные договором. Следовательно, на календарный план наложены ограничения, которые подраз деляются на ограничения логического типа (например, на технологическую по следовательность выполнения работ) и ограничения ресурсного типа (напри мер, на число рабочих). Построение расписания работ (графика процесса строительства объекта) предполагает определение сроков начала и окончания каждой работы на объекте, при этом все ограничения должны быть удовлетво рены. В целях более полного учета специфики выделим основные особенности строительства линейно-протяженных объектов: • перемещение фронта работ в пространстве, следовательно, необходи мо осуществление перебазировки линейной бригады вслед за фронтом работ; • достаточно ограниченная, по сравнению с обычными объектами, но менклатура работ, подлежащих выполнению; • наличие преобладающего материального ресурса, используемого при производстве работ, например, щебень при дорожном строительстве или трубы при строительстве трубопровода. Все эти особенности строительства линейно-протяженных объектов при водят к тому, что основным методом строительства является поточный метод с выделением ведущего потока. Поэтому организационно-технологическая мо дель описания подобного процесса должна учитывать его особенности. Рассмотрим существующие формы представления расписаний работ. Как известно, существуют три формы представления календарных гра фиков: • линейная;
• циклограммная; 27 • сетевые графики. Линейные модели [1] представляют собой простейшее графическое изо бражение процесса строительства объекта. Такое представление однозначно определяет номенклатуру и последовательность выполнения работ, сроки нача ла и завершения каждой работы и всего строительства в целом, объемы работ, подлежащих выполнению, состав исполнителей. Такая модель имеет простое математическое описание: определить мно жество фиксированных значений сроков начала и окончания работ, то есть где Р - множество, определяющее расписание работ; Т" - срок начала 1-й рабо ты; Т,0 - срок окончания -й работы; ¡=1,2,...,п - нумерация работ, п - число ра бот, подлежащих выполнению. При этом на сроки выполнения работ могут быть наложены ограничения вида это означает, что ¡-ая работа должна быть начата не ранее момента времени и, и завершена не позднее и ,. Линейные модели представления календарного графика характеризуются простотой, наглядностью и доступностью, что объясняет их широкое распро странение для описания ОТМ. Данная модель позволяет хорошо описывать особенности поточного метода производства работ, выделяя ведущий процесс. Вместе с тем у этих моделей наряду с достоинствами есть и существенные не достатки: • линейное представление процесса возведения объекта характеризует только один из возможных вариантов технологии и организации работ на объ екте; если в процессе работы возникает необходимость внесения изменений, то это, как правило, ведет к полной переработке модели, то есть такие модели не устойчивы к внешним возмущениям;
• данная модель не представляет возможным выделение процессов, ока зывающих ключевое влияние на продолжительность всего строительства, не даст ответа на вопросы оперативного управления процессом строительства, то есть как изменится общий срок строительства, если увеличилась продолжи тельность выполнения некоторой работы; • ограниченность математического представления не позволяет исполь зовать вычислительную технику. Другой формой представления календарных планов являются цикло граммные модели, которые хорошо описывают особенности поточного строи тельства. Эти модели являются обобщением линейных моделей с изображением перемещения бригад с захватки на захватку при условии непрерывности их ра боты и соблюдения принятых при поточном методе строительства ограничений. При этом формализованное описание циклограммных моделей может быть представлено в следующем виде: Ти>то Ти>То А Г$ — Г—1,5 * — Г.5—15 при этом должно выполняться условие непрерывности потоков Т° -Т н= УЧ П1 Аг1 ¿-и ,’Г59 5“! где г - номер потока; б - номер захватки (8=1,2,.. .,п). Основная проблема заключается в увязке потоков, достигалось максимально возможное сближение смежных тигается сокращение сроков строительства. причемтак,чтобы потоков.Этимдос Относительно просто такая задача решается для равноритмичных пото ков, но уже для разноритмичных потоков задача увязки становится гораздо сложнее. Рассмотрим этот алгоритм на простейшем примере [1]. Пусть Ь - длина участка объекта линейно-протяженного строительства в километрах, тогда длительность смежных потоков р и г определяется по сле дующей формуле:
29 где у р,у г - интенсивность смежных потоков, выражаемая километрами в сме ну; к р,к г - сменность выполнения работ по потокам р и г соответственно. Необходимо определить минимально возможную величину организаци онного перерыва между потоками р и г гг при условии, что между этими пото ками должен выдерживаться минимальный организационный перерыв 1.сф. За время, равное тг, бригада потока р выполнит объем работ, равный тгкр1р, в то время как объем выполненных работ по потоку г будет равен 0. За произвольный промежуток времени Д1 объемы работ соответственно будут равны тгкр1р+ А1кр1р и А1кг1г. Тогда фронт работ для рассматриваемого по тока будет определяться выражением (1.2.1) Причем, согласно основным требованиям поточного метода производства работ, на весь период совместного функционирования потоков необходимо со блюдение следующего неравенства: Р >I тах(к I ;к I ). (1.2.2) гСф\рр>гг/ При этом возможны два случая: • темп рассматриваемого потока ниже темпа предыдущего, то есть • темп рассматриваемого потока выше темпа предыдущего (к р1р < к г1г). Рассматривая первый случай, запишем соотношение (1.2.2) с учетом (1.2.1) в следующем виде: Так как рассматривается первый случай, то это означает, что выражение в квадратных скобках будет всегда положительным, поэтому величина тг должна равняться минимально возможному организационному перерыву, то есть х =гСф * (1.2.4)
30 Рассматривая второй случай, приходим к неравенству следующего вида: X, '1- ^ ' (1.2.5) МрVМру В данном случае выражение в скобках будет всегда отрицательным, по неравенство (1.2.5) будет выполняться, только если положить этому Д1 = Тр- тг. После преобразований получаем =к„-х+ТР- Для случая синхронизированных потоков получаем тг = 1 . Таким образом, увязка потоков при построении циклограммных моде лей представляет собой достаточно сложную задачу, хотя данные модели хо рошо учитывают специфику поточного метода производства работ. Но вме сте с тем для данных моделей характерны и все недостатки, присущие ли нейным моделям. Большими возможностями в области оперативного управления производ ства по сравнению с линейными и циклограммными моделями обладают сете вые модели. Эти модели хорошо передают последовательность выполнения работ, позволяют определить набор работ, в наибольшей степени влияющих на об щую продолжительность строительства, и сделать выводы о возможном из менении сроков строительства в случае изменения сроков выполнения от дельной работы. Математическое описание модели представляет собой набор неравенств вида т°-ти>г,тм-т° >о, I I •» J ) > где I,- продолжительность ¡-й работы; ¡, ) —номера зависимых работ; } = 1 ,2 ,...,п. В сетевых моделях учет директивных сроков строительства осуществля ется путем задания ограничений в форме неравенств Т" > и,, Т° < и„.
31 Следует отметить, что традиционные сетевые модели имеют ряд сущест венных недостатков, связанных со сложностью представления поточной орга низации строительства, с гибкой взаимоувязкой отдельных потоков. Данные модели не позволяют описать совмещение работ, которое на практике имеет место. Для моделирования совмещения работ приходится разбивать объект строительства на фиксированное количество захваток, после чего возможно по строение сетевой модели. В том случае, если число захваток в силу каких-то причин изменилось, приходится строить модель заново, так как при этом меня ется вся топология сети и весь расчет необходимо осуществлять заново. Таким образом, при построении сетевой модели приходится заранее зада ваться числом захваток, то есть необходимо заранее определить степень со вмещения выполняемых работ. Но, как известно из практики, степень совме щения работ является величиной нечеткой, значение которой может изменяться в некоторых пределах, а, как уже было сказано, всякое такое изменение в ко нечном итоге приводит к необходимости повторного построения модели. В целях устранения этих недостатков традиционные сетевые графики по лучили дальнейшее развитие в обобщенных сетевых моделях (ОСМ). Обобщенные сетевые модели представляют собой попытку объединения достоинств линейных моделей при моделировании совмещения работ и досто инств традиционных сетевых моделей в части оперативного управления про цессом строительства. Для процедуры формализованного описания совмещения работ исполь зуют метод, который оперирует коэффициентами совмещения работ [3]. Из вестны два вида коэффициентов совмещения: • коэффициент совмещения по началу (Кн); • коэффициент совмещения по концу (К0). Коэффициент совмещения по началу определяет, какая часть предыду щей работы должна быть выполнена к началу последующей. Коэффициент совмещения по концу показывает, какая часть последую щей работы должна остаться после завершения предыдущей (рис. 1.2.1).
Предыдущая работа 32 1------------------- ------------------------------------- 1 1а] а2 Последующая рг -------- в, -------------------- ------В2 -------1 Рис. 1.2.1 Кн=а, /(а,+а2), К0= В2/ (В1+В2) Величина коэффициента совмещения может варьироваться в пределах от Одо 1. Она определяется экспертно в зависимости от объемно-планировочного и конструктивно-технологического решения здания, трудоемкости работ, со става и количества бригад, методов механизации процессов, требований техни ки безопасности и др. Полученные коэффициенты совмещения могут быть использованы для четких количественных расчетов при определении взаимосвязи между различ ными работами. Применение сетевых моделей объясняется их хорошей формализацией, то есть возможностью использования математических алгоритмов, позволяю щих получить оптимальный по некоторым критериям календарный график. Но в данном случае следует отметить, что все задачи календарного планирования относятся к классу многокритериальных задач, в то время как преобладающее большинство алгоритмов направлены на решение исключительно однокритери альных задач оптимизации. В связи с этим возникает проблема редукции ис ходной задачи к задаче с единственным критерием оптимальности. Такое преобразование может быть выполнено одним из следующих спо собов: • сверткой множества критериев в один, интегральный; но 03
33 • выделением одного критерия в качестве критерия оптимальности, при этом остальные будут играть роль ограничений; • ранжирование критериев с использованием лексиграфических пред почтений; • использование метода последовательных уступок в целях нахождения множества компромиссных решений. Построение интегрального критерия оптимальности может быть осуще ствлено различными путями, например, в качестве такой результирующей оценки может быть принято выражение вида Р. •Р, •••Р_ Р -Р ---Р п+1 где Р,,Р2,...,Рп - показатели, которые необходимо увеличить; Рп+1,Рп+2,...,Рп - по казатели, которые необходимо уменьшить. Естественно, что все используемые в данном подходе критерии должны быть приведены к безразмерному виду и пронормированы.
- Assistant
Принял.
- User
Другой подход к данной проблеме заключается в использовании взве шенной суммы отдельных критериев, то есть интегральный критерий находится по формуле вида К = а,Р, + а 2Р2+ ... + а тРт . В данном случае используемые здесь критерии должны быть не только безразмерными и пронормироваными, но и приведенными к одному типу пара метров: или все критерии должны быть типа «чем больше, тем лучше», или же наоборот. Весовые коэффициенты а, позволяют усилить или ослабить влияние отдельного параметра на результат решения. Назначение этих коэффициентов осуществляется экспертным путем, что сильно затрудняет процедуру решения, так как проведение процедуры экспертного опроса является достаточно дли тельным и дорогостоящим мероприятием. Использование интегрального критерия достаточно ограничено при ре шении задач оптимизации календарного планирования. Объясняется это тем, что результирующий показатель может принимать достаточно высокое значе К п+2 1 |т 34 ние только за счет какого-то одного из критериев, в то время как остальные мо гут иметь неприемлемое значение для разработчика. В качестве примера можно рассмотреть задачу на быстродействие, то есть построение такого расписания работ, которое бы выполнялось за мини мальное время. Казалось бы, сокращение сроков строительства должно устраи вать всех, но, оказывается, при линейно-протяженном строительстве такое со кращение связано с привлечением дополнительных трудовых и технических ресурсов (необходимо привлечение дополнительных линейных бригад), а это в свою очередь приводит к увеличению непроизводительных расходов, связан ных с перебазировкой линейных бригад вдоль трассы строительства, неполной загрузкой мощностей предприятия и снижением фондоотдачи, то есть получен ное оптимальное решение не будет являться таковым для строительной органи зации. Но сокращение сроков строительства оказывается выгодным и для строи тельных организаций, важно только определить точку экстремума, но опреде ление весовых коэффициентов и в этом случае представляет собой сложней шую задачу, которая до сих пор не имеет точного решения. Устранение указанного недостатка возможно на основе выделения одного критерия в качестве критерия оптимальности, а остальные критерии можно учесть в виде ограничений, предварительно задав их пороговые значения. В этом случае задача многокритериальной оптимизации приводится к задаче ма тематического программирования с ограничениями в форме неравенств. Другим способом решения задачи многокритериальной оптимизации мо жет служить ранжирование всех показателей по возрастанию их предпочти тельности. Тогда решение х, соответствующее некоторому фиксированному на бору значений оцениваемых параметров, будет предпочтительнее, чем вариант у , только тогда, когда выполняется одно из трех условий: р,(х) > Р,(у), Р,(х) = Р,(у), Р2(х)>Р2(у), Р,(х) = Р,(у), Р2(х) = Р2(у), Р ,(х )> Р 3(у).
35 Такая задача получила название лексиграфической задачи оптимизации. Но использование данного алгоритма может быть затруднено тем обстоя тельством, что строительство, как область производственной деятельности, за трагивает интересы различных структур, а эти интересы зачастую противопо ложны. Эти противоречия делают процедуру ранжирования весьма субъектив ной и неоднозначной: все зависит от того, кто это ранжирование производит, то есть от его функционального места в строительном производстве. В какой-то степени эти противоречия может сгладить метод последова тельных уступок, который не предполагает столь жесткого ранжирования кри териев, как лексиграфический метод. Сущность алгоритма заключается в том, что, выстроив критерии в поряд ке возрастания важности, осуществляют решение задачи оптимизации по пер вому критерию Р,, находя его оптимальное значение Р,Ф. Затем задают величи ну возможного ухудшения этого критерия АР,, добавляют к системе ограниче ний исходной задачи новое ограничение вида Р," - Р, < АР, и решают получен ную задачу оптимизации, но уже по критерию Р,. Аналогично осуществляется решение задачи оптимизации и по всем кри териям. То есть решение многокритериальной задачи с п критериями опти мальности заменяется на решение п задач оптимизации по одному критерию. Данный метод привлекателен тем, что дает количественную оценку для компромиссного решения, то есть становится ясно, какой ценой достигается выигрыш по каждому из показателей. В целом следует отметить, что трудности построения оптимальных рас писаний связаны с многогранностью сферы строительного производства, в ко торую вовлечены многие участники с антагонистическими целями, поэтому следует уделять особое внимание экономическому обоснованию постановки задачи, так как никакой, даже самый совершенный, алгоритм не в состоянии будет компенсировать изначальные ошибки, заложенные в модель.
36 1.3. Методы решения организационно-управленческих задач при строительстве автомобильных дорог Основные особенности линейно-протяженного строительства, рассмот ренные в предыдущем параграфе, являются основой для задач, характерных именно для этого типа строительства. К таким задачам, в первую очередь, от носятся задачи на определение оптимального радиуса действия линейной бри гады; определение численного состава линейной бригады и числа линейных бригад, необходимых для выполнения заданного объема работ. Следует отметить, что все эти задачи вытекают из основной особенности линейно-протяженного строительства - перемещения фронта работ в простран стве. Это вынуждает осуществлять перебазировку линейных бригад, затрачивая время и дополнительные средства. Естественно, возникает задача сокращения перебазировок линейной бригады при строительстве одного объекта. В целом же следует отметить, что общий годовой фонд рабочего времени линейной бригады определяется следующим образом [4]: (1.3.1) где Т^- время работы линейной бригады на нм объекте; Т„6 - время, затрачи ваемой линейной бригадой на передислокацию с объекта на объект или с одно го места временного базирования на другое; Т п - время, затрачиваемое линей ной бригадой на перемещение от места временного базирования до фронта ра бот; Тм - затраты времени на ликвидацию места временного базирования и создания его на новом месте; N - число объектов, которые необходимо постро ить за данный календарный период. Таким образом, необходимо определить оптимальный радиус действия линейной бригады, при котором непроизводительные затраты времени были бы минимальны. Будем считать, что операционная область, в которой выполняются рабо ты, будет иметь форму круга, площадь которого равна Р.
37 Предположим, что оптимальный радиус действия линейной бригады ра вен Я01тт, тогда бригада, перемещаясь от одного места дислокации к другому, будет проходить непроизводственный путь, величина которого определяется по формуле Хьпб=4 +К,+-+ЬМ„• (1.3.2) 1 Зная радиусдействия бригады 1101ГТ, можно найти площадь, соответст вующую данному радиусу: Г= Тогда, зная общую площадь области, в которой должна будет действовать линейная бригада, число мест временного базирования можно определить как отношений площадей: M вf>= F / f . (1.3.3) С другой стороны, число мест временного базирования линейной брига ды при строительстве N объектов можно подсчитать по формуле м. м„=тг— +'■ (13.4) ОПТ Приравнивая выражения (1.3.3) и (1.3.4), получим соотношение вида \ лЯопт При определении оптимального радиуса действия линейной бригады бу дем исходить из минимизации полных затрат на строительство линейно протяженного объекта единичной длины. При этом полные затраты будут включать в себя следующие компоненты: С - себестоимость строительства без учета непроизводственных затрат; С нп - затраты на перемещение бригады от места временного базирования до места строительства; С пб - затраты на пере базирование линейной бригады. Производственные затраты С определяются на основе сметной докумен тации. Затраты на перемещения от места временного базирования до фронта работ С нпмогут быть определены по формуле К (1.3.5) 'ооп/
где снп - удельные расходы на перемещение бригады; Ь ср - усредненная длина линейно-протяженного объекта. Зная усредненное значение длины линейно-протяженного объекта Ьср, находим непроизводительный путь линейной бригады при строительстве тако го объекта. Его значение будет определяться формулой ^ = -^Т-[бЬсР(21(|-1 ,)-(2 Ь ср-1„Х1П-1,)], (13.7) п где 1п - объем работ, выполняемый бригадой в последний день работы; 1, - объ ем работ, выполняемый бригадой в первый день работы. Учитывая (1.3.7), найдем затраты на непроизводственное перемещение бригады: 612 ' } п Таким образом, полные затраты можно записать с учетом (1.3.8) в виде „ ^.=..К(2|,-1,)-(2Ь,-|,)(1,-1|)]1к„П "■ бТ ь•’ п ср где кпб - коэффициент, учитывающий затраты на перебазировку; П - объем производственной программы. Принимая, что Л = Ьср, соотношение (1.3.9) запишем как сЛб1ф1„ -1,)-(2К-1,XI.-!.)], к^П С*TM, = С + - ^ — — ---------^ -----— + - г - . (1.3.10) к. Таким образом, (1.3.10) представляет собой целевую функцию затрат от параметра Л. Находим производную по Л, приравниваем полученное выраже ние к нулю и находим значение для оптимального радиуса действия линейной бригады при условии минимизации полных затрат. Значение для оптимального радиуса действия будут определяться следующим выражением:
К 39 (1.3.11) Рассматривая сроки строительства линейно-протяженных объектов, при ходим к заключению, что сокращение сроков строительства связано с возраста нием сметной стоимости и ростом непроизводственных расходов, связанных с увеличением затрат на перебазировку. Связано это с тем, что существенное со кращение сроков строительства возможно только при увеличении числа линей ных бригад и строительной техники, задействованных на объекте. А это ведет к снижению эффективности использования техники и увеличению затрат на пе ребазировку. Эти затраты могут существенно превысить экономию от сокра щения сроков строительства. В связи с этим возникает задача определения ми нимального количества линейных бригад для выполнения заданного объема ра бот, при этом директивные сроки строительства должны быть соблюдены, а полные затраты должны быть минимальны. Согласно [4], полные затраты определяются по следующей формуле: (1.3.12) о где г- время с начала строительства; Тп- продолжительность строительства; гн- годовой фонд рабочего времени; п - число линейных бригад; а - планируемый уровень рентабельности; 3,, 32 - затраты на содержание и перебазирование ли нейной бригады соответственно; с - стоимость строительства линейно протяженного объекта единичной длины. Интегрирование выражения (1.3.12) приводит к соотношению вида 1п(1 + а)1_ В том случае, когда строительство ведется одной бригадой, продолжи тельность строительства определяется по формуле (1.3.14)
40 Если будет задействовано п бригад, тогда продолжительность может быть найдена из выражения Тп= Т /п , с учетом этого выражение (1.3.13) может быть приведено к виду 3 = п(с11И+3,)- (l + a)ni«-1 + п32(1+ а)п,н. (1.3.15) 1п(1 + а ) Выражение (1.3.15) представляет собой целевую функцию затрат относи тельно числа бригад п. Дифференцируя это соотношение по п и приравнивая полученное выражение к нулю, получаем уравнение для нахождения числа ли нейных бригад п, решая которое находим L 1+кЬЛ1п(1+а) v L(cL + 3,)tH 1.4. Методы решения задач дискретной оптимизации п1 1, t ■ ' (1.3.16) 2 3 2 1 п ( 1 + ОС) + J J 3 2 1п(1 + а ) -1- (cl„+3,)t. Из анализа моделей и методов, применяемых при организационно технологическом проектировании линейно-протяженного строительства, мож но сделать заключение о том, что предметная область описывается дискретны ми параметрами: местами дислокации производственных ресурсов типа мощ ности (линейных бригад); набором технологических решений; участками, тре бующими ремонта и реконструкции, и т.п. То есть стоимость ремонта участка дороги будет зависеть от выбранной технологии, используемых материалов и техники. Причем зависимость будет носить дискретный характер, то есть опре деленному сочетанию технологии, материалов и оборудования будет соответ ствовать конкретная величина затрат и конкретные параметры потребительских свойств, приобретаемых данным участком дороги после ремонта, а также ве личина межремонтного срока. Следовательно, выбор оптимальных вариантов производства работ будет производиться в пространстве дискретных состоя ний, то есть относиться к ЫР-трудным задачам оптимизации (задачи комбина торной оптимизации).
41 Рассмотрим основные методы решения задач дискретной оптимизации. Рассмотрим постановку задач дискретной оптимизации (экстремальных задач комбинаторного типа) [25]. Задано конечное множество Q допустимых решений (комбинаций). В качестве таких комбинаций могут выступать пере становки п чисел (число возможных решений п!), сочетания из п элементов m (число решений СTM), последовательность из п чисел, каждый член которой мо жет принимать одно из m значений (число возможных решений шп) и т.д. Для каждой комбинации rceQ определена функция ф(я) в том смысле, что есть алгоритм вычисления функции ф(я) для любого TteQ. Требуется опреде лить комбинацию TtoeQ, для которой ф(7с) принимает максимальное или мини мальное значение. Сложность решения задач дискретной оптимизации состоит в том, что число допустимых решений экспоненциально растет с ростом раз мерности задачи п. Поэтому простой перебор всех решений невозможен при больших п. В то же время эти задачи относятся, как правило, к классу NP- трудных задач, для которых доказано, что не существует методов их точного решения, отличных от перебора. Существует несколько схем решения задач дискретной оптимизации. Ниже дается их краткое описание [25]. Определим для каждого решения л множество Р(л:) так называемых со седних решений (окрестность решения л). При заданной процедуре получения соседних решений алгоритм локальной оптимизации работает следующим об разом [9]. Берем какое-либо решение л0 Рассматриваем окрестность Р(ло) и в этой окрестности определяем наи лучшее решение п\9такое, что ф(тс)= min ф(л) (1*4.1) *вр(Яо> (имеется в виду задача минимизации). Если <р(л) < ф(7г0), то рассматриваем окрестность Р(лО, определяем наи лучшее решение л2и т.д., до тех пор пока не получим решение 7СК, такое, что
Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д. Можно поступить по-другому, расширив окрестность. Если як- локаль но-оптимальное решение, то определяем окрестность следующим образом: р(*к)= UpW- (1А2) Другими словами, Р(лк) - это объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальным решения. Если лкостается локально-оптимальным решением в новой окрестности, то либо производим дальнейшее расширение окрестности, либо останавливаемся на полученном решении. Достоинством методов локальной оптимизации является простота соот ветствующих алгоритмов. Недостатком схемы является отсутствие оценок бли зости получаемого решения к оптимальному. В задачах календарного планирования метод локальной оптимизации реализуется в основном в так называемых алгоритмах «сглаживания» и в алго ритмах улучшения решения путем изменения очередности работ критического пути. Рассмотрим два простых примера, иллюстрирующих эти подходы. Пример 1.4.1 [25]. На рис. 1.4.1 приведен сетевой график проекта из 4 ра бот, которым соответствуют вершины сети. В нижней половине вершин указа ны объемы работ. Примем, что количество ресурсов на работах 1 и 2 не может превышать 4, а на работах 3 и 4 не может превышать 1.
43 На рис. 1.4.2 приведен график использования ресурсов при выполнении всех работ с максимальной интенсивностью Рис. 1.4.2 Заметим, что работы 1 и 3 критические, а работы 2 и 4 имеют полные ре зервы времени, равные 4. Поэтому сдвигаем начало работы 2 на 3 единицы и выполняем ее в интервале (3, 7) тремя единицами ресурсов. При этом, естест венно, сдвигается работа 4 на 4 единицы. График использования ресурсов после локальной оптимизации на рис. 1.4.2 заштрихован. Пример 1.4.2 (задача о станках) [25]. Требуется обработать п деталей. Каждая деталь проходит обработку на двух станках. Продолжительность обра ботки детали ( на первом станке равна а ,, а на втором Ь( . Имеется всего один станок первого типа и достаточное количество станков второго типа. Требуется определить очередность обработки деталей, минимизирующую продолжитель ность обработки всех деталей. На рис. 1.4.3 приведен сетевой график из трех деталей. В нижней полови не вершин указаны времена обработки. Возьмем произвольную очередность, например, 1,2,3 (очередность обра ботки указана пунктиром на рис. 1.4.3, критический путь выделен двойными дугами). Продолжительность обработки Т = 23. Естественно определить сосед ние решения как решения, получаемые изменением очередности работ, лежа
44 щих на критическом пути. В нашем случае окрестность состоит из одного ре шения (2,1,3), рис. 1.4.4. Рис. 1.4.3 Продолжительность обработки Т = 22 уменьшилась. Для нового решения имеем два соседних (1,2,3) и (2,3,1). Из них первое мы уже рассматривали. Для второго имеем Т = 20. Это решение, как легко показать, является локально оп тимальным. Более того, можно показать, что для данной задачи описанный ал горитм всегда дает глобально оптимальное решение. •» •» \« Рис. 1.4.4 Обобщением метода локальной оптимизации являются так называемые ге нетические алгоритмы. В этих алгоритмах окрестность определяется не для одно го решения, а для пары решений (родителей) и даже для нескольких решений. Из полученной окрестности отбираются наиболее перспективные «дети» и [HJ [23] [221
45 формируются новые пары (возможно с привлечение других решений) и т.д. На пример, на основе перестановок (1,2,3,4) и (3,4,2,1) можно получить окрест ность, беря очередность пары соседних элементов из первой перестановки, а очередность оставшейся пары - из второй, а потом наоборот, очередность пары соседних элементов из второй перестановки, а очередность другой пары - из первой. Получаем шесть детей: (1,2,3,4), (2,3,4,1), (3,4,2,1), (3,4,1,2), (4,2,1,3) и (2,1,3,4). Из них двое полностью идентичны одному из родителей. Исключая их, получаем окрестность из четырех перестановок: (2,3,4,1), (3,4,1,2), (4,2,1,3) и (2,1,3,4). Предположим, что «дети» (2,3,4,1) и (3,2,1,3) наиболее перспективны. На основе этой пары можно получить новую окрестность, и т.д. В основе метода ветвлений лежит процедура последовательного получения решения. Разобьем множество всех решений на подмножества, каждое под множество на другие подмножества и т.д. до получения отдельных решений (рис. 1.4.5) [20, 23, 224, 26, 27]. ©©©••• о о •••© Рис. 1.4.5 Если теперь для каждой вершины полученного дерева определить неко торую функцию оценки соответствующего подмножества (функция приорите
46 та), качественно характеризующую вероятность того, что в данном подмноже стве найдется оптимальное или хотя бы «достаточно хорошее» решение, то мы получаем алгоритм поиска решения, двигаясь по ветви дерева, имеющей мак симальное значение функции оценки (или минимальное, если вероятность на личия достаточно хорошего решения тем больше, чем меньше значение функ ции оценки). В задачах календарного планирования метод ветвлений реализу ется в так называемых эвристических алгоритмах распределения ресурсов [25]. Метод ветвей и границ - это метод ветвлений, в котором в качестве функций оценки подмножеств берутся оценки снизу (или сверху) целевой функции задачи на данном подмножестве решений. Основное преимущество этого метода по сравнению с методом ветвлений в том, что возможна оценка близости получаемого решения к оптимальному. Действительно, если мы полу чили решение п со значением целевой функции ф(я), а оценки снизу остальных подмножеств т|(С>) > ф(л) (рассматриваем задачу на минимум), то очевидно, по лученное решение оптимально. Если наилучшая оценка ц(С)) < ф(я), то разность Д = ф (л) - г|(С>) определяет погрешность полученного решения [22, 25, 27, 28]. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних оценок. При плохих оценках это фактически полный пе ребор, при достижимой нижней оценке это получение оптимального решения за один проход по дереву ветвлений. Заметим, что функция приоритета, основанная на степени критичности фронта работ в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хороша эта оценка - от дельный вопрос). Дадим иллюстрацию метода на примере задачи обработки де талей (рис. 1.4.3). Возьмем деталь 1 с минимальным и разобьем множество всех решений на два подмножества. В первом подмножестве деталь 1 делается последней, а во втором - не делается последней. Очевидно, что оценка снизу продолжительности обработки для первого подмножества равна пп "П, = + ш т Ь , = 1 3 + 7 = 2 0 , а д л я в т о р о г о г \ 2 = + т т Ь ( = 1 3 + 9 = 2 2 .
47 Выбираем подмножество с минимальной оценкой, то есть деталь 1 обра батывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальную величину Ь} из оставшихся деталей) обрабатывается предпоследней, а во втором - нет (то есть обрабатывается первой). Оценка пер вого подмножества Л=(СЬО=птах(19,20)- 20, а оценка второго Л=No12)=тах (22,20)=22. Выбираем первое подмножество. Соответствующая очередность обработки деталей (2,3,1) с продолжи тельностью обработки Т = 20. Это решение оптимально, поскольку оценка ос тальных подмножеств больше 20 (рис. 1.4.6). На рисунке число в скобках у дуг (например, (1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.). Рис. 1.4.6 В основе метода лежит сведение задачи оптимизации к задаче определе ния экстремальной траектории (минимальной или максимальной длины) в не котором специальным образом построенном семействе возможных траекторий. Принцип оптимальности Веллмана гласит: любой участок оптимальной траек тории оптимален [17, 25, 26]. В случае дискретных задач метод динамического программирования сво дится к определению пути максимальной или минимальной длины в специаль ным образом построенной сети. Дадим иллюстрацию метода на примере клас сической задачи о ранце. Имеются п предметов. Каждый предмет имеет цен
48 ность оц и вес С. Требуется выбрать подмножество £> предметов так, чтобы их суммарная ценность А((2) = 2 ^ а 1 была максимальной при ограничении на суммарный вес У]с, ^ Я . ,ея Способ построения сети рассмотрим на примере. Имеются четыре предмета, данные о ценностях и весах которых приведе ны в табл. 1.4.1. 11234 ai С| 3245 2134 Пусть Я = 6. Строим на плоскости систему координат, одна ось которой соответствует предметам, а вторая - их весу. По оси предметов отмечаем номера предметов 1,2,3,4 (рис. 1.4.7). Из начала координат проводим две дуги - одна - горизонтальная в точку (1,0), а другая - наклонная в точку (1,2), где 2 - в е с первого предмета. Первая дуга соответствует случаю, когда первый предмет не берется, а вторая - когда он берется. Из каждой полученной точки (1, 00) и (1,2) проводим также по две дуги для второго предмета. Получаем четыре точки (2,0), (2,1), (2,2) и (2,3), соответствующие четырем возможным вариантам для двух предметов. Продолжая таким образом, получим сеть, приведенную на рис. 1.4.7. Очевидно, что любой путь в сети из начальной вершины 0 в одну из ко нечных вершин соответствует некоторому набору предметов. И наоборот, лю бому набору предметов суммарным весом не более 6 однозначно соответствует путь в сети, соединяющий начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному весу предметов. Примем длины горизонтальных дуг равными 0, а длины наклонных равными ценности соответствующего предмета. В этом случае длина пути, соединяюще го начальную вершину с одной из конечных, равна суммарной ценности соот Таблица 1.4.1
49 ветствующего набора предметов. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на рис. 1.4.7 толстыми дугами. Рис. 1.4.7 Метод динамического программирования можно представить в другой эквивалентной форме, удобной для сравнения его с методом дихотомического программирования. Эта форма не требует построения сети, а использует мат ричный способ вычислений (рис. 1.4.8).
- Assistant
Принял.
- User
Первая матрица соответствует второму слою сети (рис. 1.4.7). В верхней половине каждой клетки указана величина веса для различных вариантов из двух первых предметов, а в нижней - соответствующая ценность. Вторая мат рица соответствует третьему слою, а третья - четвертому. Если в матрице име ется несколько клеток с одинаковыми весами, то в следующую матрицу для этого значения веса берется максимальное значение ценности. Это и есть прин цип оптимальности Веллмана для матричного представления метода динамиче ского программирования. В последнем столбике (см. рис. 1.4.8) приведены оп тимальные значения суммарной ценности предметов при любых ограничениях на вес ранца. Метод динамического программирования является эффективным мето дом решения некоторых задач дискретной оптимизации, существенно сокращая перебор. Так, например, для рассмотренной задачи о ранце при целочисленных 50 значениях весов предметов объем вычислений пропорционален числу вершин 'у сети, то есть не более чем Я п. При заданном К объем вычислений растет про порционально п, что свидетельствует о высокой эффективности метода. К со жалению, метод динамического программирования применим к ограниченному классу задач. Подводя итоги краткого обзора основных методов решения задач дис кретной оптимизации, отметим, что к точным методам решения (или к методам решения с оценкой точности) относятся метод ветвей и границ и метод дина мического программирования. Эффективность метода ветвей и границ в суще ственной степени зависит от точности нижних (или верхних) оценок оптималь ного решения на подмножествах решений. Получение хороших оценок во многих случаях по сложности сравнимо с решением исходной задачи. 1оУ ум 9 12 8 11 у4 6 4X т х 7 уьXй 10 зX зх 7X 6 XУ2х /5Х5XIо9 I/ 0X 9X 2 У 6х 5 X X /8 ХоХо/з У1 2X 0X 7 У2У^X7 6 X XI Хо СУ:- 1х1х5X 4 9X 0X 4X 3 Рис. 1.4.8 Метод динамического программирования, как уже отмечалось выше, применим к ограниченному классу задач. Описываемый в следующих параграфах метод дихотомического про граммирования, с одной стороны, обобщает метод динамического программи рования (при дихотомическом представлении типа дерева), а с другой - для У^9 юХ X X14 5X 5 У 9X /7 У1 XI2 ХоХоуъ 5 УгХ оX 4X 2 Х4Хо 3 1 2 О
при ограничении 51 общего случая дает достаточно универсальный алгоритм получения нижних (верхних) оценок, что позволяет эффективно применять метод ветвей и границ. 1.5. Методы сетевого и дихотомического программирования Многие задачи дискретной оптимизации сводятся к следующей поста новке: определить вектор х = {х(} с дискретными компонентами, минимизи рующий аддитивную функцию ф(х)=£ф,(х,) (1.5.1) 1=1 Цх)>Ь. (1.5.2) Любая функция дискретных переменных допускает сетевое представле ние, такое, что вычисление значений функции сводится к последовательному вычислению значений более простых функций. В частности, любая функция дискретных переменных допускает дихотомическое представление, когда вы числение значения функции сводится к последовательному вычислению значе ний функций двух переменных. Так, функция А(х) = ЭДЭДхь х2), Т2(х2, х3)] допускает дихотомическое пред ставление (рис. 1.5.1). При этом функции {} и {2 удобно представлять в мат ричном виде (рис. 1.5.2). Такое представление широко используется в методах комплексного оце нивания программ развития предприятий, регионов, результатов деятельности подразделений, уровня безопасности объектов и др. [2, 3, 4, 6, 16]. Рис. 1.5.1
52 В работах [6, 65] доказаны теоремы о представлении непрерывных функ ций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных (в частности, двух переменных). Так, например, любая непрерывная функция трех переменных представима в виде [1] г(х1,х2,х3)= ь1(х|,ф|(х2,хз))+ь2(х1,ф2(х2,хз))+ь3(х|,фз(х2,х3)). Ее сетевое представление приведено на рис. 1.5.3. Рис. 1.5.2 Рис. 1.5.3 В сетевом виде можно представить и систему неравенств. Рассмотрим, например, систему неравенств
53 fj(x)^ bj5 j = l,m . (1.5.3) Без ограничения общности можно принять, что bj - положительные и одинаковые числа, bj = ь > 0. В этом случае систему неравенств (3.3.3) можно заменить одним неравенством f(x)<b, где f(x) = m axf(x). Очевидно, что jj функция f(x) допускает сетевое представление, если все функции fj допускают такое представление. Ниже описывается новый метод решения задач дискретной оптимизации, использующий сетевое представление функции f(x). Этот метод естественно назвать методом сетевого программирования (в частном случае дихотомического представления получаем метод дихотомиче ского программирования [25]). Рассмотрим случай, когда функция f(x) допускает сетевое представление в виде дерева. Дадим описание метода сетевого программирования для задачи (1.5.1), (1.5.2). На рис. 1.5.4 приведен пример функции трех переменных, имеющей вид f(xbх2,Хз)=<po[f|(xbХ2), Х3] =фо(у,х3). Значения функций <p,(xj) даны в нижних половинах квадратов, соответст вующих переменным Х|, х2и х3. Идея метода состоит в следующем. Сначала решается задача минимизации функции двух переменных при ограничении Ф^Х,) -ь <р2(х2) fl(X|, х2)>у, соответствующая начальной вершине сетевого представления. Обозначим z(y) решение этой задачи в зависимости от у. Далее решаем задачу минимизации функции двух переменных z(y) + ср3(х3) при ограничении Фо(у> х3) > Ь, соответствующую конечной вершине сетевого представления. Решение этой задачи определяет оптимальное решение исходной задачи.
54 Несложно обобщить описанный метод на случай произвольного сетевого представления функции f(x) в виде дерева. Главное, чтобы задачи, соответст вующие каждой вершине сетевого представления, имели эффективные методы решения. В случае дихотомического представления это всегда имеет место. Заметим, что дихотомическое представление (см. рис. 1.5.4) имеет струк туру в виде ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае ди хотомического представления в виде дерева является обобщением метода ди намического программирования, расширяя круг задач, решаемых на основе данного подхода (рис. 1.5.4). Рис. 1.5.4 Если в методе динамического программирования решением задачи явля ется путь в некоторой специальным образом построенной сети, то в методе ди хотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно принцип оптимальности в методе дихотомического про граммирования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным.
55 Формально этот принцип оптимальности можно записать следующим об разом: где р(у) - множество пар (¡, }), таких, что {к(уь у]) = у. Рассмотрим произвольное сетевое представление функции А(х), задавае мое сетью, входом которой является вершина, соответствующая функции ]Г(х), авыходами- вершины,соответствующиепеременнымх{,/=1,п. Рассмотрим множество конечных вершин, которые не являются висячи ми, т.е. их степени захода больше 1. Разделим произвольным образом затраты на к* частей, где к} - число заходящих дуг. Фактически мы как бы разделили вершину I на к* висячих вер шин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина со степенью захода больше 1, мы делим затраты на соот ветствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако это решение может не быть решением исходной задачи. Тем не менее имеет место следующая тео рема: Теорема. Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. Доказательство. Заметим, что множество решений модифицированной сети содержит все решения исходной задачи. Эти решения имеют следующий вид. Если в вершину, соответствующую переменной х^, заходит хотя бы одна дуга полученного решения, то все дуги, заходящие в эту вершину, также при надлежат полученному решению. Отсюда следует, что полученное оптимальное решение модифицирован ной задачи дает нижнюю оценку для оптимального решения исходной задачи.
56 1.6 Выводы и постановка задач исследования Показано, что область строительного производства функционирует по всем признакам, характерным для технологии управления проектами. Дорож ное строительство представляет собой одну из специфических сфер деятельно сти строительных фирм. Произведен анализ современного состояния дорожной отрасли в целом по России, выявлены проблемы, стоящие перед дорожным хозяйством, и воз можные пути их решения. На основе выявленных особенностей линейно-протяженного строитель ства (перемещение фронта работ в пространстве (следовательно, необходимо осуществление перебазировки линейной бригады вслед за фронтом работ); дос таточно ограниченная, по сравнению с обычными объектами, номенклатура ра бот, подлежащих выполнению; наличие преобладающего материального ресур са, используемого при производстве работ; отсутствие самостоятельного про изводственно-экономического значения; сезонность) произведен анализ моде лей организации и управления данной отраслью. Было установлено, что основным инструментом управления проектами в дорожной сфере является календарный план, принимающий три основные формы представления расписания работ: линейную, циклограммную и сетевую, включая обобщенную, модели. Определены достоинства и недостатки каждой из моделей, выявлен двойственный характер процесса производства вообще и строительного производства в частности, когда календарный план может рас сматриваться, с одной стороны, как расписание работ, подлежащих выполне нию, а с другой - как график потребления ресурсов некоторог о вида. Показано, что учет этой двойственности может быть полноценно обеспе чен только на основе сетевых моделей. В связи с этим были проанализированы известные методы и алгоритмы решения задач распределения ресурсов на ос нове теории графов. В итоге анализа было установлено, что, несмотря на существование опре деленного методологического обеспечения для определения объемов работ по
57 строительству, ремонту и содержанию автомобильных дорог, отсутствуют ка кие-либо рекомендации относительно расположения ресурсов предприятия с целью успешной реализации своей производственной программы с учетом рас средоточенного характера объектов, включенных в неё. Таким образом, можно сделать вывод о том, что в основе эффективного управления отраслью дорожного строительства в условиях дефицита финансо вых средств должны лежать современные методы и модели, адаптированные к отраслевым особенностям и обеспечивающие повышение объективной состав ляющей в процессе принятия управленческих решений. Следовательно, цель диссертационной работы определяется необходимо стью разработки моделей, определяющих рациональное расположение и ис пользование производственных ресурсов типа мощности в процессе реализации проектов дорожного строительства. Для достижения цели работы необходимо решить следующие основные за дачи:
- Проанализировать существующие методы и модели управления до рожным строительством.
- Дать постановку задач календарного планирования в сфере дорожного строительства с учетом времени перемещения ресурсов с работы на работу.
- Предложить алгоритм определения продолжительности проекта при заданных потоках по графу перемещений ресурсов.
- Решить задачу оптимального распределения ресурсов для случая неза висимых работ с учетом времени перемещения ресурсов с работы на работу для одного и нескольких пунктов расположения ресурсов.
- Разработать методы решения задачи распределения т единиц ресурсов (бригад) по критерию минимизации времени выполнения проекта.
- Предложить модель определения очередности выполнения работ од ной бригадой (единицей ресурсов) при учете времени перемещения бригады от работы к работе при различных видах транспортных схем и случаях располо жения объектов.
58 7. Построить модель определения минимального числа бригад, которое позволит осуществить выполнение проекта при заданных сроках начала работ. 8. Разработать геометрический подход к оценке оптимального решения минимизации отклонения от плановых сроков для случая, когда число бригад больше одной, а транспортная схема является радиальной. 9. Получить точное решение задачи минимизации отклонения от плано вых сроков для радиальной транспортной схемы и нескольких бригад. 10.Дать постановку и предложить методы решения задачи распределения средств на ремонт участков дорог с целью снижения степени опасности участ ков дороги
- Assistant
Принял.
- User
- ИССЛЕДОВАНИЕ МОДЕЛЕЙ И МЕХАНИЗМОВ УПРАВЛЕНИЯ ПРОЕКТАМИ С УЧЕТОМ ТОПОЛОГИИ 2.1. Исследование двойной сетевой модели Введем основные понятия, характеризующую двойную сетевую модель. В задачах распределения ресурсов по комплексу работ предполагается, что они находятся в некоторой зависимости между собой. Эти зависимости обычно отображаются в виде сетевого графика. Существуют два способа изо бражения работ в сетевом графике. В первом способе работы изображаются в виде вершин сети, а зависимости между работами - в виде дуг сети. Во втором способе вершины сети соответствуют событиям сети, то есть моментам завер шения одной или нескольких работ, а дуги - работам сети. При этом для ото бражения всех требуемых взаимосвязей иногда приходится вводить дуги спе циального вида - фиктивные работы или работы нулевой продолжительности, не требующие ресурсов. Как правило, в задачах ресурсного планирования на сетях операции удобно рассматривать в виде «вершина-работа». Как показано в первой главе, для реализации комплекса работ требуются ресурсы одного или нескольких видов. Отметим, что если ресурсы неразличи мы в условиях конкретной задачи по их влиянию на скорость выполнения рабо ты, то они называются ресурсами одного вида [65, 70]. Понятно, что каждый вид ресурса участвует в выполнении какого-то набора операций, которые мож но объединить в классы. Таким образом, операции одного класса выполняются ресурсами одного вида. Рассмотрим процесс выполнения комплекса операций. После выполнения одной операции ресурсы перемещаются на другие операции своего класса (об разуют поток по множеству операций). Совершенно очевидно, что перемеще ние ресурсов с одной операции на другую невозможно по тем или иным причи нам (отсутствие транспортных средств, высокая стоимость или невозможность перемещения данного вида ресурсов и т. д.). В связи с этим возникает необхо 60 димость определения графа перемещения ресурсов (граф ПР). Он состоит из к компонент (по числу классов операций). Вершины графа соответствуют опера циям, от вершины 1 идет дуга к вершине], если возможно перемещение ресур сов от -й на]-ую операцию. Кроме того, каждой дуге (1,]) ставят в соответствие параметр цу - перемещение ресурсов от -й операции на ,)-ую. На рис. 2.1.2 показан граф ПР для сети на рис. 2.1.1. Он состоит из двух компонент, так как в комплекс входят работы двух классов. Л3[6] Отметим, что сеть рис. 2.1.1 является сопряженной, т. е. операциям кОхМ- плекса соответствуют вершины сети, а дуги отражают зависимости между опе рациями. Такое изображение более удобно, так как в графе ПР вершины также соответствуют операциям. К первому классу относятся операции А|, А2, Аб, А7, ко второму - А3, А4, А5. Числа в скобках равны потоку ресурсов по соответст вующей дуге. В квадратах хь х2 каждой компоненты графа ПР пишется количество ре сурсов Ы|, N2, предназначенных для выполнения операций соответствующего класса (N1= N2= 6 на рис. 2.1.2). Фиктивные вершины хь х2могут соответство вать некоторым пунктам, в которых находятся ресурсы. В свою очередь, Ъ, ъ2 могут соответствовать пунктам, в которые нужно собрать ресурсы после вы полнения комплекса. Определив некоторый поток ресурсов по графу ПР, мож но найти момент окончания каждой операции и, следовательно, время выпол-
нения всего комплекса. 61 Рис. 2.1.2. Граф перемещения ресурсов Фронтом операций в момент / называется множество Д /) операций, кото рые выполняются или могут выполняться в этот момент. Основная группа ал горитмов для решения задач распределения ресурсов основана на последова тельном получении решения путем распределения ресурсов по операциям фронта. Для этого определяется некоторое правило (пли несколько правил), по зволяющее в любой момент времени принимать решение о распределении ре сурсов по операциям фронта. В дальнейшем будем называть момент перерас пределения ресурсов конфликтной ситуацией. Процесс разрешения конфликт ных ситуаций удобно изображать графически в виде дерева. Вместо таких пра вил можно определять некоторую функцию (функция предпочтения) и выби рать распределение ресурсов, при котором эта функция принимает минималь ное (максимальное) значение. Приведем два простых правила [36, 184], кото рые часто применяются в алгоритмах такого типа. Правило 1. В первую очередь выполняются операции с меньшим полным резервом времени (резерв времени определяется при условии достаточного ко личества ресурсов).
62 Правило 2. В первую очередь выполняются операции с меньшей дли тельностью. Если для получения решения используются эвристические правила (взя тые из интуитивных соображений или на основании опыта), то целесообразно испробовать различные правила (или системы правил), выбирая затем наилуч шее решение. Отметим, что большинство правил эквивалентно заданию некоторой функции предпочтения. Например, распределение ресурсов, полученное по правилу 1 , минимизирует функцию Е и.(0Ат!(1)> *еР(1) где р(0 - множество номеров операций фронта; Дт ) - количество ресурсов, расходуемых в ¡-й операции. Распределение, полученное по правилу 2, минимизирует функцию X и.(Ф ,> ио где Т{- время выполнения операции, и т.д. В некоторых случаях удобно в качестве функции предпочтения взять нижнюю границу времени выполнения комплекса при выбранном распределе нии ресурсов по операциям фронта. При этом если мы уже получили какое- либо решение, а значение функции предпочтения на остальных вершинах дере ва решений больше или равно времени выполнения комплекса для полученного решения, то, очевидно, полученное решение оптимально. Рассмотрим на примере определение моментов окончания операций при заданном потоке ресурсов. Пример 2.1. Примем, что параметр перемещения ресурсов с операции на операцию равен нулю. Кроме того, примем, что не разрешается снимать ресур сы с операции, пока она не закончена (отказ от этих предположений несущест венно меняет методику расчета). Пусть скорость выполнения операции прямо пропорциональна количеству ресурсов, т. е. примем = ць \ = 1 7 (рис. 2.1.1,
63 рис. 2.1.2). Объемы операции представлены в табл. 2.1.1. Таблица 2.1.1 Номероперации 1 2 3 4 5 6 7 м>, 12 12 6 16 6 12 12 Определение моментов окончания операций производится последова тельным просчетом сети. Пусть А1}, А,2, А, - операции, непосредственно предшествующие операции А{; ^ ^ - моменты окончания этих операций. Тогда ^ = т а х ( ^ , - возможный момент начала ьй операции. Далее пусть Аи, А,5, А(б - операции, с которых перемещаются ресурсы на операцию А;; ^ , !5> !6 “ моменты окончания этих операций (соответственно моменты прихода ресурсов на ью операцию, если времена перемещения равны нулю). Для опре деления момента окончания ьй операции применяем формулу + Дт,. На рис. 2.1.2 показан некоторый поток ресурсов по 1рафу ПР. Будем обо значать множество операций, непосредственно предшествующих операции А, а Р - множество операций, с которых перемещаются ресурсы на операцию А*.
- ОперацияА|.<3]=0,.Р1=0, 1_^ =4,
-
- ОперацияА2.СЬ=0,Р2={А1}. Применяя формулу ^
- ОперацияА3.СЬ={А|},Р3=0,г,= =3,
- ОперацияА4.<34={АьА2},Р4=0,1°=шах^],1^=^=5, \у 1~ и, ^ + Дт,, получаем
64 114(0 = 2, 1*=1»+ ^ = 13. 5) ОперацияА5.СЬ={А2},Р5=0,4=4=5, и5(0=2,4=4+ ^ =8. 6) ОперацияА6.С!б={А3,А4},Р6={А,},4=шах(4,4)=13, 7)Операция А7.0-= {А4,А5},Р7= {А2,А6}, 4 =тах(4,4) =13. И м е е м г 1, = 4 + + 6 Моменты окончания операции указаны в скобках на рис. 2.1.1. Время вы полнения комплекса Т = тах^ = 17. Теперь появляется возможность улучшить решение, изменив поток ре сурсов (ресурсы с операций, имеющих большие резервы, перебрасываются на критические или близкие к ним операции). Уменьшим, например, потоки ре сурсов через вершины А3, А5 графа Г1Р на единицу и увеличим поток через вершину А4 на две единицы (рис. 2.1.3). При этом время выполнения комплекса уменьшилось до Т= 14 (рис. 2.1.4). Действительно, последовательно определяем 3
65 г; = 4 + ^ . = 5 + ^ = п , и5 1 4 =шах(1з;1’)+-^-=9+^ =13, ч6 3 , , w7—3*2 .._ 17=16+ -^ -------14,5. Аз а2 а7 Рис, 2.1.3 Аз[9] Иногда решение задачи должно удовлетворять дополнительному усло вию: количество ресурсов на операции не меняется в процессе ее выполнения.
66 Такое условие позволяет упростить процедуру. Действительно, в этом случае время выполнения операции определяется по формуле V/ Т=^ Г где и - поток ресурсов, в х о д я щ и й в соответствующую вершину. Теперь достаточно дополнить сетевой график недостающими дугами, по которым проходит ненулевой поток, и применить обычные алгоритмы опреде ления критического пути. Используя пример 2.1 (рис. 2.1.2), имеем распределе ние и продолжительности операций, представленные в табл. 2.1.2. Таблица 2.1.2 Номероперации 1234567 4322236 3438342 Добавляя в сетевой график (рис. 2.1.4) дуги (Аь А2) и (А6, А7), получаем сеть (рис. 2,1.5), просчитывая которую обычным способом, определяем Т = 21. Увеличение времени выполнения комплекса по сравнению с предыдущим слу чаем (Т = 17) вызвано запрещением изменения количества ресурсов в процессе выполнения операции. Определим критический путь в случае потока ресурсов, изображенного на рис. 2 .1 .5. А3[6] Рис. 2.1.5
67 Продолжительности операций указаны в табл. 2.1.3. i1234567 u, 4 3 1 4 1 3 6 X, 3 4 6 4 6 4 2 Сетевой график с поздними моментами окончания операций приведен на рис. 2.1.6. Аз[9] Можно предложить также другой способ определения времени выполне ния комплекса в случае запрета на изменение количества ресурсов на операции в процессе ее выполнения. Рассмотрим зависимость v(t) (рис. 2.1.7) начиная с момента возможного начала операции т (в момент т мы могли бы начать операцию, если бы имелось достаточное количество ресурсов). Если начать операцию в момент tJ? то она w будет выполняться со скоростью v,, момент окончания t = t + —L. Естественно vj определить момент начала операции так, чтобы момент окончания был мини мальным, т. е. момент окончания определяется по формуле w w. ь + — = t Jo + t, = min Для примера (рис. 2.1.7) имеем в случае w, = 36. Таблица 2.1.3
68 ^=пип(36,15,13,14 /7,19/2,)=13. т=0 Ь]-3 г2=7 /з=9 //=/5 /¿=/5 Рис. 2.1.7 При таком способе определения ^ добавочные дуги следует проводить в сети только от тех операций, ресурсы с которых перемещаются на ¡-ю опера цию в моменты времени не позднее Т . Ресурсы, приходящие позже, не прини мают участия в выполнении операции и сразу перемещаются на следующие операции. Заметим, что этот способ определения моментов окончания операций можно рассматривать как простейший алгоритм оптимизации распределения ресурсов. Рассмотрим, например, поток на рис. 2.1.3. Для операции А2имеем Л 12 о 12^_с /2=пип 0+—-;3+— -6, 23' то есть более выгодно выполнять операцию А2 двумя единицами ресурсов, не ожидая прихода третьей. Более того, эту третью единицу можно направить те перь на операцию А6, уменьшив время ее выполнения до т6= 3. Такое преобра зование потока ресурсов уменьшает время выполнения комплекса в нашем примере с 17 до 15. После введения основных понятий и определения графа ПР мы в состоя нии четко поставить задачу оптимального распределения ресурсов. Задана сетевая модель комплекса из п операций, в которую входит: 1 ) сетевой график; 2) граф ПР; 3) матрица |||Лу||, где Цу- параметр перемещения ресурсов с ьй операции наую;
69 4) зависимость ч\ = У|(щ) скорости выполнения ьй операции от количества ресурсов соответствующего вида (предполагаем, что - неубывающие функ ции щ); 5) количество ресурсов щ^го вида (} = 1, к ), где к - число классов опера ций. Требуется определить поток ресурсов по графу ПР, оптимизирующий не который параметр. В качестве такого параметра можно принять время выпол нения комплекса, упущенную выгоду, стоимость и т.д. Описанная модель охватывает довольно большой круг практических за дач. Отметим лишь, что ее частными случаями являются такие известные зада чи, как задача коммивояжера, задача определения оптимального порядка обра ботки деталей на станках и др. 2.2. Разработка классификационной модели объектов строительства по топологическому признаку Как правило, строительная организация одновременно ведет строительст во некоторого комплекса объектов, расположенных на некотором удалении от места постоянного базирования машин, механизмов и трудовых ресурсов, транспортировка которых к фронту работ может потребовать значительных за трат различного рода. В настоящих исследованиях рассмотрим затраты в виде стоимости и времени. Совершенно очевидно, что затраты на перемещение ре сурсов могут быть значительны и поэтому требуют их учета. Таким образом, рассмотрим модели и механизмы устранения узкого места на затраты переме щения ресурсов. С целью устранения или снижения влияния узкого места на перемещение ресурсов иногда целесообразнее передислоцировать их базирование ближе к фронту работ. При возведении нескольких объектов, расположенных друг от друга «близко» и «далеко» от места постоянного базирования ресурсов, можно переместить на время работ на этих объектах «ближе» к объектам. Таким обра зом, приведем некоторую терминологию, используемую в дальнейших иссле
70 дованиях. Сгруппированные объекты, на которые ресурсы перемещаются для выполнения работ с временного места базирования, назовем классом, а это ме сто - центром класса. Место постоянного базирования ресурсов назовем цен тром, а объекты, на которые ресурсы перемещаются для выполнения работ из центра, - центральным классом. В настоящих исследованиях примем, что работу выполняет только одна единица ресурса (бригада). Причем следует отметить, что при рассмотрении механизма классификации объектов строительства для одного ресурса понятия объект и работа эквивалентны1. Для классификации объектов строительства будем использовать параметр перемещения ресурсов между объектами. В качестве такого параметра примем стоимость единичного перемещения одной единицы ресурса, а критерием каче ства разбиения - минимизацию стоимости комплекса работ. Таким образом, задача классификации объектов строительства заключа ется в разбиении множества N = {1,2, ..., п} объектов и центров N0= {1, 2, ..., по} на подмножества Nk= {1, 2, ..., nk}, где k е Н = {1, 2, ..., h} - множество классов (рис. 2.2.1), с учетом множества возможных параметров пе ремещения ресурса между объектами Му = {ру1, ру2, ..., рур}, рур> 0, i, j е N u No, где p - число возможных параметров перемещений между объек- h тами. Следует отметить, что множество N = [jN k. Совершенно очевидно, что k—1 целесообразнее использовать р = min р[*. р Пусть комплекс работ выполняет одна бригада, то есть u = 1. Понятно, что при постоянном количестве ресурсов каждая работа имеет известную про должительность Tj на объекте i и может быть определена по формуле 1Если рассматриваемая бригада выполняет несколько работ на объекте, то всегда можно до бавить фиктивные объекты, параметр перемещения ресурсов между которыми равен нулю.
71 Если под параметром перемещения ресурсов принять стоимость одного перемещения одной единицы ресурса, то стоимость перемещения ресурсов из центра в рамках центрального класса можно определить по формуле C0¡=(Hoi+Ию)■ti, i € Но. (2.2.1) Заметим, что параметр po¡ перемещения из начального пункта в пункт i, где выполняется работа i, в общем случае не равен параметру p¡o возвращения в начальный пункт. Дело в том, что po¡ может включать показатели на подготовительные работы, подбор инструмента и т.д., а (¿¡о может включать показатели на подготовку техники и инструмента к отъезду. Стоимость центра класса можно определить по формуле ск= сск+ ск*тк,кеН, (2.2.2) где сск - стоимость постройки и ликвидации k-го центра класса, ск > 0; ск - стоимость эксплуатации k-го центра класса в единицу времени, ск > 0; тк- про должительность эксплуатации k-го центра класса, Тк > 0. Сравнивая правые части равенств (2.2.1) и (2.2.2), получим предельные границы центрального класса: (Hoi+ho)-'ti< ck+ c ít,.
или 72 (Ро.+Р.о" Ск)-*, < Ск (2ц0,“О -т<с"приНО!=Рю- '0| У1^ '’'к (2.2.3) Если система состоит только из одного объекта (рис. 2.2.2), то справедли вость неравенства (2.2.3) показывает принадлежность объекта к центральному классу.
- Assistant
Принял.