Содержание к диссертации
Введение
1. Анализ моделей линейно - протяженного строительства 15
1.1. Модели управления строительством линейно - протяженных объектов 15
1.2. Методы решения управленческих задач при строительстве линейно - протяженных объектов 35
1.3. Сетевые модели и методы решения задач распределения ресурсов 40
1.4. Механизмы распределения ресурсов на корпоративном уровне 47
1.5. Выводы и постановка задач исследования 51
2. Распределение ресурсов на основе конкурсных ме ханизмов 54
2.1. Распределение ресурсов при двухуровневом конкурсном механизме 54
2.2. Многоэтапные механизмы конкурсного распределения ресурсов . 67
2.3. Механизм распределение ресурсов на основе двухуровневого конкурса в общем случае 74
3. Модели распределения ресурсов организации в пространстве 80
3.1. Модель распределения ресурсов организации в пространстве 80
3.2. Задача размещения территориально-рассредоточенных объектов с учетом объемов выполняемых работ 95
3.3. Методы решения задачи содержания объектов и обслуживания потребителей 102
3.4. Проектирование технической оснащенности строительного предприятия 115
3.5. Модель формирования производственной программы предприятия 121
Заключение 125
Литература 126
Приложение 1 141
Приложение 2 142
Приложение 3 143
- Методы решения управленческих задач при строительстве линейно - протяженных объектов
- Сетевые модели и методы решения задач распределения ресурсов
- Многоэтапные механизмы конкурсного распределения ресурсов .
- Задача размещения территориально-рассредоточенных объектов с учетом объемов выполняемых работ
Введение к работе
Актуальность темы. Область строительного производства функционирует по всем признакам, характерным для технологии управления проектами. Линейно-протяженное строительство представляет собой одну из специфических сфер деятельности строительных фирм. Причем проекты линейно-протяженного строительства носят, как правило, масштабный характер, охватывая значительную территорию, и требуют для своей реализации привлечения производственных организаций, построенных по корпоративным принципам. В процесс реализации проекта вовлечено большое количество контрагентов, которые находятся по отношению к руководителю проекта в различной степени подчиненности: от прямого подчинения, в рамках существующей организационной структуры предприятия, до исполнителей, являющихся самостоятельными юридическими лицами, совершенно автономных от организационной структуры, внутри которой находится руководитель проекта.
В процессе реализации проекта линейно-протяженного строительства, распределение ресурсов является ключевой процедурой в процессе подготовки строительного производства. Процедуры распределения ресурсов, а также характер распределяемых ресурсов сильно зависят от уровня иерархии управления, на котором происходит это распределение. В принципе можно выделить два уровня: корпоративный, когда распределению подлежат чаще всего финансовые ресурсы и производственный, когда распределению подлежат материально-технические ресурсы.
На корпоративном уровне характер распределяемого ресурса, как правило, не учитывается и может представлять собой как сырье, финансы, энергию, так и любой другой вид продукции, необходимой для работы производственных организаций, вовлеченных в реализацию конкретного проекта.
В процессе распределения материально - технических ресурсов, то есть распределения на производственном уровне, особое значение приобретает распределение ресурсов типа мощности (техника, рабочие кадры и т.п.), которые в отличие от остальных ресурсов необходимо распределять не только по времени, но и в пространстве. В сложившейся практике проектирования распределение материально-технических ресурсов осуществляется как распределение усилий производственной организации только по времени. Распределение же производственных ресурсов типа мощности в пространстве осуществляется путем констатации желательного их месторасположения в определенные моменты.
Следовательно, актуальность диссертационной работы определяется необходимостью разработки моделей и механизмов управления, побуждающих исполнителей к максимальному использованию всех резервов с целью достижения наибольшей эффективности в использовании выделяемого ресурса и определяющих рациональное расположение, использование и техническое оснащение производственных подразделений предприятий, занятых строительством линейно-протяженных объектов.
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:
федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»;
госбюджетная научно-исследовательская работа «Разработка и совершенствование моделей и механизмов внутрифирменного управления» №ГОО-3.3-306.
Цель и задачи исследования. Целью диссертации является разработка моделей и механизмов управления проектами строительства линейно - протяженных объектов, обеспечивающих наибольшую эффективность в использовании выделяемого ресурса и определяющих рациональное расположение, использование и техническое оснащение производственных подразделений предприятий линейно-протяженного строительства.
Достижение цели работы потребовало решения следующих основных задач:
проанализировать существующие механизмы и модели управления линейно-протяженным строительством;
построить механизм распределения ресурса на корпоративном уровне;
рассмотреть задачу распределения производственных ресурсов типа мощности для организации, занятой в линейно-протяженном строительстве, отличающуюся учетом уже существующего размещения ресурсов и неразмещения двух единиц ресурса в близких или соседних пунктах;
разработать метод решения задачи размещения объектов обслуживания по критерию минимизации затрат на обслуживание для различных типов зависимостей затрат от объема работ по обслуживанию;
применить метод сетевого программирования для получения нижних оценок затрат при размещении территориально рассредоточенных объектов, используемых в методе ветвей и границ;
дать формулировку обобщенной двойственной задачи для задачи размещения, решение которой дает нижнюю оценку затрат на содержание объектов и обслуживание пользователей.
Методы исследования. В работе использованы методы моделирования организационных систем управления, теории активных систем, системного анализа, математического программирования.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
механизм распределения ресурса на корпоративном уровне, основанный на разбиении всех претендентов на ресурс, на группы, в каждую из которых включаются контрагенты с одинаковым уровнем эффективности; при числе групп больше двух это позволяет применять данный механизм для любого количества групп, имеющих различную эффективность;
эвристические правила распределения производственных ресурсов типа мощности для организации, занятой в линейно-протяженном строительстве, с учетом уже существующего размещения и неразмещения двух единиц ресурса в близких или соседних пунктах, отличающиеся тем, что затраты на
создание и содержание объектов обслуживания зависят от объема работ "по обслуживанию пользователей;
метод решения задачи размещения объектов обслуживания по критерию минимизации затрат на обслуживание для выпуклых кусочно-линейных и кусочно-постоянных зависимостей затрат от объема работ по обслуживанию;
метод сетевого программирования для получения нижних оценок затрат при размещении территориально рассредоточенных объектов, используемых в методе ветвей и границ;
решение обобщенной двойственной задачи для задачи размещения, результат которой дает нижнюю оценку затрат на содержание объектов и обслуживание пользователей; доказано, что это задача выпуклого программирования.
Практическая значимость и результаты внедрения. На основании выполненных автором исследований разработаны модели и механизмы, позволяющие на корпоративном уровне повысить эффективность использования выделенных ресурсов, а на производственном - рационально распределить ресурсы типа мощности в пространстве.
Использование разработанных в диссертации моделей и механизмов позволяет многократно применять разработки, тиражировать их и осуществлять их массовое внедрение с существенным сокращением продолжительности трудозатрат и средств.
Разработанные модели используются в практике работы ЗАО «Газпром инвест Юг» и ООО «Газпром трансгаз Москва» Воронежское УМГ.
Модели, алгоритмы и механизмы включены в состав учебного курса «Управление проектами», читаемого в ГОУВПО «Воронежский государственный архитектурно-строительный университет».
Апробация работы. Материалы диссертации, ее основные положения и результаты докладывались и обсуждались на следующих конференциях и семинарах: международных и республиканских конференциях, симпозиумах и научных совещаниях (2005 - 2009), 58 - 62 научно-технических конференциях ВГАСУ (Воронеж, 2005 - 2009); V Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Воронеж, 2008); Всероссийской научно-технической конференции «Управление в организационных системах» (Воронеж, 2008).
Публикации. По теме диссертации опубликовано 12 научных работ, в том числе 8 - в изданиях, рекомендованных ВАК РФ.
В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: [1], [4], [11], [12] механизм распределения ресурса на корпоративном уровне; [3], [5], [11] эвристические правила распределения производственных ресурсов типа мощности; [8], [11] метод решения задачи размещения объектов обслуживания по критерию минимизации затрат на обслуживание; [9], [10] метод сетевого программирования для получения нижних оценок затрат при размещении территориально рассредоточенных объектов; [2], [11] формулировка обобщенной
двойственной задачи для задачи размещения.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 186 наименований и приложений. Основная часть изложена на 143 страницах, содержит 26 рисунков и 18 таблиц.
Методы решения управленческих задач при строительстве линейно - протяженных объектов
Основные особенности линейно - протяженного строительства, рассмотренные в предыдущем параграфе, являются основой для задач, характерных именно для этого типа строительства. К таким задачам, в первую очередь, относятся задачи: определение оптимального радиуса действия линейной бригады; определение численного состава линейной бригады и числа линейных бригад, необходимых для выполнения заданного объема работ.
Следует отметить, что все эти задачи вытекают из основной особенности линейно — протяженного строительства: перемещения фронта работ в пространстве. Это вынуждает осуществлять перебазировку линейных бригад, затрачивая время и дополнительные средства. Естественно возникает задача сокращения перебазировок линейной бригады при строительстве одного объекта.
Зная радиус действия бригады Rom можно найти площадь, соответствующую данному радиусу: f = пК20ПТ. Тогда, зная общую площадь области, в которой должна будет действовать линейная бригада, число мест временного базирования можно определить как отношение площадей:
При определении оптимального радиуса действия линейной бригады будем исходить из минимизации полных затрат на строительство линейно - протяженного объекта единичной длины. При этом, полные затраты будут включать в себя следующие компоненты: С - себестоимость строительства без учета непроизводственных затрат; Снп- затраты на перемещение бригады от места временного базирования до места строительства; Спб- затраты на перебазирование линейной бригады.
Рассматривая сроки строительства линейно - протяженных объектов, приходим к заключению, что сокращение сроков строительства связано с возрастанием сметной стоимости и ростом непроизводственных расходов, связанных с увеличением затрат на перебазировку. Связано это с тем, что существенное сокращение сроков строительства возможно только при увеличении числа линейных бригад и строительной техники, задействованной на объекте. А это ведет к снижению эффективности использования техники и увеличению затрат на перебазировку. Эти затраты могут существенно превысить экономию от сокращения сроков строительства. В связи с этим, возникает задача определения минимального количества линейных бригад для выполнения заданного объема работ, при этом директивные сроки строительства должны быть соблюдены, а полные затраты должны быть минимальны.
Выражение (1.2.15) представляет собой целевую функцию затрат относительно числа бригад п. Дифференцируя это соотношение по п, и приравнивая полученное выражение к нулю, получаем уравнение для нахождения числа линейных бригад п, решая которое находим: На первом этапе четырехэтапного конкурса в число победителей входят два претендента с эффективностью 8 и один претендент с эффективностью 7. Эффект от первого этапа составляет 16 + 14 = 30, а от остальных трех этапов - 54, что в сумме дает 84 76. Остаток ресурса составляет 10% единиц. Рассмотрим разбиение претендентов на три группы. Путь из трех дуг, имеющий максимальную величину L это путь: i(3)=(l, 3, 5, 6). Ему соответствует разбиение претендентов на три группы. В первую группу входят претенденты с эффективностями 8 и 7, во вторую — претенденты с эффективностями 5 и 4 и в третью - с эффективностью 2. Эффект от трехэтапного конкурса составит 30 единиц на первом этапе, 64 единицы — на втором и 10 единиц - на третьем, что в сумме дает: L(3)=104 84. Экономия ресурса составляет 7 единиц. Рассмотрим разбиение всех претендентов на две группы. Путь из двух дуг, составляют пути: ц(2)=(1, 4, 6), ц(2)=(1, 5, 6). Первому пути соответствует разбиение претендентов на две группы, в первую из которых входят претенденты с эффективностями 8, 7, 5, а во вторую - претенденты с эффективностями 4 и 2. На первом этапе двухэтапного конкурса эффект составит 64 единицы, а на втором - 58, что в сумме дает L(2)=122 103. Экономия ресурсов составляет 3 единицы. Второму пути соответствует разбиение претендентов также на две группы, в первую из которых входят претенденты с эффективностями 8, 7, 5, 4, а во вторую - претенденты с эффективностью 2. Эффект от первого этапа составляет 108 единиц, а от второго - 10 единиц, что в сумме составляет 118 122.
Экономия ресурса составляет 5 единиц. Оценим теперь эффект простого конкурса. Нетрудно показать, что в случае простого конкурса в равновесии финансируются все претенденты с эффективностями 8, 7 и 5 и один претендент с эффективностью 4, что дает эффект 108. Таким образом, оптимальным является разбиение претендентов на две группы, в первую из которых входят проекты с эффективностями 8, 7 и 5, а во вторую - с эффективностями 4 и 2.
Сетевые модели и методы решения задач распределения ресурсов
Задачи распределения ресурса на сетях удобно рассматривать, изображая операции вершинами сети, а события (зависимости) - дугами (представления «операции-дуги, события-вершины» и «зависимости-дуги, операции-вершины» эквивалентны [15]). Пунктиром могут быть отражены ресурсные зависимости -когда для выполнения одних и тех же операций должны быть использованы одни и те же ресурсы. Примером могут являться сети, изображенные на рис. 1.3.1 и 1.3.2.
Для определения оптимального распределения ресурса необходимо найти критические пути для каждого из вариантов распределения ресурса и сравнить длины этих путей (в сети, приведенной на рис. 1.3.1, существует общий для операций «0-1» и «0-2» ресурс; потенциалы вершин, соответствующие различным способам использования этого ресурса - сначала выполняется операция «0-1», затем «0-2» и наоборот, приведены на рис. 1.3.1 соответственно в квадратных скобках и без скобок).
К сожалению, универсальных эффективных точных методов решения задач распределения ресурсов на сетях не существует. В качестве частного случая, для которого существует простой алгоритм, приведем следующий пример.
В сети, изображенной на рис. 1.3.2, для трех операций известны длины критических путей ТІ (от них через некоторую сеть до конечной вершины). Требуется определить очередность выполнения этих трех операций при условии, что все операции выполняются одной единицей ресурса и поэтому не могут выполняться одновременно.
Если для выполнения проекта выделено ограниченное количество ресурса, то возникает задача наилучшего его использования. Обозначим w( - объем /-ой операции, f yi) - скорость ее выполнения в зависимости от количества ресурса V/. Предположим, что fi( ) - непрерывная справа неубывающая функция, причем fj(0) = 0. Если vfa) - количество ресурса на /-ой операции в момент времени /, то момент ti ее окончания определяется как минимальное время, удовлетворяющее уравнению:
Если количество ресурса, используемое при выполнении некоторой операции, не изменяется во времени, то говорят, что она выполняется с постоянной интенсивностью. Тогда продолжительность операции определяется выражением:
В настоящее время общих алгоритмов поиска распределения ограниченных ресурсов между операциями, минимизирующих время завершения проекта, не существует. Поэтому рассмотрим несколько частных случаев.
В практике реального управления проектами, возникает необходимость таким образом распределить ограниченные ресурсы, чтобы получить максимально возможный эффект от их использования при существующих ограничениях. Рассмотрим метод «затраты-эффект» на следующем примере [1].
Изменим номера мероприятий так, чтобы самое эффективное мероприятие получило номер 1, следующее за ним - номер 2 и т.д. При новой нумерации строим табл. 1.3.2, в которой, помимо затрат и эффекта, по каждому мероприятию добавляются столбцы, в которых определяются затраты и эффект нарастающим итогом. Таблица затрат и эффекта нарастающим итогом, в которой мероприятия пронумерованы в порядке убывания эффективности и отражает зависимость «затраты-эффект». График этой зависимости приведен на рис. 1.3.3. Эта зависимость имеет замечательное свойство - она определяет максимальный эффект по данному критерию, который можно получить от заданного множества мероприятий при заданной величине финансирования. Фактический эффект может быть меньше за счет дискретности мероприятий. Действительно, если имеется 140 единиц финансовых ресурсов, то нельзя реализовать первые два мероприятия, требующие 160 единиц ресурса. Оптимальный вариант - реализовать второе и третье мероприятия, что дает суммарный эффект 380 единиц, что меньше, чем получается по зависимости рис. 1.3.3 - эффект 480 единиц. Конечно, если бы каждое мероприятие можно было реализовать частично, с пропорциональным уменьшением и затрат, и эффекта, то зависимость рисунка соответствовала бы реальному эффекту при любом уровне затрат.
Для решения этой задачи, при различных значениях R эффективным является метод динамического программирования. Для применения метода пред 44 варительно строим на плоскости систему координат, одна ось которой соответствует мероприятиям, а вторая - объему финансирования (см. рис. 1.3.4). По оси мероприятий отмечаем номера мероприятий — 1, 2, 3, 4. Из начала координат проводим две дуги — одна горизонтальная, в точку (1,0), а другая - в точку (1,60), где 60 - объем финансирования первого мероприятия. Первая дуга соответствует случаю, когда первое мероприятие не финансируется, а вторая, - когда оно финансируется. Из каждой полученной точки ((1,0) и (1,60)) проводим также по две дуги, для второго мероприятия. Получаем уже четыре точки -(2,0), (2,60), (2,100) и (2,160), соответствующие четырем возможным вариантам для двух первых мероприятий (если бы оба мероприятия требовали одинакового финансирования, то мы получили бы три точки). Продолжая таким же образом, получаем сеть, приведенную на рис. 1.3.4. Очевидно, что любой путь в сети из начальной вершины (0,0) в конечные вершины соответствует некоторому набору мероприятий. И наоборот, любому набору мероприятий соответствует вполне определенный путь в сети, соединяющий начальную вершину с конечной.
Значение координаты по второй оси равно объему финансирования соответствующего набора мероприятий (или пакета проектов). Примем длины горизонтальных дуг равными 0, а длины наклонных — эффектам от соответствующих мероприятий. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, будет равна суммарному эффекту от соответствующего этому пути множества мероприятий. Следовательно, путь максимальной длины, соединяющий начало координат и точку (4, S) будет соответствовать множеству мероприятий, дающему максимальный эффект среди всех множеств мероприятий, требующих совокупного финансирования ровно единиц. Таким образом, мы получаем оптимальные наборы мероприятий при любых объемах финансирования.
Многоэтапные механизмы конкурсного распределения ресурсов .
Из условия равновесия для победителей, имеющего вид: получаем величину заявок, сообщающую победителями простого конкурса где q 3j для всех групп j, вошедших в число победителей.
Оценим эффективность многоэтапного конкурса. Легко видеть что во всех группах не финансируются только первые претенденты, поскольку они требуют минимальных затрат в своей группе. Заметим, что ресурса R = 57 достаточно для проведения конкурсов во всех группах. Суммарный эффект составит: Lnp=4-9+312+215+18=120 112. Предыдущие выводы и примеры убедительно продемонстрировали преимущества многоэтапных конкурсов. В случае, если претенденты внутри одной группы имеют разные эффективности, анализ многоэтапного конкурса становится более сложной задачей. Приближенные оценки можно получить, принимая эффективности претендентов в одной группе равными минимальной эффективности в этой группе. Пример 2.2.2. Имеются 3 группы по два претендента в каждой группе. Данные о претендентах приведены в табл. 2.2.2. Таблица 2.2.2. Для первой группы возьмем Зі = 7, для второй Э2 = 4, а для третьей Э3 = 1. Пусть R = 30. группа проекты -С,j ги Эц I 1 16 2 8 21 3 7 II 1 25 5 5 24 6 4 Ш 1 20 10 2 18 18 1 Проведем сравнение простого и трехэтапного конкурсов, считая, что претенденты в каждой из трех групп имеют одинаковые эффективности. Простой конкурс. / шаг Определяем: R 30 30 так как qi Э2, то определяем: L.+L, 86 13 q =_! 2- = — = 2—, 30 30 15 так как qi Э3, то в равновесии для простого конкурса финансируются первые две группы с суммарным эффектом Lnp=86. Трехэтапный конкурс. При эффективности претендентов первой группы Зі = 7 затраты первого претендента этой группы следует скорректировать: Гп Э, 7 7 Так как ru ri2 = 3, то в конкурсе внутри первой группы побеждает второй претендент. Аналогично следует скорректировать затраты первого претендента третьей группы: Г2 Э2 4 4 И затраты первого претендента третьей группы: =20 = 20. Э3 1 При проведении конкурса во второй группе побеждает первый претендент, (выполняется условие г;2 г22) при проведении конкурса в третьей группе также побеждает первый претендент, так как i 3 г2. Суммарный эффект трехэтапного конкурса составит: LTp=21+25+20=66 86. Таким образом, организация трехэтапного конкурса в данном случае не целесообразна. Приведем точное сравнение эффективностей простого и трехэтапного конкурсов. Для простого конкурса по-прежнему примем, что финансируются претенденты первых двух групп при сообщении оценок: где L,+L2 R 15 Суммарный эффект не изменился: Lnp=86. При трехэтапном конкурсе на первом этапе побеждает первый претендент при сообщении оценки: Sn= - = 2-. 11 7 7 На втором этапе побеждает также первый претендент при сообщении оценки: 12 4 4 На третьем этапе также побеждает первый претендент при сообщении оценки: S = = 20. із х Суммарная эффективность трехэтапного конкурса составляет: Lnp=16+25-20=61 86.
В общем случае претенденты имеют разные эффективности. В многоэтапных конкурсах претенденты уже разбиты на группы и каждый этап свя 75 зан с проведением конкурса претендентов одной группы. Если такого разбиения на группы нет, то для проведения многоэтапного конкурса необходимо предварительно разбить претендентов на группы. Такой конкурс будем называть двухуровневым. Первый уровень связан с разбиением всех претендентов на несколько групп, а второй уровень связан с проведением многоэтапного конкурса. Разбиение следует проводить таким образом, чтобы эффективности претендентов в одной группе были максимально близкими. В качестве критерия близости примем отношение минимальной эффективности в группе к максимальной. Обоснованием выбора такого критерия служит гарантированная оценка эффективности простого конкурса, приведенная в [104].
Вершины пронумерованы по убыванию эффективностей соответствующих претендентов. Примем, что число претендентов, имеющих некоторую эффективность Э, больше 1.
Каждую пару вершин i, j, такую что i j, соединим дугой (i, j), длина % которой равна величине а в группе, содержащей претендентов от і — го до (j - 1). Каждую вершину і соединим с вершиной - выходом (п + 1) дугой (i,n+l), длина &т+\ которой равна величине а в группе, содержащей всех претендентов с і — го до п - го.
Заметим, что любому пути в этой сети, соединяющему вершину 1 с выходом, соответствует вполне определенное разбиение всех претендентов на группы, число которых равно числу дуг пути. Верно и обратное, любому разбиению проектов на Р групп соответствует путь в сети, соединяющий вершину 1 с вершиной выходом, число дуг которого равно Р. Задача свелась к определению пути ц, имеющего максимальную величину минимальной длины дуг, то есть имеющему максимум величины: L = min ... (2.3.3) Алгоритм решения задачи. 1 шаг. Помечаем вершину 1 индексом: Л., =0. к-ый шаг. Пусть помечены все вершины от 1 до (к-1). Помечаем вершину к индексом: Я.к =maxmin[A,.; ik]. Индекс вершины (п + 1) будет равен максимальной величине (2.3.3). Доказательство достаточно очевидно следует из того факта, что генезис каждой вершины равен максимальной величине (2.3.3) для путей, соединяющих вершину 1 с данной вершиной. Путь, имеющий максимум величины (2.3.3) определяется методом обратного хода. А именно, начиная с вершины (п + 1) определяем вершину іь такую что 4+i=min(4;At.B+J Далее, определяем вершину іг іі, такую что и так далее, пока не дойдем до вершины is=l. Путь i = (l,is_,v.. i2,i,) является решением задачи. Пример 2.3,1. Пусть число претендентов равно 10. Причем имеются по два одинаковых претендента. Соответствующие данные приведены в табл. 2.3.1. Таблица 2.3.1. і 1 2 3 4 5 Гі 1 2 4 6 5 l\ 8 14 20 24 10 ЗІ 8 7 5 4 Рис. 2.3.1 скобках у соответствующих дуг. Семь из шести вершин приведена на рис. 2.3.1. Длины дуг указаны в Путь с максимальной величиной L=l состоит из пяти дуг, что соответствует разбиению всех претендентов на 5 групп. Пусть R = 30. В этом случае, финансируется по одному претенденту из каждой группы с суммарным эффектом: L(5)=76, при этом остается ресурс в количестве 12 единиц. Рассмотрим разбиение на 4 группы. Из всех путей, состоящих из 4 дуг максимальную величину L=7/8 имеет путь: ц=(1,3, 4, 5, 6), которому соответствует разбиение претендентов на 4 группы. В первую группу входят 4 претендента с эффективностями 8 и 7, а в остальные три группы входят по два претендента с эффективностями 5, 4 и 2, соответственно.
Задача размещения территориально-рассредоточенных объектов с учетом объемов выполняемых работ
Рассмотрим задачи размещения объектов обслуживания. Имеются п возможных пунктов размещения объектов, которые должны обслуживать т пользователей, расположенных в различных пунктах. Для каждого пользователя задан объем работ по обслуживанию Wj и затраты dy на обслуживание единицы объема у-го пользователя из пункта обслуживания /. Для каждого пункта обслуживания задана зависимость fi(Vi) затрат на содержание г -го пункта от объема работ по обслуживанию (содержания и обслуживания).
В этом случае возникает следующая задача: определить множества Q пунктов размещения объектов обслуживания и определить объемы работ х0-по обслуживанию у-го пользователя в г-м пункте обслуживания, при которых суммарные затраты на содержание пунктов обслуживания и на обслуживание пользователей минимальны: = W/І ТО + 2j dtjxijl (3.2.1) при ограничениях «К? где Vt=ZjXtJ. (3.2.2) Заметим, что если пренебречь затратами на обслуживание, то получаем задачу минимизации затрат на содержание пунктов обслуживания.
Если сложность обслуживания единицы объема не зависит от пункта расположения пользователя (например, если затраты на перевозку или доставку бригад обслуживания несет пользователь), то есть если dtj = dt, то также получаем задачу 1 с критерием: =ад/да)+ад. (3.2.6)
Если множество Q пунктов обслуживания и объемы работ V{ по обслуживанию, которые может выполнить /-ый пункт определены, то получаем задачу минимизации затрат на обслуживание. Задача 2 (задача обслуживания). Определить объемы Ху обслуживания /-го пользователя в г -том пункте обслуживания, минимизируются затраты на обслуживание: F(x) = Е№ ? Гр=1 dijXij, (3.2.7) при ограничениях (3.2.2) и (3.2.3). Это обычная транспортная задача, методы решения которой хорошо разработаны. Замечание. Если функция fi(Vj) являются минимальными /,(Ц)=ВД, (3.2.8) то также получаем транспортную задачу с критерием: Fix) = T,iBQ Zi№ + йфхіґ (3.2.9) Рассмотрим методы решения поставленных задач, которые будут зависеть от вида функцийf(V,). Рассмотрим несколько случаев. ПустьftiV,) - выпуклые функции, то есть: fttaxt + (1 - а)Уі) aftM + (1 - сс)ГіУі, (3.2.10) где О ос 1. Методы решения задачи при вогнутых зависимостях хорошо известны. Поэтому дадим краткое описание. Если f дифференцируемые функции и /"(0)=0, то применяется метод множителей Лагранжа. Условия оптимальности имеют вид fi (Vi)=Ati=Ui, (3.2.11) где X - множитель Лагранжа, который определяется из уравнения где Yt - функции, обратные /.
В том случае, когда зависимость затрат от выполняемых работ имеет кусочно-линейный непрерывный вид, возможно примение следующего алгоритма: 1. Упорядочиваем все отрезки линейности по возрастанию угловых коэффициентов. 2. Распределяем объемы работ по отрезкам в соответствии с наименьшим упорядочиванием, пока не распределим объем W.
Пример разрывной зависимости Задачи такого типа относятся к сложным многоэкстремальным задачам. Рассмотрим применение метода ветвей и границ. Для получения нижних оценок (границ) построим «овыпукление» функций fi («овыпуклением» называется построение выпуклой функции нигде не превышающей исходную функцию), то есть максимально близкий к исходной функции. На рис. 3.2.2 примером показана функция f, полученная в результате операции овыпук-ления. Получаем случай кусочно-линейных выпуклых функций, для которого задача легко решается. Как было замечено выше в оптимальном решении оценочной задачи для не более чем одного объекта будет иметь число несовпадение функции /и f. Именно по этому объекту целесообразно проводить ветвление, поскольку метод ветвей и границ подробно описан в литературе [26], ограничимся иллюстрацией алгоритма на примере.
Получим достаточные условия оптимальности решения. Обозначим R( - множество потребителей, обслуживаемых і-м пунктом в решении оценочных задач и, - XX Следствие. Если для всех і, таких что Q, 0 имеет место т,=а/, то полученное решение является оптимальным. Доказательство очевидно, поскольку в этом случае нижняя оценка является достижимой. Следствие дает процедуру улучшения оценки, то есть процедуру изменения {Sy}: если для некоторой / имеет место Uj ah то соответствие Sy, j є R, следует увеличивать. Действительно, в рассмотренном примере на втором шаге мы увеличили S41, поскольку 1єі?4, а и/=2 12. На третьем шаге мы увеличили S43, поскольку в первом решении 3 є Я4, a w =2 10, а также увеличили ui3, так как во втором решении Зєі?1} a U]=0 ai. Составной частью метода является решение задачи (3.3.7) и (3.3.8).
