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

Оптимальное решение определяется клеткой (16;24) либо клеткой (17;24). Само решение определяем методом ―обратного хода‖. Клетке (16;24) соответствует вариант 3 табл. 5.2.6 и вариант 2 табл. 5.2.4. Варианту 3 табл. 5.2.6 соответствует включение в план первого периода второго варианта комплексного проекта 7, то есть включение проекта 2. Варианту 2 табл. 5.2.4 соответствует включение в план первого периода проектов 5 и 6. Таким образом, проекты 2, 5 и 6 выполняются в первом периоде, а проекты 1, 3 и 4 во втором.

Общий случай многих периодов

Пусть число периодов Т2. Для получения верхних оценок рассмотрим (Т – 1) задач следующего вида:

максимизировать

						Vk (x) =							+		,						(5.2.5)
при ограничении
												≤ R .									(5.2.6)
															k
Обозначим Wk						(k = 1, Т − 1) величину в оптимальном решении задачи
(5.2.5), (5.2.6).
Теорема 5.2.1. Величина
							W =			(				-				)	,		(5.2.7)
									=							−
где w = 0, w =					+	дает верхнюю оценку для исходной задачи.
0	T					,
Доказательство. Запишем (5.2.7) в следующем виде:
						W =		(		-				)			,			= 0.	(5.2.8)
							=			−								+
Для произвольного решения обозначим QK множество проектов,
выполняемых в периодах от 1 до К включительно.
						V(QK) =		+							( , ) ( ) ,

где U(Qk) – множество дуг соответствующего подграфа. Очевидно, что V(Qk ) ≤ Wk для любого Qk , k = 1,T. Это доказывает теорему.

Таким образом, для получения верхней оценки требуется решить (Т-1)

задачу (5.2.5), (5.2.6).

Обозначим Tk множество проектов, полученных в результате решения

задачи (5.2.6), (5.2.7), k = 1, Т-1.
Теорема 5.2.2. Если имеет место
Т1 Т2 ТТ-1 ,	(5.2.9)
то совокупность Tk, k = 1, Т − 1 определяет оптимальное решение задачи.

Если граф взаимодействия является паросочетанием, то для решения задач (5.2.5), (5.2.6) можно применить метод дихотомического программирования.

Пример 5.2.2. Пусть Т =3, R1=15, R2=30, R3= 44, n=8, q1=2, q2=1, q3=0,5.

Данные о проектах приведены на рис. 5.2.4.

111

1	8
3	2
(4)	(3)
2	7
5	9

3	6
7	4

(8)		(2)
	4	5
	2	6

Рис. 5.2.4

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

Таблица 5.2.8

i	1	2	3	4	5	6	7	8
ci	3	7	4	6	5	2	9	8

Формируем 4-комплексный проект.

Таблица 5.2.9

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

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

Таблица 5.2.10

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

Вариант	0	1	2
Затраты	0	4	10
Эффект	0	7	17

Таблица 5.2.11

Комплексный проект III (проекты 5, 6)

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

Таблица 5.2.12

Комплексный проект IV (проекты 7, 8)

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

1 шаг. Рассматриваем комплексные проекты I и II. Решение приведено в табл. 5.2.13.

Таблица 5.2.13

2		10;17	13;20	17;22	20;29
1		4;7	7;10	11;12*	14;19*
		0;0	3;3	7;5*	10;12*
II		0	1	2	3
	I

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

Таблица 5.2.14

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

Вариант	0	1	2	3	4	5	6	7
Затраты	0	3	4	7	10	13	17	20
Эффект	0	3	7	10	17	20	22	29

2 шаг. Рассматриваем комплексные проекты III и IV. Решение приведено в табл. 5.2.15.

Таблица 5.2.15

	3	7;12	15;14*	16;21	24;26
	2	5;6	13;8*	14;15	22;20*
	1	2;4	10;6*	11;13*	19;18*
	0	0;0	8;2*	9;9*	17;14*
	III	0	1	2	3
	IV

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

Таблица 5.2.16

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

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

113

Рассматриваем комплексные проекты V и VI. Решение приведено в табл. 5.2.17.

Таблица 5.2.17

7

24;26

27;29

28;33

-

-

-

-

-

6

16;21

19;24

20;28

23;31

26;38

29;41

-

-

5

14;15

17;18

18;22

21;25

24;32

27;35

-

-

4

11;13

14;16

15;20

18;23

21;30

24;33

28;35

-

3

7;12

10;15

11;19

14;22

17;29

10;32

24;34*

27;41

2

5;6

8;9

9;13

12;16

15;23

18;26

22;28

25;35

1

2;4

5;7

6;11

9;14

12;21

15;24

19;26

22;33

0

0;0

3;3

4;7

7;10

10;17

13;20

17;22

20;29

VI

0

1

2

3

4

5

6

7

V

Определяем оптимальные решения при R1 = 15

и

R2 = 30. Имеем:

оптимальное решение при R1 = 15 определяется клеткой (15; 24). Применяя

метод обратного хода,

получаем, что клетке (15; 24) соответствует вариант 5

комплексного проекта V и вариант 1 комплексного проекта VI. Варианту 5

комплексного проекта V соответствует вариант

1 комплексного проекта I и

вариант 2 комплексного проекта II, то есть выполнение в первом периоде

проектов 1, 3

и 4. Варианту 1 комплексного проекта VI соответствует вариант

0 комплексного проекта IV

и вариант 1

комплексного проекта III, то есть

выполнение в первом периоде проекта 6. Имеем Т1= (1, 3, 4, 6). Получим оптимальное решение при R2 = 30. Оно определяется двумя клетками: (29; 41) и

(27; 41).

Рассмотрим клетку (29;41). Ей соответствует вариант 5 комплексного проекта V и вариант 6 комплексного проекта VI. Варианту 5 комплексного проекта V соответствует включение в план первых двух периодов проектов 1, 3 и 4, а варианту 6 комплексного проекта VI соответствует включение в план двух периодов проектов 5, 6 и 7. Имеем Т1= (1, 3, 4, 6), Т2 = (1, 3, 4, 5, 6, 7). Поскольку Т1 Т2, полученное решение является оптимальным.

Имеем w1 = 24,w2 = 41, W = 2 ∙ 24 + 1∙ 17 + 0,5 ∙ 14 = 72. Рассмотрим клетку (27; 41). Ей соответствует вариант 7 комплексного проекта V, вариант 3 комплексного проекта VI. Варианту 7 комплексного проекта V соответствует включение в план первых двух периодов проектов 1, 2, 3 и 4. Варианту 3 комплексного проекта VI соответствует вариант 3 комплексного проекта III и вариант 0 комплексного проекта 4, то есть включение в план первых двух периодов проектов 5, 6. Имеем T1 = (1, 3. 4, 6), T = (1, 2, 3, 4, 5, 6). Поскольку Т1 Т2, то полученное решение также является оптимальным.

114

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

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

Пример 5.2.3. Граф взаимозависимостей приведен на рис. 5.2.5.

1

4

(5)

4

7

(7)

2

6

3

3

Рис. 5.2.5

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

Таблица 5.2.18

i	1	2	3	4
ci	2	6	3	7

Примем R1 = 6, R2 = 10, R3 = 18. Имеем два комплексных проекта.

Таблица 5.2.19

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

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

Таблица 5.2.20

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

Вариант	0	1	2	3
Затраты	0	3	7	10
Эффект	0	3	7	17

Рассматриваем комплексные проекты I и II. Решение приведено в табл. 5.2.21. Таблица 5.2.21

3		10;17	12;21	16;23	18;32
2		7;7	9;11	13;13	15;22
1		3;3	5;7	9;9	11;18
0		0;0	2;4	6;6	8;15
II		0	1	2	3
	I
			115

Оптимально решение при R1 = 6 определяется клеткой (5;7), что
соответствует включению в план первого периода проектов 1 и 3, Т1= (1;3).
Оптимальное решение при R2 = 10 определяется клеткой	(10;17), что
соответствует включению в план первых двух периодов проектов	3 и 4, то есть
Т2= (3, 4) . Примем q1 = 2, q2 = 1, q3 = 0,5. Имеем w1 = 7, w2 = 17. Оценка сверху

равна W = q1 ∙ w1 + q2 (w2 - w1) + q3(w3 - w2) = 31,5.

Применим метод ветвей и границ. Для ветвления выберем проект 1. Оценка первого подмножества (x11 = 1). Поскольку проект 1 является решением первой задачи, то он должен входить и в решение второй. Поэтому вариант 0 комплексного проекта 1 исключаем. В этом случае оптимальный вариант определяется клеткой (8;15), что соответствует включению в план двух

периодов проектов 1 и 2.	Имеем w1 = 7, w2 = 15. Оценка сверху равна 2 ∙ 7 +
1 ∙ (15 – 7) + 0,5 (32 –	15) = 30,5. Оценка второго подмножества (x11 = 0).

Поскольку проект 1 не входит в план первого периода, то варианты 1 и 3 комплексного проекта I исключаем при R1 = 6. Оптимальный вариант определяется клеткой (6; 6), что соответствует включению в план первого периода проекта 2 (Т1= 2). Для плана двух периодов ранее было получено решение Т2= (3; 4). Имеем w1 = 6, w2 = 17. Оценка сверху равна 2 ∙ 6 = 1 ∙ (17

– 6) + 0,5 (32 – 17) = 30,5. Выбираем второе подмножество. Для ветвления выбираем проект 2. Оценка первого подмножества (x21 = 1). Имеем при R1 = 6

Т1 = (2), w1 = 6.

Рассматриваем R2 = 10. У первого комплексного плана исключаем варианты 0 и 1. Оптимальное решение определяется клеткой (8; 15), что соответствует включению в план первых двух периодов проектов 1 и 2, Т2= (1,2). Поскольку Т1 Т2, то это решение оптимально в подмножестве

x11 = 0, x21 = 1. Имеем w1 = 6, w2 = 15. Оценка равна 2 ∙ 6 + 1 ∙ (15 – 6) + 0,5 (32

– 15) = 29,5. Оценка второго подмножества (x21 = 0). Имеем T1 = (3), Т2 = (3, 4), w1 = 3, w2 = 17, оценка равна 2 ∙ 3 + 1 ∙ 14 +0,5 ∙18 = 29.

Теперь выбираем подмножество x11 = 1 с оценкой 30,5. Для ветвления выбираем проект 3. Оценка первого подмножества (x31 = 1). Имеем при R1 = 6 Т1 = (1; 3), w1 = 7. Имеем при R2 = 10 Т2 = (1; 3), w2 = 7, поскольку при включении в план проектов 1 и 3 больше ни одного проекта нельзя включить в план двух периодов. Оценка равна 2 ∙ 7 + 0,5 ∙ 25 = 26,5. Оценка второго подмножества (x31 = 0). Имеем при R1 = 6, Т1 = (1), w1 = 4. Имеем при R2 = 10,

Т2 = (1; 4), w2 = 11. Оценка равна 2 ∙ 4 + 1 ∙ (11 – 4) + 0,5 ∙ 21 = 26,5.

Теперь наилучшую оценку имеет подмножество x11 = 0, x21 = 1, которое и определяет оптимальное решение Т1 = (2), Т2 = (1; 2). Эффект равен 29,5. Дерево ветвлений приведено на рис. 5.2.6.

116

		31,5
	X11=1	X11=0
	30,5		30,5
X31=1	X31=0	X21=1	X22=0
26,5	26,5	29,5	29

Рис. 5.2.6

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

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

bij= uij + vij,,			(i, j)		U	(5.2.10)
и определим для всех (i, j) U
di (u; v) = ai + uij,						(5.2.11)
dj (u; v) = aj + vij .
Рассмотрим задачу о ранце:
максимизировать
(u, v) x				i		(5.2.12)
при ограничении
		≤ R .				(5.2.13)
				T
Как было показано выше, решение			этой		задачи	дает оптимальные

решения при всех RK, k = 1, Т . Обозначим Wk(u, v) значение (5.2.12) в

оптимальном решении задачи (5.2.12), (5.2.13) при					R = Rk.	По аналогии с
теоремой 5.2.1 имеет место
Теорема 5.2.3. Величина
W(u, v) =			(w (u, v) – w	k-1	(u, v) ) ,	(5.2.14)
	=		k
где w0 (u, v) = 0, wт(u, v) = ( , )		дает оценку сверху для исходной задачи.

Обобщенная двойственная задача: определить u, v , удовлетворяющие (5.2.10) и минимизирующие (5.2.14). Для применения метода ветвей и границ выберем значения uijи vij исходя из следующих условий:

+ =

uij +vij= bij,

Решая эту систему, получаем

				−		+
uij=									,
				+
						117

+			,
(i,j)				U.
				−		+
vij=									.	(5.2.15)
				+

При этом, если uijbij, то принимаем uij=bij, vij= 0, а если uij< 0, то

принимаем uij= 0, vij= bij.

Пример 5.2.4. Рассмотрим задачу из примера 5.2.2 и решим ее, получая оценки методом сетевого программирования.

1 шаг. Определяем diи dj согласно (5.2.11), (i, j) U.

Таблица 5.2.22

i	1	2	3			4			5			6	7	8
di	3,6	8,4	7			10			8			4	9	5
ci	3	7	4			6			5			2	9	8
ri	1,2	1,2	1	3		1	2		1	3		2	1	5
				4			3			5
														8

где ri = , i =1 , n.

2 шаг. Решаем задачу о ранце: максимизировать

3,6 x1 + 8,4 x2 + 7 x3 + 10 x4 + 8 x5 + 4 x6 + 9 x7 + 5 x8

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

3 x1 + 7 x2 + 4 x3 + 6 x4 + 5 x5 +2 x6 + 9 x7 + 8 x8 30.

Мы не будем подробно рассматривать решение этой задачи. Приведем сразу результаты.

При R1 = 15 оптимальное решение

x3 = 1, x4 = 1, x5 = 1,

то есть в план первого периода включаются проекты Т1= (3, 4, 5), w1 = 25. При R2 = 30 оптимальное решение

	x1= 1, x3 = 1, x4 = 1, x5 = 1, x6	= 1, x7 = 1, w2 = 41,6,
то есть	Т2= (1, 3, 4, 5, 6,	7).

Поскольку Т1 Т2, то полученное решение является допустимым для исходной задачи. Однако, поскольку di(u,v) = 3,6 >ai = 3, то это решение дает оценку сверху W = 2 ∙ 25 + 1 ∙ 16,6 + 0,5 ∙ 13,4 =74,3. Для данного решения определим суммарный эффект. Он равен Q = 2 ∙ 23 + 1 ∙ 18 + 0,5 ∙ 14 = 71.

Возможность оценить погрешность полученного решения является несомненным достоинством предложенного метода. В данном случае она составляет не более 2,1 или примерно 3 %.

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

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

Оценка первого подмножества (x61 = 1). В этом случае оптимальное решение при R1 = 15 имеет вид Т1 = (1, 3, 4, 6), w1 = 24,6.

118

При R2 = 30 оптимальное решение остается прежним: Т2 = (1, 3, 4, 5, 6, 7).

Оценка равна W(x51 = 1) = 2 ∙ 24,6 + 1 ∙ 17 + 0,5 ∙ 13,4 = 73,9.

Оценка второго подмножества (x61 = 0). Если проект 6 не включен в план первого периода, то u56 = 0 для плана первого периода и b5 = 6. В этом случае оптимальное решение для первого периода имеет вид Т1(3, 4, 5) с оценкой w1 = 23. Оценка сверху равна

W(x51 = 0) = 2 ∙ 23 + 1 ∙ 18,6 + 0,5 ∙ 13,4 = 72,3.

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

допустимого решения эффект равен
Ф = 2 ∙ 24 + 1 ∙ 17 + 0,5						∙ 14 = 72.
Полученное решение Т1 = (1, 3, 4, 5, 6, 7)						является оптимальным.
Дерево ветвлений приведено на рис. 5.2.7.
			74,3
x61=1						x61=0
	73,9
						72,3

x21=1	X21=0
67	72

Рис. 5.2.7

Метод «затраты – эффект»

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

ri =

, i = 1, . Далее проекты включаются в план в этой очередности. Примем

этот метод для решения задачи о ранце, полученной в результате применения метода сетевого программирования. (Задача (5.2.13), (5.2.14)). Алгоритм рассмотрим на примере 5.2.5.

Пример 5.2.5. Упорядочим проекты таблицы по убыванию эффективностей ri .

119

Таблица 5.2.23

i	6	3			4			5			1	2	7	8
di	4	7			10			8			3,6	8,4	9	5
ci	2	4			6			5			3	7	9	8
ri	2	1	3		1	2		1	3		1,2	1,2	1	5
			4			3			5
														8

1 шаг. R1 = 15. Включаем в план первого периода проекты Т1= (6, 3, 4),

w1 = 21.

2 шаг.R2 = 30. Включаем в план второго периода проекты Т2= (1, 2, 3, 4, 5, 6),

w2 = 41.

Поскольку в этом методе всегда Т1 Т2, то получено допустимое решение. Оценка равна W = 2 ∙ 21 + 1 ∙ 20 + 0,5 ∙ 14 = 69. Заметим, что это верхняя оценка с учетом погрешности метода «затраты – эффект». Соответствующее решение является оптимальным с учетом погрешности метода, то есть его нельзя улучшить на основе применения метода «затраты – эффект». Однако это не всегда так. Если например, R2 = 26, то в план второго периода будут включены проекты Т2 = (6, 3, 4, 5, 2) и соответствующая оценка

W2 = 37,4, W = 2 ∙ 21 + 1 ∙ 16,4 + 0,5 ∙ 17,6 = 67,2 будет только оценкой сверху,

поскольку b2 = 8,4 >a2 = 5. На самом деле полученное решение дает эффект Ф = 2 ∙21 + 1 ∙ 13 + 0,5 ∙ 21 = 65,5. В данном случае можно применить метод ветвей и границ с получением оценок с помощью метода «затраты – эффект». Ветвление проводим по проекту 2.

Оценка первого подмножества (x22 = 1). Метод «затраты – эффект» дает решение Т2= (6, 3, 4, 5, 2), w2 = 34, поскольку проект 1 не выполняется. Имеем W = 2 ∙ 21 + 1 ∙ 13 + 0,5 ∙ 21 = 65,5. Это решение является допустимым.

Оценка второго подмножества (x22 = 1). Решение, полученное методом

«затраты – эффект», Т2= (6, 3, 4, 5, 1), причем	b1 = 3, поскольку проект 2 не
выполняется в первых двух периодах. Имеем	W2 = 32, W = 2 ∙ 21 + 1 ∙ 11 +

0,5 ∙ 23 = 64,5. Это решение также является допустимым. Выбирая первое подмножество, получаем оптимальное решение в рамках погрешности метода «затраты – эффект».

Если решать задачу при R2 = 26 не приближенно (на основе метода «затраты – эффект»), то из табл. 5.2.23 получаем оптимальное решение Т1 = (1, 3, 4, 6), Т2 =(1, 3, 4, 5, 6, 7) со значением эффекта 72. Ошибка составляет 6,5 или примерно 9 %. Этот пример показывает, что при малом числе проектов метод «затраты – эффект» может дать ощутимую погрешность.

Общий случай

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

120