Уч.пособие-по-ОДМ-2012

s

HH

s

s

H

s

v1

@

w1

v1 HH w1

H

@

v2 s HHHsw2

v2 s HHHsw2

v3

s

sw3

v3

s

sw3

v4 s

sw4

v4 s

sw4

sw5

sw5

П2

П2

.

4.

П

v

H

w

Опять ищем тонкую цепь..

1

sJ HH s

1

Последовательность ребер

J H

H

Вw

А

v2

s JJ Hsw2

v

v

w .

БарашевH H

7→3 7→ 5

JJ

4

7→

3

v3 s@@ JJ sw3

.

- искомая цепь, соединяющая ненасыщенные

v4 s

@@

Jsw4

вершины v4 и w5.

@@

Ребра {v4, w3} и {v3, w5}, входящие в данную

Унучек

G

sw5

цепь - тонкие, ребро {vС3, w3}

- толстое.

@sw5

МИРЭА@sw5

5. Исключим ребро {v3, w3} из паросочетания П2, включив тонкие

ребра.

v1 sHHH sw1

v1 sHHH sw1

v2 s

H

Hsw2

v2 s

H

Hsw2

s@@

s

s @

s

v3

@

w3

v3

@

w3

@

sw4

sw4

v4 s @@

@

v4 s @@

@

П3

П3

П3 = {{v1, w2}, {v2, w1}, {v4, w3}, {v3, w5}}

221

- полное паросочетание.

6.Так как ненасыщенная вершина w4 в графе одна, тонкой цепи, соединяющей две ненасыщенные вершины, нет. Алгоритм закончен. Паросочетание П3 - искомое максимальное.

Так как |П3| = 4 = |V |, то П3 является также совершенным паросочетанием.

Пример 12.5. Найти максимальное паросочетание в графе G:

v

H

w

.

.П

1

sJ HH

s

1

s

H

s

J HH

v2

H J

H

w2

@HJ

s

@ JH

sw3

.

v3

@ JHH

@J

А

s

@J

swВ4

v4

G

@J

.

Решение.
		П1 = {{v1, w2}, {v2, w1}, С{v4, w4}} - полное па-
	s s
		Барашев
		Унучек	и w3	нена-
		МИРЭА

паросочетание, с чередовасоединяющей максималь-

паросочетание.

12.3 Задача об оптимальном назначении

Каждый i рабочий

выполняет j работу с эффективностью cij > 0. Требуется распределить работу между работниками таким образом, чтобы суммарная эффективность работ была бы максимальной.

222

Данная задача обычно называется задачей об оптимальном назначении. Эффективность выполнения работ как правило задается квадратной матрицей Cn×n = {cij}, элементом cij которой является эффективность выполнения i-тым рабочим j-той работы (строки матрицы соответствуют работникам, столбцы - выполняемым работам).

Задачу удобно формулировать с помощью графов.

Дан двудольный граф G =< (V, W ), E >, ребра {vi, wj} которого

имеют вес cij (вес ребра равен эффективности выполняемой работы),
множество V вершин соответствует рабочим, множество W - работам.
					.
В графе G требуется выделить такое совершенное паросочетание П,
				П
чтобы сумма весов ребер, вошедших в П, была бы максимальной среди
сумм весов всех возможных совершенных паросочетаний графа G.
			.
Эту задачу обычно решают с помощью следующего алгоритма.
			В			.
12.3.2 Алгоритм поиска оптимального назначения
					А
1. В каждой строке матрицы эффективности находим максималь-
ный элемент ai = max cij			С
			и подчеркиваем его (очевидно, что
j=1;:::;n				.

таких элементов в строке может быть несколько). Всем строкам приписываем метки, равные ai, всем столбцам - метки bj = 0.

2.Строим двудольный граф G =< (V, W ), E >, соответствующий подчеркнутым элементам. Число вершин в обеих долях равно n - порядку матрицы эффективности (|V | = |W | = n).

Если элемент cij матрицы Cn×n подчеркнут, то в графе G рисуем ребро {vi, wj} с весом cij. Ребро {vi, wj} соединяет вершину vi из левой доли графа G с вершиной wj из правой доли.

3.Используя венгерский алгоритм, выделяем в графе G максимальное паросочетание.

4.Если построенное паросочетание совершенно (|П| = |V | = n), то найденное паросочетание - искомое оптимальное назначение. Ал-

горитм заканчивает свою работу (переход к пункту 7 нашего ал-

горитма).БарашевУнучекМИРЭА

5. Если |П| ≠ |V | = n, то, согласно теореме Холла, среди вершин V графа G можно выделить такое подмножество вершин S, что

223

|S| > |φ(S)|, где φ(S) - окружение множества S (вершины из W , смежные с вершинами из S). Находим множество S V , удовлетворяющее указанному неравенству.

Метки ai, соответствующие вершинам из S, понижаем на 1. Остальные метки, приписанные строкам, не меняем. Метки bj, соответствующие вершинам из φ(S), повышаем на 1. Остальные метки, приписанные столбцам, оставляем без изменения.

6. Находим такие элементы cij в матрице эффективности, что значение элемента равно сумме меток, приписанных строке.i и столбцу

j, на пересечении которых он находится: cij = ai + bj. Подчерки-
ваем эти элементы и переходим к пункту 2.		П
7. (Окончание работы алгоритма).	В		П . Оно зада-
Выписываем найденное совершенное паросочетание.

ет оптимальное распределение работ между работниками. Сум-
	А
мируем веса всех ребер, вошедших в паросочетание..Полученная
Барашев	.

сумма эфф - максимальная эффективность выполнения всех работ.

Заметим, что оптимальное распределение всех работ между работниками может быть не единственным, но их суммарная эффек-

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

8. Делаем проверку полученного назначения. Эффективность эфф, равная сумме весов ребер, вошедших в итоговое паросочетание П , должна равняться сумме меток всех строк и всех столбцов на момент завершения алгоритма:

Пример 12.6. Решить задачу об оптимальном назначении с матрицей

эфф = ∑i ai + ∑j	bj.
Унучек
МИРЭА

		4	6	5	5
		4	6	8	4
эффективности C =		3	9	8	4
		5	7	5	6

Решение.

224

1.Находим максимальные элементы каждой строки, подчеркиваем их.

2.Метки ai, приписанные строкам, равны максимальным элементам строки:

a1 = max{4, 6, 5, 5} = 6, a2 = max{3, 9, 8, 4} = 9, a3 = max{5, 7, 5, 6} = 7, a4 = max{4, 6, 8, 4} = 8.

Все метки, приписанные столбцам, равны 0:

							b1 = b2 = b3 = b4 = 0.
		0	0	0	0		Метки строк a	записываем.левее эле-
							ментов матрицыi	напротив соответству-
	6	4	6	5	5
	9	3	9	8	4		ющей строки, метки.Пстолбцов bj - вы-
	7	5	7	5	6				.
							ше элементов матрицы напротив соот-
	8	4	6	8	4		ветствующего столбца.

v1 sHБарашевHH sw1									подчеркнутым
3. Строим граф G1						, ребра которого соответствуютВ
элементам матрицы C.
v1 HH			HH6		w1	Так как |V | = |W | = 4, каждая.Адоля графа
	s				s	G1 содержит по 4 вершины.
	s	9		H	sw2	В графе G1 4 ребра.
v2				7 H						2
v3 s				Унучекsw3 v , w
v3 s				sw3		Подчеркнутому элементуСc12 = 6 соответ-
						ствует ребро {v1, w2};
v4 8					w4	МИРЭА			};
						элементу c22 = 9 - ребро	{v2, w2
	s		G1		s	элементу c32 = 7 - ребро	{	v3, w2	}	;
						элементу c43 = 8 - ребро {v4, w3}.
4. Находим максимальное паросочетание П1 в графе G1.
v2 s				H6HHsw2		В него входит 2 ребра: ребро {v4, w3} и лю-
						бое из ребер, инцидентных вершине w , на-
v4 s 8					sw4	пример, ребро { 1 2}.
			П1

5.Поскольку |П1| = 2 ≠ |V | = 4, паросочетание П1 не является совершенным. Значит, по теореме Холла найдется такое подмножество S вершин из левой доли, что выполняется неравенство

225

|S| > |φ(S)|, где φ(S) - окружение множества S.

В качестве множества S можно взять все вершины из V , так как в графе G1 количество вершин, смежных с вершинами из V меньше, чем число вершин в V :

|V | = 4 > |φ(V )| = 2.

Мы возьмем только 3 вершины из левой доли: S = {v1, v2, v3}, отбросив ребро {v4, w3} графа G1, так как вершины v4 и w3

инцидентны только одному ребру.												.
Все вершины множества S смежны только с вершиной w2:
		S = {v1, v2, v3}, φ(S) = {w2									П
										}; |S| = 3 >		|φ(S)| = 1.
										.				:
6. Понизим на 1 метки, приписанные вершинам v1, v2 и v3
		a1 = 6			− 1 = 5, a2 = 9					В	= 7 −
									− 1 = 8, a3				1 = 6.
									Метку, приписанную.вершине
Барашев
				0	1	0	0		w2, повысим на 1:
				0	↑ 0	0	0
												А
	5	↓	6	4	6	5	5
	8		9 3		9	8	4			b2 =.0 + 1 = 1.
		↓
	6		7	5	7	5	6		Метки, приписанные					осталь-
	8	↓	8	4	6	8	4		ным вершинам,С				оставляем без
									изменения.

7.Находим в матрице С элементы cij = ai + bj, значение которых равно сумме меток, приписанных строке i и столбцу j, на пересечении которых находится элемент cij. Все уже подчеркнутые элементы удовлетворяют этому равенству. Найдем другие элементы,

для которых это равенство верно и дважды подчеркнем их. В первой строке таких элементов два:Унучек

	5	4	6	5		5			МИРЭАтов по одному:
								c13		= 5 = a1 + b3 = 5 + 0;
								c14 = 5 = a1 + b4 = 5 + 0.
		0	1	0		0				В двух следующих строках таких элемен-
	8	3	9	8		4				c = 8 = a + b = 8 + 0;
										c23	= 6 = a2	+ b3 = 6 + 0.
	6	5 7		5		6
										34	3	4
	8	4	6	8		4
										В последней строке таких элементов нет.

226

8. Построим граф G2, ребра которого соответствуют подчеркнутым

элементам матрицы C.
v		H					w
	1	sJ@J@HHH					s 1
		s	HH			HH	s	Все ребра графа G1 являются также ребра-
v2			J@
		H		J @ w2
				JH@				ми графа G2. Добавляются ребра, соответ-
v3		sHHH J sw3						ствующие дважды подчеркнутым элемен-
v4		s HHJHJsw4						там матрицы.
				G2						.
9. Находим максимальное паросочетание П2 в графе G2.
v1		sHHH					sw1	В него входит 3 ребра..П
v2		s			H6HHsw2
		s	6H				s	Так как |П2| = 3 ̸= |V | = 4, паросочетание
v3		HH				w3
										А
				H				П2 не является совершенным.
v4		Барашев							В		.
		s8 HHsw4								.
				П2

10. По теореме Холла найдется такое подмножествоС S вершин из V , что его окружение содержит меньшее количество вершин. В S войдут все вершины из V , так как они смежны с тремя вершинами из W :

S= {v1, v2, v3, v4}, φ(S) = {w2, w3, w4}; |S| = 4 > |φ(S)| = 3.

11.Вершины из S приписанные им метки понижают на 1 :

				Унучек
a1 = 5						МИРЭА								= 8 − 1 = 7.
		− 1 = 4, a2 = 8							− 1 = 7, a3 = 6 − 1 = 5, a4
Вершины из множества φ(S) приписанные им метки повышают
на 1:
			b2 = 1 + 1 = 2, b3 = 0 + 1 = 1, b4 = 0 + 1 = 1.
					2	1			1
				0
	4	↓	5	0	↑ 1	↑ 0			↑ 0				Метка b1 = 0,	приписанная
				4	6		5		5				вершине w1, остается без изме-
	7		8	3	9		8		4
		↓
	5	↓	6	5	7	5			6				нения.
		↓
	7		8	4	6	8			4

227

12. Находим в матрице эффективности элементы cij = ai + bj.

		0		2	1		1			Кроме всех уже подчеркнутых элемен-
										тов, для которых это равенство верно,
	4	4		6	5		5
										подчеркнем еще два элемента:
	7	3		9	8		4			c11 = 4 = a1 + b1 = 4 + 0;
	5	5		7	5		6
	7	4		6	8		4			c31 = 5 = a3 + b1 = 5 + 0.

Других элементов, для которых было бы выполнено равенство, нет.

13. Строим граф G3, ребра которого соответствуют. всем подчеркнутым элементам матрицы C и находим максимальное

паросочетание П3					в графе G3.			4
v		H		w	v				w
							s
	1	s@HJJ@HH s 1				1			s.1 П		.
		s	HH	s			s	9	s
v2			J@ HH	w2	v2				w2
		H	J @
			JH@
		Барашев
		JH@H			v3 sHH6H Вsw3
v3 sHHH J sw3										.А
v4 s HHJHJsw4					v4 s8 HHHsw4
			G3					П3
|П3| = 4 = |V | = 4; паросочетание П3 - совершенное.С

14. Оптимальное распределение работ между работниками:

П3 = {( {v1, w1}, 4), ({v2, w2}, 9), ({v3, w4}, 6), ({v4, w3}, 8) };

эфф = 4 + 9 + 6 + 8 = 27

-суммарная максимальная эффективность всех выполняемых работ.

15.Проверка: Унучек

i∑4	МИРЭА
4
	ai = 4 + 7 + 5 + 7 = 23;
=1
j∑4	bj = 0 + 2 + 1 + 1 = 4;
=1
∑1	ai + bj = 23 + 4 = 27 = эфф (верно).

228

Пример 12.7. Решить задачу об оптимальном назначении с матрицей

									2		5		4	2		5
									4		3		7	4		6
									4		2		3	4		6
эффективности					C =
									3		5		2	3		4
									2		6		5	2		3
Решение.
1. Найдем и подчеркнем максимальные элементы в строке.
			0	0	0	0	0					В первой строке 2 максимальных эле-
												мента, подчеркиваем оба..Приписыва-
	5		2	5	4	2	5
	7		4	3	7	4	6					ем строкам и столбцам соответствую-
	6		4	2	3	4	6
												щие метки:
																				В
	5	3 5 2 3 4										a		= 5 a																						= 6
													1				2	= 7			,	a			= 6 a = 5 a										5
															,										3.П, 4									,		;
	6	2 6 5 2 3												b	1	= b			2	= b				3		= b		4	= b				5	= 0
																																		.
2. Строим граф G1, находим в нем максимальное паросочетание.																																					П1.
	Барашевv4 s @@AA sw4																					v4				s	@@6							sw4
			v	H						w												v				H								w
				1 sAAHHH			H			s	1												1			s	HHH5							s 1
					A			H																							АH
			v2 sHHAH					sw2														v2 sHHH.sw2
						A H																							H7
							H			sw3												v3 s@С								H		H		sw3
						A H
			v3 s@ A
					@ A																						@

4.Метки, приписанные вершинамМИРЭАv1, v3, v4 и v5, понижаем на 1, а метки, приписанные вершинам w2 и w5, повышаем на 1. концыявляетсяУнучек

a1 = 5 − 1 = 4, a3 = 6 − 1 = 5, a4 = 5 − 1 = 4, a5 = 6 − 1 = 5.

229

					b2 = 0 + 1 = 1, b5 = 0 + 1 = 1.
					1	0	0	1
				0
				0	↑ 0	0	0	↑ 0
										Метки,	приписанные
	4	↓	5	2	5	4	2	5
	7		7	4	3	7	4	6
										остальным	вершинам,
	5	↓	6	4	2	3	4	6
	4		5	3	5	2	3	4		оставляем без изменения.
		↓
	5	↓	6	2	6	5	2	3

.

5. Находим в матрице С элементы cij = ai + bj, значение которых

равно сумме соответствующих меток.

0

1

0

0

1

Все уже подчеркнутые элементы удо-

4

2

5

4

2

5

влетворяют этому равенству. Найдем

7

4

3

7

4

6

другие элементы,.дляПкоторых это ра-

5

4

2

3

4

6

4

3

5

2

3

4

венство верно и дважды подчеркнем

В

А

5

2 6 5 2

3

их.

.

БарашевG2

П2

6. Строим новый граф

G2

. Максимальное паросочетание П2 в дан-

ном графе совпадает с П1 и не является совершенным..

v

H

w

v

H

HHH5

w

1 s@AA@HHH

s

1

1

s

s 1

Унучек

СHH

sw2

A @

HH

v2 sHHAH@ sw2

v2 sHHH

H7

A H@

H

H

A @H

МИРЭА

v3 s@ A sw3

v3 s@

sw3

v4 s

@ A

sw4

v4 s

@

sw4

@ A

@

@6

@ A

@A

v5 s

@

@sw5

v5 s

@Asw5

7.

S = {v1, v2, v3, v4, v5} = V ,

φ(S) = {w2, w3, w5}; |S| = 5 > |φ(S)| = 3.

8.Все метки, приписанные строкам, понижаем на 1.

Метки, приписанные вершинам w2, w3 и w5 на 1 повышаем. Метки b1 и b4 оставляем без изменения.

230