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

2 шаг. Рассматриваем последовательную сеть (0,4,2). (Комплексная работа I). Заметим, что ТI не может быть меньше 4 и не может быть больше 12. Имеем B TII d04 d02 TII 4 .

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

3x04 4x42

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

3x04 2x42 TI 4 .

Ее решение приведено в табл. 2.2.3.6.

Таблица 2.2.3.6

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

Вариант	0	1	2
ТII	4	6	9
СII	0	4	7

3шаг. Рассматриваем параллельную сеть из комплексной работы I и работы (0,2). Заметим, что ТII не может быть меньше 4 и не может быть больше 12.

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

Таблица 2.2.3.7

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

Вариант	0	1	2	3
ТII	4	6	7	9
СII	0	4	9	13

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

Таблица 2.2.3.8

1		4;4	6;8	7;13	-	-
0		0;0	2;4	3;9	5;12	-
(2,3)		0	1	2	3	4
	II

Оптимальное решение определяется клеткой (7;13). Ему соответствует вариант 1 работы (2,3) (то есть ее выполнение собственными силами) и вариант 2 комплексной работы II. Варианту 2 комплексной работы II соответствует вариант 1 комплексной работы I и вариант 1 работы (0,2) (выполнение своими силами). Наконец, варианту 1 комплексной работы I соответствует выполнение

71

работы (4,2) своими силами. Окончательно своими силами выполняются работы (0,2), (4,2) и (1,3) с эффектом 20.

Заметим, что обе работы (0,1) и (0,4) не входят в число выполняемых работ. Поэтому в силу теоремы 2.2.3.2 получено оптимальное решение. Однако это не всегда так. Пусть например c13=2 вместо 7. В этом случае на шаге 1 мы получаем оптимальное решение х01=1, то есть работа (0,1) выполняется своими силами. В то же время работа (1,4) выполняется внешними организациями. Поэтому полученная в этом решении оценка эффекта 16 будет оценкой сверху. В данном случае возможны два варианта.

Первый вариант. Улучшаем оценку, решая ОДЗ. Для этого уменьшаем u01 на 1 и увеличиваем v04 на 1. Теперь на шаге 1 получаем два оптимальных решения: х01=1 или х13=1. На втором шаге также получаем два оптимальных

решения: х04=1 или х42=1. Выбирая пару х01=1, х04=1 или пару х13=1, х42=1 получаем два оптимальных решения, поскольку условия теоремы 2.2.3.2

выполняются для обоих решений.

Первое решение: х01=1, х04=1, х02=1, х42=1. Второе решение: х13=1, х02=1, х42=1, х23=1. Оба с эффектом 15.

Второй вариант. Не тратить время на решение ОДЗ, а применить метод ветвей и границ. В нашем случае разбиваем множество всех решений на два подмножества. В первом работа (0,1) выполняется своими силами, а во втором

– выполняется внешними организациями.

Алгоритм решения остается прежним при фиксации переменных хij тех работ, на основе которых производится разбиение на подмножества.

2.2.4. Модели с несколькими видами ресурсов

Рассмотрим ряд задач, которые объединены названием «задачи обработки деталей на станках». Имеется n деталей. Каждая деталь проходит обработку на двух станках. Известно время обработки деталей. Обозначим ai продолжительность обработки i–й детали на первом станке, bi - на втором. Рассмотрим ряд задач, отличающихся числом станков первого и второго типа.

Один станок первого типа, n станков второго типа

Для данной задачи оптимальная очередность обработки деталей определяется правилом: детали обрабатываются в очередности убывания bi. Действительно, рассмотрим оптимальную последовательность. Пусть в этой последовательности детали j и i находятся рядом, причем деталь i обрабатывается первой.

Если bj<bi, то, очевидно, продолжительность обработок двух деталей составит аj+аi+bi. Поменяем местами детали j и i. Время обработки детали i равно

аi+bi<аj+аi+bi.

Время обработки детали j равно

72

аi+аj+bj<аj+аi+bi.

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

b1≥b2≥…≥bn.

На рис. 2.2.4.1 приведен сетевой график обработки деталей (для случая n=4, работы изображены вершинами).

1 1

2 2

3 3

4 4

Рис. 2.2.4.1

Пусть длина критического пути в этой сети больше Т. Тогда ряд деталей следует отдать внешним исполнителям. Обозначим хi=1, если i–я деталь обрабатывается своими силами, хi=0 − в противном случае. Для того, чтобы обработка деталей была завершена за время, не большее Т, необходимо, чтобы длины всех путей сети не превышали Т. Это можно записать в виде системы неравенств:

k
xiai	T bk ,	k	1,n	.	(2.2.4.1)
i 1
Задача. Определить {xi, i=1,n}, максимизирующие
	C(x) ci xi .				(2.2.4.2)

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

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

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

1шаг. Проверяем условие a1 T b1 или рассматриваем первые две детали.

Решаем задачу максимизации

C(x) c1x1 c2 x2

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

a1x1 a2 x2 A2 ,

где А – параметр, A2 T b2 .

В результате получаем зависимость C1(A) максимального эффекта от параметра А.

73

Рассматриваем первые (k+1) деталей.
kшаг. Пусть уже	получена	зависимость Ck(A), Ak T bk .	Зависимость
Ck+1(A), Ak 1	T bk 1	определяется из уравнения Беллмана
	Ck 1 (A) min [ck (A ak 1 ) ck 1 ] ,		(2.2.4.3)
		A

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

Таблица 2.2.4.1

i	1	2	3	4
аi	6	4	10	3
bi	7	5	4	2
ci	5	4	3	6

Примем Т=16.
1 шаг.	Проверяем условие a1		6 T b1		9 A1 .
2 шаг.	Берем детали 1 и 2. A8		8 .
Решение приведено в табл. 2.2.4.10.
							Таблица 2.2.4.2
			1	4;4		-
			0	0;0		6;5
		2		0		1
			1

Правое число в клетке равно затратам (времени), а второе - эффекту от экономии средств. Результаты сведены в табл. 2.2.4.3

Таблица 2.2.4.3

Комплексная деталь II

Вариант	0	1	2
С2	0	4	5
А2	0	4	6

3 шаг. Добавляем деталь 3. Решение приведено в табл. 2.2.4.4.

A3 16 4 12 .

Таблица 2.2.4.4

Комплексная деталь III

1		10;3		-	-
0		0;0		4;4	6;5
3		0		1	2
	II
			74

Результаты сведены в таблицу 2.2.4.5.

											Таблица 2.2.4.5
		Вариант			0		1		2
		С3			0		4		6
		А3			0		4		5
Оставлены только Парето-оптимальные варианты.
4 шаг. Добавляем деталь 4.					Решение				приведено в табл. 2.2.4.6
A4 16 2 14 .
											Таблица 2.2.4.6
		1		3;2			7;6		9;7
		0		0;0			4;4		6;5
		4		0			1		2
		II

Оптимальное решение определяется клеткой (9;7). Этой клетке соответствует вариант 1 детали 4 (эта деталь обрабатывается своими силами) и вариант 2 комплексной детали III. Варианту 2 комплексной детали III соответствует обработка деталей 3 и 2 внешними исполнителями и обработка детали 1 своими силами. Окончательно получаем, что своими силами обрабатываются детали 1 и 4. Дополнительные затраты составляют 7 единиц.

Один станок второго типа и n станков первого типа

Пусть Q − множество деталей, обрабатываемых своими силами. Тогда оптимальная очередность обработок этих деталей определяется правилом: детали обрабатываются в очередности возрастания аi. Действительно, если aj ai и деталь j обрабатывается первой, то продолжительность обработки этих

двух деталей равна

max( aj bj bi ; ai bi ).

Если поменять детали местами, то получим время обработки:

max(ai bi bj; aj	bj ) .
Заметим, что ai bi bj aj bj bi	, а (aj bj ) aj bj bi , что

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

Однако мы не знаем множество Q, а значит, не знаем, какая деталь будет обрабатываться первой. Поэтому переберем все n вариантов. При этом если первой обрабатывается деталь i, то в множество обрабатываемых своими силами деталей не должны входить детали, у которых aj ai .

Пусть детали пронумерованы по возрастанию a i , то есть a1 a2 ... an .

75

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

		i
Ci (x) ci xi				(2.2.4.4)
	j i
при ограничениях
bi xi T ai ,
	i	1,n	.	(2.2.4.5)
j i

Эта задача для каждого i также решается методом динамического программирования аналогично предыдущей задаче.

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

Таблица 2.2.4.7

i	1	2	3	4
аi	6	8	10	13
bi	4	5	6	8
ci	1	4	5	6

Примем Т=19.

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

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

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

4х1+5х2+6х3+8х4≤19-6=13, 5х2+6х3+8х4≤19-8=11, 6х3+8х4≤19-10=9,

8х4≤19-13=6.

Ее решение х1=1, х3=1, с1=6.

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

4х2+5х3+6х4

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

5х2+6х3+8х4≤11, 6х3+8х4≤9,

8х4≤6.

Ее решение х2=1, х3=1, с2=11.

3 шаг. Третья деталь обрабатывается первой. Решаем задачу максимизации

5х3+6х4

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

6х3+8х4≤9,

8х4≤6.

Ее решение х3=1, с3=5.

Оптимальным является обработка первой второй детали.

76

Один станок каждого типа (задача Джонсона)

Рассмотрим ситуацию, когда имеется по одному станку каждого типа. Эта задача известна как задача Джонсона. Решение задачи Джонсона получается на основе следующего правила: сначала обрабатываются детали, для которых ai≤bi, в очередности возрастания ai. Затем обрабатываются детали, для которых ai≥bi в очередности убывания bi.

Пусть детали пронумерованы согласно этому правилу. В этом случае допустимое решение должно удовлетворять следующей системе неравенств:

k	n
ajxj	bjxj	T,	k 1,n	(2.2.4.6)
j 1	j k

Задача заключается в определении {xj, j 1.n }, максимизирующих

C(x) cjxj	(2.2.4.7)
j

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

Для решения задачи можно применить программы решения задач дискретной оптимизации в переменных 0,1. Однако в ряде случаев эффективным является метод ограниченного перебора. Так, если для выполнения неравенств (3,6) достаточно удалить не более k любых деталей, то перебор составляет не более

Mcni , i 1

ипри небольших k алгоритм достаточно эффективен.k

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

Таблица 2.2.4.8

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

Примем Т=25.

Получаем систему неравенств

12х1+9х2+4х3+5х4≤25,

4х1+16х2+4х3+5х4≤25, 4х1+7х2+12х3+5х4≤25, 4х1+7х2+8х3+11х4≤25.

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

77

Рассмотрим два частных случая.

1случай. Имеет место ai≥bj для всех i, j.

Вэтом случае момент окончания обработки детали k выполняется по формуле

k
tk aj	bk ,	(2.2.4.8)

j 1

что совпадает с моментом окончания обработки k-ой детали в случае, когда имеется один станок первого типа и n станков второго типа (см. формулу (2.2.4.1)). Поэтому в этом случае можно применить метод динамического программирования, как описано выше.

2 случай. Имеет место ai≤bj для всех i,j.

В этом случае момент окончания отработки k-й детали, в случае, когда первой обрабатывается деталь i≠k, вычисляется по формуле

tk ai bj	(2.2.4.9)
j i

(см. формулу (2.2.4.5)).

Как описано выше, задача решается перебором всех деталей. Для каждого i (деталь i обрабатывается первой) решается задача (2.2.4.4), (2.2.4.5) методом динамического программирования.

Три типа станков. Один станок для второго типа

Рассмотрим задачу, когда каждая деталь обрабатывается на трех станках, причем станков первого и третьего типа достаточно, а станок второго типа один. Обозначим τi, ai, bi − продолжительности обработки i-й детали на станках соответственно первого, второго и третьего типов.

Заметим, что начало обработки i-й детали на втором станке равно di i 1,

а поздний момент окончания равен

Di Т bi .

Таким образом, i-я деталь должна быть обработана на отрезке времени [di , Di ] . Для решения задачи применяем потоковую модель, описанную в

п.2.1.4. Разница в том, что каждая деталь обрабатывается на одном станке. Поэтому пропускные способности c0i ai , cij ij , cjz j , i 1,m , где m- число интервалов.

Пример 2.2.4.4. Имеются 5 деталей, данные о которых приведены в табл. 2.2.4.9. Таблица 2.2.4.9

i	1	2		3	4	5
τi	5	2		3	6	7
аi	2	2		3	3	1
bi	5	7		6	4	3
ci	5	4		3	2	1
			78

Примем Т=12.

Интервалы [di , Di ] приведены в табл. 2.2.4.10.

Таблица 2.2.4.10

i	1	2	3	4	5
di	6	4	4	7	8
Di	7	5	6	8	9

Выделим шесть интервалов длительности. Потоковая сеть приведена на рис. 2.2.4.2.

(2)2

2(2)

0 (3)0

(3)1

(1)1

1

1

1	1
			2
	1			(1)1
2				(1)1
	0		3	(1)1
3	0				z
	0	1		1(1)
			4
4	0			(1)1

	1	(1)1
		5
	5
	1	6

Рис. 2.2.4.2

Пропускные способности всех дуг (i,j) и (j,z) равны 1. Потоки указаны у дуг (без скобок). На исполнение внешним организациям передается деталь 3 и 2/3 части обработки детали 4 с дополнительными затратами 2/3·3·2+3=7 единиц. В данном случае мы допустили передачу обработки части детали на втором станке. Заметим, что обработка деталей − это только одна из интерпретаций задачи. Как правило, имеются другие содержательные интерпретации, более близкие к управлению проектами (выполнение проектных работ, выполнение строительных работ, завершение проекта и др.). Если передача части работ недопустима, задача становится существенно сложнее и в настоящее время не решена.

79

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

1.Сформулировать алгоритм решения задачи оптимизации объемов работ для случая линейной зависимости продолжительностей работ от их объемов.

2.В чем заключается суть потоковой модели для задачи оптимизации объемов работ при переменном уровне ресурсов?

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

4.Какие методы решения задачи оптимизации объемов работ можно предложить для дискретных моделей?

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

6.В чем заключаются постановки задач оптимизации объемов работ с несколькими видами ресурсов.

ГЛАВА 3. ОПТИМИЗАЦИОННЫЕ МОДЕЛИ УПРАВЛЕНИЯ ПРОЕКТАМИ ПРИ РЕКОМЕНДАТЕЛЬНЫХ ЗАВИСИМОСТЯХ МЕЖДУ РАБОТАМИ

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

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

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

Пусть имеется проект из n работ, мягкие зависимости между которыми описаны сетевым графиком (рис. 3.1.1). Будем рассматривать зависимости «финиш-старт». Вершины сетевого графика соответствуют работам проекта. В верхней половине вершины указан номер работы, а в нижнем − ее

80