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

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

Пример 5.2.6. Рассмотрим граф взаимозависимостей на рис. 5.2.8.

2

3

		(3)				(5)
		1
		2
						(2)

(4)

(3)

5

1

(6)

4

7

Рис. 5.2.8

Таблица затрат приведена в табл. 5.2.24.

i	1	2	3	4	5
ci	4	3	2	5	3

3

4

Таблица 5.2.24

Если удалить вершину 1, то получаем паросочетание. Поэтому следует рассмотреть два варианта: вершина 1 входит в план первого периода или вершина 1 входит в план второго периода. Примем q1=2, q2=1, R1=12, R2=17.

Первый вариант

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

Таблица 5.2.25

Комплексный проект I (проекты 2 и 3)

Вариант	0		1	2	3
Затраты	0		2	3	5
Эффект	0		4	6	15
	121

К эффекту проекта 2 добавлен эффект b12 = 3, поскольку проект 1 включен в план первого периода.

Таблица 5.2.26

Комплексный проект II (проекты 4 и 5)

Вариант	0	1	2	3
Затраты	0	3	5	8
Эффект	0	5	7	18

Рассматриваем комплексные проекты I и II.

Таблица 5.2.27

3		8;18	10;22	11;24	-
2		5;7	7;11	8;13	10;22
1		3;5	5;9	6;11	8;20
0		0;0	2;4	3;6	5;15
II		0	1	2	3
	I

Оптимальное решение определяется клеткой (8;20), что соответствует включению в план первого периода проектов 1, 2, 3, 5. Имеем w1 = 22, w2 = 40,

Ф = 2 ∙ 22 + 1 ∙ 18 = 62.

Второй вариант

Таблица 5.2.28

Комплексный проект I (проекты 2 и 3)

Вариант	0	1	2
Затраты	0	2	5
Эффект	0	4	12

Таблица 5.2.29

Комплексный проект II (проекты 4 и 5)

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

Рассматриваем комплексные проекты I и II.

Таблица 5.2.30

2		5;12	8;13	10;19	-
1		2;4	5;5	7;11	10;18
0		0;0	3;1	5;7	8;14
I		0	1	2	3
	II
			122

1, .

Оптимальное решение определяется клеткой (10;19), что соответствует включению в план первого периода проектов 2, 3 и 4. Имеем w1 = 19, w2 = 40,

Ф = 2 ∙ 19 + 1 ∙ 21 = 59.

Оптимальному варианту соответствует включение в план первого периода проектов 1, 2, 3 и 5 с эффектом 62.

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

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

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

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

Имеютcя nпроектов. Каждый проект характеризуется эффектом aiот его реализации и временем τi его реализации. Если выполнить два проекта i и j, то возникает дополнительный (синергетический) эффект bij. Для описания взаимозависимости проектов определим граф взаимозависимостей G, вершины которого соответствуют проектам, а дуги отражают наличие дополнительного

эффекта при реализации обоих	проектов. Проекты выполняются
последовательно. Если

ti – момент окончания проекта i, tj – момент окончания проекта j,

то дополнительный эффект возникает в момент t=max (ti, tj). Чем позже реализован проект, тем больше упущенная выгода от его реализации.

Пусть π = (i1, i2, …,in) – некоторая последовательность реализации проектов. Тогда упущенную выгоду можно записать в виде

F(π) =

( ) +

( , )

max(

, ) ,

(5.3.1)

где =

, k = 1, .

=1

Если эффекта взаимозависимости нет (все bij=0), то получаем классическую задачу максимизации упущенной выгоды. Ее решение состоит в упорядочении проектов по убыванию величины:

qi = , i = (5.3.2)

Учет синергетического эффекта делает задачу существенно более

сложной.
Получение нижних оценок
Для получения нижних оценок представим
bij = uij+ vij, (i, j) G .	(5.3.3).
123

Имеет место неравенство

u t

+ v t

max (t

i

, t

).

(5.3.4)

ij i

ij j

j

Действительно,

u t

+ v t

max (t

i

; t

)

+

max (t

i

; t

) =

max (t

i

, t

).

ij i

ij j

j

j

j

Подставляя в (5.3.1), получаем

(π) =

(

+

( )

+

)

.

(5.3.5)

ik

,

Обозначим

b

(u, v) = a +

( , )

+

( , )

,

(5.3.6)

i

i

где U – множество дуг графа G.

Получаем оценочную задачу: определить последовательность π,

минимизирующую

(π) =

(u, v)

.

(5.3.7)

Ее решение известно, необходимо упорядочить проекты по убыванию:

	=	( , )	,	i = 1, .	(5.3.8)

Обозначим W(u, v) значение (5.3.7) в оптимальном решении задачи.

Теорема 5.3.1. W(u, v) является нижней оценкой для исходной задачи. Доказательство следует из неравенства (5.3.4).

Обобщенная двойственная задача (ОДЗ)

Определить u, v, максимизирующие W(u, v) при условиях (5.3.3).

Теорема 5.3.2. ОДЗ является задачей выпуклого программирования.

Доказательство. Пусть 1,

1

и 2, 2 – допустимые решения ОДЗ.

Возьмем их выпуклую линейную комбинацию u, v

= 1 +

1 − 2 ,

= 1 + 1 − v2, (i, j) .

ij

Очевидно,

что (u, v)

– допустимое решение ОДЗ. Представим bi(u, v) в

виде

bi(u, v) = α [

+

+ 1

+

− 1

] + (1 – α) [

+

+ 2 +

− 2 ] .

( , )

,

( , )

,

Заметим, что максимум суммы меньше или равен суммы максимумов.

Поэтому			, ≥ α			( 1, 1) + (1 – α)			( 2, 2).

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

124

Частный случай графа взаимозависимостей (паросочетание)

Пусть граф взаимозависимостей является паросочетанием (рис. 5.3.1).

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

Рис. 5.3.1

Определим значение двойственных переменных, решая систему

уравнений

Pi (u, v) =

+

=

+

= pj(u, v),

(i, j) .

Учитывая, что uij+ vij= bij , получаем

uij=

− +

,

+

vij =

− +

.

(5.3.9)

+

Пот этом, если uij>bij , то полагаем

uij=

bij , vij= 0.

Если uij< 0, то полагаем

uij= 0, vij=

bij.

Теорема 5.3.3. Значения

u, v,

определяемые (5.3.9), дают оптимальное

решений ОДЗ.

Доказательство. Если

pi(u, v) = pj(u, v),

(i, j) , то эти два проекта в

оптимальном решении находятся рядом. Пусть первым выполняется проект i,

а вторым – проект j .	Если уменьшить uij,, то проекты меняются местами и
оценка увеличивается.	Если uij>bij в решении (5.3.9), то, полагая uij= bij,

получаем, что pj(u, v)>pi(u, v) и в оптимальном решении проект j выполняется раньше проекта i . Если uij< 0 в решении (5.3.9), то, полагая uij= 0, мы получаем pi(u, v)>pj(u, v) и проект i выполняется раньше проекта j.

	Заметим, что если	0 <uij<bij , то проекты	i	и j выполняются рядом. В
этом	случае заменим	их одним проектом	с	параметрами ij	i j ,
aij ai	a j bij . Получим необходимые условия оптимальности.
		125

Пусть проекты k , i и j выполняются последовательно, причем

pi(u, v) = pj(u, v) . Рассматривая проекты

i и j как один сложный проект (i, j),

поменяем местами проекты kи

(i,

j). Если подпоследовательность k , i , j

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

(t

k

)bk (t k

i

)ai

(t k

i

j

)(a j bij )

(t

i

)ai (t

i

j

)(ai

bij ) (t i

j

r

)bk .

После несложных преобразований получаем

Pk

=

+ +

= pij .

(5.3.10)

+

Аналогично можно показать, что если два сложных проекта (i, j) и (k, s) расположены рядом (причем проект (i, j) первый в оптимальном решении должно выполняться условие

+ +		+ +
			.	(5.3.11)
+
		+

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

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

1 шаг. Определяем двойственные переменные u, v по формуле (5.3.9).

2 шаг. Все пары проектов, для которых 0 <uij<bij, превращаем в сложные проекты с параметрами = + + , = + .

3шаг. Упорядочиваем проекты по убыванию эффективностей piиpij.

4шаг. Определяем величину упущенной выгоды.

Пример 5.3.1. Имеются шесть проектов (рис.5.3.1). Данные о продолжительностях приведены в табл. 5.3.1.

Таблица 5.3.1

i	1	2	3	4	5			6
τi	2	3	4	2	3			3
pi	3	2	1	4	1			1
					13			23

1. Определяем двойственные переменные:

		2 ∙6 −3 ∙6 +2 ∙6			6	1						6	4
(1, 2): u12 =			=			= 1				,	v12 = 6 -		= 4		;
	5				5				5			5		5
	4 ∙ 8 −2 ∙ 4 + 4 ∙4					2
(3, 4): u34=				= 6				.
	6						3

Поскольку u34 > 4, то полагаем u34 = 4, v34 = 0,

	(5, 6): u56=	3 ∙ 7 −3 ∙ 4 + 9	= 3, v56 = 0.
		6

2.Поскольку u12 > 0, то образуем сложный проект с эффективностью p12 = 185 = 3,6

3.Упорядочиваем проекты, включая сложный проект по убыванию эффективностей (табл. 5.3.2).

126

Таблица 5.3.2

i	4	(1,2)	6			5			3
pi	4	3,6	2	1		2	1		2
				3			3

В сложном проекте проект 1 делается первым, поскольку p1>p2. Получаем оптимальное решение π = (4, 1, 2. 6, 5, 3). Упущенная выгода равна

F = 2 ∙ 8 + 4 ∙ 6 + 7 ∙ 12 + 10 ∙ 7 + 13 ∙ 7 + 17 ∙ 8 = 421.

Общий случай. Приближенный алгоритм

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

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

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

2шаг. Определяем ( 1, 1), ( 1, 1), оптимальную последовательность проектов π1 и оценку снизу упущенной выгоды w(u, v).

3шаг. Для полученного решения определяем реальную величину

упущенной выгоды F(π1). Если погрешность 1 = F((π1) – W(u, v) в пределах допустимой, алгоритм закончен. Определим ошибку приближения. Для этого

обозначим H( 1, 1) множество дуг (i ; i

) таких, что k<s и 1

или 1

больше

k

s

нуля. Ошибка приближения равна

( 1, 1) =

1

1

( 1

+ 1

) (

-

).

(5.3.12)

( , )

Для уменьшения ошибки применяем алгоритм локальной оптимизации.

Для этого выбираем пару (

,

) такую, что

k<s,

или

больше

( 1, 1)

нуля и

>

( 1, 1)

. Уменьшаем 1

(либо

) либо до 0,

либо до

выполнения равенства

=

. Затем берем следующую пару и т. д.

Пример 5.3.2. Рассмотрим граф взаимосвязей на рис. 5.3.2.

	1
	4	(3)
	(3)
	2	5
	6	3
	(4)	(5)
	3	4
	2
	Рис. 5.3.2	2
	127

Таблица продолжительностей приведена ниже.

Таблица 5.3.3

i	1	2	3	4	5
	3	2	1	2	4

Возьмем следующие начальные значения 1, 1.

Таблица 5.3.4

(i, j)	(1,2)	(1,3)	(1,4)	(1,5)
uij	2	2	2	2
vij	2	2	3	1

Вычисляем

b1 = 4 + 1 = 2 = 2 = 2 = 11, b2 = 6 + 2 = 8, b3 = 2 + 2 = 4, b4 = 5 + 3 = 8, b5 = 3 + 1 = 4.

Определяем эффективности:

p1 = 323; p2 = 4; p3 = 4; p4 = 4; p5 = 1.

Оптимальная последовательность: π1 = (2. 3, 4, 1, 5). Оценка упущенной выгоды:

W1 = 2 ∙ 8 + 3 ∙ 4 + 5 ∙ 8 + 8 ∙ 11 + 12 ∙ 4 = 204.

Упущенная выгода для решения π1:

F(π1) = 2∙ 6 + 3 ∙ 2 + 5 ∙ 5 + 8 ∙ 16 + 12 ∙ 6 = 243.

Ошибка равна 39 или примерно 16 %.

Применяем алгоритм локальной оптимизации.

Шаг 1. Берем пару (1, 5). Уменьшаем u15 до 0 соответственно v15 = 3. Легко проверить, что оптимальная очередность остается прежней.

Однако оценка увеличивается и станет равной 212. Погрешность уменьшилась до 31 или примерно 12 %.

	Шаг 2. Берем пару (1, 2). Из уравнения	6 + 12	=	8+ 12	=	8+(3− 12)
		2		3		3

определяем v12 = 45; u12 = 2 15.

Эффективность проектов 1 и 2 сравнялась и равна 3, 4. Оптимальная последовательность π2 = (3, 4, 2, 1, 5). Оценка увеличилась и стала равна

W1 = 1 ∙ 4 + 3 ∙ 8 + 5 ∙ 645 + 8 ∙ 1015 + 12 ∙ 6 = =215,6.

Оценка опять увеличилась до 215,6, а ошибка уменьшилась до 11 %. Заметим, что эффективность первого проекта стала равной 3,4. Далее

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

	4+ 12+ 13+ 14		=		6+ 12	=	2+ 13	=	5+ 14	= λ.
3				2			1		2
Вычисляем: 9 - 12 = 2 λ ,		12 = 9 - 2 λ,
				128

6 - 13 = λ ,	13 = 6 - λ,
10 - 14 = 2 λ,	14 =10 – 2 λ.

Подставляя в левое выражение, получаем:

4 + (9 – 2 λ) + (6 – λ) + (10 – 2 λ) = 3 λ или λ= 298 = 3 58 ,

12 = 1 34, 13 = 2 38, 14 = 2 34,

v12 = 1 14, v13 = 1 58, = 2 14.

Определим оценку снизу.

Имеем b1 = 10 78, b2 = 7 34 , 3 = 3 58, 4 = 7 14, 5 = 6.

Поскольку оптимальных решений оценочной задачи несколько, возьмем любые из них, например, π3 = (1, 2, 3, 4, 5).

Вычисляем: W = 3 ∙ 10 87 + 5 ∙ 7 34 + 6 ∙ 3 58 + 8 ∙ 7 14 + 12 ∙ 6 = 223 18.

Заметим, что решение π2 также является оптимальным решением оценочной задачи. Погрешность F(π1) - W = 19 87 или примерно 8 %.

Однако можно определить оптимальное решение оценочной задачи с меньшей упущенной выгодой. Возьмем, например,решение, в котором первым выполняется проект 1, а остальные выполняются в порядке убывания эффективностей: π4 = (1, 3, 4, 2, 5).

Вычисляем:

F(π4) = 3 ∙ 4 + 4 ∙ 6 + 6 ∙ 10 + 8 ∙ 9 + 12 ∙ 6 = 240.

	Погрешность составляет 11	5	или 7 %.
		8

Граф взаимозависимостей типа «куст»

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

Рассмотрим эту ситуацию в общем случае. Имеется один бизнесобразующий проект 1 и (n – 1) сопутствующих проектов. Примем, что продолжительности всех проектов одинаковы, то есть τ1 = 1, i = 1, .

Пусть проект 1 выполняется k-м по очереди. Тогда (k – 1) проект выполняется до него, а (n – k) после него.

Обозначим sij= j (ai+ kb1i) , j = 1, − 1 ; sij= j (ai + b1i) , j = + 1, ;

s1k= ai. .

129

Примем xij = 1, если проект i выполняется на j-м месте, xij = 0 в противном случае. Очевидны ограничения: xik = 1,

		= 1,	j = 1, , j			k,	(5.3.13)
=2
≠			= 1, i = 2,			.	(5.3.14)
Покажем, что
Sk (x)=		,			+	∙ .	(5.3.15)
					1
Определяет величину упущенной выгоды. Действительно,							если = 1 и

j<k, то упущенная выгода от проекта i составляет jai + kb1i, поскольку эффект

b появляется только в момент k. Если		= 1 и j>k,	то упущенная выгода
1i
составляет (ai+ b1i) j. Наконец, упущенная выгода от проекта 1 равна				а1∙ .
Таким образом, задача свелась	к	решению	n задач по	критерию

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

Пример 5.3.3. Рассмотрим граф взаимозависимостей (рис. 5.3.2).

1 шаг. Полагаем, что проект 1 выполняется первым. Матрица (sij) приведена табл. 5.3.5.

Таблица 5.3.5

	j	2	3	4	5
	i
	2	18	27	36	45
	3	12	18	24	30
	4	20	30	40	50
	5	12	18	24	30

В данном случае решение известно: проекты нужно выполнять в порядке убывания эффективностей (ai+ b1i), то есть оптимальная последовательность

π1 = (1, 4, 2, 3, 5).

Упущенная выгода s1 = 4 + 20 + 27 + 24 + 30 = 105.

2 шаг. Проект 1 выполняется вторым (табл. 5.3.6).

Таблица 5.3.6

	j	1	3	4	5
i
2		12	27	36	45
3		10	18	24	30
4		15	30	40	50
5		9	18	24	30

Получаем решение задачи x21 = 1, x43 = 1, x34 = 1, x55 = 1, S2 = 12 + 30 +

24 + 30 + 4 ∙ 2 = 104.

3 шаг. Проект 1 выполняется третьим (табл. 5.3.7).

130