Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

На правах рукописи

УДК 338.24.57

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

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

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

доктора технических наук

МОСКВА - 2012

Работа выполнена в Институте проблем управления
им. В.А. Трапезникова РАН

Официальные оппонентыаЦадоктор технических наук, профессор

       Дорофеюк Александр Александрович

        -        доктор технических наук, профессор

               Горошко Игорь Владимирович

        -        доктор технических наук, профессор

               Сигал Израиль Хаимович

       

Ведущая организацияаа        ЦаИнститут системного анализа РАН

Защита состоится ла__а ________ 2012аг. в _______ час.
на заседании диссертационного совета _____________ при Институте проблем управления им. В.А. Трапезникова  РАН по адресу:

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

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

Автореферат разослан ла__а ________ 2012аг.

Ученый секретарь

Диссертационного Совета
к.т.н.        В.Н. Лебедев

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

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

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

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

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

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

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

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.
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 г.

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

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

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

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

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

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

• формирование пакета инвестиционных проектов (задача о ранце и ее модификации);
• распределение ресурсов по проекту с учетом времени их перемещения с работы на работу (задача коммивояжера);
• распределение работ по исполнителям по критерию равномерности загрузки (задача о камнях);
• распределение ресурсов в проекте по критерию максимизации объема выполненных работ проекта (задача о максимальном потоке);
• задача оптимизации программы развития регионов на основе комплексных оценок социально-экономического уровня.

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

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

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

(1)                

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

(2)        .        

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

       ,

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

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

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

       f(x)а=а(x1x2а+аx12)x3а+аx3x4а+аx1x4        

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

       y1а=аx1x2а+аx12

       y2а=y1x3

       y3а=x1x4

       y4а=x3x4

       y5а=аy2а+аy3 а+аy4

Рис. 1.

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

Пример 2. Рассмотрим функцию

       φ(x)а=а(x1а+аx2)x3(x1а+аx4)а+аx3x4.

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

Пусть функции f(x) и φ(x) в задачах (1) и (2) являются с-подобными. Построим их общее сетевое представление. Пусть далее целевая функция f является монотонной функцией обобщенных переменных y (без ограничения общности можно принять, что f - возрастающая функция y). Аналогично примем, что функция φ также является возрастающей функцией y. В сетевом представлении выделим вершины нулевого уровня, которым соответствуют переменные xi. Вершинам первого уровня соответствуют задачи оптимизации следующего вида: максимизировать

       yiа=аfi(x)        

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

       ziа=аφi(x)ааp,        

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

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

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

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

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

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

(3)        ,        

где xiа∈аXi является аддитивной.

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

Доказательство. Пусть Gn - сетевое представление некоторой функции n переменных, xi - начальные вершины сети, . Для каждого значения xiа∈аXi определим поток величины fi(xi) из вершины xi в конечную вершину сетевого представления. В силу условий потоковости величина потока в конечной вершине равна fi(xi) для любого сетевого представления. Теорема доказана.

Поскольку поток величины fi(xi) для каждого xi можно определять произвольно, существует бесконечное число сетевых представлений функции (3).

Пусть переменная xi принимает mi значений xij, . Обозначим sij - поток величины cijа=аfi(xij) из вершины xi в конечную вершину. Sа=а{sij} - совокупность всех потоков, F(S) - оценка сверху величины (3), полученная методом сетевого программирования при сетевом представлении определяемом совокупностью потоков S. Естественно поставить задачу определения такой совокупности потоков S, для которой оценка сверху минимальна. Эту задачу назовем обобщенной двойственной к исходной. Сформулируем ее.

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

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

(4)        

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

(5)        ,

(6)        .

На рис. 2 приведено сетевое представление ограничений (5), (6) (через Xj обозначено j-е ограничение (5), ).

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

       ,

Рис.2.

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

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

(7)        

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

(8)        .

Обозначим через Fj(h) значение целевой функции в оптимальном решении j-ой подзадачи.

Теорема 3. Функционал

(9)        

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

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

Теоремаа4. Функционал F(h) является выпуклым.

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

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

Примера3. Возьмем одно из допустимых решений двойственной задачи . Первые m подзадач принимают вид:

       

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

       .

Очевидно, что . Опираясь на это утверждение, получаем

(10)        .

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

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

       

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

       .

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

       .

Решаем (m+1) подзадач: определить целочисленный неотрицательный вектор x, максимизирующий 

(11)        

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

(12)        .

Обозначим Fj(s) значение Sj(х) в оптимальном решении j-й подзадачи. Согласно теореме 3

(13)        

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

       .

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

Получим необходимые и достаточные условия оптимальности решения двойственной задачи. Пусть s - некоторое решение. Обозначим через Рj (sj) множество оптимальных решений j-й подзадачи (11), (12), .

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

(14)        

при условиях

(15)        .

Пример 4. xiа=а0,а1; iа=а.

       ,

       ,

(16)        .

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

       

где х2 определяется неравенством (16). При заданном - это задача лодномерный ранец. Она является NP-трудной, если неизвестна зависимость от n правой части b2 ограничения (16). Однако на практике, как правило, b2 либо не зависит от n, либо является линейной функцией n. В этом случае при целочисленных параметрах задача эффективно решается методами динамического либо дихотомического программирования. Имеем оптимальное значение , оценка сверху . Этому значению 0 соответствуют следующие значения :

(17) 

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

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

Поскольку уi1а+ауi2а=а0. то обозначим уiа=ауi1а=а-уi2. В этом случае система (14), (15) запишется в виде

.

Одно из решений этой системы

.

Возьмем , так как при появляется новое решение во второй подзадаче. Имеем:

 

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

       .

Нетрудно видеть, что это неравенство не имеет решений. Действительно, из условия у1а+ау2а+ау3а<ау1а+ау2а+ау4 следует у3а<ау4, а из условия у2а+ау4а<ау2а+ау3 следует у4а<ау3 , что противоречиво. Следовательно, получено оптимальное решение двойственной задачи. Полученную оценку сверху можно использовать в методе ветвей и границ. Возьмем для ветвления временную х1. Если х1а=а1, то решив соответствующую двойственную задачу, получим ту же оценку F(х1=1)а=а201/2. В случае х1а=а0 оценка F(х1=0)а=а14. Выбираем значение х1а=а1 и производим ветвление по переменной х2. Если х2а=а1, то получаем достижимую оценку F(х1=1,ах2=1)а=а18. Если х2а=а0, то получаем также достижимую оценку F(х1=1,ах2=0)а=а17. Следовательно, оптимальное решение х1а=а1, х2а=а1, х3а=а0, х4а=а0, Сmаха=а18.

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

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

       

       

       

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

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

Пусть множество всех проектов разбито на m непересекающихся подмножеств Qj, jа=а1,а2,аЕ,аm. В каждом подмножестве допускается выбор одного и только одного пректа. Для формальной постановки задачи введем переменные , принимающие значения 0 или 1 (nj - число элементов множества Qj). Примем xijа=а1, если проект iа∈аQj взят в портфель и xijа=а0, в противном случае. Задача заключается в определении {xij}, максимизирующих

(18)                

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

(19)                

(20)                

(cij, aij соответственно ценность и вес предмета iа∈аQj).

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

Рис. 3.

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

(21)                

Задача заключается в максимизации (18) при ограничениях (19) и (21). Полагаем, что , в противном случае задача распадается на m несвязанных задач о ранце.

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

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

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

               

               

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

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

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

               

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

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

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

Рис. 4.

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

(22)        cijа=аuijа+аvij

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

Определить {xij}, iа∈аQ, максимизирующие

(23)                

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

(24)        .        

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

(25)                

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

(26)                

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

Согласно теореме 3 сумма

(27)        Ф(uj)а+аФ(v)

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

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

Теорема 6. В решении двойственной задачи имеет место uijа=аj для всех jа∈аQ, .

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

               

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

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

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

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

Теорема 7. Если 2n-1ааb, то оптимальной структурой является максимально симметричное дерево.

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

Рис. 5

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

N(q)а=аNqа+а2(nа-аq)b,

а для второй

N(qа+а1)а=аNq+1а+а2(nаЦаqа-а1)b.

Заметим, что N(q)а=аN(qа+а1) при

.

Следовательно, при bа<аbq оптимальной структурой является структура с Nq клетками, а при bа>аbq - структура с Nq+1 клетками.

В таблице 1 приведены значения Nq и bq для .

Таблица 1

2q	4	8	16	32	64	128	256	512	1024	2048	4096	8192
q	2	3	4	5	6	7	8	9	10	11	12	13
Nq	4	12	24	48	88	164	304	584	1120	2184	4272	8444
вq	4	6	12	20	38	70	140	268	582	1044	2086

Рассмотрим задачу формирования портфеля взаимосвязанных проектов. Пусть дан набор возможных проектов {xi}, 1ааiааn. Заданы затраты проектов {ci}, а так же матрица взаимовлияния ||dij||, характеризующая собственный доход от реализации проектов, а также учитывающая доход от синергетического эффекта влияния проектов на другие.

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

(28)        

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

(29)        

На первом этапе решаем n задач оптимизации: определить xjiа=а{0;а1}, (xiiа=аxi), минимизирующие

       

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

       .

При xiа=а1 задача сводится к минимизации

(30)        

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

(31)        

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

Пусть Gi(zi,аpi) - значение целевой функции задачи (30)-(31) в оптимальном решении. Тогда на втором этапе будет решаться следующая задача:

(32)        

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

(33)        .

Согласно теореме 1, значение целевой функции задачи (32)-(33) Ф(z,P) в оптимальном решении, является оценкой снизу задачи (28).

Двойственная задача

Определить zi, максимизирующие Ф(z,аP) при ограничениях (29)

Теорема 8: Ф(z,аP) - вогнутая функция.

Следовательно, двойственная задача является задачей выпуклого программирования. Обозначим ij - изменение переменной zij. Предполагаем, что ij такое, что исходное оптимальное решение оценочной задачи остается оптимальным. Тогда величина Ф(z,аP) изменится на

       .

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

       

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

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

Была разработана программа на языке PHP 5.0. Для оценки времени работы алгоритма, сравним его с частичным методом перебора. Данный метод перебора заключается в следующем. Разделим все имеющиеся проекты на 2 типа: проекты без влияния (одноцелевые) и проекты с влиянием (многоцелевые). Для первой группы выберем оптимальное решение, решая задачу о ранце. Для второй группы используем перебор всех возможных комбинаций многоцелевых проектов. Для каждой комбинации включим в нее решения проектов первой группы, пересчитывая все решения с учетом влияния проектов.

Получили следующие результаты работы программы.

N=20 - количество проектов.

N1 - количество проектов с влиянием на другие.

T1- время работы алгоритма с частичным перебором.

T2 - время работы основного алгоритма.

N1	T1 сред./(сек)	T2 сред./(сек)
4	1,2	5
5	1,5	5,4
6	2,4	11,7
7	3,4	4
8	8,2	15,8
9	16,8	12,4
10	40,9	8,8
11	99,5	10,6
12	148,6	24,2
13	239,4	25,7
14	а	38,4
15	а	24,8
16	а	28,12
17	а	52,3
18	а	31,8

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

По оси x отложены значения N1.

По оси y отложены значения времени T.

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

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

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

       

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

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

Задана также величина инновационного фонда R.

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

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

       

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

       

       

Метод решения (первый алгоритм).

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

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

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

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

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

       

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

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

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

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

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

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

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

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

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

Обозначим Ri - множество интервалов, в которых может выполняться работа i, Psi - множество работ, которые могут выполняться в s-ом интервале. Заданы ограничения Qs на объем проектных работ в каждом интервале. Обозначим через xis - объем i-ой работы, выполняемый в s-ом интервале, cis - максимальный объем i-ой работы, который можно выполнить в s-ом интервале. Задача заключается в определении , , , так, чтобы

       ,

       ,        

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

       , ,        

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

       

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

Для решения задачи определим двудольный граф G(X,Y). Вершины iа∈аX соответствуют работам, а вершины sа∈аY соответствуют интервалам. Пропускные способности вершин iа∈аX равны объемам Wi соответствующих работ, а пропускные способности вершины sа∈аY равны объему работ, который можно будет выполнить в соответствующем интервале, то есть Qs.

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

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

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

               

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

               

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

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

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

Рис. 8.

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

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

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

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

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

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

Рис. 9.

Рис. 10.

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

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

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

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

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

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

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

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

Пусть в организации имеются m подразделений, располагающих мощностями ресурсов одного вида. Обозначим Qi объем работ, который может выполнить i-е подразделение, Wi - объем i-й работы, . Требуется распределить работы между подразделениями, так, чтобы загрузка подразделений (или их перегрузка) была максимально равномерной. Обозначим xijа=а1 если i-я работа выполняется подразделением j, xijа=а0 в противном случае. Тогда уровень загрузки (перегрузки) подразделения i можно оценить величиной

       .

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

       .

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

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

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

(34)        .

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

(35)        .        

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

(36)        , .

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

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

(37)        .        

при ограничениях (69) и (70):

(38)        , .        

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

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

Рис. 11.

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

Рис. 12.

Все ai также делим на 2 части uij и vij для каждой вершины нижнего уровня так, что

(39)        uijа+аvijа=аai, для всех i, j.        

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

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

       

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

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

       

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

Обозначим Sm(u) и Lm(v) оптимальные решения первой и второй задач при заданных u и v. Оценочная задача заключается в определении {uij} и {vij}, минимизирующих

(40)        F(u,v)=Sm(u) + Lm(v)        

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

uijа=аyi, vijа=аaiаЦаyi,

Во-вторых, решение первой задачи очевидно:

               

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

(41)                .

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

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

(42)        .

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

(43)        ,

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

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

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

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

       

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

(44)        

(45)        

(46)        ,

где uiа≥а0; i,аjаа=а1,а2,аЕа,аn;аiа≠аj.аУсловие (46) гарантирует получение гамильтонова контура.

Рассмотрим симметричную задачу коммивояжера, то есть lijа=аlji ∀ i,аj.

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

(47)        .

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

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

       .

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

       .

Обозначим L1(p) (L2(q)) значение целевой функции в оптимальном решении первой (второй) задачи.

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

(48)        L1 (P)а+аL2 (Q)а=аL(P,Q)

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

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

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

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

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

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

Пример 3. Рассмотрим граф, рис. 13.

Рис. 13.

Рис. 14.

Оценка снизу определяется любым i-деревом, и равна l(Ti)а=а9, . Разобьем граф на 2 (рис. 14). Имеем для первого графа l(T3)а=а9, а для второго l(T2)а=а9. Оценка снизу равна l(T3)а+аl(T2)а=а18, т.е. в два раза лучше. Более того, она является достижимой. Оптимальный маршрут - (1,2,6,5,4,3,1).

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

       .

Определение. Последовательность (i1,аi2,аЕа,аin) называется однопиковой, если

,

где , .

Теорема 12. юбая однопиковая последовательность определяет оптимальный маршрут, длина которого равна 2λmax.

Для получения оценок задач 1 и 2 определим λn, , , так, чтобы

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

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

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

.

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

.

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

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

       ,

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

Имеется n проектов - претендентов на участие в программе. Каждый проект характеризуется затратами Ck и показателями эффекта jki  вклад k-го проекта в i-й критерий. Обозначим xk = 1, если k-ый проект включен в программу xk = 0 в противном случае. Предполагая, что эффекты суммируются, получаем, что увеличение i-го критерия в результате реализации программы составит

       

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

       

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

(49)        .

Обозначим K(J) - комплексную оценку программы при оценках направлений

       

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

Частный случай. Рассмотрим ситуацию, когда для каждого направления i существует свое множество проектов Q, причем эти множества не пересекаются. В этом случае алгоритм решения задачи становится существенно проще.

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

        

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

       

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

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

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

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

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

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

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

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

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

Для получения нижних оценок разделим затраты сij на две части:

(50)        uijа+аvijа=асij.        

Получаем две оценочные задачи.

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

(51)                

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

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

(52)                

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

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

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

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

В силу теоремы 4 это задача выпуклого программирвоания.

Опишем основной шаг алгоритма решения двойственной задачи. Пусть при заданных u и v получены оптимальные решения первой и второй задачи {xk} , {yk}, , где S - число решений первой задачи, t - число решений второй задачи. Обозначим zij - изменение переменной uij, и соответственно (-zij) - изменение переменной vij. Предполагаем, что zij такое что, оптимальные решения первой и второй задачи остаются оптимальными. В первой задаче величина U(u) изменяется на

       .

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

       .

Суммарное изменение нижней оценки F(u,v) составит

       

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

       .        

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

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

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

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

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

Заключение

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

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

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. Буркова И.В., Косенков А.В., Харитонова Т.Б. Метод дихотомического программирования в задачах управления рыночной стоимостью объектов недвижимости. - Системы управления и информационные технологии, научно технический журнал, №1.1 (23), 2006. С. 123-126.
10. Буркова И.В., Толстых А.В., Уандыков Б.К. Задача оптимизации программ обеспечения безопасности. - Системы управления и информационные технологии научно технический журнал, №1 (18), 2005. С. 36-40.
11. Буркова И.В., Толстых А.В., Уандыков Б.К. Модели и методы оптимизации программ обеспечения безопасности. - Проблемы управления научно технический журнал, №1, 2005. С. 51-55. 
12. Баркалов С.А., Буркова И.В., Хатунцев А.В. Задачи формирования программы развития региона - Вестник Воронежского государственного технического университета. 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. БондарикаВ.Н., БурковааИ.В., КрюковаС.В. Задача оптимизации программ по стоимостиа // Динамика неоднородных систем. - 2010. - №53 (2) вып. 14 Труды ИСА РАН под ред. член-корр. РАН Попкова Ю.С. - С. 65-72.

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

19. Баркалов С.А., Бабкин В.Ф., Буркова И.В. Модели, методы и механизмы повышения эффективности учебного процесса М. 2001 (Препринт / Институт проблем управления им. В.А. Трапезникова РАН) - 88 с.
20. Бабкин В.Ф., Баркалов С.А., Буркова И.В., Портных В.А. Информационные технологии в управлении бизнес-процессами М.: Институт проблем управления им. В.А. Трапезникова РАН, 2001. - 64 с.
21. Баркалов П.С., Буркова И.В., Глаголев А.В., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН). - 64 с.
22. Баркалов С.А., Бакунец О.Н., Буркова И.В., Колпачев В.Н., Русман И.Б. Оптимизационные модели распределения инвестиций на предприятии по видам деятельности М.: 2002 (Научное издание / Институт проблем управления им. В.А. Трапезникова РАН). - 68 с.
23. Бурков В.Н., Буркова И.В. Метод дихотомического программирования в задачах дискретной оптимизации М.: 2003 (Научное издание / ЦЭМИ РАН). - 41 с.
24. Буркова И.В., Михин П.В., Попок М.В., Семенов П.И., Шевченко Л.В. Модели и методы оптимизации планов проектных работ. Научное издание / Институт проблем управления им. В.А. Трапезникова РАН - М. 2005. - 68 с.
25. Математические основы управления проектами: Учебн. пособие/С.А. Баркалов, И.В. Буркова, В.И. Воропаев и др. Под ред. В.Н. Буркова. - М.: Высшая шк., 2005. - 423 с.: ил.
26. Бурков В.Н., Буркова И.В., Горгидзе И.А., Джавахадзе Г.С., Хуродзе Р.А., Щепкин А.В. Задачи управления в социальных и экономических системах. М.: СИНТЕГ, 2005. Серия Управление организационными системами. - С. 51-111.
27. Буркова И.В., Курочка П.Н., Семенов П.И., Михин П.В., Котенко А.М., Половинкина А.И., Потапенко А.М. Оптимизационные модели и механизмы  в управлении строительными проектами (в 4-х томах). Краснодар, 2005. 973 c.
28. Баркалов С.А., Бурков В.Н., Буркова И.В., Глотов Т.И., Ерохин А.В., Курочка П.Н., МихинаП.В. Модели и методы управления проектами при реформировании и реструктуризации предприятий. Воронеж. Гос.арх.-строит. Ун-т. 2007. - 311 с.
29. Бурков В.Н., Бурджанидзе В.О., Буркова И.В., Горгидзе Д.А., Горгидзе И.А., Джавахадзе Г.С., Хомерики И.О., Хуцишвили С.А. Некоторые задачи управления корпоративными системами. Издательский дом Технический университет, 2007 (Серия Управление, вычислительная техника, информатизация). - 98 с.
30. Баркалов С.А., Буркова И.В., Курочка П.Н., Михин П.В. Модели и методы управления строительными проектами. М., ООО Уланов-пресс, 2007. - 440 с.
31. Буркова И.В. Основные задачи оптимизации управления строительными проектами. В кн. Оптимизационные модели и методы в управлении строительным производством [Текст]: монография / П.И. Семенов [и др.]; ГОУ ВПО ВГАСУ. - Воронеж: Научная книга, 2007. - 423 с., С. 11-50.
32. Бурков В.Н., Буркова И.В., Губко М.В., Динова Н.И., Еналеев А.К., Кондратьев В.В., Коргин Н.А., Новиков Д.А., Цветков А.В., Чхартишвили А.Г., Щепкин А.В. МЕХАНИЗМЫ УПРАВЛЕНИЯ: Мультифункциональное учебное пособие / Под ред. чл.-к. РАН Д.А. Новикова - М.: Ленанд, 2010. - 192 с.

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

33. Баркалов П.С., Буркова И.В., Колпачев В.Н. Модель распределения ресурсов при переменном их уровне на проекте Труды международной научной конференции Современные сложные системы управления, Воронеж, 2003 г. С. 204-206.
34. Буркова И.В., Колпачев В.Н., Лихотин Ю.П. Модель распределения накапливаемых ресурсов при управлении проектом Труды международной научной конференции Современные сложные системы управления, Воронеж, 2003 г. С. 207-209.
35. Баркалов П.С., Буркова И.В., Колпачев В.Н. Эвристические алгоритмы календарного планирования при управлении проектами Труды международной научной конференции Современные сложные системы управления, Воронеж, 2003 г. С. 220-224.
36. Бурков В.Н., Буркова И.В. Метод дихотомической оптимизации Материалы международной научно-технической конференции Системные проблемы качества, математического моделирования, информационных и электронных технологий, Радио и связь, 2003. С. 23-28.
37. Бурков В.Н., Буркова И.В., Попок М.В. Решение задачи о камнях методом дихотомического программирования - Материалы IV Международной конференции Современные сложные системы управления. Тверь, 2004.С. 142-146.
38. Бурков В.Н., Буркова И.В., Колпачев В.Н. Задачи дихотомической оптимизации - Вестник научно-технический журнал ВГАСУ, 2004, выпуск 2. С. 112-114.
39. Бурков В.Н., Буркова И.В., Попок М.В. Метод дихотомического программирования - Управление большими системами / Сборник трудов. Выпуск 9: Лаборатория активных систем. 30 лет. Общая редакция - Д.А. Новиков. - М.: ИПУ РАН, 2004. - С. 57-75.
40. Буркова И.В., Колпачев В.Н., Потапенко А.М. Геометрический метод составления расписания в управлении проектами. - Журнал Автоматика и телемеханика № 12, 2004г. C. 144-152.
41. Буркова И.В., ПоловинкинаА.И., Толстых А.В. Специфика управления организационными проектами и базовые механизмы. - Вестник Воронежского государственного университета. Научно-техн. журнал. Серия САПР и системы автоматизации производства. Выпуск 3.4 - Воронеж 2004г. C. 37-42.
42. Буркова И.В., Колпачев В.Н. Системная модель взаимодействия предприятия общественного питания с внешней средой. - Вестник Воронежского государственного университета. Научно-техн. журнал. Серия САПР и системы автоматизации производства.  Выпуск 3.4 - Воронеж 2004г. - C. 95-99.
43. Баркалов С.А, Буркова И.В., Половинкина А.И. Оптимизационная модель программы повышения региональной безопасности (статья). - Системы жизнеобеспечения и управления в чрезвычайных ситуациях: Ч.2: Межвуз. сб. науч. тр. - Воронеж: Воронеж. гос. техн. ун-т, 2004. 254 с. C. 107-117.
44. Буркова И.В., Половинкина А.И., Толстых А.В. Оптимизация программ обеспечения региональной безопасности . Сборник трудов международной конференции Современные сложные системы управления, том 1. - Тула, 2005.С. 73-85.
45. Буркова И.В., Михин П.В., Попок М.В. Задача о максимальном потоке. Сборник трудов международной конференции Современные сложные системы управления, том 2. - Тула, 2005.С. 80-90.
46. Бурков В.Н., Буркова И.В., Баранчиков В.В., Володин С.В. Решение задач дискретной оптимизации на основе метода сетевого программирования. - Системы управления эволюцией организации (CSOEТ2008): сборник трудов VI международной конференции / ИПУ РАН им. В.А. Трапезникова. - Воронеж: Научная книга, 2008 - С. 103-107.
47. Буркова И.В., Косенков К.В. Конкурсные механизмы в корпоративном управлении. - Журнал ИЗВЕСТИЯ Серия: строительство, Архитектура и реставрация. Выпуск 8 часть 2. Тула, 2005. С. 93-101.
48. Буркова И.В., Котенко А.М. Оптимизация последовательности выполнения проектов. - Журнал ИЗВЕСТИЯ Серия: строительство, Архитектура и реставрация. Выпуск 8 часть 2. Тула, 2005. С. 166-174.
49. Буркова И.В., Котенко А.М. Оптимизация программ по стоимости. - Журнал ИЗВЕСТИЯ Серия: строительство, Архитектура и реставрация. Выпуск 8 часть 2. Тула, 2005. С. 80-89.
50. Буркова И.В., Половинкина А.И., Семенов П.И. Задачи оптимизации программ развития по стоимости. - Известия Тульского государственного университета, 2005, выпуск 8. С. 120-127. 
51. Буркова И.В., Колпачев В.Н., Толстых А.В., Уандыков Б.К. Метод дихотомического программирования в задаче оптимизации программ по стоимости (статья). - Научный вестник ВГАСУ. Серия: Управление строительством. Выпуск №1 - Воронеж, 2005. - С. 39-41.
52. Аснина Н.Г., Буркова И.В., Котенко А.М Оптимизационная модель последовательности выполнения проектов. - Современные сложные системы управления: Сб. науч. тр. междунар. конф. Т. 1/Воронеж. гос. арх.-строит. ун-т. - Воронеж, 2005. С. 89-94.
53. Баркалов С.А., Буркова И.В., Семенов П.И., Юшин Г.Д. Модель оптимизации программ развития по стоимости. - Современные сложные системы управления: Сб. науч. тр. междунар. конф. Т. 1/Воронеж. гос. арх.-строит. ун-т. - Воронеж, 2005. - С. 94-99.
54. Агеев И.А., Буркова И.В., Семенов П.И. Стратегия развития корпорации с учетом возможностей совмещения различных бизнесов. Современные сложные системы управления Сборник научных трудов восьмой научной конф. Краснодар-Воронеж-Сочи 2005. С. 103-108.
55. Буркова И.В., Потапенко А.М., Половинкина А.И. Разработка стратегии реализации проекта с учетом риска. Современные сложные системы управления Сборник научных трудов восьмой научной конф. Краснодар-Воронеж-Сочи 2005. С. 119-125.
56. Бурков В.Н., Буркова И.В. Человеческий фактор в задачах управления социальными и экономическими системами. - Человеческий фактор в управлении / Под.ред Н.А.аАбрамовой, К.С.аГинсберга, Д.А.аНовикова. - М.: КомКнига, 2006 - 496 с. - С. 151-155.
57. Буркова И.В. Методы решения задач дискретной оптимизации. В кн. Модели и методы управления проектами в дорожном строительстве./ Баркалов С.А., Курочка П.Н., Полонвинкина А.И., Беляев Ю.А., Ерохин А.В., - М.: ООО Уланов-пресс, 2007. - 384 с. - С.51-60.
58. Буркова И.В. Методы сетевого и дихотомического программирования. В кн. Модели и методы управления проектами в дорожном строительстве./ Баркалов С.А., Курочка П.Н., Полонвинкина А.И., Беляев Ю.А., Ерохин А.В., М., ОООУланов-пресс, 2007. - 384 с.  С.60-71.
59. Буркова И.В., Власенко В.А., Мясищев Р.Ю. Оптимизация систем управления на основе задачи о максимальной циркуляции. Материалы Международной научной конференции Сложные системы управления и менеджмент качества CCSQMТ2007. 12-14 марта 2007 г. - Старооскольский технологический институт, Старый Оскол. С. 8-10.
60. Буркова И.В., Врублевская С.С., Толстикова И.В. Решение задачи выбора множества объектов методом сетевого программирования. Материалы Международной научной конференции Сложные системы управления и менеджмент качества CCSQMТ2007. 12-14 марта 2007 г. Старооскольский технологический институт, Старый Оскол. С. 11-13.
61. Буркова И.В., Сиренько С.В., Половинкина А.И. Метод дихотомического программирования при составлении плана закупок материалов. Материалы Международной научной конференции Сложные системы управления и менеджмент качества CCSQMТ2007. 12-14 марта 2007 г. Старооскольский технологический институт, Старый Оскол. С. 64-66.
62. Буркова И.В., Кашенков А.Р. О задачах оптимизации корпоративных бизнесов в случае совместного финансирования бизнесов. Теория активных систем  / Труды международной научно-практической конференции (14-15 ноября 2007 г., Москва, Россия). Общая редакция - В.Н.аБурков, Д.А.аНовиков. - М.: ИПУ РАН, 2007. - 300 с. - С. 226-230.
63. Буркова И.В., Новиков А.А., Романченко О.В. Алгоритм дихотомического программирования  в задачах выбора вариантов оптовых закупок. - Системы управления эволюцией организации Четвертая международная конф. (12-19 апреля 2007г. г. Санья, китайская Народная республика). - С. 167-172.
64. Баранчиков В.В., Буркова И.В., Ещенко Р.В., Урманов И.А. Определение первоочередных значимых объектов на основе сетевого  программирования. - Международная научно-практическая конференция 22-23  ноября  2007г. г. Старый Оскол. ТОМ 3. - С. 122-127
65. Баркалов С.А., Буркова И.В., Березнев П.И., Ефремов М.А. Определение оптимального варианта производства работ на основе анализа функции затрат. Международная научно-практическая конференция 22-23  ноября  2007г. Старый Оскол. ТОМ 3. - С. 127-135
66. Буркова И.В., Каратаева Т.В., Дудин А.М., Тютерев Д.А. Минимизация неопределенности при составлении расписания проекта. Международная научно-практическая конференция 22-23 ноября 2007г. Старый Оскол. ТОМ 3. - С. 139-145
67. Бурков В.Н., Буркова И.В. Метод сетевого программирования в задачах управления проектами. Труды международного симпозиума Управление проектами: власть, общество, бизнес. CD. Нижний Новгород, февраль 2007 года.
68. Буркова И.В. Метод сетевого программирования в задаче оптимизации корпоративных бизнесов. Доклад. Четвертая международная конференция по проблемам управления. (26-30 января 2009г. ИПУ РАН, Москва). CD.
69. Бурков В.Н., Буркова И.В. Метод сетевого программирования при решении задач управления проектами. Док. Четвертая международная конференция по проблемам управления. (26-30 января 2009г. ИПУ РАН, Москва). CD.
70. Бурков В.Н., Буркова И.В. Метод сетевого программирования в задачах управления проектами. Плен. док. VI Международная конференция Управление проектами в развитии общества, 21-22 мая 2009 года, Киев. С. 8-15.
71. Алферов В.И., Буркова И.В., Керусова В.А. Решение многоэкстремальных задач распределения ресурсов на основе метода дихотомического программирования. Труды 2-й Всероссийской науч.-тех. Конференции Управление в организационных системах, Воронеж, 18-21 мая 2009 г. - С. 127-131.
72. Буркова И.В. Владимир Николаевич Бурков - 70 активных лет. Теория активных систем / Труды международной научно-практической конференции (17-19 ноября 2009 г., Москва, Россия). Том I. Общая редакция - В.Н.аБурков, Д.А.аНовиков. - М.: ИПУ РАН, 2009. - С. 34-41.
73. Буркова И.В., Захарченко О.С., Руденко З.Г. Задача выбора оптимальной стратегии интегрирования компаний. Теория активных систем / Труды международной научно-практической конференции (17-19 ноября 2009 г., Москва, Россия). Том 2. Общая редакция - В.Н.аБурков, Д.А.аНовиков. - М.: ИПУ РАН, 2009. - С.25-26.
74. Бурков В.Н., Буркова И.В.Системы управления инновационным развитием регионов: проблемы и пути решения Управлiния проектами: стан та перспективи: Матерiали мижнародноi науково-практичноi конференцii. - Миколаiв: НУК, 2010. С. 46-50.
75. 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 февраля.
76. Бурков В.Н., Буркова И.В. Метод сетевого программирования в задаче оптимизации программ по стоимости - Труды четвертой международной конференции "Управление развитием крупномасштабных систем MLDS-2010 (4-5 октября 2010 г., Москва, Россия).
77. .аБурков В.Н., Буркова И.В., Крюков С.В. Разработка региональных программ на основе метода сетевого программирования. Материалы VII Международной научно-технической конференции Управление проектами: состояние и перспектива. Украина, Николаев,20-23 сентября 2011 г. - Николаев: НУК, 2011. - С. 58-65.
78. Буркова И.В., Кашенков А.Р. Метод сетевого программирования в задаче целочисленного линейного программирования. Труды международной научно-практической конференции Теория активных систем-2011 (14-16 ноября 2011 г., Москва, Россия). Том 1. Общая редакция - В.Н.аБурков, Д.А.аНовиков. - М.: ИПУ РАН, 2011. - С. 25-26.

   Авторефераты по всем темам  >>  Авторефераты по техническим специальностям