Содержание к диссертации
Введение
1. Управление проектами 6
1.1. Понятие проекта 6
1.2. Понятие управления проектом 21
1.3. Задачи ресурсного планирования комплексов работ 30
Основные понятия и определения 30
Оптимизация по стоимости 39
1.4. Постановка задач исследования 42
2. Метод дихотомического программирования 43
2.1. Методы решения задач дискретной оптимизации 43
Методы локальной оптимизации 43
Метод ветвлений 47
Метод ветвей и границ 48
Метод динамического программирования 50
2.2. Дихотомическое представление функций и систем ограничений 53
2.3. Дихотомическое представление типа дерева 55
2.4. Общий случай 58
2.5. Задача целочисленного линейного программирования 61
2.6. Некоторые обобщения 67
3. Задачи управления проектами 71
3.1. Оптимизация последовательности выполнения проектов 71
3.2. Оптимизация программ по стоимости 78
3.3. Разработка программ регионального развития 87
Заключение 97
Литература
- Задачи ресурсного планирования комплексов работ
- Оптимизация по стоимости
- Метод динамического программирования
- Оптимизация программ по стоимости
Введение к работе
Управление проектами это раздел науки управления в социальных и экономических системах, который занимается разработкой методологии, методов, методик и программных средств управления изменениями в условиях ограниченных ресурсов. Важным разделом управления проектами являются задачи оптимального распределения ограниченных ресурсов. Как правило, задачи распределения ресурсов относятся к сложным многоэкстремальным задачам, эффективные методы решения которых известны только для ряда частных случаев.
В общем случае для получения точных решений применяются метод ветвей и границ и метод динамического программирования. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних или верхних оценок подмножеств решений. Метод динамического программирования применим только для определенного класса задач. Таким образом, актуальной является задача разработки эффективных методов решения задач оптимального распределения ограниченных ресурсов, применимых для решения широкого круга задач.
Цель диссертационной работы состоит в разработке эффективных методов решения задач распределения ресурсов при управлении проектами. Для достижения этой цели в работе поставлены и решены следующие задачи:
Разработка метода дихотомического программирования для решения задач дискретной оптимизации (при дихотомическом представлении типа дерева) и для получения нижних или верхних оценок целевой функции задачи в общем случае.
Разработка метода ветвей и границ на основе нижних или верхних оценок, получаемых методом дихотомического программирования.
Решение ряда задач распределения ресурсов с применением дихотомического программирования.
Научная новизна и значимость результатов диссертационной работы состоит в следующем:
Предложен метод дихотомического программирования для решения задач дискретной оптимизации при дихотомическом представлении типа дерева и аддитивной целевой функции.
Предложен метод получения оценок (нижних и верхних) целевой функции задачи дискретной оптимизации на основе решения оценочной задачи методом дихотомического программирования. Метод применен для получения оценок в задаче целочисленного линейного программирования.
Метод дихотомического программирования применен для решения трех задач управления проектами:
задача оптимизации проекта по стоимости (доказана теорема о представимости продолжительности проекта, как функции продолжительности работ, в дихотомическом виде типа дерева);
задача определения оптимальной очередности выполнения работ проекта при зависимостях рекомендательного типа;
задача разработки программы развития региона, обеспечивающей требуемое значение комплексной оценки состояния региона при минимальных затратах бюджетных средств.
Практическая значимость результатов работы состоит в возможности разработки эффективных алгоритмов оптимизации программ и проектов.
Методы исследования. Для решения поставленных задач использовались современные методы исследования операций, теории графов, математического программирования.
Апробация работы и публикации. Основные положения и результаты диссертационной работы докладывались и обсуждались на научных семинарах ИПУ РАН и ВГАСУ, международной научной конференции «Современные сложные системы управления», Воронеж, 2003, международных научно-технических конференциях «системные проблемы качества, математического моделирования, информационных и электронных технологий», Сочи, 2002, 2003 гг., Международной научно-практической конференции по теории активных систем, Москва, 2003.
Публикации. Основные положения диссертационной работы опубликованы в 10 научных работах общим объемом 7,5 печатных листа.
Работа состоит из введения, трех глав, заключения и списка литературы и содержит 103 страницы.
Во введении определена цель работы, обоснована актуальность рассматриваемых задач, приведена структура работы и краткое содержание основных разделов, а также - основные положения, выносимые на защиту.
В первой главе, носящей обзорный характер, дается описание методологии управления проектами, постановка задач оптимального распределения ограниченных ресурсов. Выделен новый тип зависимостей — зависимости рекомендательного типа. Любая из четырех известных зависимостей: «старт-финиш», «старт-старт», «финиш-старт», «финиш-финиш», в случае, если она имеет рекомендательный характер, может нарушаться, но это приводит к определенным потерям.
В заключение главы даны постановки задач исследования.
Во второй главе предложен новый метод решения задач дискретной оптимизации - метод дихотомического программирования.
В третьей главе метод дихотомического программирования применен для решения трех задач управления проектами: оптимизация последовательности выполнения проектов при зависимостях рекомендательного типа, оптимизация проекта по стоимости и разработка программ регионального развития.
В заключении приведены основные результаты работы.
Задачи ресурсного планирования комплексов работ
При постановке задач ресурсного планирования предполагается, что проект описан в виде комплекса работ в определенными зависимостями между ними. Зависимости между работами отображаются в виде сетевого графика (сети).
Существуют два способа изображения работ в сетевом графике. В первом способе работы изображаются в виде вершин сети, а зависимости между работами - в виде дуг сети. Во втором способе вершины сети соответствуют событиям сети, то есть моментам завершения одной или не скольких работ, а дуги — работам сети, при этом, для отображения всех требуемых взаимосвязей иногда приходится вводить дуги специального вида - фиктивные работы (можно считать, что такие дуги соответствуют работам нулевой продолжительности, не требующим ресурсов). На рис. 3.1.а приведен комплекс работ в виде «вершина — работа», а на рис. 3.1.6 этот же комплекс представлен в виде «вершина — событие» (зависимость, соответствующая фиктивной работе показана пунктиром). В скобках на рис. 3.1.6 указаны номера работ рис. 3.1.а, которым соответствуют дуги рис. 3.1.6. Как правило, будем применять изображение комплекса работ в виде «вершина — работа». Для полного описания комплекса работ необходимо задать описание каждой работы [5].
Важной характеристикой работы является ее объем W. Он определяется на основе нормативов, экспертных оценок или имеющегося опыта. Объем может измеряться в единицах трудоемкости, стоимости и т.д.
Следующей характеристикой работы является ее продолжительность (время выполнения). В простейшем случае работа описывается величиной продолжительности и количеством требуемых для ее выполнения ресурсов. В этом случае будем говорить, что работа выполняется с фиксированной интенсивностью. Тогда объем работы для решения задачи ресурсного планирования не нужен, он используется при контроле хода реализации проекта. Если количество ресурсов на работу может принимать различные значения, то и продолжительность работы тоже может быть разной. При этом, если количество ресурсов в процессе выполнения работы не меняет ся, то будем говорить, что работа выполняется с постоянной интенсивностью. Для описания работы, выполняемой с постоянной интенсивностью достаточно задать продолжительность работы при различных уровнях ресурсов, то есть зависимость т(и), где и — количество ресурсов, выполняющих работу. Отношение определяет интенсивность выполнения работы (производительность участвующих в работе ресурсов), которую мы будем называть скоростью выполнения работы (или просто — скоростью работы). Из выражения (3.1) видно, что скорость измеряется объемом работ, выполняемым в единицу времени. Без ограничения общности можно принять, что скорость работы является неубывающей функцией количества ресурсов.
Заметим, что одновременное увеличение (уменьшение) и объема, и скорости работы в одно и то же число раз не изменяет ее продолжительности. Следовательно, и величина объема, и его единица измерения могут быть выбраны произвольно. Как правило, единица измерения объема выбирается из содержательного смысла.
Наиболее сложным является случай, когда работа может выполняться с переменной интенсивностью, то есть количество ресурсов на работе может меняться в процессе ее выполнения. Для описания работы в этом случае необходимо задать ее объем W и зависимость w = f(u) скорости работы от количества выполняющих ее ресурсов. Обозначим через u(t) количество ресурсов на работе в момент времени t, tH — момент начала работы, tK — момент ее окончания. Имеет место соотношение:
Типичный вид зависимости скорости операции от количества ресурсов приведен на рис. Сначала с ростом количества ресурсов средняя производительность растет, а затем она начинает падать.
На практике применяются более простые — либо линейные зависимости вида О, и а f(u)=«a, a u b, (3.3) b, b u либо степенные вида f(u) = ua (как правило, a 1). Важной характеристикой работы являются затраты ресурсов к S=Ju(x)dT (3.4) t„ (прямые затраты сырья, материалов, трудозатраты, финансовые и т.д.). В ряде случаев ограничения наложены на затраты ресурсов на работу. Очевидно, что с ростом затрат продолжительность работ не увеличивается при разумном использовании ресурсов. Определим зависимость продолжительности работы т от затрат на ее выполнение при заданной зависимости скорости работы от количества ресурсов, предполагая, что ресурсы распределяются оптимально. Примем сначала, что зависимость f(u) является вогнутой дифференцируемой функцией, то есть, для любого 0 a 1 и любых Ui и и2 f(au, + (l-a)u2) af(uO + (l-a)f(u2). Теорема 1.1 [5]. Оптимальному распределению ресурсов соответствует выполнение работы с постоянной интенсивностью.
Оптимизация по стоимости
Рассмотрим постановку задач дискретной оптимизации (экстремальных задач комбинаторного типа). Задано конечное множество Q допустимых решений (комбинаций). В качестве таких комбинаций могут выступать перестановки п чисел (число возможных решений п!), сочетания из п элементов то m (число решений С„ ) последовательность из п чисел, каждый член которой может принимать одно из m значений (число возможных решений mn) и т.д. Для каждой комбинации neQ определена функция ф(л) в том смысле, что есть алгоритм вычисления функции ф(л) для любого rceQ. Требуется определить комбинацию rco Q, для которой ф(я) принимает максимальное или минимальное значение. Сложность решения задач дискретной оптимизации состоит в том, что число допустимых решений экспоненциально растет с ростом размерности задачи п. Поэтому простой перебор всех решений невозможен при больших п. В то же время, эти задачи относятся, как правило, к классу NP — трудных задач, для которых доказано, что не существует методов их точного решения, отличных от перебора.
Существует несколько схем решения задач дискретной оптимизации. Ниже дается их краткое описание [9, 11, 12, 13, 26, 28].
Методы локальной оптимизации Определим для каждого решения л множество Р(л) так называемых соседних решений (окрестность решения л). При заданной процедуре получения соседних решений алгоритм локальной оптимизации работает следующим образом [9]. Берем какое-либо решение л0 Рассматриваем окрестность Р(ло) и в этой окрестности определяем наилучшее решение Ль такое что ф(л)= min ф(л) (1.1) (имеется в виду задача минимизации). Если р(Л) ф(ло), то рассматриваем окрестность Р(7Гі), определяем наилучшее решение %г и т.д. до тех пор пока не получим решение лк, такое, что ф(тск)= min ф(тс) яєр(як) Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д.
Можно поступить по-другому, расширив окрестность. Если жк — локально-оптимальное решение, то определяем окрестность следующим образом РК)= UPW 0-2) яєР(Як)
Другими словами, Р(лк) это объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальным решения. Если 7СК остается локально-оптимальным решением в новой окрестности, то производим дальнейшее расширение окрестности, либо останавливаемся на полученном решении.
Достоинством методов локальной оптимизации является простота соответствующих алгоритмов. Недостатком схемы является отсутствие оценок близости получаемого решения к оптимальному.
В задачах календарного планирования метод локальной оптимизации реализуется, в основном, в так называемых алгоритмах «сглаживания» и в алгоритмах улучшения решения путем изменения очередности работ критического пути. Рассмотрим два простых примера, иллюстрирующих эти подходы.
Пример 1.1. На рис. 1.1 приведен сетевой график проекта из 4 работ, которым соответствуют вершины сети. В нижней половине вершин указаны объемы работ. Примем, что количество ресурсов на работах 1 и 2 не может превышать 4, а на работах 3 и 4 не может превышать 1.
Заметим, что работы 1 и 3 критические, а работы 2 и 4 имеют полные резервы времени равные 4. Поэтому сдвигаем начало работы 2 на 3 единицы и выполняем ее в интервале (3, 7) тремя единицами ресурсов. При этом, естественно сдвигается работа 4 на 4 единицы. График использования ресурсов после локальной оптимизации на рис. 1.2 заштрихован.
Пример 1.2 (задача о станках). Требуется обработать п деталей. Каждая деталь проходит обработку на двух станках. Продолжительность обработки детали і на первом станке равна а( , а на втором b{ . Имеется всего один станок первого типа и достаточное количество станков второго типа. Требуется определить очередность обработки деталей, минимизирующую продолжительность обработки всех деталей.
Возьмем произвольную очередность, например, 1,2,3 (очередность обработки указана пунктиром на Рис. 1.3, критический путь выделен двойными дугами). Продолжительность обработки Т = 23. Естественно определить соседние решения, как решения, получаемые изменением очередности работ, лежащих на критическом пути. В нашем случае окрестность состоит из одного решения (2,1,3), Рис. 1.4.
Метод динамического программирования
Многие задачи дискретной оптимизации сводятся к следующей постановке: определить вектор х = {xj} с дискретными компонентами, минимизирующий аддитивную функцию п ФМ=І І(ХІ) (2.1) при ограничении f(x) b. (2.2)
Широкий класс функций f(x) допускает дихотомическое представление, такое что вычисление значений функции сводится к последовательному вычислению значений функций двух переменных. Так функция f(x) = fo[f,(x,,x2), f2(x2,x3)] допускает дихотомическое представление (рис. 2.1). При этом соответствующие функции f0, fj, f2 удобно представлять в матричном виде (рис. 2.2). Такое представление широко используется в методах комплексного оценивания программ развития предприятий, регионов, результатов деятельности подразделений, уровня безопасности объектов и др. [2,3,16].
Колмогоровым A.H.[4] и Арнольдом В.И. [1, 21] доказаны теоремы о представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных (в частности, двух переменных). Так, например, любая непрерывная функция трех переменных представима в виде [1] 5(х1,х2,Хз)=Ь1(х1,ф,(х2,Хз))+Ь2(х1,ф2(х2,Хз))+Ь3(х1,фз(х2,х3)) Ее дихотомическое представление (в агрегированном виде) — на рис. 2.3.
Поскольку функция дискретных переменных может быть продолжена до непрерывной функции, то, тем более, любая функция дискретных переменных представима в дихотомическом виде. В дихотомическом виде можно представить и систему неравенств. Рассмотрим, например, систему неравенств fjMsbj, j=Un" (2.3) Без ограничения общности можно принять, что bj - положительные и одинаковые числа, bj = b 0. В этом случае систему неравенств (2.3) можно заменить одним неравенством
Очевидно, что функция f(x) допускает дихотомическое представление, если все функции fj допускают такое представление [14, 15].
В задачах комплексного оценивания [2, 3, 16 и др.] функция f(x), дающая интегральную оценку объекта, как правило, допускает дихотомическое представление в виде дерева. В этом случае можно предложить эффективный метод решения задачи (2.1), (2.2). На рис. 3.1 приведен пример построения интегральной оценки трех показателей, имеющей вид f(xbx2,x3) = cpo[fi(xi,x2), х3] = Фо(у,х3) Значения функций q i(Xj) даны в нижних половинах квадратов, соответствующих переменным хь Х2 и х3. Дадим описание алгоритма на примере рис. 3.1. 1 шаг. Рассматриваем нижнюю матрицу и для каждого элемента этой матрицы записываем в нижней половине соответствующей клетки сумму функций фі(хі) и фг(х2) для соответствующих значений xj и х2. Так, например, клетке (хі,хг) = (3,2) соответствует сумма Ф,(3) + ф2(2) = 20+10 = 30. Далее будем называть эту сумму затратами на достижение соответствующего состояния. 2 шаг. Из всех элементов матрицы имеющих одно и то же значение y = fi(xi,X2) выбираем элемент с минимальной суммой Фі(хі)+ф2(х2). Минимальную сумму записываем в нижнюю половину клетки, соответствующей этому значению у в верхней матрице. Так, например, значению у = 3 соответствуют 5 элементов нижней матрицы: (3;2), (4;2), (3;3), (4;3) и (2;4). Из них элемент (3;2) имеет минимальную сумму 30 (это число записано в нижней половине соответствующей клетки). Поэтому в верхней матрице значению у = 3 соответствует число 30, записанное в нижней половине соответствующей клетки.
Далее шаги 1 и 2 повторяются для верхней матрицы. В результате для каждого значения f(x) мы получаем минимальную величину ф(х).
Несложно обобщить описанный алгоритм на случай производльного дихотомического представления функции f(x) в виде дерева. Шаги 1 и 2 алгоритма повторяются, начиная с висячих вершин дерева дихотомического представления.
Заметим, что дихотомическое представление Рис. 3.1 имеет тип ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае, когда дихотомическое представление имеет вид дерева, является обобщением метода динамического программирования, расширяя круг задач, решаемых на основе данного подхода (Рис. 3.2).
Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программи рования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным.
Оптимизация программ по стоимости
Минимальную длину имеют две вершины (2,5) и (4,2). В этом случае удаляем вершину с минимальной пропускной способностью. Однако в данном случае и пропускные способности одинаковы. Поэтому рассмотрим оба варианта.
1 вариант. Удаляем вершину (2, 5) с вершинами 2, 4, 7. Остается вершина 6, поэтому удаляем вершину (4, 2). Получаем разрез [(3, 5), (2, 5), (4, 2)] пропускной способности 7.
2 вариант. Удаляем вершину (4, 2) с вершинами 4, 6, 7. Остается вершина 2, поэтому удаляем вершину (1,2). Получаем разрез [(3, 5), (4, 2), (1, 2)] пропускной способности 6, который является оптимальным.
Оптимизация программ по стоимости
Задача оптимизации программы по стоимости относится к классическим задачам управления проектами. На рис. 2.1 приведен пример сетевого графика программы.
Работам соответствуют вершины сетевого графика, а зависимостям между работами - дуги. Номера работ указаны в верхней части соответствующей вершины, их продолжительности - в нижней левой, а ранние моменты окончания - в нижней правой. Продолжительность всей программы То определяется длиной критического пути (самого длинного пути в сетевом графике). В нашем примере продолжительность программы составляет 15 месяцев. Если полученный срок завершения программы не удовлетворяет требуемому сроку (То Tg), то необходимо принять меры к сокращению продолжительностей ряда работ так, чтобы длина критического пути была не больше Тдир.
Сокращение продолжительности работ, естественно, потребует увеличения затрат. Задача заключается в сокращении продолжительности работ таким образом, чтобы программа была реализована в требуемые сроки, а дополнительные затраты были минимальными. Это известная в управлении проектами задача оптимизации сети по стоимости.
Существуют методы ее решения для кусочнолинейных и выпуклых зависимостей стоимости работы от ее продолжительности.
На практике, зависимость стоимости работы от ее продолжительности является часто дискретной, то есть имеется конечное число вариантов, отличающихся по стоимости и продолжительности. В этом случае задача становится сложной комбинаторной задачей, для решения которой необходимо применять методы дискретной оптимизации.
Покажем, что для описанной задачи можно применить метод дихотомического программирования.
Теорема 2.1. Продолжительность программы, как функция продолжительности работ, допускает дихотомическое представление.
Доказательство. Обозначим через Qj множество работ, непосредственно предшествующих работе і. Пусть R — множество конечных работ сетевого графика, то есть работ, не имеющих исходящих дуг. Очевидно, что Т = max tj ieR где tj - момент окончания работы і. Как известно, функция «max» допускает дихотомическое представление. В свою очередь ti = Xi+0i где tj — продолжительность работы і, i = max tj момент начала работы і. Обе функции и tj, и О; допускают дихотомическое представление. Далее tj = Tj+0j где 0j = max tq и т.д.
Таким образом, момент завершения программы Т, как функции продолжительности работ Tj допускает дихотомическое представление.
На Рис. 2.2 приведено дихотомическое представление для сетевого графика (рис. 2.1). В вершинах сети приведены соответствующие функции (это либо взятие максимума двух переменных, либо сумма двух переменных).
Заметим, что последовательное множество работ можно агрегировать в одну работу с зависимостью затрат от продолжительности, получаемой в результате решения задач минимизации затрат при различных продолжи-тельностях для этого множества.
Определение 2.2. Параллельным множеством работ называется подмножество работ сетевого графика, у которых множество непосредственно предшествующих работ одно и то же, и множество непосредственно следующих работ одно и то же.
Параллельное множество работ можно агрегировать в одну работу с зависимостью затрат от продолжительности, получаемой в результате решения задачи минимизации затрат, при различных продолжительностях для этого подмножества.
Определение 2.3. Сетевой график называется агрегируемым, если путем агрегирования последовательных и (или) параллельных множеств работ его можно свести к одной работе.
Теорема 2.2 Для того, чтобы продолжительность программы Т(т) допускала дихотомическое представление типа дерева необходимо и достаточно, чтобы сетевой график был агрегируемым.
Необходимость. Пусть Т(т) допускает дихотомическое представление типа дерева. Будем рассматривать операции свертки двух переменных, двигаясь «снизу-вверх», то есть от висячих вершин дерева, соответствующих отдельным работам, к корневой вершине. Каждая операция свертки либо является суммой двух переменных, либо максимумом двух переменных. Покажем, что, если это сумма, то соответствующие работы образуют последовательное множество.
Действительно, если предшествующая работа имеет степень исхода больше единицы, то ее продолжительность будет использована еще хотя бы в одной операции свертки, а это противоречит дихотомическому представлению типа дерева. Если последующая работа имеет степень захода больше единицы, то мы не можем применять операцию суммирования. Действительно, в этом случае время начала этой работы определяется операцией максимума.
Пусть операция свертки является операцией максимума. Покажем, что в этом случае эти работы образуют параллельное множество. Если работы имеют разные множества непосредственно предшествующих работ, то в общем случае они могут начинаться в разные моменты времени.
Аналогично, если работы имеют разные множества непосредственно следующих работ, то нельзя утверждать, что моменты начала работ этих множеств определяются максимальным из моментов окончания рассматриваемых работ. Следовательно, для того, чтобы операция взятия максимума была корректной во всех случаях, необходимо чтобы обе работы имели одни и те же множества непосредственно предшествующих работ, а так же одни и те же множества непосредственно следующих работ, то есть образовывать параллельное множество. Фактически мы показали, что дерево свертки является деревом агрегирования работ в одну агрегированную работу.
Достаточность. Пусть сетевой график агрегируем. В этом случае достаточно очевидно, что дерево агрегирования представляет собой укрупненное описание дерева свертки. Действительно, операцию взятия максимума продолжительностей нескольких работ, образующих параллельное множество, легко представить в виде дихотомического представления типа дерева. Аналогично, операцию суммирования продолжительностей нескольких работ также легко представить в виде дихотомического представления типа дерева.
