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

2.1.5. Многоресурсная модель

Рассмотрим произвольный сетевой график, в котором работы выполняются ресурсами многих видов. При этом имеется определяющий ограниченный ресурс. Остальные ресурсы имеются в достаточном количестве, так что продолжительности работ, выполняемых другими ресурсами, можно принять равными τi. Количество ограниченного ресурса равно N. При этом предлагается, что работы, выполняемые ограниченными ресурсами независимы, то есть никакие две работы не принадлежат одному пути. Пример такой сети приведен на рис. 2.1.5.1. В данном случае удобно работы изображать вершинами сети. Работы, выполняемые ограниченными ресурсами, отмечены двойными кружками. В нижних половинах вершин указаны продолжительности τi. Для удобства работы, выполняемые ограниченным ресурсом, пронумерованы от 1 до n, где N – число таких работ.

Пусть Т=32. Определим ранние и поздние времена начала работ, выполняемых ограниченным ресурсом. Для определения ранних моментов начала просчитываем сеть с начала.

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

			[12]	4	[16]
		[5]		6		[22]
		7				10
	[0]	7				7
							[29]
				3
	5		[12]		[19]		13
		[5]		3		[25]
	5						3
		8				11
	[0]	3				4	[30]
	6						14
	4		[8]	2	[21]		2
		[4]		4		[25]
		9				12
		28				5

41

[6]5 [20]

Рис. 2.1.5.1

Теперь можно определить интервалы, в которых должны выполняться работы:

работа 4: [13;22]; работа 3: [13;22]; работа 2: [9;25]; работа 1: [7;25].

61

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

Получаем четыре интервала (7;8), (9;12), (13;22), (23;25):

1=2, 2=4, 3=10, 4=3. Примем N1=5,N2=6,N3=3,N4=2.

Данные о работах приведены в табл. 2.1.5.1.

Таблица 2.1.5.1

i	1	2	3	4
wi	30	20	15	42
аi	6	5	5	7
ci	5	4	3	2

Построим потоковую сеть (рис. 2.1.5.2).

1шаг. Определяем поток максимальной величины по дуге (0,1): x11 10, x12 14, x14 6 , x01 30 .

2 шаг. Определяем поток максимальной величины по дуге (0,2): x22 10, x23 10 , x02 20 .

3 шаг. Определяем поток максимальной величины по дуге (0,3):

x33 15 , x03 15 .

4 шаг. Определяем поток максимальной величины по дуге (0,4):

			x43 5 , x04	5 .
		1	(10)
				1
			(24)14
	(30)30	(18)6	(60)0			(10)10
	(20)20	2	(20)10	2	(24)24
			(50)10
	(15)15		(15)		30(30)	0
0		3		3
			(30)15
	(42)5				(6)
		4	(70)5	4

Рис. 2.1.5.2

Оптимальные объемы работ:

х1=30, х2=20, х3=15, х4=5.

Объемы работ, передаваемых на субподряд, равны:

у1=0, у2=0, у3=0, у4=37.

Затраты составляют 37·2=74 единицы.

62

2.2.Дискретные модели

2.2.1.Последовательные и параллельные сети

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

Пусть проект представляет собой последовательную цепь (путь) из n работ. Обозначим τi – продолжительность i-й работы, di – ее продолжительность при выполнении внешней организацией (очевидно, что

di<τi и di T ). Если	T(w) i T,	то часть работ придется отдать
i	i
внешним исполнителям.	Обозначим xi 0 ,	если работа i отдается внешним

исполнителям, xi 1 – в противном случае.

Задача. Определить {xi, i 1.n }, минимизирующие

(1 xi )ci ,

i

где сi – оплата i–й работы, выполняемой внешними исполнителями при ограничении

(1 xi )di xi i T

i

или

xi ( i di ) T di .

i

i

Обозначим i di bi , T di B эффект во времени при выполнении

i

работы внешним исполнителем. Тогда задачу можно преобразовать к виду: максимизировать

ci xi	(2.2.1.1)
i
при ограничении
bi xi B .	(2.2.1.2)

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

Пример 2.2.1.1. Имеются пять работ, данные о которых приведены в табл. 2.2.1.1.

63

Таблица 2.2.1.1

i	1	2	3	4	5
τi	7	4	5	8	9
di	3	2	2	3	8
ci	5	4	3	2	1
bi	4	2	3	5	1

Пусть Т=24, B T di 6 .

i

Задача о ранце имеет вид: максимизировать

5х1+4х2+3х3+2х4+х5.

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

4х1+2х2+3х3+5х4+х5≤6.

Примем метод дихотомического программирования. Возьмем структуру дихотомического представления задачи (рис. 2.2.1.1).

		IV
				III
	I		II
1	2	3	4	5

Рис. 2.2.1.1

1шаг. Рассматриваем работы 1 и 2. Решение приведено в табл. 2.2.1.2.

Таблица 2.2.1.2

1		4;2	9;6
0		0;0	5;4
2		0	1
	1

Первое число в клетке – это эффект, второе – затраты. Результаты сведены в табл. 2.2.1.3.

Таблица 2.2.1.3

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

2 шаг. Рассматриваем работы 3 и 4. Решение приведено ниже в табл. 2.2.1.4.

Таблица 2.2.1.4

1		2;5	-
0		0;0	3;3
4		0	1
	3

Результаты сведены в табл. 2.2.1.5 (оставлены только Паретооптимальные варианты). Так вариант (2,5) исключен, поскольку при больших затратах мы получаем меньший эффект.

																		Таблица 2.2.1.5
					Вариант						0			1
					Эффект						0			3
					Затраты						0			3
3 шаг. Рассматриваем			объединенную								работу				II и работу 5. Решение
приведено в табл. 2.2.1.6.
																		Таблица 2.2.1.6
		1			3;3			4;4				-			-
		0			0;0			1;1				-			-
		II			0			1				-			-
			5
Результаты сведены в таблицу 2.2.1.7.
																		Таблица 2.2.1.7
		Вариант					0				1			2		3
		Эффект					0				1			3		4
		Затраты					0				1			3		4

4 шаг. Рассматриваем объединенные работы I и III. Решение приведено в табл. 2.2.1.8.

Таблица 2.2.1.8

3		9;6	-	-	-
2		5;4	6;5	-	-
1		4;2	5;3	7;5	8;6
0		0;0	1;1	3;3	4;4
I		0	1	2	3
	II
			65

Оптимальное решение определяется клеткой (9;6). Ей соответствует вариант 3 объединенной работы I, то есть выполнение своими силами работ 1 и 2 и передача на субподряд работ 3, 4 и 5. Дополнительные затраты составят

3+2+1=6.

Параллельные (независимые) работы

Случай независимых работ является достаточно простым. Действительно, если τi>T , то работу i следует отдавать внешним исполнителям. Если обозначить Q множество работ, такие что τi>T, то дополнительные затраты составят

C(Q) ci .

i Q

2.2.2. Агрегируемые сети

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

Пример агрегируемой сети приведен на рис. 2.2.2.1. (работы изображены дугами сети).

1	(4;2)		3
				(6;3)
(6;3)
	(7;2)
0				6
		(8;4)		(7;3)
(5;3)	2		(3;2)	5

Рис. 2.2.2.1

Работы (0,1) и (1,3) образуют последовательную сеть. Заменяя их одной комплексной работой, получаем параллельную сеть из двух работ (0,3). Заменяя их одной комплексной работой (0,3), получим последовательную сеть (0,3,6), которую агрегируем в комплексную работу (0,6).

Аналогично последовательную сеть (0,2,5) агрегируем в комплексную работу (0,5), которая вместе с работой (0,5) образует параллельную сеть. Ее агрегируем в комплексную работу (0,5), которая вместе с работой (5,6) образует последовательную сеть. Агрегируя эту сеть, получаем комплексную работу (0,6), которая вместе с полученной ранее комплексной работой (0,6) образует параллельную сеть. Агрегируя эти две работы, получаем одну комплексную работу (0,6). Методы решения задачи синтеза объемов работ для

66

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

Пример 2.2.2.1. Рассмотрим сеть на рис. 2.2.2.2.

(8;5) 1 (6;2)

0	(12;6)	2	(5;4)	3

Рис.2.2.2.2

Данные о работах приведены в таблице 2.2.2.1.

Таблица 2.2.2.1

(i,j)	(0,1)	(0,2)	(1,2)	(2,3)
τij	8	12	6	5
dij	5	6	2	4
bij	3	6	4	1
cij	5	4	3	6

У дуг сети приведены значения τij и dij. Примем Т=15.

1шаг. Рассматриваем	последовательную	сеть (0,1,2). Заметим,		что
продолжительность Т02 пути (0,1,2)		не может	быть меньше	чем
d01 d12 7 и не должна быть больше чем T d23			11 . Следовательно,
Т02 принимает значения от 7 до 11.
Определяем B02 T03	d01 d12 T03 7 .

Следовательно, B02 принимает значения от 0 до 4. Решаем задачу о ранце:

минимизировать

C02 5x01 3x12

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

3x01 4x12 4 .

Как известно решение задачи о ранце при B02 4 дает решения для всех

меньших значений B02. Решение приведено в табл. 2.2.2.2.

Таблица 2.2.2.2

Комплексная работа I

Вариант	0	1
B02	0	3
С02	0	5
Т02	7	12
	67

Вариант x12 1, x01 0 отбрасываем, поскольку он доминируется вариантом x12 0, x01 1 (при меньшем b получаем больший с).

2 шаг. Рассматриваем параллельную сеть из комплексной работы I и работы (0,2). Величина Т02 по-прежнему может принимать значения от 7 до 11.

Результаты приведены в табл. 2.2.2.3.

Таблица 2.2.2.3

Комплексная работа II

Вариант	0	1
ТII	7	10
СII	0	5

Поясним табл. 2.2.2.3. При Т02=7,8,9, очевидно, все работы отдаются внешним исполнителям. При Т02=10 появляется возможность выполнять работу (0,1) своими силами (работы (0,2) и (0,2) по-прежнему выполняются внешними исполнителями). При Т02=11 появляется возможность выполнять работу (1,2) своими силами. Однако при этом работы (0,1) и (0,2) выполняются внешними исполнителями. Но это менее выгодный вариант, чем передача внешним исполнителям работы (0,1), поскольку c01 c12 .

3 шаг. Рассматриваем последовательную сеть из комплексной работы II и работы (2,3). Определяем: ВIII=T-11=4.

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

5xII 6x23

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

3xII 1x23 4 .

Поясним это ограничение. Для комплексного проекта II имеем ТII=7 или 10. Поскольку

dII max( d01 d12 ;d02 ) 7 ,

то bII равно либо 0 либо TII dII 3 . Оптимальное решение задачи

xII 1, x23 1, CIII 11 .

Само решение определяем методом обратного хода. Решению xII 1 соответствует вариант 1 табл. 2.2.2.3, то есть выполнение (0,1) своими силами,

арешение x23 1 соответствует выполнение работы (2,3) своими силами.

2.2.3.Общий случай

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

Разделим вершину 1 на две 1 и 4, соответственно поделив с01 произвольным образом также на две части u01и u04, u01+u04= с01 (рис. 2.2.3.2).

68

	(5;2)		1			(14;9)
				(4;2)		(7;3)
0					2			3
			(10;4)
				Рис. 2.2.3.1
		(5;2)		1		(13;9)
	0		(5;2)	4	(4;2)			3
							(7;3)
				(7;4)		2

Рис. 2.2.3.2

Получили агрегируемую сеть. Имеет место

Теорема 2.2.3.1. Решение задачи оптимизации объемов работ для агрегируемой сети дает оценку сверху для исходной задачи.

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

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

Теорема 2.2.3.2. Пусть в оптимальном решении для агрегируемой сети для любой дуги (i,j), разделенной на дуги (i,p)и (i,s),имеет место либо хip=хis=1, либо хip=хis=0. В этом случае полученное решение является оптимальным для исходной задачи.

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

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

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

Определить

uij vis cij ,

(i, j) P ,

где Р - множество разделенных дуг, так, чтобы с(u,v) была минимальной.

Теорема 2.2.3.2. ОДЗ является задачей выпуклого программирования. Доказательство. Пусть (u1,v1) и (u2,v) два допустимых решения ОДЗ. Возьмем выпуклую линейную комбинацию

69

uu1 (1 )u2 ,

vv1 (1 )v2 ,

(u,v) также является допустимым решением для ОДЗ. Рассмотрим задачу максимизации.

C(x,u, v) cij xij	u1ij	(1 )uij2 xij v1ij (1 )vij2 xij
(i,j) P	(i,j) P
при ограничении
	T(x) T.
Представим cij cij	(1 )cij	. Имеет место
C(u, v) max C(x, u, v) max C(x,u1 , v1 ) (1 ) max C(x, u2 , v2 )
x	x	x

C(u1 , v1 ) (1 )C(u2 , v2 )

Таким образом, ОДЗ можно решать методами локальной оптимизации.

Пример 2.2.3.1. Рассмотрим сеть (рис. 2.2.3.1) и агрегируемую сеть (рис. 2.2.3.4). Данные о работах приведены в таблице 2.2.3.4.

Таблица 2.2.3.4

(i,j)	(0,1)	(0,2)	(1,2)	(1,3)	(2,3)
τij	5	7	4	13	7
dij	2	4	2	9	3
bij	3	3	2	4	4
cij	6	5	4	7	4

Примем Т=15. Возьмем u01 u04 3. Решаем задачу для агрегируемой

сети.
1шаг. Рассматриваем	последовательную	сеть	(0,1,3).	Имеем

B T d01 d13 4.

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

C(0,1,3) 3x01 7x13

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

3x01 4x13 4 .

Решение приведено в табл. 2.2.3.5

Таблица 2.2.3.5

Вариант	0	1	2
Т	11	14	15
СI	0	3	7

Оптимальному решению соответствует вариант 2, то есть выполнение работы (1,3) своими силами.

70