Метод сетевого программирования в задачах управления проектами тема диссертации и автореферата по ВАК РФ 05.13.10, доктор технических наук Буркова, Ирина Владимировна

• Буркова, Ирина Владимировна
• доктор технических наук
• 2012

Оглавление диссертации доктор технических наук Буркова, Ирина Владимировна

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

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

2.1.1. Постановка задачи.

2.1.2. Метод локальной оптимизации.

2.1.3. Метод ветвлений.

2.1.4. Метод ветвей и границ.

2.1.5. Метод динамического программирования.

2.2. Метод сетевого программирования.

2.2.1. Сетевое представление функций.

2.2.2. Метод сетевого программирования.

2.2.3. Случай аддитивных функций.

2.2.4. Сетевое представление типа дерева.

2.2.5. Сетевое представление задачи нелинейного программирования.

2.2.6. Метод ветвей и границ.

3. ЗАДАЧА О РАНЦЕ И ЕЕ МОДИФИКАЦИИ.

3.1. Одномерный ранец.

Описание алгоритма.

3.2. Оптимизация пакета взаимозависимых проектов.

3.3. Оптимизация пакета инновационных проектов.

3.4. Оптимальная структура дихотомического представления.

4. ПРИКЛАДНЫЕ ЗАДАЧИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ.

4.1. Задача о максимальном потоке.

4.2. Задача "о камнях".

4.3. Симметричная задача коммивояжера.

Решение оценочных задач для симметричной задачи коммивояжера

4.4. Алгоритм решения двойственной задачи.

5. ЗАДАЧИ ОПТИМИЗАЦИИ ПРОГРАММ И ПРОЕКТОВ.

5.1. Оптимизация программ по стоимости.

Постановка задачи.

Частный случай.

Первый способ (перебор многоцелевых проектов).

Второй способ (метод сетевого программирования).

Двухоценочная система комплексного оценивания.

5.2. Разработка стратегии и программы развития в РОАО «Росагробиопром».

Описание холдинга РОАО «Росагробиопом».

Стратегия развития.

Стратегия дифференциации.

Стратегия диверсификации.

Применение результатов работы.

5.3. Разработка региональных программ социально-экономического развития.

Человеческие ресурсы.

Природные ресурсы.

Оценка инновационного потенциала изменений.

Приоритетные направления и проекты развития, дающие основной вклад в достижение целей.

Введение диссертации (часть автореферата) на тему «Метод сетевого программирования в задачах управления проектами»

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

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

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

- Разработать новый подход к решению задач многоэкстремальной оптимизации - метод сетевого программирования.

- Применить разработанный подход к решению ряда прикладных задач в области управления проектами.

Методы исследования. В диссертации используются методы исследования операций, теории графов, многоэкстремальной оптимизации.

Научная новизна и значимость результатов работы в следующем:

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

2. Для задачи нелинейного программирования введено понятие двойственной задачи, показано, что метод множителей Лагранжа дает одно из допустимых решений двойственной задачи. Доказана теорема о том, что двойственная задача является задачей выпуклого программирования.

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

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

• формирование пакета проектов (задача о ранце и ее модификации);

• задача календарного планирования при учете времени перемещения ресурсов (задача коммивояжера);

• задача максимизации объема выполненных работ проекта (задача о максимальном потоке);

• задача равномерного использования ресурса (задача о камнях);

• задача формирования программ развития регионов на основе комплексных оценок;

• и др.

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

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

Личный вклад соискателя. Диссертация выполнена единолично. В ней представлены результаты, принадлежащие лично автору.

Апробация работы. Основные результаты диссертационной работы докладывались на семинарах ИЛУ РАН, на международных и Российских конференциях:

1. «Современные сложные системы управления», Воронеж, 2003 г.

2. «Системные проблемы качества, математического моделирования, информационных и электронных технологий», 2003 г.

3. Международная научно-практическая конференция ТАС-2003. (17-19 ноября 2003г., Москва, ИПУ РАН)

4. IV Международная конференция «Современные сложные системы управления». Тверь, 2004.

5. Международная конференция «Современные сложные системы управления», Тула, 2005.

6. «Современные сложные системы управления», Воронеж, 2005.

7. «Современные сложные системы управления» VIII научная конференция Краснодар-Воронеж-Сочи 2005.

8. Международная научно-практическая конференция ТАС-2005. (16-18 ноября 2005 г., Москва, Россия).

9. Научная сессия МИФИ-2007.

Ю.Международная научная конференция «Сложные системы управления и менеджмент качества» CCSQM'2007, Старый Оскол.

11 .Международная научно-практическая конференция ТАС-2007. (14-15 ноября 2003г., Москва, ИПУ РАН)

12.«Системы управления эволюцией организации» IV международная конф. (12-19 апреля 2007г. г. Санья, Китайская Народная республика).

13.Международный симпозиум «Управление проектами: власть, общество, бизнес». Нижний Новгород, февраль 2007 года.

14.IV международная конференция по проблемам управления. (2630 января 2009г. ИПУ РАН, Москва)/

15.VI Международная конференция «Управление проектами в развитии общества», 21-22 мая 2009 года, Киев.

16.11 Всероссийская науч.-тех. Конференция «Управление в организационных системах», Воронеж, 18-21 мая 2009 г.

17.Международная научно-практическая конференция ТАС-2009. (17-19 ноября 2009 г., Москва, Россия).

Публикации. По результатам работы имеется 65 публикаций. Из них 18 в журналах, входящих в список ВАК.

Заключение диссертации по теме «Управление в социальных и экономических системах», Буркова, Ирина Владимировна

Основные результаты работы

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

2. Для общей задачи нелинейной оптимизации получена оценка сверху на основе метода сетевого программирования. Введено понятие обобщенной двойственной задачи и доказана ее выпуклость. Показано, что метод множителей Лагранжа дает допустимое решение обобщенной двойственной задачи (в общем случае — не оптимальное).

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

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

- формирование пакета проектов (задача о ранце и ее модификации);

- задача календарного планирования при учете времени перемещения ресурсов (задача коммивояжера);

- задача максимизации объема выполненных работ проекта (задача о максимальном потоке);

- задача равномерного использования ресурса (задача о камнях);

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

5. Для задачи о ранце определена оптимальная структура дихотомического представления по критерию минимизации максимального суммарного числа клеток матриц дихотомического представления. Показано, что оптимальная структура является сочетанием максимально симметричной и Беллмановской структур.

6. Разработан программный комплекс для решения следующих задач методом сетевого программирования:

- Задача о ранце;

- Задача формирования пакета взаимосвязанных проектов;

- Задача выбора пакетов инновационных проектов;

- Задача минимизации стоимости программы при ограничениях на величину комплексных оценок.

7. Разработанные методы применены при решении практических задач формирования программ развития предприятий и регионов, программ обеспечения безопасности дорожного движения, программ обеспечения безопасности при уничтожении химического оружия.

Заключение

Список литературы диссертационного исследования доктор технических наук Буркова, Ирина Владимировна, 2012 год

1. Агеев И.К., Буркова И.В. Методы решения задач оптимизации бизнесов на основе совместного финансирования. — «Системы управления и информационные технологии» научно технический журнал, №4 (21), 2005. С. 30-32.

2. Агеев И.К., Буркова И.В., Половинкина А.И. Методы оптимизации бизнесов с учетом риска. «Системы управления и информационные технологии» научно технический журнал, №4 (21), 2005. С. 32-35.

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

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

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

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

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

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

9. Баркалов С.А., Буркова И.В., Хатунцев A.B. Задачи формирования программы развития региона Вестник Воронежского государственного технического университета. 2010. Том 6. № 7. С. 154-157.

10. Ю.БеллманР. Динамическое программирование. -М.: ИЛ. 1960.-400 с.

11. П.Белов И.Г., Буркова И.В. Формирование портфеля инвестиционных проектов с ограничениями по сегментам инвестирования. «Системы управления и информационные технологии», научно технический журнал, №1.2 (31), 2008. С. 289-291

12. Бурдюк В.Я., Шкурба В.В. Теория расписаний. Задачи и методы решений // Кибернетика. 1971, № 1. С. 89-102.

13. Бурков В. Н., Буркова И.В. Метод сетевого программирования в задачах управления проектами — Управление большими системами. Специальный выпуск 30.1 "Сетевые модели в управлении". М.: ИПУ РАН, 2010. С. 40-61.

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

15. Бурков В.Н., Буркова И.В. Задачи дихотомической оптимизации.

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

17. Бурков В.Н., Буркова И.В., Ириков В.А. Управление инновационным развитием регионов: современный подход Проблемы теории и практики управления. 2010. №11/10. С. 8-12.

18. Бурков В.Н., Буркова И.В., Кашенков А.Р., Колесников П.А. Структурно-эквивалентные функции в задачах дискретной оптимизации. «Проблемы управления» научно технический журнал, №1,2007. - С. 13-19.

19. Бурков В.Н., Буркова И.В., Овчинникова Т.И., Попок М.В. Метод сетевого программирования. «Проблемы управления» № 3, 2005. С. 25-27.

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

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

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

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

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

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

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

27. Буркова И.В. Метод сетевого программирования в задачах дискретной оптимизации — Вестник Воронежского государственного технического университета. 2010. Том 6. № 7. С. 158-160

28. Буркова И.В. Метод сетевого программирования в задачах нелинейной оптимизации. — «Автоматика и телемеханика», журнал. 2009. №10. С. 15-21.

29. Буркова И.В. Метод сетевого программирования в симметричной задаче коммивояжера. «Проблемы управления» научно технический журнал, №4, 2008. - С. 7-10.1 I ■(■ ■ ■ IIB I I ■

30. Буркова И.В. Ткаченко М.В., Чураков П.П. Задача выбора множества проектов при выпуске инновационной продукции — Вестник Воронежского государственного технического университета. 2010. Том 6. № 9. С. 120-124.

31. Буркова И.В., Кашенков А.Р., Колесников П.А. Метод решения двойственной задачи коммивояжера. «Системы управления и информационные технологии», научно технический журнал, №1.2 (31), 2008. С. 289-291.

32. Буркова И.В., Подвальная Н.М. Формирование портфеля инвестиционных проектов с учетом ограничений на минимальные объемы инвестиций Системы управления и информационные технологии. Научно-технический журнал. 2010г. № 3 (41). С. 60-62.

33. Буркова И.В., Толстых A.B., Уандыков Б.К. Задача оптимизации программ обеспечения безопасности. «Системы управления и информационные технологии» научно технический журнал, №1 (18), 2005. С. 36-40.

34. Буркова И.В., Толстых A.B., Уандыков Б.К. Модели и методы оптимизации программ обеспечения безопасности. «Проблемы управления» научно технический журнал, №1, 2005. С. 51-55.

35. Вентцель Е.С. Элементы динамического программирования. М.: Наука. 1964.

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

37. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург. 2002.

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

39. Гладков В.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: ФИЗМАТЛИТ. 2006.

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

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

42. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука. 1981.

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

44. Корбут А.А., Сига И.Х., Финкелыитейн Ю.Ю. Метод ветвей и границ. Обзор теории, алгоритмов, программ и приложений. // Math. Operation Forsch. Staist. Ser. Optimization. 1977. -V. 8, № 2. -P. 253-280.

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

46. Корбут А.А., Финкелыптейн Ю.Ю. Приближенные методы дискретного программирования. // Известия АН СССР. Технич. кибернетика.-1983.-№ 1.-С. 165-176.

47. Кормен, Томас X., Лейзерсон, Чарльз И., Ривест, Рональд JL, Штайн, Клифорд Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание— М.: «Вильяме», 2005. — С. 230 234.

48. Курейчик В.В., Курейчик В.М. Генетический алгоритм определения пути коммивояжеа.// Известия РАН. Теория и системы управления. 2006. -№ 1.-С. 94-100.

49. Лазарев А.А. Алгоритмы декомпозиционного типа решения задачи минимизации суммарного запаздывания. // Исследования по прикладной математике. Казань: Изд-во Казан, гос. ун-та. 1990. Вып. 17.-С. 71-78.

50. Лазарев А.А. Графический подход к решению задач комбинаторной оптимизации. // Автоматика и телемеханика. 2007. № 4. С. 13-23.

51. Лазарев А.А. Эффективные алгоритмы решения некоторых задач теории расписаний для одного прибора с директивными сроками обслуживания требований: Дис. канд. физ.-мат. наук. Казань. 1989.-108 с.

52. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. Физический факультет МГУ. 2011. - 222 с.

53. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи коммивяжера. // Экономика и математические методы. -1965.-Том 1, вып. 1.-С. 90-107.

54. Математические основы управления проектами. / Под ред. Буркова В.Н. М.: Высшая школа. 2005. - 432 с.

55. Мелмед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы. // Автоматика и телемеханика. —1989. -№ 10. С. 3-29.

56. Мелмед И.И., Сигал И.Х. Задачи комбинаторной оптимизации с двумя и тремя критериями. // ДАН 1999. -Т.366, № 2. - С. 170-173.

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

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

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

60. Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, ГРФМЛ. 1981.

61. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука. 1978.

62. Посыпкин М.А., Сигал И.Х. Исследование алгоритмов параллельных вычислений в задачах дискретной оптимизации ранцевого типа. // ЖВМиМФ. 2005. - Т. 45, № 10. - С. 1801-1809.

63. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наукова думка, 1985.

64. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: ФИЗМТЛИТ, 2007. - 304 с.

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

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

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

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

69. Финкелынтейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. -М.: Наука, 1976.

70. Шкурба В.В., Подчасова Т.П., Пшичук А.Н., Тур Л.П. Задачи календарного планирования и методы их решения. Киев: Наукова думка. 1966. 154 с.

71. Bellman R. Mathematical aspects of scheduling theory. // Journal of the Society of Industrial and Applied Mathematics. 1956. Vol. 4. P. 168-205.

72. Brucker P. Scheduling Algorithms. Springer-Verlag. 2001. 365 p.

73. Gafarov E.R., Lazarev A.A., Werner F. On Lower and Upper Bounds for the Resource-Constrained Project Scheduling Problem. // Preprint 8/10, FMA, Otto-von-Guericke-Universitat Magdeburg. 2010. 27 pp.