Дискретная математика

4.

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

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

221

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

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

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

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

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

12.3.1Постановка задачи

Задача 12.2. n работников выполняют n работ. Каждый 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. Решить задачу об оптимальном назначении с матрицей

Решение.

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:

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 − 1 = 8, a3 = 7 − 1 = 6.

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

В первой строке таких элементов два:

c13 = 5 = a1 + b3 = 5 + 0; c14 = 5 = a1 + b4 = 5 + 0.

226

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

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

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

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

a1 = 5 − 1 = 4, a2 = 8 − 1 = 7, a3 = 6 − 1 = 5, a4 = 8 − 1 = 7.

Вершины из множества φ(S) приписанные им метки повышают на 1:

227

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

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

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

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

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

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

15.Проверка:

∑4

ai = 4 + 7 + 5 + 7 = 23;

i=1

∑4

bj = 0 + 2 + 1 + 1 = 4;

j=1

∑4

ai + bj = 23 + 4 = 27 = эфф (верно).

1

228

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

Поскольку |П1| = 3 ≠ |V | = 5, паросочетание П1 не является совершенным.

3. Находим множества S и φ(S):

S = {v1, v3, v4, v5}, φ(S) = {w2, w5}; |S| = 4 > |φ(S)| = 2.

Так как ребро {v2, w3} инцидентно только двум вершинам, концы ребра в множества S и φ(S) не включены.

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

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

6. Строим новый граф G2. Максимальное паросочетание П2 в данном графе совпадает с П1 и не является совершенным.

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

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

230