автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Метод дихотомического программирования в задачах управления проектами

ВВЕДЕНИЕ.

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 печатных листа.

Работа состоит из введения, трех глав, заключения и списка литературы и содержит 103 страницы.

Во введении определена цель работы, обоснована актуальность рассматриваемых задач, приведена структура работы и краткое содержание основных разделов, а также - основные положения, выносимые на защиту.

В первой главе, носящей обзорный характер, дается описание методологии управления проектами, постановка задач оптимального распределения ограниченных ресурсов. Выделен новый тип зависимостей — зависимости рекомендательного типа. Любая из четырех известных зависимостей: «старт-финиш», «старт-старт», «финиш-старт», «финиш-финиш», в случае, если она имеет рекомендательный характер, может нарушаться, но это приводит к определенным потерям.

В заключение главы даны постановки задач исследования.

Во второй главе предложен новый метод решения задач дискретной оптимизации - метод дихотомического программирования.

В третьей главе метод дихотомического программирования применен для решения трех задач управления проектами: оптимизация последовательности выполнения проектов при зависимостях рекомендательного типа, оптимизация проекта по стоимости и разработка программ регионального развития.

В заключении приведены основные результаты работы.

ЗАКЛЮЧЕНИЕ

В заключении перечислим основные результаты работы:

1. Предложен новый метод решения задач дискретной оптимизации — метод дихотомического программирования, в основе которого лежит возможность представления функций и систем ограничений в дихотомическом виде.

2. При дихотомическом представлении в виде дерева предложен эффективный метод решения задач оптимизации, обобщающий метод динамического программирования Беллмана.

3. Для общего случая рассмотрен метод ветвей и границ, в котором нижние или верхние оценки получаются на основе дихотомического представления системы ограничений в виде дерева.

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

- задача определения оптимальной очередности выполнения работ одной бригадой при зависимостях рекомендательного типа;

- задача оптимизации проекта по стоимости;

- задача разработки региональных программ развития.

5. Разработанные методы применены для формирования программ корпоративного и регионального развития.

1. Арнольд В.И. О функциях трех переменных. - ДАН СССР, 1957, №2.

2. Андронникова Н.Г., Баркалов С.А., Бурков В.Н., Котенко A.M. Модели и методы оптимизации региональных программ развития. (Препринт) -М.: Институт проблем управления им. В.А. Трапезникова РАН, 2001.

3. Андронникова Н.Г., Бурков В.Н., Леонтьев С.В. Комплексное оценивание в задачах регионального развития (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН) М.: 2002.

4. Бабкин В.Ф., Баркалов С.А., Буркова И.В. Модели, методы и механизмы повышения эффективности учебного процесса — М. 2001 (Препринт / Институт проблем управления им. В.А. Трапезникова РАН).

5. Баркалов П.С., Буркова И.В., Глаголев А.В., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами. — М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН), 63 с.

6. Баркалов С.А., Бурков В.Н. и др. Прикладные модели в управлении организационными системами. ИПУ РАН, ВГАСУ, ТГУ, Тула. 2002.

7. Баркалов С.А. Теория и практика календарного планирования в строительстве. Воронеж: ВГАСА, 1999.

8. Бурков В.Н., Новиков Д.А. Как управлять проектами. М.: СИНТЕГ ГЕО, 1997.

9. Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов. Тбилиси: Мецниереба, 1974.

10. Бурков В.Н., Ловецкий С.Е. Эвристический подход к решению динамических задач распределения ресурсов. Автоматика и телемеханика- 1966, №5.

11. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных комбинаторных задач (обзор). Техническая кибернетика — 1968, № 4.

12. Бурков В.Н., Ловецкий С.Е. Комбинаторика и развитие техники. — М.: Знание, 1968.

13. Бурков В.Н., Ловецкий С.Е. Методы решения экстремальных задач комбинаторного типа (обзор). Автоматика и телемеханика - 1968, №11.

14. Бурков В.Н., Буркова И.В. Задачи дихотомической оптимизации. — Материалы международной научно-технической конференции «Системные проблемы качества, математического моделирования, информационных и электронных технологий», Радио и связь, 2003. С. 23-28.

15. Бурков В.Н. и др. Теория активных систем и совершенствование хозяйственного механизма. — М.: Наука, 1984.

16. Власюк Б.А. Оптимальное расписание обработки деталей на трех последовательных механизмах. — Изв. АН СССР. Техническая кибернетика. 1967, №4.

17. Воропаев В.И. Управление проектами в России. М.: Алане. 1995.

18. Голенко Д.И., Тарнопольский Ю.Я. Оптимизации я календарных планов методами направленного поиска. Кибернетика - 1970. № 6.

19. Емеличев В.А. Дискретная оптимизация. Последовательностные схемы решения. I, II. — Кибернетика — 1971. № 6; 1972, № 2.

20. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных. ДАН СССР, 1956, 108, №2.

21. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. — М.: Наука, 1969.

22. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. I, II. — Кибернетика — 1965. № 1; 2.

23. Михалевич B.C., Ермольев Ю.М., Шкурба В.В., Шор Н.З. Сложные системы и решение экстремальных задач. — Кибернетика 1967. № 5.

24. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983.

25. Теория расписаний и вычислительные машины. Под ред. Э.Г. Кофф-мана. — М.: Наука, 1984.

26. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. — М.: Наука, 1975.

27. Уздемир А.П. Динамические целочисленные задачи оптимизации в экономике. М.: Физматлит, 1995.

28. Управление проектами. Под общей редакцией В.Д. Шапиро. СПб.: Два три, 1996.

29. Бурков В.Н., Грацианский Е.В., Еналеев А.К., Умрихина Е.В. Организационные механизмы управления научно-техническими программами. М.: ИЛУ РАН, 1993.