Венгерский метод решения задач о назначениях. Венгерский метод решения задачи о назначениях

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

Алгоритм венгерского метода рассмотрим па примере решения задачи по заданной матрице стоимости

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

А. Решение задач на минимум затрат

1. Проводим редукцию матрицы по строкам и столбцам, как и в методе ветвей и границ


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

Минимальный элемент сокращенной матрицы (2) вычитаем из всех ее элементов и складываем его с элементами, расположенными на пересечениях вычеркнутых строк и столбцов: 12 + 2 = 14; 3 + 2 = 5 редуцированной матрицы. В результате получаем эквивалентную матрицу

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

В. Решение задач на максимум прибыли

1. Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (17) так, чтобы матрица не содержала бы отрицательных элементов:


2. Редуцируя матрицу по строкам и столбцам, получим эквивалентную матрицу

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

Пример 4.6. Распределить производство трех видов товара Т|, Т 2 , Т3 среди пяти предприятий П|, П 2 , П:(, П 4 , П-, с целью получения максимальной прибыли от продажи товаров по следующим данным:

Издержки производства с,у единицы товара (долл.)

Годовой спрос (шт.) и цепа товара (долл.)

Формируем матрицу годовой прибыли с учетом спроса (тыс. долл.)

2. Модифицируем матрицу умножением всех элементов на (-1) и сложением с максимальным числом матрицы (8000) и для устранения дисбаланса вводим два вида Т 4 , Т Г) фиктивной продукции с нулевой прибылью, поскольку матрица должна быть квадратной:

3. Редуцируем матрицу по строкам и столбцам:


4. Модифицируем матрицу путем исключения строк 4, 5 и столбцов 3, 4, получим сокращенную матрицу

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


по которой строим матрицу назначения

и по ней, наложив на матрицу исходных данных, определяем максимальное значение прибыли

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

Таблица 4.18

Должность

Качества

Директор

Ответственность, организатор, образование, опыт работы, воля, здоровье, интуиция, энтузиазм, коммуникабельность, самокритичность, уравновешенность, объективность, умение разбираться в людях, бесконфликтность, знание этикета

Менеджер

Образование, опыт, коммуникабельность, уравновешенность, работа с людьми, интуиция, целеустремленность, находчивость, сообразительность, активность, консультативное^, реакция

Экономист

Образование, аналитичность, опыт, коммуникабельность, уравновешенность, работа с людьми, интуиция, пунктуальность, бесконфликтность, умение предвидеть, уверенность, умение составлять бизнес-план, практичность

Бухгалтер

Образование, стаж, внимательность, усидчивость, любовь к счету, четкость, пунктуальность, исполнительность, ответственность, целеустремленность, умение вести контроль, неподкупность, логичность, практичность, самообладание, аналитичность, формализм, бюрократизм

Коммер

сант

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

Для примера в качестве претендентов воспользуемся такими известными литературными персонажами, как Гобсек, Чичиков, Собакевич, Плюшкин, Остап Бендер, положительные и отрицательные качества которых описаны в известных произведениях (табл. 4.19).

Таблица 4.19

Ум, хитрость, уравновешенность, твердость, практичность, осторожность, сдержанность, проницательность, образованность, ловкость, деловитость, педантичность, недоверчивость, организованность, умение разбираться в людях, ответственность, целеустремленность, умение вести контроль, логичность, энтузиазм, воля, интуиция, объективность, знание этикета, реакция, сообразительность, находчивость, воля,здоровье

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

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

Корыстолюбие, небрежность, беспринципность, жуликоватость, дерзость, меркантильность, плутовство, фантазерство, нахальство, азартность

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

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

Хозяйственность, деловитость, основательность, хваткость, умение торговаться, точность в делах, недоверчивость, обязательность, внимательность, четкость, исполнительность, умение вести контроль, практичность, здоровье, интуиция, объективность, умение разбираться в людях, целеустремленность, кругозор в товарных группах, конкурентоспособность, аналитичность, опыт, интуиция

Неуклюжесть, грубость, невежество, плутовство, подозрительность, бескультурье, нетерпимость к людям, конфликтность, безволие

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

Решение начинаем с определения веса - значимости должностных качеств (см. табл. 4.18) методом парных сравнений (см. п. 1.3), начиная с директора (табл. 4.20).

Определяем правильность заполнения матрицы:

Вес качеств определяем по формуле М; = 5,-/и 2 , результаты заносим в табл. 4.20.

Затем, сравнивая необходимые качества должности директора (см. табл. 4.20) с качествами претендентов (табл. 4.21), строим матрицу наличия качеств директора у претендентов (см. табл. 4.21) и вычисляем значения коэффициентов эффективности Су.

Наиболее подходящим кандидатом на эту должность является Гобсек, Су = 0,6224.

По результатам сравнения определяем коэффициенты эффективности су и заносим в табл. 4.22.

Аналогичным образом проводим операции сравнения по другим должностям, а полученные значения Су представим в виде матрицы эффективности (см. табл. 4.22).

Решая полученную матрицу венгерским методом на максимум, получим матрицу оптимального распределения претендентов по должностям (табл. 4.23).

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

Таблица 4.20

Качества

директора

Качества директора

1. Ответственность

2. Образование

3. Энтузиазм

4. Здоровье

5. Организатор

7. Интуиция

8. Опыт работы

9. Коммуникабельность

10. Самокритичность

11. Уравновешенность

12. Объективность

14. Знание этикета

Качества директора

Претендент

1. Ответственность

2. Образование

3. Энтузиазм

4. Здоровье

5. Организатор

7. Интуиция

8. Опыт работы

9. Коммуникабельность

10. Самокритичность

11. Уравновешенность

12. Объективность

13. Умение разбираться в людях

14. Знание этикета

Таблица 4.22

  • Tutorial

Привет, друзья! В этой статье хотел бы рассказать про интересный алгоритм из дисциплины «Исследование операций» а именно про Венгерский метод и как с его помощью решать задачи о назначениях. Немного затрону теории про то, в каких случаях и для каких задач применим данный алгоритм, поэтапно разберу его на мною выдуманном примере, и поделюсь своим скромным наброском кода его реализации на языке R. Приступим!

Пару слов о методе

Для того чтобы не расписывать много теории с математическими терминами и определениями, предлагаю рассмотреть пару вариантов построения задачи о назначениях, и я думаю Вы сразу поймете в каких случаях применим Венгерский метод:
  • Задача о назначении работников на должности. Необходимо распределить работников на должности так, чтобы достигалась максимальная эффективность, или были минимальные затраты на работу.
  • Назначение машин на производственные секции. Распределение машин так, чтобы при их работе производство было максимально прибыльным, или затраты на их содержание минимальны.
  • Выбор кандидатов на разные вакансии по оценкам. Этот пример разберем ниже.
Как Вы видите, вариантов для которых применим Венгерский метод много, при этом подобные задачи возникают во многих сферах деятельности.

В итоге задача должна быть решена так, чтобы один исполнитель (человек, машина, орудие, …) мог выполнять только одну работу, и каждая работа выполнялась только одним исполнителем.

Необходимое и достаточное условие решения задачи – это ее закрытый тип. Т.е. когда количество исполнителей = количеству работ (N=M). Если же это условие не выполняется, то можно добавить вымышленных исполнителей, или вымышленные работы, для которых значения в матрице будут нулевыми. На решение задачи это никак не повлияет, лишь придаст ей тот необходимый закрытый тип.

Step-by-step алгоритм на примере

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


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


В каждой строке и в каждом столбце должен быть только один выбранный ноль. (т.е. когда выбрали ноль, то остальные нули в этой строке или в этом столбце уже не берем в расчет). В этом случае это сделать невозможно:


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


Т.к. все минимальные элементы – нулевые, то матрица не изменилась. Проводим редукцию по столбцам:


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


Продолжаем решение дальше. Вычеркиваем строки и столбцы, которые содержат нулевые элементы (ВАЖНО! Количество вычеркиваний должно быть минимальным ). Среди оставшихся элементов ищем минимальный, вычитаем его из оставшихся элементов (которые не зачеркнуты) и прибавляем к элементам, которые расположены на пересечении вычеркнутых строк и столбцов (то, что отмечено зеленым – там вычитаем; то, что отмечено золотистым – там суммируем; то, что не закрашено – не трогаем):


Как теперь видно, в каждом столбце и строке есть только один выбранный ноль. Решение задачи завершаем!


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


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

Реализация на языке программирования R

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

Данные для решения задачи берутся из файла example.csv который имеет вид:


#Подключаем библиотеку для удобства расчетов library(dplyr) #Считываем csv фаил (первый столбик - названия строк; первая строка - названия столбцов) table <- read.csv("example.csv",header=TRUE,row.names=1,sep=";") #Проводим расчеты unique_index <- hungarian_algorithm(table,T) #Выводим cat(paste(row.names(table)," - ",names(table)),sep = "\n") #Считаем оптимальный план cat("Оптимальное значение -",sum(mapply(function(i, j) table, unique_index$row, unique_index$col, SIMPLIFY = TRUE))) #____________________Алгоритм венгерского метода__________________________________ hungarian_algorithm <- function(data,optim=F){ #Если optim = T, то будет искаться максимальное оптимальное значение if(optim==T) { data <- data %>% apply(1,function(x) (x-max(x))*(-1)) %>% t() %>% as.data.frame() optim <- F } #Редукция матрицы по строкам data <- data %>% apply(1,function(x) x-min(x)) %>% t() %>% as.data.frame() #Нахождение индексов всех нулей zero_index <- which(data==0, arr.ind = T) #Нахождение всех "неповторяющихся" нулей слева-направо unique_index <- from_the_beginning(zero_index) #Если количество "неповторяющихся" нулей не равняется количеству строк в исходной таблице, то.. if(nrow(unique_index)!=nrow(data)) #..Ищем "неповторяющиеся" нули справа-налево unique_index <- from_the_end(zero_index) #Если все еще не равняется, то продолжаем алгоритм дальше if(nrow(unique_index)!=nrow(data)) { #Редукция матрицы по столбцам data <- data %>% apply(2,function(x) x-min(x)) %>% as.data.frame() zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) if(nrow(unique_index)!=nrow(data)) { #"Вычеркиваем" строки и столбцы которые содержат нулевые элементы (ВАЖНО! количество вычеркиваний должно быть минимальным) index <- which(apply(data,1,function(x) length(x)>1)) index2 <- which(apply(data[-index,],2,function(x) length(x)>0)) #Среди оставшихся элементов ищем минимальный min_from_table <- min(data[-index,-index2]) #Вычитаем минимальный из оставшихся элементов data[-index,-index2] <- data[-index,-index2]-min_from_table #Прибавляем к элементам, расположенным на пересечении вычеркнутых строк и столбцов data <- data+min_from_table zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) #Если все еще количество "неповторяющихся" нулей не равняется количеству строк в исходной таблице, то.. if(nrow(unique_index)!=nrow(data)) #..Повторяем весь алгоритм заново hungarian_algorithm(data,optim) else #Выводим индексы "неповторяющихся" нулей unique_index } else #Выводим индексы "неповторяющихся" нулей unique_index } else #Выводим индексы "неповторяющихся" нулей unique_index } #_________________________________________________________________________________ #__________Функция для нахождения "неповторяющихся" нулей слева-направо___________ from_the_beginning <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ #Выбор индексов нулей, которые не лежат на строках i, и столбцах j find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ #Записываем индекс строки в вектор i <- c(i,as.vector(find_zero)) #Записываем индекс столбца в вектор j <- c(j,as.vector(find_zero)) #Записываем индексы в data frame (это и есть индексы уникальных нулей) index <- rbind(index,setNames(as.list(find_zero), names(index))) #Повторяем пока не пройдем по всем строкам и столбцам from_the_beginning(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________ #__________Функция для нахождения "неповторяющихся" нулей справа-налево___________ from_the_end <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ i <- c(i,as.vector(find_zero)) j <- c(j,as.vector(find_zero)) index <- rbind(index,setNames(as.list(find_zero), names(index))) from_the_end(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________


Результат выполнения программы:

Предположим, что у нас имеются $4$ склада $A_1,\ A_2,\ A_3,\ A_4$ и $4$ магазина $B_1,\ B_2,\ B_3,\ B_4$. Расстояния от каждого склада до каждого магазина заданы с помощью следующей матрицы:

Например, расстояние от $A_1$ до $B_1$ равно элементу $a_{11}=10$, расстояние от $A_2$ до $B_2$ равно элементу $a_{12}=20$, и т.д.

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

Венгерский алгоритм

  1. В каждой строке матрицы назначения находим минимальный элемент и вычитаем его из всех элементов строки.
  2. В каждом столбце полученной матрицы находим минимальный элемент и вычитаем его из всех элементов столбца.
  3. Находим строку с одним нулем. Этот ноль заключаем в квадрат и называем отмеченным. В столбце, где стоит отмеченный ноль, все остальные нули зачеркиваем и в дальнейшем не рассматриваем. Этот шаг продолжаем, пока возможно.
  4. Находим столбец с одним нулем и этот ноль отмечаем. В строке, где стоит отмеченный ноль, все остальные нули зачеркиваются. Этот шаг продолжаем, пока возможно.
  5. Если после выполнения шагов $3$ и $4$ еще остаются неотмеченные нули, то отмечаем любой их них, а в строке и столбце, где стоит отмеченный ноль, все остальные нули зачеркиваются.
  6. Если каждая строка и каждый столбец матрицы содержит ровно один отмеченный ноль, то получено оптимальное решение. Каждый из отмеченных нулей прикрепляет поставщика к потребителю. В противном случаем проводим минимальное количество пересекающихся вертикальных и горизонтальных прямых через все нули. Среди не зачеркнутых этими прямыми чисел ищем минимум. Этот минимум вычитаем их всех не зачеркнутых чисел и прибавляем ко всем числам на пересечении прямых. К полученной матрице применяем вышеприведенный алгоритм, начиная с шага $3$.

Пример решения

Находим минимальный элемент в каждой строке матрицы и вычитаем его из всех элементов строки.

В полученной матрице проделываем тоже самое со столбцами, то есть находим в каждом столбце минимальный элемент и вычитаем его из всех элементов столбца.

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

Следующая строка, в который находится ровно один ноль, это $4$-я. С ней поступаем точно так же. Больше нет строк, содержащих ровно один ноль, но имеются столбцы с одним нулем. Второй столбец содержит ровно один ноль, который мы и отметим. Поскольку этот ноль находится в $3$-й строке, то вычеркиваем все нули, находящиеся в $3$-й строке. Получим матрицу:

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

Находим минимальный элемент среди не зачеркнутых этими прямыми чисел: ${\min \left(5,\ 13,\ 7,\ 2,\ 11,\ 8\right)\ }=2$. Вычитаем найденный минимум из всех не зачеркнутых чисел и прибавляем его ко всем числам, стоящими на пересечении прямых. Получим матрицу:

Полученное распределение не является оптимальным, поскольку в $4$-й строке нет отмеченных нулей. Проводим прямые:

${\min \left(11,\ 5,\ 9,\ 6,\ 6,\ 1\right)\ }=1$. Вычитаем найденный минимум из всех не зачеркнутых чисел и прибавляем его ко всем числам, стоящими на пересечении прямых. Получим матрицу:

К полученной матрицы применяем вышеописанный алгоритм:

Видим, что в каждой строке и в каждом столбце матрицы находится ровно один отмеченный ноль. Получено оптимальное распределение. $A_1$ прикрепляем к $B_4$, $A_2$ - к $B_1$, $A_3$ - к $B_2$, $A_4$ - к $B_3$. Для того, чтобы найти суммарное распределение, нужно сложить числа, расположенные в исходной матрице на месте отмеченных нулей. Получим: $5+3+8+8=24$.

Стоит отметить, что задача о назначениях может решаться и на максимум (чтобы суммарное расстояние было максимальным). В этом случае каждый элемент матрицы умножается на $-1$ и к полученной матрице применяется вышеописанный алгоритм.

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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 (xij)m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

Если эти условия являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk (xij)m,n. Близость этой матрицы к решению задачи характеризует число Dk - суммарная невязка матрицы Хk:

В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю. Соответствующая матрица Хk является решением транспортной задачи.

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 - суммарная невязка подготовительного этапа).

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

    Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. – 436 с.

    Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.

    И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.

    Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.

    Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.

    Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.

Задача о назначениях ставится весьма естественно.

Приведём несколько вариантов постановки (как легко видеть, все они эквивалентны друг другу):

Отметим, что все приведённые выше постановки "квадратны ": в них обе размерности всегда совпадают (и равны ). На практике часто встречаются аналогичные "прямоугольные " постановки, когда , и надо выбрать элементов. Впрочем, как легко заметить, от "прямоугольной" задачи всегда можно перейти к "квадратной", добавив строки/столбцы с нулевыми/бесконечными значениями соответственно.

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

Венгерский алгоритм

Историческая справка

Алгоритм был разработан и опубликован Гарольдом Куном (Harold Kuhn) в 1955 г. Сам Кун дал алгоритму название "венгерский", потому что он был в значительной степени основан на более ранних работах двух венгерских математиков: Денеша Кёнига (Dénes Kőnig) и Эйгена Эгервари (Jenő Egerváry).

В 1957 г. Джеймс Манкрес (James Munkres) показал, что этот алгоритм работает за (строго) полиномиальное время (т.е. за время порядка полинома от , не зависящего от величины стоимостей).

Поэтому в литературе данный алгоритм известен не только как "венгерский", но и как "алгоритм Куна-Манкреса" или "алгоритм Манкреса".

Впрочем, недавно (в 2006 г.) выяснилось, что точно такой же алгоритм был изобретён за век до Куна немецким математиком Карлом Густавом Якоби (Carl Gustav Jacobi). Дело в том, что его работа "About the research of the order of a system of arbitrary ordinary differential equations", напечатанная посмертно в 1890 г., содержавшая помимо прочих результатов и полиномиальный алгоритм решения задачи о назначениях, была написана на латыни, а её публикация прошла незамеченной среди математиков.

Также стоит отметить, что первоначальный алгоритм Куна имел асимптотику , и лишь позже Джек Эдмондс (Jack Edmonds) и Ричард Карп (Richard Karp) (и независимо от них Томидзава (Tomizawa)) показали, каким образом улучшить его до асимптотики .

Построение алгоритма за

Сразу отметим во избежание неоднозначностей, что мы в основном рассматриваем здесь задачу о назначениях в матричной постановке (т.е. дана матрица , и надо выбрать из неё ячеек, находящихся в разных строках и столбцах). Индексацию массивов мы начинаем с единицы, т.е., например, матрица имеет индексы .

Назовём потенциалом два произвольных массива чисел и таких, что выполняется условие:

(Как видно, числа соответствуют строкам, а числа — столбцам матрицы.)

Назовём значением потенциала сумму его чисел:

С одной стороны, легко заметить, что стоимость искомого решения не меньше значения любого потенциала:

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

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

Зафиксируем некоторый потенциал. Назовём ребро жёстким , если выполняется:

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

Перейдём непосредственно к описанию алгоритма .

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

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

    Все рёбра паросочетания ориентируются по направлению от второй доли к первой, все остальные рёбра графа ориентируются в противоположную сторону.

    Напомним (из терминологии поиска паросочетаний), что вершина называется насыщенной, если ей смежно ребро из текущего паросочетания. Вершина, которой не смежно ни одно ребро из текущего паросочетания, называется ненасыщенной. Путь нечётной длины, в котором первое ребро не принадлежит паросочетанию, а для всех последующих рёбер происходит чередование (принадлежит/не принадлежит) — называется увеличивающим путём.

    Из всех ненасыщенных вершин первой доли запускается обход в глубину /в ширину . Если в результате обхода удалось достигнуть ненасыщенной вершины второй доли, то это означает, что мы нашли увеличивающий путь из первой доли во вторую. Если прочередовать рёбра вдоль этого пути (т.е. первое ребро включить в паросочетание, второе исключить, третье включить, и т.д.), то тем самым мы увеличим мощность паросочетания на единицу.

    Если же увеличивающего пути не было, то это означает, что текущее паросочетание — максимально в графе , поэтому в таком случае переходим к следующему пункту.

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

    Обозначим через множество вершин первой доли, которые были посещены обходом алгоритма Куна при попытке поиска увеличивающей цепи; через — множество посещённых вершин второй доли.

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

    Эта величина строго положительна.

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

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

    (Доказательство. Для этого надо показать, что по-прежнему для всех и выполняется: . Для случаев, когда или — это так, поскольку для них сумма и не изменилась. Когда — неравенство только усилилось. Наконец, для случая — хотя левая часть неравенства и увеличивается, неравенство всё равно сохраняется, поскольку величина , как видно по её определению — это как раз максимальное увеличение, не приводящее к нарушению неравенства.)

    Кроме того, старое паросочетание из жёстких рёбер можно будет оставить, т.е. все рёбра паросочетания останутся жёсткими.

    (Доказательство. Чтобы некоторое жёсткое ребро перестало быть жёстким в результате изменения потенциала, надо, чтобы равенство превратилось в неравенство . Однако левая часть могла уменьшиться только в одном случае: когда . Но раз , то это означает, что ребро не могло быть ребром паросочетания, что и требовалось доказать.)

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

    (Доказательство. Во-первых, любая вершина, которая была достижимой, достижимой и останется. В самом деле, если некоторая вершина достижима, то до неё есть некоторый путь из достижимых вершин, начинающийся в ненасыщенной вершине первой доли; а поскольку для рёбер вида сумма не меняется, то весь этот путь сохранится и после изменения потенциала, что и требовалось доказать. Во-вторых, покажем, что в результате пересчёта потенциала появилась хотя бы одна новая достижимая вершина. Но это почти очевидно, если вернуться к определению : то ребро , на котором был достигнут минимум, теперь станет жёстким, а, значит, вершина станет достижимой благодаря этому ребру и вершине .)

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

Таким образом, рано или поздно будет найден потенциал, которому соответствует совершенное паросочетание , являющееся ответом на задачу.

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

Реализацию за мы здесь приводить не будем, поскольку она всё равно получится не короче, чем описанная ниже реализация за .

Построение алгоритма за ()

Научимся теперь реализовывать тот же алгоритм за асимптотику (для прямоугольных задач — ).

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

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

Для этого мы вспомним два факта, доказанных нами выше:

Отсюда вытекают ключевые идеи , позволяющие достичь требуемой асимптотики:

Таким образом, алгоритм принимает такой вид: во внешнем цикле мы добавляем в рассмотрение строки матрицы одну за другой. Каждая строка обрабатывается за время , поскольку при этом могло происходить лишь пересчётов потенциала (каждый — за время ), для чего за время поддерживается массив ; алгоритм Куна суммарно отработает за время (поскольку он представлен в форме итераций, на каждой из которых посещается новый столбец).

Итоговая асимптотика составляет — или, если задача прямоугольна, .

Реализация венгерского алгоритма за ()

Приведённая реализация фактически была разработана Андреем Лопатиным несколько лет назад. Её отличает удивительная лаконичность: весь алгоритм помещается в 30 строк кода .

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

Массивы и хранят потенциал. Изначально он нулевой, что верно для матрицы, состоящей из нуля строк. (Отметим, что для данной реализации не важно, имеются или нет в матрице отрицательные числа.)

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

Массив содержит для каждого столбца вспомогательные минимумы, необходимые для быстрого пересчёта потенциала:

Массив содержит информацию о том, где эти минимумы достигаются, чтобы мы впоследствии смогли восстановить увеличивающую цепочку. На первый взгляд кажется, что в массиве для каждого столбца надо хранить номер строки, а также завести ещё один массив: для каждой строки запомнить номер столбца, из которого мы в неё пришли. Однако вместо этого можно заметить, что алгоритм Куна всегда попадает в строки, проходя по ребру паросочетания из столбцов, поэтому номера строк для восстановления цепочки всегда можно взять из паросочетания (т.е. из массива ). Таким образом, для каждого столбца содержит номер предшествующего столбца (или , если такого нет).

Сам алгоритм представляет из себя внешний цикл по строкам матрицы , внутри которого происходит добавление в рассмотрение -ой строки матрицы. Внутренняя часть представляет собой цикл "do-while (p != 0)", который работает, пока не будет найден свободный столбец . Каждая итерация цикла помечает посещённым новый столбец с номером (посчитанным на прошлой итерации; а изначально равным нулю — т.е. стартуем мы с фиктивного столбца), а также новую строку — смежную ему в паросочетании (т.е. ; а изначально при берётся -ая строка). Из-за появления новой посещённой строки нужно соответствующим образом пересчитать массив , заодно мы находим минимум в нём — величину , и в каком столбце этот минимум был достигнут (заметим, что при такой реализации могло оказаться равной нулю, что означает, что на текущем шаге потенциал можно не менять: новый достижимый столбец есть и без того). После этого производится пересчёт потенциала , соответствующее изменение массива . По окончании цикла "do-while" мы нашли увеличивающую цепочку, оканчивающуюся в столбце , "раскрутить" которую можно, пользуясь массивом предков .

Константа — это "бесконечность", т.е. некоторое число, заведомо большее всех возможных чисел во входной матрице .

Vector< int > u (n+ 1 ) , v (m+ 1 ) , p (m+ 1 ) , way (m+ 1 ) ; for (int i= 1 ; i<= n; ++ i) { p[ 0 ] = i; int j0 = 0 ; vector< int > minv (m+ 1 , INF) ; vector< char > used (m+ 1 , false ) ; do { used[ j0] = true ; int i0 = p[ j0] , delta = INF, j1; for (int j= 1 ; j<= m; ++ j) if (! used[ j] ) { int cur = a[ i0] [ j] - u[ i0] - v[ j] ; if (cur < minv[ j] ) minv[ j] = cur, way[ j] = j0; if (minv[ j] < delta) delta = minv[ j] , j1 = j; } for (int j= 0 ; j<= m; ++ j) if (used[ j] ) u[ p[ j] ] + = delta, v[ j] - = delta; else minv[ j] - = delta; j0 = j1; } while (p[ j0] ! = 0 ) ; do { int j1 = way[ j0] ; p[ j0] = p[ j1] ; j0 = j1; } while (j0) ; }

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

Vector< int > ans (n+ 1 ) ; for (int j= 1 ; j<= m; ++ j) ans[ p[ j] ] = j;

Стоимость найденного паросочетания можно просто взять как потенциал нулевого столбца (взятый с противоположным знаком). В самом деле, как легко проследить по коду, содержит в себе сумму всех величин , т.е. суммарное изменение потенциала. Хотя при каждом изменении потенциала изменяться могли сразу несколько величин и , суммарное изменение величины потенциала в точности равно , поскольку пока нет увеличивающей цепи, число достижимых строк ровно на единицу больше числа достижимых столбцов (только текущая строка не имеет себе "пары" в виде посещённого столбца):

int cost = - v[ 0 ] ;

Примеры задач

Приведём здесь несколько примеров на решение задачи о назначениях: начиная от совсем тривиальных, и заканчивая менее очевидными задачами:

  • максимальное паросочетание минимального веса (т.е. в первую очередь максимизируется размер паросочетания, во вторую — минимизируется его стоимость).

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

  • Дан двудольный граф, требуется найти в нём паросочетание максимальное паросочетание максимального веса .

    Решение опять же очевидно, только все веса надо умножить на минус единицу (либо в венгерском алгоритме заменить все минимумы на максимумы, а бесконечности — на минус бесконечности).

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

    Для решения мы просто строим и решаем задачу о назначениях, где в качестве весов рёбер выступают евклидовы расстояния между точками.

  • Задача детектирования движущихся объектов по локаторам : есть два локатора, которые умеют определять не положение объекта в пространстве, а лишь направление на него. С обоих локаторов (расположенных в различных точках) поступила информация в виде таких направлений. Требуется определить положение объектов, т.е. определить предполагаемые положения объектов и соответствующие им пары направлений так, чтобы минимизировать сумму расстояний от объектов до лучей-направлений.

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

  • Покрытие ориентированного ациклического графа путями : дан ориентированный ациклический граф, требуется найти наименьшее число путей (при равенстве — с наименьшим суммарным весом), чтобы каждая вершина графа лежала бы ровно в одном пути.
  • Раскраска дерева . Дано дерево, в котором каждая вершина, кроме листьев, имеет ровно сыновей. Требуется выбрать для каждой вершины некоторый цвет из цветов так, чтобы никакие две смежные вершины не имели одинакового цвета. Кроме того, для каждой вершины и каждого цвета известна стоимость покраски этой вершины в этот цвет, и требуется минимизировать суммарную стоимость.

    Для решения воспользуемся методом динамического программирования. А именно, научимся считать величину , где — номер вершины, — номер цвета, а само значение — это минимальная стоимость раскраски вершины вместе с её потомками, причём сама вершина имеет цвет . Чтобы посчитать такую величину , надо распределить остальные цветов по сыновьям вершины , а для этого надо построить и решить задачу о назначениях (в которой вершины одной доли — цвета, вершины другой доли — вершины-сыновья, а веса рёбер — это значения соответствующих динамик ).

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

  • Если в задаче о назначениях веса заданы не у рёбер, а у вершин, причём только у вершин одной доли , то можно обойтись без венгерского алгоритма, а достаточно лишь отсортировать вершины по весу и запустить обычный алгоритм Куна (более подробно см. ).
  • Рассмотрим следующий частный случай . Пусть каждой вершине первой доли приписано некоторое число , а каждой вершине второй доли — . Пусть вес любого ребра равен (числа и нам известны). Решить задачу о назначениях.

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

  • Задача о потенциалах . Дана матрица . Требуется найти два массива и такие, что для любых и выполняется , но при этом сумма элементов массивов и максимальна.

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

Литература

  • Harold Kuhn. The Hungarian Method for the Assignment Problem
  • James Munkres. Algorithms for Assignment and Transportation Problems


СХОЖИЕ СТАТЬИ