Учебное пособие 800519

2 вариант. Найдется ближайший интервал, такой, что объем работ, который должен быть выполнен в s-м интервале, превышает Qs (таким образом, ресурсов не хватит для выполнения всех работ, которые должны быть

завершены в интервалах 1,S ). В этом случае определяем

				V(s)
	1	max	1;
				H(s)		,

где V(s) - объем работ, которые должны быть выполнены в интервалах 1,S ,

s

H(s) Qp , и применяем правило А.

p 1

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

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

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

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

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

	Fi	1			wi xij .	(4.2.1)
		Qi
					j
	Задача заключается в распределении работ по подразделениям так, чтобы
	минимизировать
	max	1			wi xij .	(4.2.2)
	i		Qi j

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

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

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

91

Tj ai xij .					(4.2.3)
i
Максимальный вес группы
T max	ai xij min .				(4.2.4)
j		i
Поскольку каждый камень должен быть помещен только в одну группу,
имеем ограничения:
xij 1,
		i 1,n .			(4.2.5)
j

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

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

размещенных в ящики вместимостью Т камней:
Ф ai xij	max			(4.2.6)
i ,j
при ограничениях (4.2.5) и
ai xij T,
	j 1,m .			(4.2.7)
i

Связь между задачами (4.2.4)-(4.2.5) и (4.2.5)-(4.2.7) очевидна. Минимальное Т, при котором в оптимальном решении задачи 4.2.2 размещены все камни, определяет оптимальное решение задачи 4.2.1.

 

j

X11

X12

j	j	j

X21 X22

Рис. 4.2.1

 

j

X31 X32

Сначала получим сетевое представление задачи 4.2.2. Оно представлено на рис. 4.2.1 для случая n=3, m=2. Поскольку структура сетевого представления имеет вид сети, а не дерева, то для построения оценочной задачи разделяем каждую вершину нижнего уровня на две вершины. Преобразованная структура

приведена на рис. 4.2.2. Все так же делим на 2 части uij и	vij для каждой
вершины нижнего уровня так, что
uij vij ai для всех i, j.	(4.2.8)
92

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

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

uij xij i ,j

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

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

vij xij i ,j

(4.2.9)

(4.2.10)

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

Обозначим Sm(u) и Lm(v) оптимальные решения 4.2.1 и 4.2.2 задач при
заданных u и v. Оценочная задача заключается в определении						uij и vij ,
минимизирующих
	F(u,v)=Sm(u) + Lm(v)					(4.2.11)
при ограничении (4.2.8).
Заметим, во-первых, что в оптимальных решениях этих задач можно
принять
uij yi
	, vij ai yi ,	j 1,m			.

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

j	j	j	j	j

X11 X12 X21 X22 X31 X32		X11	X12 X21 X22 X31 X32
Рис. 4.2.3
Sm (x) y i			(4.2.12)
	i
В-третьих, решение m задач 4.2.4 при заданных {уi} сводится к решению
одной задачи о ранце: определить xi 0,1, максимизирующие
xi (ai	y i )		(4.2.13)
i
при ограничении
xi ai T .			(4.2.14)
i
Решим задачу (4.2.13) и (4.2.14) при yi 0,			i 1,n .
	93

Обозначим через Q {Qj }множество векторов х, удовлетворяющих

(4.2.14) и упорядоченных по убыванию: M j ai ,				Yj		yi , а
	i Qj					i Qj
	Z max(Mj Yj ) .							(4.2.15)
	j
Заметим, что	при заданных {yi } Z определяет оптимальное решение
каждой из m вторых задач. Оценка (4.2.11) при этом равна
	F(y) mZ y i ,							(4.2.16)
	i
где y i 0 удовлетворяют неравенствам
	yi Z Mj ,
		j 1,N .						(4.2.17)
	i Qj
где N − число различных решений неравенства (4.2.14). Таким образом,
								и 0 Z Mj ,
оценочная задача	свелась к определению	0 y i		ai		, i 1,n

максимизирующих (4.2.16) при ограничениях (4.2.17). Это обычная задача линейного программирования.

Фиксируем величину Z и определяем максимальный номер k такой, что

Z M k . Рассматриваем следующую

задачу линейного

программирования:

определить 0 y i ai ,

i 1,n , минимизирующие

Y(Z) yi

(4.2.18)

i

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

(4.2.17), где

j 1,k . Двойственная

задача имеет вид:

определить uj 0 ,

j 1,k , максимизирующие

k

(Mj

Z)uj

j 1

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

uj

1,

i 1,n ,

j Ri

где Ri — множество j, содержащих камень i.

Обозначим через Y0(Z) минимальное значение Y(Z). Оценочная задача сводится к минимизации функции одного переменного

Y0 (Z) mZ min .

(4.2.19)

Берем T0 A / m , где A ai , и решаем задачу 4.2.2. Если Фmax (T0 ) A ,

i

то увеличиваем Т0 до T1 так, чтобы появился хотя бы один новый вектор Qj. Если Фmax (T1 ) A , то продолжаем увеличение T до тех пор, пока не получим

величину Tk такую, что Фmax (Tk ) A . Величина Tk является нижней оценкой

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

94

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

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

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

4.В чем заключается «задача о камнях»?

5.Сформулируйте формальную постановку «задачи о камнях»?

ГЛАВА 5. МЕТОДЫ ФОРМИРОВАНИЯ ПОРТФЕЛЕЙ ВЗАИМОЗАВИСИМЫХ ПРОЕКТОВ И КАЛЕНДАРНЫХ ПЛАНОВ ИХ РЕАЛИЗАЦИИ

5.1. Формирование портфеля взаимозависимых проектов

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

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

Имеются n проектов.

Обозначим ai эффект от проекта

i,

aij дополнительный эффект при

включении в портфель обоих проектов i

и

j,

сi

– затраты на проект i, R –

средства на реализацию проектов. Введем переменные

xi= 1, если проект i

включен в портфель, xi = 0 в противном случае,

i = 1, .

Предполагается, что ai,

aij, ci – целые положительные числа для всех

i, j,

R – целое положительное

число.

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

А(x) =

+

(5.1.1)

,

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

≤ R.

(5.1.2)

Рассмотрим теоретико-графовую интерпретацию задачи. Определим n – вершинный граф G взаимосвязей проектов с эффектами ребер аij и весами (затратами) вершин сi. Задача заключается в определении подграфа, имеющего максимальную сумму эффектов ребер и вершин при ограничении R на суммарный вес вершин. Пример такого графа приведен на рис. 5.1.1.

Верхние числа в вершинах соответствуют номерам проектов, нижние – эффектам числа у ребер – эффектам aij.

95

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

Удалим из графа взаимосвязей минимальное число вершин так, чтобы получить многокомпонентный граф с небольшим числом вершин в каждой компоненте. Существует эффективный эвристический алгоритм решения этой задачи: последовательно удаляем вершины с максимальной степенью, следя за тем, чтобы не образовались компоненты с ―очень малым‖ числом вершин (например, с одной вершиной). Это требование обусловлено тем, что при наличии таких компонент увеличивается как число удаляемых вершин, так и число компонент. Так, если в графе (рис. 5.1.1) удалить вершину 11 с максимальной степенью, а затем вершину 10, то получим трехкомпонентный граф, у которого каждая компонента состоит из трех вершин. Каждую компоненту графа будем называть комплексным проектом.

1	2	2
3		4
	3	5
4
				4
3	6	1	2	6
					1
8		2
	9	12		2	5
					5
					6
		1	5	6
		9
				6
	3	7
7		4	9
7			9
	3	5

8

8

Рис. 5.1.1

96

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

1 шаг. Для каждой компоненты графа рассматриваем все возможные варианты вхождения в портфель проектов. Таких вариантов 2q , где q– число вершин компоненты. В результате получаем таблицу ―затраты – эффект‖ для каждой компоненты.

2 шаг. Рассматриваем все возможные варианты вхождения в портфель удаленных вершин (таких вариантов 2р , где p – число удаленных вершин). Для каждого варианта корректируем таблицы ―затраты – эффект‖, добавляя эффект от проектов, вошедших в портфель. Упорядочиваем варианты таблиц ―затраты

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

3 шаг. Сравнивая все варианты вхождения в портфель удаленных вершин, определяем оптимальный вариант.

4 шаг. Для оптимального варианта находим решение задачи (перечень проектов, входящих в портфель) методом обратного хода.

Пример 5.1.1. Рассмотрим граф рис. 5.1.1. Затраты проектов приведены в табл. 5.1.1.

Таблица 5.1.1

	i		1		2	3	4	5	6	7	8	9	10		11
	сi		2		3	5	6	4	7	3	2	8	10		7
Примем R=20.				После			удаления			вершин				10		и 11	получаем
трехкомпонентный граф.
1 шаг. Рассматриваем					компоненту,					состоящую				из		вершин	1, 2, 3

(комплексный проект 1). Возможные варианты вхождения в портфель соответствующих проектов приведены в табл. 5.1.2.

Таблица 5.1.2

Вариант	0	1	2	3	4	5	6	7
Затраты	0	2	3	5	5	7	8	10
Эффект	0	3	4	8	9	15	15	24

Рассматриваем компоненту, состоящую из вершин 4, 5, 6 (комплексный проект 2). Возможные варианты приведены в табл. 5.1.3.

Таблица 5.1.3

Вариант	0	1	2	3	4	5	6	7
Затраты	0	4	6	7	10	11	13	17
Эффект	0	5	6	6	12	17	14	26

Рассматриваем компоненту, состоящую из вершин 7, 8, 9 (комплексный проект 3). Возможные варианты представлены в табл. 5.1.4.

97

Таблица 5.1.4

Вариант	0	1	2	3	4	5	6	7
Затраты	0	2	3	5	8	10	11	13
Эффект	0	8	7	18	9	22	20	36

2 шаг. Рассматриваем все варианты вхождения в портфель проектов 10

и11. Таких вариантов 4.

1вариант. Ни один проект не входит в портфель. Удаляем из таблиц все доминируемые варианты. Получаем таблицы затраты – эффект для комплексных проектов 1, 2, 3.

Таблица 5.1.5

Комплексный проект 1

Вариант	0	1	2	3	4	5
Затраты	0	2	3	5	7	10
Эффект	0	3	4	9	15	24

Таблица 5.1.6

Комплексный проект 2

Вариант	0	1	2	3	4	5
Затраты	0	4	6	10	11	17
Эффект	0	5	6	12	17	26

Таблица 5.1.7

Комплексный проект 3

Вариант	0	1	2	3	4
Затраты	0	2	5	10	13
Эффект	0	8	18	22	36

Решаем задачу методом дихотомического программирования. Рассматриваем комплексные проекты 1 и 2. Решение приведено табл. 5.1.8.

Таблица 5.1.8

	5		17;26*	19;29*	20;30*	-	-	-
	4		11;17*	13;20*	14;21*	16;26*	18;32	-
	3		10;12*	12;15*	13;16*	15;21*	17;27*	20;36
	2		6;6*	8;9*	9;10*	11;15*	13;21*	16;30
	1		4;5	6;8*	7;9*	9;14*	11;20*	14;29
	0		0;0	2;3	3;4	5;9	7;15	10;24
2			0	1	2	3	4	5
		1
					98

Результаты сведены в табл. 5.1.9.

Таблица 5.1.9

Комплексный проект 4

Вариант	0	1	2	3	4	5	6	7	8	9	16
Затраты	0	2	3	4	5	7	10	14	16	18	20
Эффект	0	3	4	5	9	15	24	29	30	32	36

Рассматриваем комплексные проекты 3 и 4. Решение приведено в табл. 5.1.10.

Таблица 5.1.10

	4			13;36	15;39	16;40			17;41				18;45					20;51				-					-				-	-	-
	3			10;22	12;25	13;26			14;27				15;31					17;37				20;46					-				-	-	-
	2			5;18	7;21	8;22			9;23				10;27					12;33				15;42					19;47				-	-	-
	1			2;8	4;11	5;12			6;13				7;17					9;23				13;32					16;37				18;38	20;40	-
	0			0;0	2;3	3;4			4;5				5;9					7;15				10;24					14;29				16;30	18;32	20;36
	3			0	1	2			3				4					5				6					7				8	9	10
		4
	Максимальный эффект F(x10 = 0; x11 = 0) = 51.
2			вариант. В			портфель					входит							проект							10. Корректируем								таблицы
―затраты – эффект‖. Заметим, что остаток ресурса равен R – C10 =10.
																																Таблица 5.1.11
								Комплексный проект 1
								Вариант					0			1		2	3				4				5
								Затраты					0			2		3	5				7				8
								Эффект					0			3		9	14				21				26
																																Таблица 5.1.12
								Комплексный проект 2
							Вариант				0			1		2		3		4					5			6
							Затраты				0			4		6		7		10					11			17
							Эффект				0			5		8		11		14					22			33

Таблица остается прежней, поскольку проект 10 не влияет на проекты 7, 8, 9. Таблица 5.1.13

Комплексный проект 3

Вариант	0		1	2	3	4
Затраты	0		2	5	10	13
Эффект	0		8	18	22	36
		99

Применяем метод дихотомического программирования. Рассматриваем комплексные проекты 1 и 2. Решение приведено в табл. 5.1.14.

Таблица 5.1.14

4		10;14*	-	-	-	-	-
3		7;11*	9;14*	10;20*	-	-	-
2		6;8*	8;4*	9;17*	-	-	-
1		4;5*	6;8*	7;14*	9;19*	-	-
0		0;0	2;3	3;9	5;14	7;21	8;26
2		0	1	2	3	4	-
	1

Результаты сведены в табл. 5.1.15

Таблица 5.1.15

Комплексный проект 4

Вариант	0	1	2	3	4	5
Затраты	0	2	3	5	7	8
Эффект	0	3	9	14	21	26

Рассматриваем комплексные проекты 3 и 4. Решение приведено в табл. 5.1.16.

Таблица 5.1.16

3		10;22	-	-	-	-	-
2		5;18	7;21	8;27	10;32	-	-
1		2;8	4;11	5;17	7;22	9;29	10;34
0		0;0	2;3	3;9	5;14	7;21	8;26
3		0	1	2	3	4	5
	4

Максимальный эффект F(x10 = 1; x11 = 0) = 34 + 2 = 36.

3 вариант. В портфель входит проект 11.

Остаток ресурсов равен R–c11= 13. Корректируем таблицы ―затраты – эффект‖.

Таблица 5.1.17

Комплексный проект 1

Вариант	0		1	2	3	4
Затраты	0		2	3	5	10
Эффект	0		3	4	17	24
		100