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

Буркова, Ирина Владимировна

Управление в социальных и экономических системах

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

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

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

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

федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова РАН

УДК 338.24.57

005012669

БУРКОВА Ирина Владимировна

МЕТОД СЕТЕВОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ УПРАВЛЕНИЯ ПРОЕКТАМИ

Специальность: 05.13.10 - «Управление в социальных

и экономических системах»

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

1 2 МДР 2012

Москва-2012

005012669

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В.А. Трапезникова РАН

Официальные оппоненты.

- ДОРОФЕЮК Александр Александрович, доктор технических наук, профессор, ИЛУ РАН, заведующий лабораторией.

- ГОРОШКО Игорь Владимирович, доктор технических наук, профессор, Академия управления МВД, зам. начальника отдела.

- СИГАЛ Израиль Хаимович, доктор технических наук, профессор, ВЦ РАН, главный научный сотрудник.

Ведущая организация-Федеральное государственное бюджетное учреждение науки Институт системного анализа РАН

Защита состоится « 29 » марта 2012 г. в 14 часов на заседании диссертационного совета Д002.226.02 ИЛУ РАН по адресу:

117997, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке ИПУ РАН.

Автореферат разослан « 27» февраля 2012 г.

Ученый секретарь Диссертационного Совета Д002.226.02 кандидат технических наук

В.Н. Лебедев

Общая характеристика работы

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

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

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

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

оптимизации - метод сетевого программирования.

• Применить разработанный подход к решению ряда прикладных

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

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

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

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

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

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

Гч1

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.

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

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

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

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

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

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

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

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

18. International Symposium on stochastik models in reliability engineering, life science and operations management, Industrial engineering and management department, SCE - Shamoon college of engineering, Beer Sheva, Israel. 8-10 февраля 2010 г.

19. Четвертая международная конференция "Управление развитием крупномасштабных систем MLDS-2010», 4-5 октября 2010 г. Москва.

20. Международная научно-практическая конференция Управление проектами: состояние и перспектива», Украина, Николаев, НУК (Университет кораблестроения), 23-25 сентября 2011 г.

21. Международная научно-практическая конференция «Теория активных систем-2011», Институт проблем управления РАН, Москва, 14-16 ноября 2011 г.

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

Личный вклад автора. Все основные результаты получены автором самостоятельно.

Структура и объем работы

Работа состоит из введения, пяти глав, заключения и списка литературы, насчитывающего 77 наименований. Объем текста диссертации- 181 страница, включая 88 иллюстраций и 61 таблица.

Содержание работы

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

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

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

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

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

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

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

Все эти задачи относятся к классу многоэкстремальных (в большинстве случаев - дискретных) задач оптимизации. Поэтому в главе дается краткий обзор методов решения задач дискретной оптимизации. Задачи дискретной оптимизации исследовались многими учеными. Отметим работы Власюка Б.А., Волковича В.Л., Емеличева B.JL, Журавлева Ю.И., Корбута A.A., Лазарева A.A., Михалевича B.C., Сигала И.Х., Уздамира А.П. и других. Оптимизационные задачи управления проектами рассматривались в работах Буркова В.Н., Воропаева В.И., Ирикова В.А., Кофмана А., Танаева B.C. и других.

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

Рассмотрим следующую задачу дискретной оптимизации: определить вектор х б X, обеспечивающий

(1) maxf(x)

хсХ

при ограничении

(2) <р{х)<Ь.

Далее будем предполагать, что

где Xj - дискретное множество чисел.

Как известно, любую функцию дискретных переменных можно представить в виде суперпозиции более простых функций (в частности - в виде суперпозиции функций от двух переменных) (В.И.Арнольд, А.Н.Колмогоров). Такое представление удобно изображать в виде сети, входы которой соответствуют переменным х„ выход - функции, а остальные вершины - функциям, входящим в суперпозицию. Поэтому такое представление будем называть сетевым представлением.

Пример 1. Рассмотрим функцию четырех переменных

fix) = (Х\Х2 + Х12)хз + Х3Х4 + Х\Хц

Ее сетевое представление приведено на рис. 1, где

У\=ХХХ2+Х? Уг =У 1X3 Уз =хрс4 у4 =ХзХ4

У5=У2+}'3 +У4

Рис. 1.

Определение 1. Функции Д.г) и <р(х) называются структурно-подобными (с-подобрыми), если в заданном классе структур существуют сетевые представления этих функций такие, что соответствующие сетевые структуры совпадают.

Пример 2. Рассмотрим функцию ф:) = (х\ + х2)х3(х1 + Х4) + Х3Х4.

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

Пусть функции /[х) и (р(х) в задаче (1)-(2) являются с-подобными. Построим их общее сетевое представление. Пусть далее целевая

функция / является монотонной функцией обобщенных переменных у (без ограничения общности можно принять, что / - возрастающая функция у). Аналогично примем, что функция & также является возрастающей функцией у, В сетевом представлении выделим вершины нулевого уровня, которым соответствуют переменные х,. Вершинам первого уровня соответствуют задачи оптимизации следующего вида: максимизировать

>'. =/(х) при ограничении

= (Pix) <р,

где р принимает все допустимые значения.

Как уже отмечалось выше, в сетевом представлении задачи, соответствующие вершинам сетевого представления (за исключением вершин первого уровня), имеют более простой вид, такой, что существуют эффективные алгоритмы их решения. В частности, если сетевое представление является дихотомическим, то каждая задача является задачей оптимизации функции двух переменных, и в дискретном случае легко решается на основе матричного представления. Решив задачи первого уровня, переходим к решению задач второго уровня, и т.д. Последней решается задача, соответствующая выходу сети. Обозначим ук(Ь) - значение целевой функции в оптимальном решении задачи, соответствующей выходу сети, где к - число вершин сети за исключением п вершин нулевого уровня.

Теорема 1. Величина ук{Ь) является верхней оценкой для исходной задачи (1), (2).

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

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

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

(3) /(*)=!/(*,),

где х, е X, является аддитивной.

Теорема 2. Аддитивная функция с-подобна любой функции того же числа переменных.

Доказательство. Пусть G„ - граф сетевого представления некоторой функции (fix) п переменных х,. Если граф G„ является деревом, то теорема очевидна.

Пусть существует вершина i сетевого представления, из которой исходят k> 1 дуг (/,/,), s = 1 ,к. Далее, пусть этой вершине соответствует обобщенная переменная^ = £(у), где у е Yh У, — множество переменных сетевого представления функции <р(х), соответствующих вершине /. Разделим функцию у, = £,(у) на к функций (у) = ylh так, что

Z^iy)-^(y)-

Обобщенные переменные у^ припишем соответствующим вершинам

Так поступаем с любой вершиной, из которой исходит к> 1 дуг. Покажем, что мы получили сетевое представление функции fix), структура которого совпадает со структурой qix).

Во-первых, граф G„, очевидно, является и графом структуры СП функции fix). Во-вторых, в силу выбора множества переменных Y„ эти множества совпадают с соответствующими множествами для структуры СП функции (f(x). Наконец, в силу аддитивности функции fix), величина, получаемая в конечной вершине графа в точности равна fix) для любого х. Теорема доказана.

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

Обобщенная двойственная задача (ОДЗ). Определить функции h (для всех вершин сетевого представления функции <р(х) с числом исходящих вершин более 1) так, чтобы верхняя оценка решения исходной задачи была минимальной.

Название ОДЗ объясняется тем, что, как будет доказано далее, ОДЗ действительно обобщает классические определения двойственной

задачи, связанные с задачей линейного программирования и методом множителей Лагранжа для задачи нелинейного программирования.

Рассмотрим задачу нелинейного программирования. Определить

х= {.г,, /= 1, и}, такой, что

(4) /(х)->тах при ограничениях

(5) <Р]{х)<Ъ}, ./ = 1«,

(6)

На рис. 2 приведено сетевое представление ограничений (5), (6) (через X) обозначеноу'-е ограничение (5), _/ = 1, т).

Рис.2.

Для применения метода сетевого программирования необходимо, чтобы целевая функция имела такую же структуру сетевого представления. Для этого представим/(х) в виде

Лх)=ЪА*)+кМ

где й/х) - произвольные функции такие, что представленные ниже задачи (7) и (8) имеют решение.

В каждой вершине сетевого представления решаются подзадачи оптимизации с одним ограничением. Первые т подзадач имеют вид: тах/гДх),

Последняя, (от+1)-я подзадача имеет вид:

(8) max/7„1+1(x)= max

Обозначим через ^(/г) значение целевой функции в оптимальном решении у'-ой подзадачи. Теорема 3. Функционал

(9) =

дает верхнюю оценку для исходной задачи.

Обобщенная двойственная задача: определить функции (х), у'=1 ,т, минимизирующие верхнюю оценку (9). Теорема 4. Функционал Л7?) является выпуклым. Таким образом, ОДЗ является задачей выпуклого программирования.

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

Пример 3. Возьмем одно из допустимых решений ОДЗ /?;(*)=Я//1,7=1,/и. Первые т подзадач принимают вид:

при ограничении

ф)<ъг

Очевидно, что ^(/1у)<Хрр у = 1 ,т. Опираясь на это утверждение, получаем

(10) F(X)< max f(x)-£ Л,(cpj(*)-*>,) = max L(a,x).

j=1 J 1

Минимизация правой части (10) по Я есть ничто иное, как метод множителей Лагранжа. Таким образом, метод множителей Лагранжа дает одно из допустимых решений ОДЗ (которое в общем случае не является оптимальным).

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

С{х) = ±сЛ

при ограничениях

п _

йЬг ]=\т+1.

Примем последнее ограничение в качестве множества Хт-,л. Разобьем коэффициенты с(,г = 1,т на т частей Примем

т -

7=1

Решаем (т+1) подзадач: определить целочисленный неотрицательный

вектор х, максимизирующий

(П)

при ограничении

(12) ±а0х><Ьг

1=1

Обозначим Р^) значение 5/х) в оптимальном решении у-й подзадачи. Согласно теореме 3

(13) =

является оценкой сверху для С(х):

Обобщенная двойственная задача', определить у =1, т},

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

Получим необходимые и достаточные условия оптимальности решения ОДЗ. Пусть ж - некоторое решение. Обозначим через I)

множество оптимальных решенийу'-й подзадачи (11), (12), ]-1,т + 1.

Теорема 5. Необходимым и достаточным условием оптимальности решения 5 является отсутствие решения неравенства

при условиях

т+1 _

(15) 2>„=0, 1=1,«.

Пример 4. х, = 0, 1; г = 1,4.

1 Ох, + 8х2 + 6х3 + 7х4 —> тах, 6х, +3х2 +2х3 +5х4 <11,

(16) Зх, + 5х2 + бх3 + Зх4 <11.

Применим метод множителей Лагранжа, т.е. найдем минимум по Я функции

11Я -г шах[(10 - 6 А)х, + (8 - ЗЯ)х2 + (б - 2 Я)х3 + (7 - 5 Д)х4 ],

где х2 определяется неравенством (16). При заданном Я - это задача «одномерный ранец». Она является КР-трудноп, если неизвестна зависимость от п правой части Ь2 ограничения (16). Однако на практике, как правило, Ь2 либо не зависит от п, либо является линейной функцией п. В этом случае при целочисленных параметрах задача эффективно решается методами динамического либо дихотомического программирования. Имеем оптимальное значение Д„ =1 оценка сверху ^0=21 X ■ Этому значению я0 соответствуют следующие значения г=1,4, ] =1,2:

(17) = Ъап==7Уъ> ¿21 = Л)°21 = Л.аз! = •у41 = = ; ■У12 = С1-'511=2К; = ¡31=3 =

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

Шаг 1. Выпишем необходимые условия оптимальности для решения (17). Имеем:

Р,={(Щ,0>, (1,0,0,1)};

Р2У = {(1,1,0,1), (ОД,1,0)}. Поскольку у,! + у,2 ~ 0. то обозначим у, = у а = -у а- В этом случае система (14), (15) запишется в виде

тах(у, + у2 + у-;,у1+у\)< тт(у, + у2+у^,у2+уг). Одно из решений этой системы

ух=-£\ уг =-с\ Уз = -£•; у4 =0; е>0. Возьмем е - У6, так как при £ - % появляется новое решение во второй подзадаче. Имеем:

5и =6Уу> ■Ь,^')^;

„,5'42=%>

?,(*,) = {(1,0,0,1); (1,1,1,0)}; ^ =12%;

Д(5г) = {(1,1,ОД); (0,1,1,0); (1,0,1,0)}; ^2=7%; ^

Шаг 2. Выпишем условия оптимальности

гпах(у, + уг + у3; у, + v4)< min[y, + у2 + у,; у2 + у3; ^ + у3).

Нетрудно видеть, что это неравенство не имеет решений. Действительно, из условия у\ +у2 +уз <У\ +У2 >4 следует уг <у4, а из условия у2 +_>'4 <>'2 +у3 следует у4 <у3 , что противоречиво. Следовательно, получено оптимальное решение ОДЗ. Полученную оценку сверху можно использовать в методе ветвей и границ. Возьмем для ветвления временную jci- Если х, ~ 1, то решив соответствующую двойственную задачу, получим ту же оценку F(xi=l) = 2072. В случае х, = О оценка F(xt=0) = 14. Выбираем значение х\ = 1 и производим ветвление по переменной х2. Если х2 = 1, то получаем достижимую оценку /г(х1=1, дг2=1) = 18. Если х2 = 0, то получаем также достижимую оценку F(X]=1, х2=0) = 17. Следовательно, оптимальное решение х, = I, Х2~ 1, = 0, ^4= 0, Спвх = 1В.

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

Рассмотрим постановку задачи. Имеются п проектов, каждый проект характеризуется затратами а,■ и эффектом q (предполагается, что О/, с/ целые положительные числа). Задано ограничение R на объем финансирования. Требуется сформировать портфель проектов так, чтобы суммарный эффект портфеля проектов был максимальным при условии, что сумма затрат не превосходит R. Обозначим х,- = 1, если /ый проект вошел в портфель, = 0 в противном случае. Математическая постановка задачи имеет вид

f(x) = Ycjxj ->max j

Xj e {0;l}, y=l,H

Структура сетевого представления задачи является деревом, поэтому метод сетевого или дихотомического программирования дает оптимальное решение.

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

Пусть множество всех проектов разбито на т непересекающихся подмножеств Q,, j =1,2,..., т. В каждом подмножестве допускается выбор одного и только одного проекта. Для формальной постановки 12

задачи введем переменные {хД г = 1,лу, ] = \,т, принимающие

значения 0 или 1 (л,- - число элементов множества Примем хц = 1, если проект г е О, взят в портфель и х0 = 0, в противном случае. Задача заключается в определении {ху}, максимизирующих

(18) Цсух»

при ограничениях

(19)

(20) £х,.=1,

1е(3]

(Су, а,, соответственно ценность и вес предмета / 6

Другая интерпретация этой задачи состоит в том, что имеются т проектов, но каждый проект имеет модификаций, отличающихся по эффекту и затратам. Необходимо выбрать одну модификацию каждого проекта. Структура сетевого представления по-прежнему является деревом (на рис. 3 приведен пример сетевого представления для случая л, = 2, у' = 1,3).

Рис. 3.

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

(21) ] =

Задача заключается в максимизации (18) при ограничениях (19) и

(21). Полагаем, что > & > в противном случае задача распадается

на т несвязанных задач о ранце.

В данном случае структура сетевого представления также имеет вид дерева, рис. 3.

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

1 шаг. Решаем т задач о ранце следующего вида:

ИСуХи ГОаХ

/ей/

Выписываем все Парето-оптимальные варианты для каждой задачи.

2 шаг. Решаем задачу выбора по одному варианту из каждой группы так, чтобы максимизировать (18) при ограничении (19).

Рассмотрим еще одно обобщение задачи о ранце. Пусть в задаче (18)-(20) количество проектов, которые помещаются в портфель, может быть более 1, то есть ограничения (20) заменим более общими ограничениями.

j = \,m

/еО,

В этом случае возможны два подхода. Первый заключается в том, что рассматриваем все возможные сочетания из щ элементов по Я, где 0 < 5 < РГ Для каждого такого сочетания определяем его ценность и вес. Если каждое такое сочетание считать некоторым проектом, то задача сводится к задаче (18)-(20). Если число сочетаний невелико, то такой подход является достаточно эффективным.

К сожалению, при больших >у и Р) метод перебора всех сочетаний становится не эффективным.

Рассмотрим сетевое представление задачи, структура которого уже не является деревом (рис. 4).

Рис. 4.

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

В результате получаем (т+1) несвязанных задач о ранце. Первые т задач имеют вид.

Определить {х,,), г е 0, максимизирующие

(23) Хщху

при ограничении

(24) 1Х</> .

Последняя задача имеет вид: максимизировать

(25)

при ограничении

(26)

Обозначим Ф/иу) значения целевых функций в оптимальных решениях задачи (23), (24), Ф(у) - значение целевой функции в оптимальном решении задачи (25), (26).

Согласно теореме 3 сумма (27) Ф{и,) + Ф(г)

является оценкой сверху целевой функции исходной задачи.

ОДЗ заключается в определении и и V, удовлетворяющих (22) и минимизирующих (27).

Теорема 6. В решении двойственной задачи имеет место ич ~ X, для всех г е ]'-\,т .

Двойственная задача заключается в нахождении

г \

при ограничении (19). Фактически мы получили функцию Лагранжа. Таким образом, решение ОДЗ свелось к методу множителей Лагранжа.

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

ттшах)

Л х

Существует много структур дихотомического представления задачи от максимально симметричной до максимально ассиметричной (ветка дерева). Заметим, что максимально ассиметричная структура соответствует методу динамического программирования Беллмана.

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

Теорема 7. Если 2"'1<Ь, то оптимальной структурой является максимально симметричное дерево.

Пусть теперь для некоторого я имеет место 2Ч > Ь. В этом случае оптимальным продолжением симметричной структуры (к конечной вершине) будет Беллмановская ветвь дерева, Рис. 5.

Таким образом, оптимальная структура сетевого представления состоит из максимально симметричной структуры с д вершинами и «прикрепленной» к ней Беллмановской ветки из р -= п - д вершин. Обозначим Ыч - максимальное суммарное число клеток у максимально-симметричной структуры с д вершинами. Осталось определить оптимальную величину д. Для этого сравним две структуры с д и (д + 1) вершинами у максимально симметричной структуры. Имеем для первой структуры суммарное число клеток

(п-д)Ь,

а для второй

Заметим, что Щд) = Ы(д + 1) при

9 2 "

Следовательно, при Ъ < Ьч оптимальной структурой является структура с клетками, а при Ъ> Ьч- структура с Л^н клетками.

В таблице 1 приведены значения Нч и Ья для д =2,12.

Таблица 1

2* 4 8 16 32 64 128 256 512 1024 2048 4096 8192

Ц 2 -> J 4 5 6 7 8 9 10 11 12 13

Ъ 4 12 24 48 88 164 304 584 1120 2184 4272 8444

вр 4 6 12 20 38 70 140 268 582 1044 2086

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

Задача выбора множества проектов по выпуску новых продуктов. Имеются п инновационных проектов (новых продуктов). Обозначим у! объем финансирования /-го продукта, если он принят к разработке.

Эффект (доход) от выпуска /-го продукта определяется выражением

где а, - постоянные затраты на разработку и освоение /-го продукта, р, - рентабельность /'-го продукта.

Заданы ограничения у, < С,, / = 1,и , где С, - максимальный объем финансирования /-го продукта, определяемый возможностями производства и рыночным спросом.

Задана также величина инновационного фонда Л. Задача. Определить множество продуктов, принятых к освоению и объем финансирования каждого продукта, так чтобы суммарный доход был максимальным при ограничении на суммарную величину инновационного фонда.

Задача заключается в максимизации

/=1

при ограничениях

О <У1<С; Метод решения (.первый алгоритм).

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

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

Теорема 8. Существует оптимальное решение такое, что все принятые к разработке продукты (за возможньм исключением одного продукта) финансируются в максимальном объеме.

Следствие. В множестве принятых к разработке продуктов финансирование менее максимального может иметь продукт с минимальной рентабельностью.

Рассмотрим структуру дихотомического представления в виде ветки дерева, вершины которого расположены в порядке нумерации продуктов. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Обозначим РО^р) ~ максимальный эффект от первых к проектов при величине инвестиционного фонда р. Уравнение Беллмана имеет вид

Пк+1; Р) = тах^(Аг; р-д)+рш тах[0; тт(См; д) - ам Ц

Рассмотрим другой алгоритм решения задачи, также использующий теорему 8. А именно, поскольку только один продукт может выпускаться с финансированием менее максимального, то рассмотрим п задач.

В г-й задаче принимается, что продукт / может выпускаться с финансированием менее максимального. Исключая этот продукт, мы получаем классическую задачу о ранце. Для оставшихся продуктов, как известно, решение задачи о ранце дает одновременно и оптимальное решение для всех меньших величин р. Обозначим Ф,(р) - максимальный эффект в 1-й задаче в зависимости от финансирования р. Максимальный эффект с учетом продукта г" определяется выражением х[Ф,(р)+а тах[0; тт(С,; Л - /?) - а, ]]

ОйреЯ

Сравнивая решения п задач, определяем оптимальное решение. Таким образом, необходимо решить п задач о ранце. Однако применение метода дихотомического программирования позволяет существенно уменьшить это число. Действительно, если например, решена задача о ранце для первых (п -1) продуктов, то для решения задачи без продукта (п -1) достаточно взять решение для первых (п - 2) продуктов и решить еще только одну задачу, добавив продукт п. Соответствующая структура дихотомического представления для п задач о ранце приведена на рисунке 7 (для случая п = 5).

Поясним эту структуру. Сначала решаются задачи о ранце без продукта 5 и без продукта 1. (Левая и правая ветки на рисунке 6). Для 18

получения решения задачи без продукта 4 решаем всего одну задачу для объединенного продукта (1, 2, 3) и продукта 5. Всего решается 3(и-2) подзадач, вместо и(и-2) при их независимом решении.

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

Рис 6. Структура дихотомического представления для 5 задач о ранце.

Задача максимизации объема работ проекта.

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

Примем, что плановый период разбит на Т интервалов определенной длины Д (недели, месяцы, кварталы и т.д.).

Обозначим Я, - множество интервалов, в которых может выполняться работа Р, - множество работ, которые могут выполняться в лом интервале. Заданы ограничения ^ на объем проектных работ в каждом интервале. Обозначим через - объем г-ой работы, выполняемый в £-ом интервале, с,Л - максимальный объем /-ой работы, который можно выполнить в .т-ом интервале. Задача заключается в определении {дси}, / = 1 ,п, 5 = 1,Т, так, чтобы

где ^ - объем г-ой работы,

2Х<а, 5=1,7-,

а суммарный объем выполненных работ

Е5л

был максимален.

Для решения задачи определим двудольный граф С(Х,У). Вершины / е X соответствуют работам, а вершины .ч е У соответствуют интервалам. Пропускные способности вершин г б X равны объемам IV, соответствующих работ, а пропускные способности вершины л е У равны объему работ, который можно будет выполнить в соответствующем интервале, то есть

Пропускные способности дуг (г, л), г = 1, и, л е Я, равны са. Задача свелась к определению максимального потока в полученной сети, что соответствует максимальному объему выполненных работ. Опишем алгоритм определения потока максимальной величины, основанный на методе сетевого программирования.

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

Рассмотрим произвольную сеть без контуров на дугах (/',/), которой заданы пропускные способности Су> 0. Как известно, потоком в сети, называется совокупность чисел 0 < хч < су, (г,у) е и ((/- множество дуг сети), таких что

; *

для всех / ф 0, и, где 0 - вход сети, ая- выход сети. Величиной потока называется

' I

Задача заключается в определении потока максимальной величины. Для решения этой задачи, как правило, применяется алгоритм Форда-Фалкерсона. Мы рассмотрим другой подход, в основе которого лежит метод сетевого программирования.

Сначала дадим определение агрегируемой сети.

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

Рис. 7.

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

Определение 2. Параллельным множеством дуг называется подмножество дуг сети, у которых начальная и конечная вершины совпадают.

Параллельное множество дуг можно агрегировать в одну дугу, пропуская способность которой равно сумме пропускных способностей дуг подмножества.

Определение 3. Сеть называется агрегируемой, если путем агрегирования последовательных и (или) параллельных множеств дуг ее можно свести к одной дуге.

Задача о максимальном потоке для агрегируемой сети эффективно решается. Рассмотрим произвольную сеть. Произвольную сеть всегда можно преобразовать в агрегируемую сеть путем разделения ряда вершин на несколько вершин. Так, если в сети (рис. 8) вершину 4 разделить на две вершины 4 и 4', то получим агрегируемую сеть, приведенную на рис. 9.

Поскольку вместо одной дуги (4,5) мы получили две дуги (4,5) и (4',5), то разделим пропускную способность С45=5 на две части произвольным образом. Возьмем, например, С45=4, С4-5=1. Определим поток максимальной величины и соответственно разрез минимальной пропускной способности в полученной сети, применяя алгоритм для агрегируемых сетей.

Нетрудно видеть, что величина потока равна 7, а в разрез заходят дуги (0,1) и (4',5). Имеет место

Теорема 9. Величина максимального потока в агрегируемой сети меньше или равна величине максимального потока в исходной сети.

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

Теорема 10 (двойственности). Существует разбиение пропускных способностей дуг, исходящих из разделенных вершин такое, что величина максимального потока в агрегируемой сети равна величине максимального потока в исходной сети.

Следствие. Если (i,j) дуга, заходящая в разрез минимальной пропускной способности в исходной сети, то все дуги (i3,j) также заходят в разрез минимальной пропускной способности в агрегируемой сети.

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

Оптимальное размещение работ между подразделениями организации

Пусть в организации имеются т подразделений, располагающих мощностями ресурсов одного вида. Обозначим Q, объем работ, который может выполнить i-e подразделение, IV¡ - объем i-й работы,

i = 1, п. Требуется распределить работы между подразделениями, так, чтобы загрузка подразделений (или их перегрузка) была максимально равномерной. Обозначим Хц- 1 если /-я работа выполняется подразделением j, Xíj = 0 в противном случае. Тогда уровень загрузки (перегрузки) подразделения / можно оценить величиной

Задача заключается в распределении работ по подразделениям так, чтобы минимизировать

ma^^-ß,-}-

Рассмотрим сначала частный случай, когда Q/=0 для всех j. В этом случае задача сводится к классической «задаче о камнях».

Дадим постановку «задачи о камнях». Имеется п «камней» разного веса. Требуется разбить их на т групп так, чтобы максимальный вес камней в группе был минимален. Задача о камнях имеет многочисленные варианты применения (равномерное распределение работ между исполнителями, функций по подразделениям организационной структуры и т.д.). Дадим формальную постановку задачи.

Задача 1. Обозначим через а, - вес г'-го камня, x,j= 1 если камень i попал ву'-ю группу, хц= 0 в противном случае. Суммарный вес камней в j-й группе равен

(34) 1] =Vfl,x„ .

Максимальный вес группы

(35) Т = таx^ö-дс,, -> min.

i i 1

Поскольку каждый камень должен быть помещен только в одну группу, имеем ограничения:

(36) 1^ = 1, / = 1,п.

Задача заключается в минимизации (35) при ограничениях (36). Мы будем рассматривать вспомогательную задачу следующего вида:

Задача 2. Фиксируем допустимый вес каждой группы Т и сформулируем следующую задачу: максимизировать сумму весов камней, размещенных в ящики вместимостью Т:

(37) Ф = —> шах.

i,j

при ограничениях (36) и (38):

(38) 1а,хц<Т, j = TJi. >

Связь между задачами (35)-(36) и (36)-(38) очевидна. Минимальное Т, при котором в оптимальном решении задачи 2 размещены все камни, дает оптимальное решение задачи 1.

Сначала получим сетевое представление задачи 2. Оно представлено на рис. 10 для случая п = 3, т = 2.

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

Все а, также делим на 2 части и, и V, для каждой вершины нижнего уровня так, что (3 9) щ + V,, = а„ для всех

Рассмотрим следующие две задачи.

Задача 3. Определить х, так, чтобы максимизировать

при ограничениях (36).

Задача 4. Максимизировать

У V х

' у и

при ограничениях (38).

Обозначим Б„,(и) и Ьт(у) оптимальные решения первой и второй задач при заданных и и V. ОДЗ заключается в определении и и V, минимизирующих (40) ^и,у)=ЗД + Хт(у)

при ограничении (39). Заметим, во-первых, что в оптимальных решениях первой и второй задач можно принять

Щ = а> ~У< Для всех'>/ Во-вторых, решение первой задачи очевидно:

В-третьих, решение второй задачи при заданных {у,} сводится к решению задачи о ранце: определить х1 =0,1, максимизирующие приограниченш

(40 ' _

Решим задачу (41) при у,.= 0, ¿ = 1 ,п. Обозначим через 0 = {х1} множество векторов х, удовлетворяющих (41) и упорядоченных по

убыванию М} - £ а,х- , У] у,х/ , а 2 = тах(Му-Г.)-> »

Заметим, что при заданных {у,} 2 определяет оптимальное решение второй задачи. Оценка (40) при этом равна

(42) Р(у) = т2^У,-

гдеу, > 0 удовлетворяют неравенствам

(43) £у,х/±г>му, у =

где N - число различных решений неравенства (41). Таким образом, оценочная задача свелась к определению 0 <у,<а.,, 1=1,п и 0 < 2, минимизирующих (42) при ограничениях (43). Это обычная задача линейного программирования. Далее можно применить метод ветвей и границ на основе полученной оценки.

Распределение ресурсов с учетом времени их перемещения между работами проекта

При решении задач распределения ресурсов, как правило, не учитываются времена перемещения ресурсов с работы на работу. Однако, в ряде случаев времена перемещения ресурсов сравнимы с продолжительностью работ и пренебрегать ими нельзя. Рассмотрим, например, задачу ремонта мостов или участков дорог. Ремонт производится одной бригадой. Необходимо определить очередность ремонта мостов (участков дорог) так, чтобы продолжительность ремонта была минимальной. Задача сводится к задаче коммивояжера. Дадим ее постановку и решим на основе метода сетевого программирования.

Задан (и+1)-вершинный граф с длинами дуг /,,, которые интерпретируются как расстояние между городами I и}. Требуется найти кратчайший гамильтонов контур (маршрут коммивояжера). Обозначим х0 = 1, если дуга (/,/) входит в маршрут, ху = 0 в обратном случае. Тогда задача сводится к минимизации

при ограничениях

(44) V/.

(45) 5>,;=! V/

(46) и1 -и) + пху <п-1,

где и, > 0; /,_/ = 1, 2, ... , п; г Ф]. Условие (46) гарантирует получение гамильтонова контура.

Рассмотрим симметричную задачу коммивояжера, то есть Ц = V;,у. Разобьем ограничения задачи на две группы. В одну группу включим ограничения (44) и (46), а во вторую - (45) и (46) Соответственно разделим на две части коэффициенты 1,р то есть представим 4 в виде

(47)

Рассмотрим две оценочные задачи.

Задача 5. Определить {*,,}, удовлетворяющие ограничениям (44) и (46) и минимизирующие

Задача 6. Определить {худовлетворяющие ограничениям (45) и (46) и минимизирующие

Обозначим Ь\(р) (1г(д)) значение целевой функции в оптимальном решении первой (второй) задачи.

В соответствии с основной теоремой 3, сумма

дает оценку снизу для исходной задачи коммивояжера. Таким образом, ОДЗ заключается в определениир ид, удовлетворяющих (47) и максимизирующих (48).

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

Метод решения оценочных задач для симметричных матриц основан на понятии /'-дерева.

Выбираем некоторую вершину ¡'. Для подграфа без вершины /' строим кратчайшее /"-дерево Т„ то есть дерево кратчайшей длины /(Т;). Для построения кратчайшего /-дерева Т1 построим кратчайшее дерево на вершинах графа без вершины / и добавим к нему два кратчайших ребра, инцидентных вершине /.

Оценка снизу для каждой задачи определяется /-деревом, для которого /(21) максимальна.

Пример 5. Рассмотрим граф, рис. 12.

Оценка снизу определяется любым /-деревом, и равна /(Г,) = 9, I = 1,6. Разобьем граф на 2 (рис. 13). Имеем для первого графа 1(Т3) = 9, а для второго 1(Т2) ~ 9. Оценка снизу равна /(Г3) + 1{Т2) = 18, т.е. в два раза лучше. Более того, она является достижимой. Оптимальный маршрут-(1,2,6,5,4,3,1).

(48) Х1(Р) + 12(0 = 1(Р,О)

Рис. 12.

Рассмотрим новый способ получения нижних оценок, в основе которого лежит построение дерева кратчайших путей. Сначала рассмотрим задачу коммивояжера с длинами дуг /&.=|Яу-4 Vi,у.

Определение. Последовательность (¿b ¿2,..., i„) называется одно-пиковой, если

Л <Л, <■■■<! >Л >Л >•••> Л, ,

Г1 '2 't-l "¿ 'i+I "л '

где \ = 0, Я1к = шах Я, = .

Теорема 11. Любая однопиковая последовательность определяет

оптимальный маршрут, длина которого равна 2Атах.

Для получения оценок задач 1 и 2 определим Л„ i = 1, п,

rain Я; = 0, так, чтобы /

и Лт = тахЯ, был максимален. /

Определение, /-деревом кратчайших путей R, называется дерево кратчайших путей из вершины г в остальные вершины графа.

Для построения ¿-дерева полагаем Л, = 0 и строим дерево кратчайших путей из вершины i в остальные вершины. Обозначим Л,-длину кратчайшего пути из вершины i в вершину у, Л(Я1) = тахЛ1.

Согласно теореме 11, величина 2является нижней оценкой для соответствующей задачи коммивояжера. Наилучшая оценка, очевидно, определяется ¿-деревом кратчайших путей, для которого

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

Постановка задачи. Рассмотрим задачу формирования программы развития региона (либо предприятия, холдинга, корпорации), обеспечивающей требуемое значение комплексной оценки с минимальными затратами. Примем, что задана процедура формирования комплексной оценки программы на основе дихотомического дерева. Программа оценивается по т критериям. Обозначим минимальное (граничное), значение /-го критерия, которому соответствует оценка /' (/': 1,2, 3, 4). Таким образом, если значение критерия^ лежит в полуинтервале

то оценка по соответствующему критерию равна у.

Имеется п проектов - претендентов на участие в программе. Каждый проект характеризуется затратами ск и показателями эффекта щ, вклад Ус-го проекта в ¡'-й критерий. Обозначим хк = 1, если к-ый проект включен в программу хк - 0 в противном случае. Предполагая, что эффекты суммируются, получаем, что увеличение /-го критерия в результате реализации программы составит

а соответствующая оценка по /-ому критерию равна

где у° - начальное значение /-го критерия, в преобразование численного значения критерия в дискретную (качественную) шкалу. Суммарные затраты на реализацию программы составят

(49) С(*)=£СЛ •

Обозначим А'(У) - комплексную оценку программы при оценках критериев

••• '-/я)

Задача. Определить множество проектов, обеспечивающих КЦ) = Кг при минимальных затратах (49). Задача относится к сложным задачам дискретной оптимизации.

Частный случай. Рассмотрим ситуацию, когда для каждого направления / существует свое множество проектов 2„ /=1 ,т, причем

эти множества не пересекаются. В этом случае алгоритм решения задачи становится существенно проще.

1 шаг. Решаем т задач о ранце для каждого критерия: минимизировать

С,0)= 1]скхк

кед,

при ограничении

ке а

Как известно, решение задачи о ранце при правой части ограничения Л,т дает оптимальные решения и для всех меньших значений правой части. Обозначим - минимальные затраты, требуемые для достижения оценки у по /-ому критерию.

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

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

Первый способ (перебор многоцелевых проектов). Пусть число многоцелевых проектов невелико. Тогда можно просто перебрать всевозможные варианты вхождения в программу этих проектов. Таких вариантов 2к, где ¿-число многоцелевых проектов. Для каждого такого варианта можно определить, какой суммарный эффект по каждому направлению должны обеспечить остальные (одноцелевые) проекты. Сравнивая все 2к варианты определяем оптимальный.

Второй способ (метод сетевого программирования). Если число многоцелевых проектов велико, то метод перебора становится не эффективным. Применим для получения нижних оценок затрат метод сетевого программирования. Для этого затраты каждого многоцелевого проекта делим на число проектов, в которые он дает эффект. После такого деления получаем частный случай, рассмотренный выше. Согласно центральной теореме метода сетевого программирования, решение оценочной задачи дает нижнюю оценку для исходной задачи. Далее, эту оценку можно улучшать, решая ОДЗ (то есть целенаправ-

ленно изменяя разбиение затрат многоцелевых проектов), либо применить эту оценку в методе ветвей и границ.

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

Сравнение алгоритмов проводилось для числа проектов N = 50. Число критериев М= 4,5. Число проектов, дающих вклад сразу в несколько критериев изменялось от 1 до 12. Стоимость реализации каждого проекта - случайное целое число от 20 до 35. Эффект от каждого проекта по одному из направлений - случайное целое число от 10 до 25.

На графиках показана зависимость времени (сек.) от числа многоцелевых проектов, дающих эффект по нескольким критериям.

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

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

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

(50) щ + У,у = ^0, г = 1, п, } = 1, т . Получаем две оценочные задачи.

Задача 1. Определить вариант программы, обеспечивающий комплексную оценку не менее К\ (по первой системе комплексного оценивания) и минимизирующий

(51) " =

где у,- - оценка варианта по г'-му критерию.

Задача 2. Определить вариант программы, обеспечивающий комплексную оценку не менее К2 (по второй системе комплексного оценивания) и минимизирующий

(52)

где ji - оценка варианта по г-му критерию.

Если обозначим U(u) значение (51) в оптимальном решении первой задачи, U(v) - значение (52) в оптимальном решении второй задачи, то оценка снизу минимальных: затрат для исходной задачи равна

(53) F(u,v) = U(u) + V(v)

Обобщенная двойственная задача. Определить и и v, удовлетворяющие (50), так чтобы F(u,v) была максимальной.

В силу теоремы 4 это задача выпуклого программирвоания. Опишем основной шаг алгоритма решения ОДЗ. Пусть при заданных и и v получены оптимальные решения первой и второй задачи

k = l,s, {/}, k = \,t, где s - число решений первой задачи, / -число решений второй задачи. Обозначим z,j - изменение переменной ujJ: и соответственно (-zy) - изменение переменной vy. Предполагаем, что Zij такое что, оптимальные решения первой и второй задачи остаются оптимальными. В первой задаче величина U(u) изменяется на

A(z)=min"jLzijXij ■ k ij

Во второй задаче величина V(v) изменится на

S(z)=- max£z„>'y • k 0

Суммарное изменение нижней оценки F(u,v) составит Д(г)+ ö(z) = min Ц Zij xij - maxZ zi} Уц

k i,j k U

Для того чтобы оценку (53) можно было увеличить необходимо и достаточно, чтобы существовало ненулевое решение неравенства

minZ Zij щ > maxS Zy y\ ■

* ij * и

Заметим, что решение z этой системы инвариантно к умножению на любое положительное число. Выбор конкретных значений {z^} определяется из условий появления новых решений хотя бы для одной задачи.

Для оценки вычислительной сложности алгоритма разработана программа на языке PHP 5.0.

Эксперименты показали, что для числа критериев от 3 до 10 при величине затрат на достижение оценки от 1 до 1000 время программы незначительно изменяется в пределах К4 миллисекунды.

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

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

• управления рыночной стоимостью объектов недвижимости;

• оптимизации корпоративных бизнесов;

• оптимизации стратегии слияния предприятий с учетом синер-гетического эффекта;

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

Заключение

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

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

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

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

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

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

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

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

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

о максимальном потоке);

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

• задача формирования программ развития регионов на основе

комплексных оценок и др.

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

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

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

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

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

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

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

Основные результаты диссертащи опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

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

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

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

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

5. Белов И.Г., Буркова И.В. Формирование портфеля инвестиционных проектов с ограничениями по сегментам инвестирования. -

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

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

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

2005. С. 25-27.

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

9. Буркова И.В., Косенков A.B., Харитонова Т.Б. Метод дихотомического программирования в задачах управления рыночной стоимостью объектов недвижимости. - «Системы управления и информационные технологии», научно технический журнал, №1.1 (23),

2006. С. 123-126.

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

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

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

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

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

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

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

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

18. Бондарик В.Н., Буркова И.В., Крюков C.B. Задача оптимизации программ по стоимости // Динамика неоднородных систем. -2010. - №53 (2) вып. 14 Труды ИСА РАН под ред. член-корр. РАН Попкова Ю.С. - С. 65-72.

Книги, научные издания, главы в книгах. -

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

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

21. Бурков В.Н., Буркова И.В. Метод дихотомического программирования в задачах дискретной оптимизации М.: 2003 (Научное издание / ЦЭМИ РАН). - 41 с.

22. Буркова И.В., Михин П.В., Попок М.В., Семенов П.И., Шевченко Л.В. Модели и методы оптимизации планов проектных работ. Научное издание / Институт проблем управления им. В.А. Трапезникова РАН-М. 2005.-68 с.

23. Математические основы управления проектами: Учебн. по-собие/С.А. Баркалов, И.В. Буркова, В.И. Воропаев и др. Под ред. В.Н. Буркова. - М.: Высшая шк., 2005. - 423 е.: ил.

24. Бурков В.Н., Буркова И.В., Горгидзе И.А., Джавахадзе Г.С., Хуродзе P.A., Щепкин A.B. Задачи управления в социальных и эконо-

мических системах. М.: СИНТЕГ, 2005. Серия «Управление организационными системами». - С. 51 -! 11.

25. Буркова И.В., Курочка П.Н.. Семенов П.И., Михин П.В., Ко-тенко A.M., Половинкина А.И., Потапенко A.M. Оптимизационные модели и механизмы в управлении строительными проектами (в 4-х томах). Краснодар, 2005. 973 с.

26. Баркалов С.А., Бурков В.Н., Буркова И.В., Глотов Т.И., Еро-хин A.B., Курочка П.Н., Михин П.В. Модели и методы управления проектами при реформировании и реструктуризации предприятий. Воронеж. Гос.арх.-строит. Ун-т. 2007. - 311 с.

27. Бурков В.Н., Бурджанидзе В.О., Буркова И.В., Горгидзе Д.А., Горгидзе И.А., Джавахадзе Г.С., Хомерики И.О., Хуцишвили С.А. Некоторые задачи управления корпоративными системами. Издательский дом «Технический университет», 2007 (Серия «Управление, вычислительная техника, информатизация»). - 98 с.

28. Баркалов С.А., Буркова И.В., Курочка П.Н., Михин П.В. Модели и методы управления строительными проектами. М., ООО «Уланов-пресс», 2007. - 440 с.

29. Буркова И.В. Основные задачи оптимизации управления строительными проектами. В кн. Оптимизационные модели и методы в управлении строительным производством [Текст]: монография / П.И. Семенов [и др.]; ГОУ ВПО ВГАСУ. - Воронеж: Научная книга, 2007.-423 е., С. 11-50.

30. Бурков В.Н., Буркова И.В., Губко М.В., Динова Н.И., Еналеев А.К., Кондратьев В.В., Коргин H.A., Новиков Д.А., Цветков A.B., Чхартишвили А.Г, Щепкин A.B. МЕХАНИЗМЫ УПРАВЛЕНИЯ: Мультифункциональное учебное пособие / Под ред. чл.-к. РАН Д.А. Новикова - М.: Ленанд, 2010.- 192 с.

Статьи и материалы конференций

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

32. Бурков В.Н., Буркова И.В., Попок М.В. Решение задачи о камнях методом дихотомического программирования - Материалы IV

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

33. Бурков В.Н., Буркова И.В., Колпачев В.Н. Задачи дихотомической оптимизации - «Вестник» научно-технический журнал ВГАСУ, 2004, выпуск 2. С. 112-114.

34. Бурков В.Н., Буркова И.В., Попок М.В. Метод дихотомического программирования - Управление большими системами / Сборник трудов. Выпуск 9: «Лаборатория активных систем. 30 лет». Общая редакция - Д.А. Новиков. - М.: ИПУ РАН, 2004. - С. 57-75.

35. Баркалов С.А, Буркова И.В., Половинкина А.И. Оптимизационная модель программы повышения региональной безопасности (статья). - Системы жизнеобеспечения и управления в чрезвычайных ситуациях: 4.2: Межвуз. сб. науч. тр. - Воронеж: Воронеж, гос. техн. ун-т, 2004. 254 с. С. 107-117.

36. Буркова И.В., Половинкина А.И., Толстых A.B. Оптимизация программ обеспечения региональной безопасности . Сборник трудов международной конференции «Современные сложные системы управления», том 1. - Тула, 2005.С. 73-85.

37. Буркова И.В., Михин П.В., Попок М.В. Задача о максимальном потоке. Сборник трудов международной конференции «Современные сложные системы управления», том 2. - Тула, 2005.С. 80-90.

38.Бурков В.Н., Буркова И.В., Баранчиков В.В., Володин C.B. Решение задач дискретной оптимизации на основе метода сетевого программирования. - Системы управления эволюцией организации (CSOE'2008): сборник трудов VI международной конференции / ИПУ РАН им. В.А. Трапезникова. - Воронеж: Научная книга, 2008 - С. 103-107.

39. Буркова И.В., Котенко A.M. Оптимизация последовательности выполнения проектов. - Журнал ИЗВЕСТИЯ Серия: строительство, Архитектура и реставрация. Выпуск 8 часть 2. Тула, 2005. С. 166-174.

40. Буркова И.В., Котенко А.М. Оптимизация программ по стоимости. - Журнал ИЗВЕСТИЯ Серия: строительство, Архитектура и реставрация. Выпуск 8 часть 2. Тула, 2005. С. 80-89.

41. Буркова И.В., Половинкина А.И., Семенов П.И. Задачи оптимизации программ развития по стоимости. - Известия Тульского государственного университета, 2005, выпуск 8. С. 120-127.

42. Буркова И.В., Колпачев В.Н., Толстых A.B., Уандыков Б.К. Метод дихотомического программирования в задаче оптимизации программ по стоимости (статья). - Научный вестник ВГАСУ. Серия: Управление строительством. Выпуск №1 - Воронеж, 2005. - С. 39-41.

43. Ленина Н.Г., Буркова И.В., Котенко А.М Оптимизационная модель последовательности выполнения проектов. - Современные сложные системы управления: Сб. науч. тр. междунар. конф. Т. 1/Воронеж. гос. арх.-строит. ун-т. - Воронеж, 2005. С. 89-94.

44. Баркалов С.А., Буркова И.В., Семенов П.И., Юшин Г.Д. Модель оптимизации программ развития по стоимости. - Современные сложные системы управления: Сб. науч. тр. междунар. конф. Т. 1/Воронеж. гос. арх.-строит. ун-т. - Воронеж, 2005. - С. 94-99.

45. Агеев И.А., Буркова И.В., Семенов П.И. Стратегия развития корпорации с учетом возможностей совмещения различных бизнесов. Современные сложные системы управления «Сборник научных трудов восьмой научной конф. Краснодар-Воронеж-Сочи 2005. С. 103108.

46. Буркова И.В., Потапенко A.M., Половинкина А.И. Разработка стратегии реализации проекта с учетом риска. Современные сложные системы управления «Сборник научных трудов восьмой научной конф. Краснодар-Воронеж-Сочи 2005. С. 119-125.

47. Буркова И.В. Методы решения задач дискретной оптимизации. В кн. Модели и методы управления проектами в дорожном строительстве./ Баркалов С.А., Курочка П.Н., Половинкина А.И., Беляев Ю.А., Ерохин A.B., - М.: ООО «Уланов-пресс», 2007. - 384 с. - С.51-60.

48. Буркова И.В. Методы сетевого и дихотомического программирования. В кн. Модели и методы управления проектами в дорожном строительстве./ Баркалов С.А., Курочка П.Н., Половинкина А.И., Беляев Ю.А., Ерохин A.B., М., 000»Уланов-пресс», 2007.-384 с. С.60-71.

49. Буркова И.В., Власенко В.А., Мясищев Р.Ю. Оптимизация систем управления на основе задачи о максимальной циркуляции. Материалы Международной научной конференции «Сложные системы управления и менеджмент качества» CCSQM'2007. 12-14 марта 2007 г. -Старооскольский технологический институт, Старый Оскол. С. 8-10.

50. Буркова И.В., Врублевская С.С., Толстикова И.В. Решение задачи выбора множества объектов методом сетевого программирования. 40

Материалы Международной научной конференции «Сложные системы управления и менеджмент качества» CCSQM'2007. 12-14 марта 2007 г. Старооскольский технологический институт, Старый Оскол. С. 11-13.

51. Буркова И.В., Сиренько С.В., Половинкина А.И. Метод дихотомического программирования при составлении плана закупок материалов. Материалы Международной научной конференции «Сложные системы управления и менеджмент качества» CCSQM'2007. 12-14 марта 2007 г. Старооскольский технологический институт, Старый Оскол. С. 64-66.

52. Буркова И.В., Кашенков А.Р. О задачах оптимизации корпоративных бизнесов в случае совместного финансирования бизнесов. Теория активных систем / Труды международной научно-практической конференции (14-15 ноября 2007 г., Москва, Россия). Общая редакция - В.Н. Бурков, Д.А. Новиков. -М.: ИПУ РАН, 2007. -300 с.-С. 226-230.

53. Буркова И.В., Новиков A.A., Романченко О.В. Алгоритм дихотомического программирования в задачах выбора вариантов оптовых закупок. - Системы управления эволюцией организации Четвертая международная конф. (12-19 апреля 2007г. г. Санья, китайская Народная республика).-С. 167-172.

54. Баранчиков В.В., Буркова И.В., Ещенко Р.В., Урманов И.А. Определение первоочередных значимых объектов на основе сетевого программирования. - Международная научно-практическая конференция 22-23 ноября 2007г. г. Старый Оскол. ТОМ 3. - С. 122-127

55. Бурков В.Н., Буркова И.В. Метод сетевого программирования в задачах управления проектами. Труды международного симпозиума «Управление проектами: власть, общество, бизнес». CD. Нижний Новгород, февраль 2007 года.

56. Буркова И.В. Метод сетевого программирования в задаче оптимизации корпоративных бизнесов. Доклад. Четвертая международная конференция по проблемам управления. (26-30 января 2009г. ИПУ РАН, Москва). CD.

57. Бурков В.Н., Буркова И.В. Метод сетевого программирования при решении задач управления проектами. Док. Четвертая международная конференция по проблемам управления. (26-30 января 2009г. ИПУ РАН, Москва). CD.

- 58. Бурков В.Н., Буркова И.В. Метод сетевого программирования в задачах управления проектами. Плен. док. VI Международная конференция «Управление проектами в развитии общества», 21-22 мая 2009 года, Киев. С. 8-15.

59. Алферов В.И., Буркова И.В., Керусова В.А. Решение многоэкстремальных задач распределения ресурсов на основе метода дихотомического программирования. Труды 2-й Всероссийской науч.-тех. Конференции «Управление в организационных системах», Воронеж, 18-21 мая 2009 г.-С. 127-131.

60. Буркова И.В., Захарченко О.С., Руденко З.Г. Задача выбора оптимальной стратегии интегрирования компаний. Теория активных систем / Труды международной научно-практической конференции (17-19 ноября 2009 г., Москва, Россия). Том 2. Общая редакция -В.Н. Бурков, Д.А. Новиков. - М.: ИПУ РАН, 2009. - С.25-26.

61. Бурков В.Н., Буркова И.В.Системы управления инновационным развитием регионов: проблемы и пути решения Управлшия проектами: стан та перспективи: Матер1али мижнародно! науково-практичжн конференцп. - Миколат: НУК, 2010. С. 46-50.

62. Vladimir Burkov, Iriya Burkova. Network Programming Method for Nonlinear Optimization Problems. Book of abstracts of the International Symposium on STOCHASTIK MODELS in RELIABILITY ENGINEERING, LIFE SCIENCE and OPERATIONS MANAGEMENT / Industrial Engineering and Management Department, SCE - Shamoon College of Engineering, Beer Sheva, Israel. 2010. P. 64. (full paper is on the CD)/ 8-10 февраля.

63. Бурков B.H., Буркова И.В. Метод сетевого программирования в задаче оптимизации программ по стоимости - Труды четвертой международной конференции "Управление развитием крупномасштабных систем MLDS-2010 (4-5 октября 2010 г., Москва, Россия).

64. Бурков В.Н., Буркова И.В., Крюков С.В. Разработка региональных программ на основе метода сетевого программирования. Материалы VII Международной научно-технической конференции «Управление проектами: состояние и перспектива». Украина, Николаев,20-23 сентября 2011 г. - Николаев: НУК, 2011. - С. 58-65.

65. Буркова И.В., Кашенков А.Р. Метод сетевого программирования в задаче целочисленного линейного программирования. Труды

международной научно-практической конференции Теория активных систем-2011 (14-16 ноября 2011 г., Москва, Россия). Том 1. Общая редакция - В.Н. Бурков. Д.А. Новиков. - М.: ИЛУ РАН, 2011. - С. 25-26.

Личный вклад автора в работах, опубликованных в соавторстве, заключается в следующем: в [6,7] автору принадлежит описание метода сетевого программирования; в [16,61] - применение метода сетевого программирования при разработке программ инновационного развития; в [23,24,27] - главы с описанием метода сетевого программирования; в [30] - раздел 7.3 (Метод «Затраты-Эффект»); в [31,34] - описание метода дихотомического программирования. В остальных работах автору принадлежат алгоритмы решения соответствующих задач на основе метода сетевого программирования.

Подписано в печать 07.02.2012 г.

Печать трафаретная Усл.п.л. - 2,7 Заказ №378 Тираж: 120 экз. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

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

ВВЕДЕНИЕ.

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. Разработка региональных программ социально-экономического развития.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• и др.

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

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

1. «Современные сложные системы управления», Воронеж, 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 в журналах, входящих в список ВАК.

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Библиография Буркова, Ирина Владимировна, диссертация по теме Управление в социальных и экономических системах

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.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00