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

• Автор: Буркова, Ирина Владимировна
• Шифр специальности: 05.13.10
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 103 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1. УПРАВЛЕНИЕ ПРОЕКТАМИ

1.1. Понятие проекта

1.2. Понятие управления проектом

1.3. Задачи ресурсного планирования комплексов работ

Основные понятия и определения

Оптимизация по стоимости

1.4. Постановка задач исследования

2. МЕТОД ДИХОТОМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

2.1. Методы решения задач дискретной оптимизации

Методы локальной оптимизации
Метод ветвлений
Метод ветвей и границ
Метод динамического программирования
2.2. Дихотомическое представление функций и систем
ограничений
2.3. Дихотомическое представление типа дерева
2.4. Общий случай
2.5. Задача целочисленного линейного программирования
2.6. Некоторые обобщения
3. ЗАДАЧИ УПРАВЛЕНИЯ ПРОЕКТАМИ
3.1. Оптимизация последовательности выполнения проектов..
3.2. Оптимизация программ по стоимости
3.3. Разработка программ регионального развития
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ
Управление проектами это раздел науки управления в социальных и экономических системах, который занимается разработкой методологии, методов, методик и программных средств управления изменениями в условиях ограниченных ресурсов. Важным разделом управления проектами являются задачи оптимального распределения ограниченных ресурсов. Как правило, задачи распределения ресурсов относятся к сложным многоэкстремальным задачам, эффективные методы решения которых известны только для ряда частных случаев.
В общем случае для получения точных решений применяются метод ветвей и границ и метод динамического программирования. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних или верхних оценок подмножеств решений. Метод динамического программирования применим только для определенного класса задач. Таким образом, актуальной является задача разработки эффективных методов решения задач оптимального распределения ограниченных ресурсов, применимых для решения широкого круга задач.
Цель диссертационной работы состоит в разработке эффективных методов решения задач распределения ресурсов при управлении проектами. Для достижения этой цели в работе поставлены и решены следующие задачи:
1. Разработка метода дихотомического программирования для решения задач дискретной оптимизации (при дихотомическом представлении типа дерева) и для получения нижних или верхних оценок целевой функции задачи в общем случае.
2. Разработка метода ветвей и границ на основе нижних или верхних оценок, получаемых методом дихотомического программирования.
3. Решение ряда задач распределения ресурсов с применением дихотомического программирования.
Научная новизна и значимость результатов диссертационной работы состоит в следующем:

1. Предложен метод дихотомического программирования для решения задач дискретной оптимизации при дихотомическом представлении типа дерева и аддитивной целевой функции.
2. Предложен метод получения оценок (нижних и верхних) целевой функции задачи дискретной оптимизации на основе решения оценочной задачи методом дихотомического программирования. Метод применен для получения оценок в задаче целочисленного линейного программирования.
3. Метод дихотомического программирования применен для решения трех задач управления проектами:
- задача оптимизации проекта по стоимости (доказана теорема о представимости продолжительности проекта, как функции продолжительности работ, в дихотомическом виде типа дерева);
- задача определения оптимальной очередности выполнения работ проекта при зависимостях рекомендательного типа;
- задача разработки программы развития региона, обеспечивающей требуемое значение комплексной оценки состояния региона при минимальных затратах бюджетных средств.
Практическая значимость результатов работы состоит в возможности разработки эффективных алгоритмов оптимизации программ и проектов.
Методы исследования. Для решения поставленных задач использовались современные методы исследования операций, теории графов, математического программирования.
Апробация работы и публикации. Основные положения и результаты диссертационной работы докладывались и обсуждались на научных семинарах ИПУ РАН и ВГАСУ, международной научной конференции «Современные сложные системы управления», Воронеж, 2003, международных научно-технических конференциях «системные проблемы качества, математического моделирования, информационных и электронных технологий», Сочи, 2002, 2003 гг., Международной научно-практической конференции по теории активных систем, Москва, 2003.
Публикации. Основные положения диссертационной работы опубликованы в 10 научных работах общим объемом 7,5 печатных листа.

и* иі

Рис. 3.3.
Далее для заданной продолжительности т определяем и* и соответственно Б = и*т, принимая полученную вогнутую зависимость за истинную, представим точку и* как выпуклую линейную комбинацию ближайших точек 11| и и2:
Разделим интервал времени т на два: Т) = ат и Т2 = (1-а)х. Примем и = и! в интервале Т] и и = и2 в интервале т2. Из условия (3.6). Имеем
то есть полученное допустимое распределение ресурсов позволяет выполнить весь объем работ с затратами ресурсов Б.
Из полученного результата следует важный вывод: для любых зависимостей Ди) и затрат Б существует оптимальное распределение затрат во времени с не более чем двумя интервалами постоянства уровней ресурсов. Типичными зависимостями затрат от времени, применяемыми на практике, являются кусочно-линейные (рис. 3.4) и степенные:
и* = аиі + (1-а)и2, 0<а<1.
Очевидно, что
Ди*) = аДиО + (1-а)Ди2).
(3.6)
тґ(и*) = ТіДиО + т2Ди2) = и,т, + и2т2 = [аиі + (1-а)и2]т = и*т,
, т>а, а>0.