Содержание к диссертации
Введение
1. Основные задачи оптимизации управления строи тельными проектами
1.1. Основные понятия управления проектами
1.2. Задачи календарного планирования в управлении проектами
1.3. Задачи распределения ресурсов проекта ;.
1.4. Методы решения задач дискретной оптимизации
1.5. Дихотомическое программирование
1.6. Выводы и постановка задач исследования
2. Разработка моделей и методов проектно-ориенти рованного управления на предприятии
2.1. Мультипроектный подход к управлению развитием предприятия .
2.2. Задачи минимизации упущенной выгоды и их классификация
2.3. Модели и алгоритмы определения минимума упущенной выгоды при независимости операций, составляющих проект
2.4. Разработка моделей по проектированию программы реформирования в случае упорядоченности событий проекта
3. Исследование моделей распределения ресурсов в управлении строительными проектами
3.1. Двойная сетевая модель распределения ресурсов
3.2. Классификационная модель строительных проектов по топологическому признаку
3.3. Распределение ресурсов в классификационной модели
4. Модели выбора вариантов производства работ
4.1. Разработка календарного плана оптимального по стоимости
4.2. Агрегируемые сетевые графики
4.3. Определение оптимального варианта производства работ при выпуклой функции затрат
4.4. Модель определения вариантов выполнения работ на объектах
4.5. Построения функции принадлежности для коэффициентов совмещения
4.6. Модель определения рационального совмещения работ при нечетких сведениях о степени совмещения
5. Корпоративные механизмы обмена ресурсами
5.1. Постановка задач оптимизации обменных схем
5.2. Динамические обменные схемы
5.3. Методы решения задач максимизации прибыли и дохода оператора при условии поставки ресурса в любом периоде
5.4. Методы решения задач максимизации прибыли и дохода оператора при условии одновременной поставки ресурса
5.5. Методы решения задач максимизации прибыли и дохода оператора при условии поставки в любом периоде с доплатой з
5.6. Методы решения задач максимизации объема обменов
6. Определение оптимальной стратегии развития строительного проекта
6.1. Постановка задач оптимального управления объектами недвижимости
6.2. Методы решения задачи максимизации рыночной стоимости объектов недвижимости
6.3. Модель управления объектом недвижимости с учетом его делимости
6.4. Разработка плана использования объекта университетского комплекса недвижимости
6.5. Постановка максимизации рыночной стоимости с учетом самофинансирования
6.6. Учет рисков в задачах управления недвижимостью
6.7. Непрерывный случай
6.8. Непрерывный случай с учетом самофинансирования
6.9. Самофинансирование с учетом риска
7. Результаты практического внедрения разработанных моделей .
7.1. Управление повышением эффективности использования финансов
7.2. Управление сокращением сроков строительства
7.3. Управление внедрением новых технологий
7.4. Повышение эффективности использования трудовых ресурсов
7.5. Переход на проектное управление
7.6. Определение оптимальной стратегии выбора вариантов производства работ
7.7. Практическая реализация обменных схем
Выводы и заключение
Литература
- Методы решения задач дискретной оптимизации
- Модели и алгоритмы определения минимума упущенной выгоды при независимости операций, составляющих проект
- Классификационная модель строительных проектов по топологическому признаку
- Построения функции принадлежности для коэффициентов совмещения
Введение к работе
Актуальность проблемы. Эффективный менеджмент, прежде всего, предполагает использование современных управленческих технологий, основанных на теории управления проектами
Деятельность предприятия можно рассматривать, как последовательность реализуемых проектов При этом, следует отметить, что существует зависимость между организационной системой и результатами проекта. Это является одной из причин перехода к проектной форме управления современных российских предприятий как организационной структуре наиболее полно отвечающей стоящим перед ними задачам Речь идет о проектно-ориентированном управлении, то есть управленческом подходе, при котором многие заказы и задачи производственной деятельности организации, рассматриваются как отдельные проекты, к которым применяются принципы и методы управления проектами
В самом широком понимании проект - это ограниченное по времени целенаправленное изменение отдельной системы с установленными требованиями к качеству результатов, возможными рамками расхода средств и ресурсов и специфической организацией
Управление проектом - это искусство руководства в координации людских и материальных ресурсов на протяжении жизненного цикла проекта путем применения современных методов и техники управления для достижения определенных в проекте результатов по составу и объему работ, стоимости, времени, качеству и удовлетворению участников проекта
Успешное завершение проекта определяется как достижение целей проекта при соблюдении установленных ограничений на. продолжительность и сроки завершения проекта; стоимость и бюджет проекта, качество выполненных работ и спецификации требований к результатам При этом конечные результаты должны быть одобрены и приняты заказчиком Ключевыми параметрами, влияющими на результаты проекта, являются продолжительность, стоимость и качество выполняемых работ По крайней мере, два из них. продолжительность и стоимость, очень тесно зависят от количества используемых ресурсов при выполнении проекта- используя большее количество ресурсов можно сократить продолжительность, но увеличить стоимость проекта и наоборот
Таким образом, актуальность темы диссертационной работы определяется тем, что на всем протяжении жизненного цикла проекта необходимо обеспечить методологическое обеспечение принятия оптимальных решений по управлению проектами
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ
федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»,
грант РФФИ «Гуманитарные науки» «Разработка оптимизационных моделей управления распределением инвестиций на предприятии по видам деятельности» № Г00-3 3-306,
госбюджетная научно - исследовательская работа «Разработка и совершенствование моделей и механизмов внутрифирменного управления»
Цель и задачи исследования: разработка моделей и методов оптимизации управления строительными проектами
Для достижения поставленной цели в работе поставлены и решены следующие задачи
проанализировать основные задачи, характерные для каждого из этапов жизненного цикла строительного проекта,
разработать метод определения эффективности проводимых организационных изменений на основе количественной оценки упущенной выгоды,
разработать алгоритм увязки двойной сетевой модели на основе метода пропорционального растяжения,
предложить процедуру распределения ресурсов на основе введенных эвристических правил,
построить модель выбора вариантов производства работ при минимуме средств направляемых на сокращение сроков выполнения,
разработать модель выбора вариантов производства строительно-монтажных работ при выпуклой функции затрат,
определить Парето-оптимальное множество возможных стратегий выбора вариантов выполнения работ при условии минимума продолжительности и затрачиваемых средств,
построить модель динамических обменных схем, разработать методы решения задачи "максимизации прибыли или дохода оператора (корпоративного центра) при различных условиях о времени поставки продукта каждым из предприятий,
разработать модель максимизации рыночной стоимости объектов недвижимости при ограниченности средств на реализацию вариантов развития с учетом возможности привлечения кредитных средств,
построить модель максимизации рыночной стоимости объектов недвижимости в непрерывном случае, когда разные части объекта могут быть реализованы по разным вариантам,
доказать существование оптимального плана развития объекта недвижимости, в котором каждый объект реализуется не более чем по двум различным вариантам,
предложить модель управления объектом недвижимости с учетом его делимости и возможности самофинансирования
Методы исследования. В работы использованы методы моделирования организационных систем управления, системного анализа, математического программирования, теории графов
Научная новизна. В результате проведенных научных исследований, анализа современных требований к управлению предприятием, обобщения опыта и внедрения отдельных задач реформирования предприятия получены и выносятся на защиту следующие основные научные результаты
метод определения эффективности проводимых организационных изменений на основе количественной оценки упущенной выгоды, отличающийся формированием критерия оптимальности и ограничений и позволяющий определить наиболее эффективную стратегию проведения организационных преобразований,
модель увязки двойной сетевой модели, отличающуюся построением графа перемещения ресурсов, что позволяет определить поток ресурсов по заданному графу, минимизирующий время выполнения комплекса, либо упущенную выгоду,
модель распределения ресурсов на основе введенных эвристических правил, отличающаяся доказательством того, что правило выполнения работ в очередности возрастания поздних моментов окончания дает оптимальное расписание проекта,
модель выбора вариантов производства работ при минимуме средств направляемых на сокращение сроков выполнения, отличающуюся учетом ограничений на технологическую последовательность выполняемых работ и позволяющую сформировать оптимальную по стоимости производственную программу,
модель выбора вариантов производства строительно-монтажных работ при выпуклой функции затрат, отличающуюся использованием свойств выпуклости, что позволяет существенно упростить процедуру получения решения поставленной задачи;
модель, решения двухкритериальной задачи выбора вариантов выполнения работ на основе определения Парето-оптимального множества возможных стратегий при условии минимума продолжительности и затрачиваемых средств, что дает возможность существенно сократить множество конкурентоспособных вариантов для лица принимающего решения,
модель динамических обменных схем, отличающуюся учетом фактора времени и позволяющую^ описать развитие технологического процесса во времени, разработка методов решения задачи максимизации прибыли или дохода оператора (корпоративного центра), отличающихся учетом технологической связи предприятий, входящих в корпорацию и обеспечивающих определение рациональной стратегии корпоративного центра при различных условиях о времени поставки продукта каждым из предприятий,
модель максимизации рыночной стоимости объектов недвижимости, созданного в результате реализации строительного проекта, отличающуюся учетом ограниченности средств, направляемых на реализацию вариантов развития и возможности привлечения кредитных средств, позволяющую построить оптимальную стратегию развития объекта недвижимости;
модель максимизации рыночной стоимости объектов недвижимости в непрерывном случае, отличающуюся тем, что разные части объекта могут развиваться по разным вариантам,
доказательство утверждения о существовании оптимального плана развития объекта недвижимости, в котором каждый объект реализуется не более чем по двум различным вариантам;
модель управления объектом недвижимости, отличающаяся учетом его делимости и возможности самофинансирования, что позволяет уменьшить величину привлекаемых дополнительных средств на реализацию выбранного варианта развития за счет вовлечения в оборот доходов, получаемых от эксплуатации объекта недвижимости на более ранних стадиях
Достоверность научных результатов Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами Они подтверждены расчетами на примерах, производственными экспериментами и многократной проверкой при внедрении в практику управления.
Практическая значимость результатов работы. На основании выполненных автором исследований разработан комплекс оптимизационных методов и моделей, обеспечивающих эффективность проекта на всем протяжении его существования
Использование разработанных в диссертации механизмов позволяет многократно применять разработки, тиражировать их и осуществлять их массовое внедрение с существенным сокращением продолжительности трудозатрат и средств
Разработанные модели используются в практике работы ООО «Липецкая инвестиционная компания», ЗАО «Воронежский комбинат строительных материалов» (Воронеж), ОАО «Воронежский завод железобетонных изделий -2» (Воронеж), ООО «Промышленно - строительная корпорация» (Воронеж), ОАО «Дороги России» (Москва), ООО «Магистраль» (Москва), ЗАО «Акрон-транс» (Санкт-Петербург), ЗАО «Трансгарант» (Санкт-Петербург)
Модели и алгоритмы, разработанные в диссертационной работе, включены в состав учебных курсов и дисциплин «Управление проектами», «Организационно-технологическое проектирование», «Организация строительного производства», читаемых в Воронежском государственном архитектурно-строительном университете
Апробация работы. Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях VII академические чтения РААСН «Современные проблемы строительного материаловедения» (Белгород, 2001), Международная научно-практическая конференция «Теория активных систем» (Москва, 2001, 2003, 2005), Международная конференция «Современные сложные системы управления» (Воронеж, 2003, 2005, Тула, 2005), Международная научная конференция «Социально-экономическое развитие регионов реальность и перспективы»
(Воронеж, 2003), Международная конференция «Системные проблемы качества, математического моделирования, информационных и электронных технологий» (Сочи, 2003), I Международная конференция по проблемам строительства и энергетики «Социально-экономические и экологические проблемы горной промышленности, строительства и энергетики» (Тула, 2003), Всероссийская научно-практическая конференция «Системы автоматизации в образовании, науке и производстве» (Новокузнецк, 2003), научно-практическая отраслевая конференция «Системы автоматизированного управления производствами, предприятиями и организациями горнометалургического комплекса» (Старый Оскол, 2003), Международная конференция «Системные проблемы качества, математического моделирования, информационных и электронных технологий» (Москва-Сочи, 2003), Международная школа-семинар «Современные проблемы механики и прикладной математики» (Воронеж, 2004), III Всероссийская научно-техническая конференция «Теория конфликта и ее приложения» (Воронеж, 2004), Всероссийская научно-техническая конференция «Информационные технологии» (Воронеж, 2005), V Всероссийская научно-практическая конференция «Системы автоматизации в образовании, науке и производстве» (Новокузнецк, 2005), Международная научно-техническая конференция «Реконструкция Санкт-Петербург 2005» (Санкт-Петербург, 2005), II Всероссийская научно-практическая конференция «Актуальные проблемы и перспективы менеджмента организаций в России» (Самара, 2006); Международная конференция Российской научной школы «Системные проблемы надежности качества, информационных и электронных технологий в инновационных проектах» (Москва, 2006); научно-практическая конференция «Образование, наука, производство и управление» (Старый Оскол, 2006).
Публикации. Основные результаты диссертации опубликованы в 73 научных работах, в том числе 25 - в изданиях, рекомендованных ВАК РФ
Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем в работах [26], [27], [16], [47], [52], [64] автору принадлежит метод определения эффективности проводимых организационных изменений на основе количественной оценки упущенной выгоды, работах [27], [4], [14], [32], [46], [63] автору принадлежит модель увязки двойной сетевой модели на основе метода пропорционального растяжения, работах [27], [7], [17], [50], [56], [66] автору принадлежит модель распределения ресурсов на основе введенных эвристических правил, работах [27], [28], [18], [49], [55], [62] автору принадлежит модель выбора вариантов производства работ при минимуме средств направляемых на сокращение сроков выполнения, работах [27], [28], [15], [20], [48] автору принадлежит модель выбора вариантов производства строительно-монтажных работ при выпуклой функции затрат, работах [27], [5], [22], [35], [44], [67] автору принадлежит модель определения Парето-оптимального множества возможных стратегий выбора вариантов выполнения работ при условии минимума продолжительности и затрачиваемых средств, работах [27], [10], [21], [34], [57], [58] автору принадлежит модель динамических обменных схем, работах [11],
[13], [19], [24], [59] автору принадлежит модель максимизации рыночной стоимости объектов недвижимости при ограниченности средств на реализацию вариантов развития с учетом возможности привлечения кредитных средств, работах [2], [8], [23], [53], [65], [68] автору принадлежит модель максимизации рыночной стоимости объектов недвижимости в непрерывном случае, когда разные части объекта могут быть реализованы по разным вариантам, работах [1], [9], [21], [38], [43], [61] автору принадлежит доказательство существования оптимального плана развития объекта недвижимости, в котором каждый объект реализуется не более чем по двум различным вариантам, работах [3], [12], [25], [37], [41], [60] автору принадлежит модель управления объектом недвижимости с учетом его делимости и возможности самофинансирования
Структура и объем работы Диссертация состоит из введения, семи глав, заключения, списка литературы из 122 наименований и приложений Основная часть работы изложена на 324 страницах, содержит 119 рисунков, 151 таблицу
Методы решения задач дискретной оптимизации
Современное состояние большинства современных российских предприятий таково, что процедуру банкротства можно возбудить в любое время против большинства из них. Анализ причин кризисного положения российских предприятий [21], показал, что большинство причин находятся в сфере стандартных мероприятий эффективного менеджмента, позволяющего переломить негативную ситуацию, сложившеюся на фирме. Поэтому, в большинстве случаев, кризисное положение большинства компаний в настоящее время можно объяснить отсутствием у руководства этих предприятий понимания имеющихся внутренних проблем организации и необходимого комплекса знаний, позволяющего разрешить хотя бы часть этих проблем.
Эффективный менеджмент, прежде всего, предполагает использование современных управленческих технологий, основанных на теории управления проектами. Это предполагает приведение организационной структуры предприятия в соответствие тем новым задачам, которые встают перед предприятием.
Если проанализировать деятельность любого предприятия, то, прежде всего, можно выделить два рода деятельности, в чем - то совпадающие, но, в тоже время, и имеющие коренные различия. Первый связан с выполнением постоянных и повторяющихся действий, а второй - с выполнением временных и уникальных действий. Первые получили название операций, вторые -проектов. Очевидно, что и организационная структура предприятия должна соответствовать тем действиям, которые оно выполняет: для операций одна, для проектов - другая.
Естественно сведение всей многообразной деятельности предприятия к двум видам весьма условно и один набор действий осуществляемых на предприятии в различных условиях может быть отнесено как к операциям, так и к проектам. Например, серийное производство, в общем - то, должно быть отнесено к операциям, так как это вид деятельности выполняется постоянно и периодически, но и может рассматриваться и как проект, направленный на выпуск определенного вида продукции, так как одновременно ему присущи и признаки проекта: временность (любое серийное производство когда-то прекращается) и уникальность (каждое изделие имеет свои конкретные особенности которые могут рассматриваться как уникальность изделия). Очевидно все дело в промежутках времени в течении которых производится анализ и в масштабах этого анализа. Учитывая это можно сделать вывод, что деятельность предприятия представляет собой последовательность реализуемых проектов. При этом проекты - обычно часть организаций, которые больше самого проекта, таких как корпорации, правительственные агентства, учреждения здравоохранения, международные организации, профессиональные ассоциации и тому подобное. Даже если проект - это собственно организация (совместное предприятие или партнерство), то проект все равно останется под влиянием организации или организаций, его воплощающих. Следует отметить, что существует два типа организаций, различающихся с точки зрения технологии проектного управления: организации, получающие доход в основном от осуществления проектов для других, - архитектурные и инженерные фирмы, консультанты, строительные организации, правительственные заказчики и др; организации, применяющие управление по проектам.
Организационная структура организаций ориентированных на проектное управление призвана обеспечить удобство ведения большого количества протекающих одновременно проектов. Организации, основой которых не являются проекты, - производственные корпорации, финансовые службы -редко имеют в наличии системы управления для своевременного и эффективного удовлетворения нужд проекта. Отсутствие систем, ориентированных на проекты, делает управление проектами более сложными. В некоторых случаях в данных организациях существуют отделы и иные подразделения, работающие в качестве структурных подразделений, ориентированных на проекты, с соответствующими системами.
Следует отметить, что существует зависимость между организационной системой и результатами проекта. Например, если организация поощряет функциональных менеджеров за сокращение рабочего времени проекта, команда управления проектом может счесть нужным организовать проверки с целью убедиться в эффективности использования занятого в проекте персонала.
Большинство организаций создали свою уникальную культуру. Она отражена в ценностях, нормах, верованиях, ожиданиях, в их политике и процедурах, во взглядах на отношение к уполномоченным лицам и во многих других факторах. Организационная культура зачастую оказывает прямое воздействие на проект. Например: необычный или высоко рискованный подход, с большей степенью вероятности получит одобрение в агрессивной или изобретательской организации. руководитель проекта со стилем управления, подразумевающим широкое участие других лиц, может столкнуться с проблемами в строго иерархической организации, тогда как руководитель с авторитарным стилем окажется в подобной ситуации в организации, противоположной по структуре.
Модели и алгоритмы определения минимума упущенной выгоды при независимости операций, составляющих проект
Если теперь для каждой вершины полученного дерева определить некоторую функцию оценки соответствующего подмножества (функция приоритета), качественно характеризующую вероятность того, что в данном подмножестве найдется оптимальное или хотя бы «достаточно хорошее» решение, то мы получаем алгоритм поиска решения, двигаясь по ветви дерева, имеющей максимальное значение функции оценки (или минимальное, если вероятность наличия достаточно хорошего решения тем больше чем меньше значение функции оценки). В задачах календарного планирования метод ветвлений реализуется в так называемых эвристических алгоритмах распределения ресурсов [8,18, 24, 34, 35].
Метод ветвей и границ Метод ветвей и границ это метод ветвлений, в котором в качестве функций оценки подмножеств берутся оценки снизу (или сверху) целевой функции задачи на данном подмножестве решений. Основное преимущество этого метода по сравнению с методом ветвлений в том, что возможна оценка близости получаемого решения к оптимальному. Действительно, если мы получили решение ж со значением целевой функции ф(л), а оценки снизу остальных подмножеств rj(Q) ф(я) (рассматриваем задачу на минимум), то очевидно, полученное решение оптимально. Если наилучшая оценка r(Q) ф(л), то разность А = Ф (к) - r,(Q) определяет погрешность полученного решения [28, 34, 35, 37]. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних оценок. При плохих оценках это фактически полный перебор, при достижимой нижней оценке - это получение оптимального решения за один проход по дереву ветвлений.
Заметим, что функция приоритета, основанная на степени критичности работ фронта в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хороша эта оценка -отдельный вопрос). Дадим иллюстрацию метода на примере задачи обработки деталей (рис. 1.4.3). Возьмем деталь 1 с минимальным bj и разобьем множество всех решений на два подмножества. В первом подмножестве деталь 1 делается последней, а во втором - не делается последней. Очевидно, что оценка снизу продолжительности обработки для первого подмножества равна
Выбираем подмножество с минимальной оценкой, то есть деталь 1 обрабатывается последней. Это подмножество разбивается на два. В первом деталь 3 (имеющая минимальную величину Ь; из оставшихся деталей) обрабатывается предпоследней, а во втором - нет (то есть обрабатывается первой). Оценка первого подмножества Л = (Qn) = max (19, 20) = 20 а оценка второго r) = (Q,2) = max(22,20) = 22 Выбираем первое подмножество. Соответствующая очередность обработки деталей (2,3,1) с продолжительностью обработки Т = 20. Это решение оптимально, поскольку оценка остальных подмножеств больше 20 (рис. 1.4.6). На Рисунке число в скобках у дуг (например (1)) показывает, какая деталь делается, а число с чертой показывает, какая деталь не делается (последней, предпоследней и т.д.).
В основе метода лежит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины) в некоторой специальным образом построенном семействе возможных траекторий. Принцип оптимальности Беллмана гласит: любой участок оптимальной траектории оптимален [28, 34].
В случае дискретных задач метод динамического программирования сводится к определению пути максимальной или минимальной длины в специальным образом построенной сети. Дадим иллюстрацию метода на примере классической задачи о ранце. Имеются п предметов. Каждый предмет имеет ценность а, и вес Cj. Требуется выбрать подмножество Q предметов так, чтобы их суммарная ценность A(Q) = ] , ієО была максимальной при ограничении на суммарный вес Способ построения сети рассмотрим на примере. Имеются четыре предмета, данные о ценностях и весах которых приведены в табл. 1.4.1. Таблица 1.4.1. Исходные данные і 1 2 3 4 Яі 3 2 4 5 Сі 2 1 3 Пусть R = 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.7 толстыми дугами.
Метод динамического программирования можно представить в другой эквивалентной форме, удобной для сравнения его с методом дихотомического программирования. Эта форма не требует построения сети, а использует матричный способ вычислений рис. 1.4.8. Первая матрица соответствует второму слою сети рис. 1.4.7. В верхней половине каждой клетки указана величина веса для различных вариантов из двух первых предметов, а в нижней соответствующая ценность. Вторая матрица соответствует третьему слою, а третья - четвертому. Если в матрице имеется несколько клеток с одинаковыми весами, то в следующую матрицу для этого значения веса берется максимальное значение ценности. Это и есть принцип оптимальности Беллмана для матричного представления метода динамического программирования. В последнем столбике рис. 1.4.8 приведены оптимальные значения суммарной ценности предметов при любых ограничениях на вес ранца.
Метод динамического программирования является эффективным методом решения некоторых задач дискретной оптимизации, существенно сокращая перебор. Так, например, для рассмотренной задачи о ранце при целочисленных значениях весов предметов объем вычислений пропорционален чис-лу вершин сети, то есть не более чем R п. При заданном R объем вычислений растет пропорционально п, что свидетельствует о высокой эффективности метода.
Классификационная модель строительных проектов по топологическому признаку
Заметим, что и настоящее время в условиях дефицита финансовых средств, насыщенности рынка и материальных, и трудовых ресурсов, ограничивающим фактором являются финансовые ресурсы. Это позволяет рассматривать задачи календарного планирования, как задачи распределения ресурсов одного вида (финансовых ресурсов). Поэтому в дальнейшем, если это не оговорено особо, будем считать, что все операции выполняются ресурсами одного вида (финансовыми ресурсами). Будем обозначать далее m Ui(t)=XqjPijv1(t) j=i количество финансовых ресурсов на і-ой операции в момент t и, соответственно, fj(u) - скорость і-ой операции в зависимости от количества ресурсов.
С учетом введенных обозначений дадим постановку задачи минимизации упущенной выгоды. Задан комплекс из п операций. Для каждой операции определена зависимость f(u) скорости операции от количества ресурсов (финансового типа). Заданы также ограничения на ресурсы (типа мощности, либо типа затрат, либо генерального типа). Требуется определить календарный план работ, удовлетворяющий ограничениям на ресурсы и обеспечивающий минимум упущенной выгоды (2.2.7). В ряде случаев мы будем рассматривать нелинейные зависимости упущенной выгоды от момента завершения операции.
В качестве оснований классификации примем вид сетевого графика, тип ограничений на ресурсы и характер зависимости скорости операции от количества ресурсов (либо продолжительности операции от величины затрат).
Будем рассматривать три вида сетевых графиков: независимые операции, сети с упорядоченными событиями и общий случай. Случай независимых операций соответствует ситуации, когда все операции могут выполняться одновременно (то есть отсутствуют технологические зависимости между операциями). На рис. 2,2,1. изображены сетевые графики для комплекса из п независимых операций (рис. 2.2.1.а соответствует изображению операций в виде вершин сети, а рис. 2.2.1.6 - в виде дуг сети, начальное и конечное события обозначены соответственно 0 и Z, пунктирные дуги отражают зависимости или фиктивные операции).
Случай сети с упорядоченными событиями соответствует ситуации, когда задана некоторая очередность событий сети, такая, что каждая операция может выполняться только в интервале между двумя определенными событиями. В сетях с упорядоченными событиями используется представление операций в виде дуг сетевого графика (рис. 2.2.2).
Рассмотрим классификацию задач по характеру зависимостей скоростей операций от количества ресурсов. В первую очередь, выделим самый простой случай линейной зависимости (рис. 2.2.3.а): f,w={u u a [а, и а Далее выделим случай выпуклых зависимостей (рис. 2.2.3.6) и случай вогнутых зависимостей (рис. 2.2.3.в) скоростей операций от количества ресурсов. Наконец, отдельного рассмотрения заслуживает случай выпукло-вогнутых зависимостей (рис. 2.2.3.г), частным случаем которого являются дискретные зависимости.
В случае ресурсов типа затрат обычно выделяют три типа зависимостей затрат S(x) от продолжительности операции т: линейные (рис. 2.2.4.а), выпуклые (рис. 2.2.4.6) и дискретные, когда операция описывается двумя числами - продолжительность операции т и затраты не ее выполнение S.
Таким образом, мы получили 3x3 различных классов задач минимизации упущенной выгоды. Следует отметить, что, как правило, эти задачи являются сложными многоэкстремальными задачами (в дискретном случае -NP-трудными). Рассматриваемые ниже методы их решения ориентированы, в первую очередь, на решение практических задач управления проектами. В ряде случаев удается получить простые точные алгоритмы поиска оптимального решения. В более сложных случаях применяются эвристические алгоритмы построения приближенных решений.
Ресурсы типа затрат. Задан комплекс из п независимых операций. Для каждой операции определена зависимость затрат Sj(Tj) от продолжительности ее выполнения ТІ. Заданы ограничения на суммарные затраты (бюджет проекта) Is.foJsS (2.3.1) i=I Требуется определить продолжительность всех операций, так чтобы минимизировать упущенную выгоду I iV (2.3.2) i=l Это классическая задача оптимального распределения ресурсов, методы решения которой хорошо разработаны [22]. Для линейных и выпуклых зависимостей Sj(Tj) получаем, соответственно, задачи линейного и выпуклого программирования.
В дискретном случае задача в постановке (2.3.1), (2.3.2) не имеет смысла, если все операции должны выполняться. Действительно, если ограничение (2.3.1) выполняется, то задача элементарна. Если же ограничение (2.3.1) не выполняется, то проект не реализуем.
Изменим постановку задачи, а именно, примем, что допускается невыполнение ряда операций. При этом если операция і исключается из проекта, то. величина упущенной выгоды будет равна d; (например, если задан планируемый период Т, то при исключении операции і упущенная выгода составит dj = CjT). В этом случае задача заключается в определении множества Q операций, которые будут выполняться, а также продолжительностей этих операций, так чтобы
Задача (2.3.5), (2.3.7) относится к задачам системной оптимизации, когда необходимо выбрать оптимальную структуру системы (в нашем случае - оптимальное множество различных операций) и решить задачу оптимального функционирования при выбранной структуре (в нашем случае - определить оптимальные продолжительности различных операций).
Построения функции принадлежности для коэффициентов совмещения
В задачах распределения ресурсов по комплексу работ предполагается, что они находятся в некоторой зависимости между собой. Эти зависимости обычно отображаются в виде сетевого графика. Существуют два способа изображения работ в сетевом графике. В первом способе работы изображаются в виде вершин сети, а зависимости между работами - в виде дуг сети. Во втором способе вершины сети соответствуют событиям сети, то есть моментам завершения одной или нескольких работ, а дуги - работам сети. При этом для отображения всех требуемых взаимосвязей иногда приходится вводить дуги специального вида - фиктивные работы или работы нулевой продолжительности, не требующих ресурсов.
Как правило, в задачах ресурсного планирования на сетях операции удобно рассматривать в виде «вершина-работа».
Как показано в первой главе, для реализации комплекса работ требуются ресурсы одного или нескольких видов. Отметим, что если ресурсы неразличимы в условиях конкретной задачи по их влиянию на скорость выполнения работы, то они называются ресурсами одного вида [11, 16]. Понятно, что каждый вид ресурса участвует в выполнении какого-то набора операций, которые можно объединить в классы. Таким образом, операции одного класса выполняются ресурсами одного вида.
Рассмотрим процесс выполнения комплекса операций. После выполнения одной операции ресурсы перемещаются на другие операции своего класса (образуют поток по множеству операций). Совершенно очевидно, что перемещение ресурсов с одной операции на другую недопустимо по тем или иным причинам (отсутствие транспортных средств, высокая стоимость или невозможность перемещения данного вида ресурсов и т. д.). В связи с этим возникает необходимость определения графа перемещения ресурсов (граф ПР). Он состоит из к компонент (по числу классов операций). Вершины графа соответствуют операциям, от вершины і идет дуга к вершине j, если возможно перемещение ресурсов от і-й на j-ю операцию. Кроме того, каждой дуге (i, j) ставят в соответствие параметр ц- перемещение ресурсов от і-й операции на j-ю.
На рис. 3.1.2 показан граф перемещения ресурсов (будем писать в дальнейшем граф ПР) для сети рис. 3.1.1. Он состоит из двух компонент, так как в комплекс входят работы двух классов.
Отметим, что сеть рис. 3.1.1 является сопряженной, т. е. операциям комплекса соответствуют вершины сети, а дуги отражают зависимости между операциями. Такое изображение более удобно, так как в графе ПР вершины также соответствуют операциям. К первому классу относятся операции А, Аг, Аб, А7, ко второму - Aj, Aj, А5. Числа в скобках равны потоку ресурсов по соответствующей дуге.
В квадратах хь х2 каждой компоненты графа ПР пишется количество ресурсов Ni, N2, предназначенных для выполнения операций соответствующего класса (N1 = N2 = 6 на рис. 3.1.2). Фиктивные вершины хи х2 могут соот 99 ветствовать некоторым пунктам, в которых находятся ресурсы. В свою очередь, Zi, z2 могут соответствовать пунктам, в которые нужно собрать ресурсы после выполнения комплекса. Определив некоторый поток ресурсов по графу ПР, можно найти момент окончания каждой операции и, следовательно, время выполнения всего комплекса.
Фронтом операций в момент і называется множество F(i) операций, которые выполняются или могут выполняться в этот момент. Основная группа алгоритмов для решения задач распределения ресурсов основана на последовательном получении решения путем распределения ресурсов по операциям фронта. Для этого определяется некоторое правило (пли несколько правил), позволяющее в любой момент времени принимать решение о распределении ресурсов по операциям фронта. В дальнейшем будем называть момент перераспределения ресурсов конфликтной ситуацией. Процесс разрешения конфликтных ситуаций удобно изображать графически в виде дерева. Вместо таких правил можно определять некоторую функцию (функция предпочтения) и выбирать распределение ресурсов, при котором эта функция принимает минимальное (максимальное) значение. Приведем два простых правила 100 [36, 43 J, которые часто применяются в алгоритмах такого типа. Правило 1. В первую очередь выполняются операции с. меньшим полным резервом времени (резерв времени определяется при условии достаточного количества ресурсов).
Если для получения решения используются эвристические правила (взятые из интуитивных соображений или на основании опыта), то целесообразно испробовать различные правила (или системы правил), выбирая затем наилучшее решение.
Отметим, что большинство правил эквивалентно заданию некоторой функции предпочтения. Например, распределение ресурсов, полученное по правилу 1, минимизирует функцию 2 ,0MO, ieF(t) где F(t) - множество номеров операций фронта, Aii(t) - полный резерв і-й операции в момент t, u;(t) - количество ресурсов расходуемых в і-й операции. Распределение, полученное по правилу 2, минимизирует функцию ieF(t) где ТІ - время выполнения операции и т.д.
В некоторых случаях удобно в качестве функции предпочтения взять нижнюю границу времени выполнения комплекса при выбранном распределении ресурсов по операциям фронта. При этом если мы уже получили какое-либо решение, а значение функции предпочтения на остальных вершинах дерева решений больше или равно времени выполнения комплекса для полученного решения, то, очевидно, полученное решение оптимально.
Рассмотрим на примере определение моментов окончания операций при заданном потоке ресурсов. Примем, что параметр перемещения ресурсов с операции на операцию равно нулю. Кроме того, примем, что не разрешается снимать ресурсы с операции, пока она не закончена (отказ от этих предположений несущественно меняет методику расчета). Пусть скорость выполнения операции прямо пропорциональна количеству ресурсов, т. е. примем w,- = u;, і = І + 7 (рис. 3.1.1, рис. 3.1.2). Объемы операции представлены в табл. 3.1.1. Таблица 3.1.1. Исходные данные к примеру 3.1. Номер операции —. ——— 1 2 3 4 5 6 7 Wj 12 12 6 16 6 12 12 Определение моментов окончания операций производится последовательным просчетом сети. Пусть Aj , Aj , Aj - операции, непосредственно предшествующие операции AJ; t\, t\ , t\ - моменты окончания этих операций. Тогда t = max(tj, tj, t]) - возможный момент начала і-й операции. Далее, пусть Aj , Aj , Aj - операции, с которых перемещаются ресурсы на операцию AJ; t\ , tj , t[ - моменты окончания этих операций (соответственно моменты прихода ресурсов на і-ю операцию, если времена перемещения равны нулю).
