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

Таблица 5.3.7

	j	1	2	4	5
	i
	2	15	21	36	45
	3	14	16	24	30
	4	20	25	40	50
	5	12	15	24	30

Получаем x21 = 1, x42 = 1, x34 = 1,							x55 = 1, S3 = 94 + 12 = 106.
4 шаг. Проект 1 выполняется четвертым (табл. 5.3.8).
												Таблица 5.3.8
		j	1		2		3			5
		i
		2	18		24		30			45
		3	18		20		22			30
		4	25		30		35			50
		5	15		18		21			30
Получаем x21 = 1, x42 = 1, x42 = 1,							x53 = 1, x34 = 1, S4 = 99 + 4 ∙ 4 = 115.
5 шаг. Проект 1 выполняется последним (табл. 5.3.9).
												Таблица 5.3.9
		j		1		2		3		4
	i
	2			21		27		33		39
	3			22		24		26		28
	4			30		35		40		45
	5			18		21		24		27
S5 = 108 + 4 ∙ 5 = 128.
Оптимальная последовательность								π =		(2, 1, 4, 3, 5) с величиной

упущенной выгоды

F(π) = 1 ∙ 6 + 2 ∙ 7 + 3 ∙ 10 + 4 ∙ 6 + 5 ∙ 6 = 104.

5.4. Задача Джонсона с критерием упущенной выгоды

Рассмотрим классическую задачу Джонсона о станках. Имеются n деталей, которые обрабатываются на двух станках. Каждая деталь сначала обрабатывается на первом станке, а затем на втором. Обозначим ai продолжительность обработки детали i на первом станке, bi − на втором. Имеется по одному станку каждого типа. Требуется определить очередность обработки детали, при которой продолжительность обработки всех деталей минимальна. Оптимальная очередность обработки деталей получается по следующему правилу: сначала обрабатываются детали, для которых ai≤bi, в очередности возрастания ai, а затем обрабатываются детали, для которых ai≥bi, в очередности убывания bi.

131

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

Обозначим сi − коэффициент упущенной выгоды, ti − момент окончания обработки i–й детали. Целевая функция имеет вид

C(t) ci ti min .

i

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

1. aj≥bi, ai≥bj.

Имеем необходимое условие оптимальности

(t ai bi )ci

или

2. aj≥τi, ai≤τj.

Имеем

(t ai bj )ci

или

3. aj≤τi, ai≤τj.

Имеем

(t ai bi )ci

или

4. aj≤bi, ai≥bj.

Имеем

(t ai bi )ci

или

(t ai aj bj )cj (t aj bj )cj (t aj ai bi )ci

aicj

ajci ,

pi

c

i

cj

pj .

ai

aj

(t ai aj bj )cj

(t aj bj )cj (t aj bj bi )ci

aici aicj ajci bjci , ai (ci cj ) ci (aj bj ),

paj b j .

ici cj

(t ai bi bj )cj (t aj bj )cj (t aj bj bi )ci

aici aicj bicj

ajci ajci bjci ,

(ai bi

aj )cj

(aj bj ai )ci ,

ai bi aj

aj b j

ai

.

ci

cj

(t ai bi

bj )cj

(t aj

bj )cj (t aj ai bi )ci

132

	aicj bicj ajcj						ajci ,
	(ai bi				aj )cj ajci ,
ai bi	aj		aj		pj	cj			ci		.
cj			cj			aj		ai	bi
										aj

Определим полный асимметрический n-вершинный граф.

Любые две вершины соединим дугой (i, j), если выполняется одно из условий оптимальности. Очевидно, что любому гамильтонову пути в графе соответствует локально-оптимальное решение задачи. И наоборот, любому локально-оптимальному решению задачи соответствует гамильтонов путь в графе.

Опишем алгоритм определения гамильтонового пути графа.

1.Берем произвольную перестановку вершин (i1, i2, …, in).

2.Если (ik, ik+1) U (U– множество дуг графа), то производим транспозицию, то есть меняем местами вершины ik и ik+1. За конечное число

транспозиций получаем гамильтонов путь.

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

Таблица 5.4.1

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

		Рассматриваем все пары вершин (деталей).
		1. Пара (1,2). Имеем															a1 b2 ,						a2 b1	(случай	1).			Поскольку
	a1	5	a2		3.5 ,				то оптимальная очередность 2→1.															В графе появляется дуга
	c1		c2
(2,1).
		2. Пара (1,3). Имеем a										b					, a			b			(случай 2). Поскольку p					5			13		, то
											1					3			3			1					1				4
оптимальная очередность (3,1). В графе появляется дуга (3,1).
		3. Пара (1,4). Имеем															a1 b4 ,						a4 b1	(случай	3).			Поскольку
	a1	b1 a4					8		a4 b4 a1				7	,			то оптимальная очередность (4,1). В графе
		c1			1				c4			4
появляется дуга (4,1).
		4. Пара (2,3). Имеем a										b					, a			b			(случай 1). Поскольку p						7	p				8
										2					3			3			2					2						3
																												4					3

, то оптимальная очередность (2,3). В графе появилась дуга (2,3).

133

5.

Пара

(2,4). Имеем

a2 b4 ,

a4 b2

a2

b2 a4

4

a4 b4 a2

7

,

то оптимальная

4

c2

c4

появилась дуга (4,2).

6.

Пара

(3,4). Имеем

a3 b4 ,

a4 b3

a2

b3 a4

10

a4 b4 a3

1,

то оптимальная

c3

3

c4

появилась дуга (4,3).

Полученный граф приведен на рис. 5.4.1.

(случай 3). Поскольку

очередность (4,2). В графе

(случай 3). Поскольку

очередность (4,3). В графе

1 2

3

4

Рис. 5.4.1

В данном случае существует единственный гамильтонов путь (4,2,3,1), который и определяет оптимальное решение задачи.

Учтем теперь взаимозависимости деталей (проектов), то есть дополнительные эффекты bij , возникающие при реализации (обработке) обоих

проектов i и j. Для этого, как и ранее, представим bij в виде bij uij vij и

воспользуемся неравенством

uijti vijtj bij max( ti ;tj ) .

Добавляя uij , j ui и vji , j ui к коэффициентам ci и решая задачу

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

Получение нижней оценки

Для получения нижних оценок примем, что станков второго типа достаточно для выполнения одновременно всех деталей. В этом случае, для любой последовательности (i1, i2, …, in) время окончания обработки детали (ik) равно

k

tik ai j ik , (5.4.1)

j 1

134

что меньше или равно реальному времени окончания обработки детали ik в этой последовательности. Оценочная задача заключается в максимизации

k

i

ai

ci

.

(5.4.2)

k

j 1

j

k

k

Покажем, что оптимальной является обработка деталей в очередности

убывания

p

ci

.

i

ai

Действительно, пусть в оптимальном решении

детали (i, j)

обрабатываются одна за другой. Поменяем местами детали i и j.

Имеем

(t ai i )ci (t ai aj j )cj (t aj j )cj (t aj ai

i )ci ,

или

aicj ajci , pi pj .

Теорема 5.4.1. Если ai j для всех i, j, то обработка деталей в очередности убывания (возрастания) pi дает оптимальное решение задачи. Доказательство. Поскольку aik jk 1 , то момент окончания обработки детали

ik в точности равен (5.4.1). Это доказывает теорему.

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

Пример 5.4.2. Граф взаимовлияний приведен на рис. 5.4.2.

		6
	1
7		8,5
2		5
3	7	4

Рис. 5.4.2

Данные о проектах (деталях) приведены в табл. 5.4.2.

Таблица 5.4.2

i	1	2	3	4	5	6
аi	2	3	6	8	8	5
τi	3	4	5	6	7	8
ci	1	2	3	4	5	6
			135

			Вычисляем:
1)			1 u12				2 7 u12			, u					3			, v			4 , b					4 ,			b		6 ,			p p				2 ;
													12						12					1						2							2
	2						3																											1
2)			3 u23					4 7 u23			, u					3		, v				4 , b					6		, b			8 , p				p			1;
														23						23					2						3				2			3
	6						8
3)			5 u56						6 8,5 u56			, u					7 , v						1,5			, b			12			, b		7,5 ,				p			p		1,5 .
																56						56						5					6							5		6
	8						5

Оптимальная очередность обработки деталей (1,2)→(5,6)→(3,4).

0 4 5 9 6 20 12 26 7,5 29 8 31 6 927 .

Для определения допустимого решения, соответствующего оценочному решению определим оптимальную очередность пар (1,2), (5,6) и (3,4) простым перебором.

1. Пара (1,2). Очередность 1→2. Вычисляем:

(a1 1 )c1 (a1 a2 2 )(c2 b12 ) 5 9 9 89 .

Очередность 2→1. Вычисляем:

(a2 2 )c2 (a2 2 1 )(c1 b12 ) 14 80 94 .

Оптимальная очередность 1→2.

2. Пара (3,4). Очередность 3→4. Вычисляем:

(a3 3 )c3 (a3 a4 4 )(c4 b34 ) 33 20 11 253 .

Очередность 4→3.

(a4 4 )c4 (a4 a3 3 )(c3 b34 ) 56 190 246 .

Оптимальная очередность 4→3.

3. Пара (5,6). Очередность 5→6. Вычисляем:

(a5 5 )c5 (a5 5 6 )(c6 b56 ) 75 333,5 408,5.

Очередность 6→5.

(a6 6 )c6 (a6 a5 5 )(c5 b56 ) 78 270 348 .

Оптимальная очередность 6→5.

Окончательно получаем допустимое решение (1,2,6,5,4,3) величиной упущенной выгоды.

5 1 9 9 18 6 13,5 25 32 4 37 10 1029,5 .

Относительная погрешность составляет

		1029 ,5 927			102 ,5	0,1,
		1039 ,5		1039 ,5

то есть примерно 10 %.

Метод локальной оптимальности

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

сучетом взаимовлияния проектов. Рассмотрим также четыре случая:

1)aj≤τj, aj≤τi.

136

Имеем

(t ai i )ci (t ai i j )(cj bij ) (t aj j )cj (t aj j i )(ci bij ) ,

или

(ai i aj )cj aibij (aj j ai )ci ajbij .

2) aj≥τj, aj≤τi.

Имеем

(t ai i )ci (t ai i j )(cj bij ) (t aj j )cj (t aj ai i )(ci bij ) ,

или

aicj icj cjbij ajcj ajci ajbij , (ai i aj )cj aici (aj j )bij .

3) ai≤τj, aj≥τi.

Имеем

(t ai i )ci (t ai aj j )(cj bij ) (t aj j )cj (t aj j i )(ci bij ) ,

или

aici aicj ajci jci ( i ai )bij . aicj (ai i )bij (aj j ai )ci .

4) ai≥τj, aj≥τi.

Имеем

(t ai i )ci (t ai aj j )(cj bij ) (t aj j )cj (t aj ai i )(ci bij ) ,

или

aicj jbij ajci ibij .

Применим эти условия к предыдущему примеру.

Пример 5.4.3. Рассматриваем все 12 пар (3 пары были рассмотрены ранее).

Пара (1,3).

b13 0 ,

c3 b34 10 .

Имеем

a1 3 ,

a3

1

(случай

3).

Вычисляем: (a3 3 a1 )c1 9 . Оптимальная очередность 3→1.

Пара (1,4). b14 0 . Имеем a1

4 ,

a4 1 (случай 4). Вычисляем:a3c1

6 .

Оптимальная очередность (1,4) или (4,1).

Пара (1,5).

b15 0 .

Имеем

a1 5 ,

a5 1 (случай

3).

Вычисляем:

a1c5 10 (a5 5 a1 )c1 13 . Оптимальная очередность 1→5.

Пара (1,6).

b16 0 ,

c6 b16

14,5 .

Имеем

a1 6 ,

a6

1

(случай

3).

Вычисляем: a1 (c6 b16 ) 29

(a6

6

a1 )c1

13 .

Оптимальная

очередность

6→1.

Пара (2,3). b23 0 , c3

b43

10 , c2

b12

9 . Имеем a2

3 , a3 2 (случай

3).

Вычисляем: a2 (c3 b43 ) 30

(a3 3 a2 )(c2

b12 ) 81.

Оптимальная

очередность 2→3.

Пара (2,4). Имеем

a2

4 ,

a4 2

(случай

3).

Вычисляем:

a2 c4

12 (a4 4

a2 )(c2

b12 ) 22 . Оптимальная очередность 2→4.

137

	Пара (2,5).		c2	b12 9 ,	c5 b56 13,5 . Имеем a2 5 ,					a5 2	(случай 3).
Вычисляем: a2 (c5			b56 ) 40,5 (a5 5			a2 )(c2		b12 ) 108 .		Оптимальная
очередность 2→5.
	Пара (2,6).		c2 b12 9 . Имеем			a2	6 ,	a6	2 (случай 3). Вычисляем:
a2 c6	18 (a6 6			a2 )(c2 b12 ) 90 . Оптимальная очередность 2→6.
	Пара (3,5).		c3	b34 10 ,	c5 b56	13,5 . Имеем a3 5 ,				a5 3	(случай 3).
Вычисляем: a3 (c5			b56 ) 81 (a5 5 a3 )(c3 b34 ) 120 .							Оптимальная
очередность 3→5.
	Пара (3,6).		c3 b34 10 . Имеем			a3	6 , a6		3 (случай 3). Вычисляем:
a3 c6	36 (a6 6			a3 )(c3 b34 ) 70 . Оптимальная очередность 3→6.
	Пара (4,5).		c5	b56 13,5 . Имеем a4 5				, a5 4 (случай 4). Вычисляем:
a4 (c5	b56 ) 108 (a5 5 a4 )c4 28 . Оптимальная очередность 5→4.
	Пара	(4,6).		Имеем	a4 6	,	a6 4		(случай	2).	Вычисляем:
a4 4 a6 )c6		54 a4c4 32 . Оптимальная очередность 6→4.
	На рис. 5.4.2 приведен граф оптимальных очередностей.
					6		1

5

2

4 3

Рис. 5.4.3

Как легко видеть, локально-оптимальных решений достаточно много. Однако можно высказать предположение, что решение, полученное на основе оценочной задачи, является оптимальным или во всяком случае достаточно близким к оптимальному. Так, например, для локально-оптимального решения

(1,2,6,4,3,5) имеем

5 81 108 96 290 526,5 1106,5 ,

что больше чем 1029,5.

Было решено 20 задач размерностью до 10 деталей. Во всех случаях было получено оптимальное решение (проверка оптимальности осуществлялась путем перебора всех локально оптимальных решений).

Выше было показано, что при ai bj для всех (i, j) получаемое на основе

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

138

примем, что ai j для всех i, j. В этом случае для любого решения (i1, i2, …, in)

имеет место

k

tik ai1 ij . (5.4.3)

j 1

При этом по аналогии с теоремой нетрудно показать, что оптимальное решение обобщенной двойственной задачи определяет оптимальное решение исходной задачи. Отличие от предыдущего случая в том, что решение зависит от выбора первой детали (то есть от величины аij). Поэтому для получения оптимального решения необходимо перебрать все варианты выбора первой детали.

Пример 5.4.4. Рассмотрим граф взаимодействия рис. 5.4.3. Данные о деталях приведены в табл. 5.4.3.

Таблица 5.4.3

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

Найдем решение обобщенной двойственной задачи:

		1)			пара			(1,2).					Вычисляем:				1 u12							5 7 u12			,
																	3
																									5
p p			1		5	, b 4			7	, b			8	1	.
		2										2
1				8			1	8					8
		2)		пара				(3,4).				Вычисляем:						3 u34							6 7 u34
																	4								6
p3	p4 1,6 , b3							6,4 , b4					9,6 .
		3)		пара				(5,6).			Вычисляем:					2 u56						4 8,5 u56					,
																									4
																	3

u12 3 78 ,

,u34 3,4 ,

u56 4143 ,

p5 p6 2141 , b1 6143 , b2 8 72 .

Оптимальное решение оценочной задачи (5,6)→(1,2)→(3,4). Определим оптимальные очередности в парах. Поскольку i aj

i, j, то всегда имеем случай 1 условий оптимальности: 1) пара (1,2). Вычисляем:

(a1 1 a2 )c2 20 (a2 2 a1 )c1 (a2 a1 )b12 23 .

Оптимальная очередность 1→2. 2) пара (3,4). Вычисляем:

(a3 3 a4 )c4 36 (a4 4 a3 )c3 (a4 a3 )b14 26 .

Оптимальная очередность 4→3. 3) пара (5,6). Вычисляем:

v12 318 ,

v34 3,6 ,

v56 4 72 ,

для всех

139

(a5 5 a6 )c6 24 (a6 6 a5 )c5 (a6 a5 )b56 28,5 .

Оптимальная очередность 5→6.

Итак, получаем допустимое решение (5,6,1,2,4,3) величиной упущенной выгоды.

10 2 19 12,5 22 1 23 12 31 6 38 10 1121,5 .

Вданном случае не требуется проверять варианты с другой первой деталью, поскольку деталь 5 имеет минимальную величину ai 3 .

Возьмем, например, решение,				в котором первой обрабатывается
деталь 1. Определяем:
p			c2 b12		12	2,4 .
	2
			a2	5

Поэтому деталь 2 обрабатывается второй. Получаем решение (1,2,5,6,4,3)

свеличиной упущенной выгоды

9 16 12 22 2 27 12,5 33 6 38 10 1160,5 1121,5.

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

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

1.Сформулируйте постановку задачи формирования портфеля взаимозависимых проектов.

2.В чем заключается модифицированный метод дихотомического программирования с частичным перебором?

3.В чем заключается метод сетевого программирования?

4.Расскажите правила построения двойственной задачи к данной задачи линейного программирования.

5.Сформулируйте обобщенную двойственную задачу.

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

7.Сформулируйте постановку задачи формирования календарного плана взаимозависимых проектов.

8.Как решить задачу формирования календарного плана взаимозависимых проектов с помощью метода дихотомического программирования?

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

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

11.В чем заключается задача Джонсона с критерием упущенной выгоды.

140