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

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

Шаг 2. (Определение назначений). На этом шаге можно использовать алгоритм поиска «наибольшего паросочетания с матрицей двудольного графа (существуют и другие возможности), если все =0 матрицы заменить на «1», а >0 на «0».

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

Шаг 3 . (Модификация редуцированной матрицы). Для редуцированной матрицы стоимостей:

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

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.

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

Перейти к шагу 2.

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

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

Итерация 1

Шаг 1 . Редукция строк и столбцов.

Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5 и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.

Шаг 2 . Поиск допустимого решения, для которого все назначения имеют нулевую стоимость. Используем алгоритм поиска наибольшего паросочетания. Преобразуем матрицу в матрицу двудольного графа, затем в рабочую таблицу:

Находим паросочетание:

Это паросочетание не совершенное, т.е. полного назначения нет. На Шаг 3.

Шаг 3. Модификация редуцированной матрицы.

а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно. Для столбцов соответствующие величины равны 2, 1, 1 и 1.

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

в) Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и 1 соответственно. Для столбцов соответствующие значения равны 2, 1, 0, и 0. Поэтому мы должны выбрать столбец 1 и вычеркнуть его вертикальной линией. После этого останется только один невычеркнутый нуль – элемент (2,2). Поэтому можно вычеркнуть либо строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией, получаем следующую матрицу:

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

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

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

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

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

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

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

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

Известны различные способы решения этой задачи - распределительный, венгерский, метод потенциалов и др. Как правило, для расчетов применяется ЭВМ.  

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

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

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

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

Корнай (Kornai) Янош (р. 1928), венгерский экономист-математик, академик АН Венгерской республики. Окончил Будапештский университет (1955), работал в АН, Институте текстильной промышленности , вычислительном центре Академии наук с 1967 г. - профессор и руководитель отдела АН Венгрии, с 1986 г. - профессор экономики в Гарвардском университете. В конце 50-х гг. вместе с Т. Липтаком разработал метод решения задач блочного программирования - метод планирования на двух уровнях (см. Корнай-Липтака метод). Исследовал проблемы функционирования экономики в условиях неравновесия, взаимоотношения между дефицитом и инфляцией. Был одним из идеологов венгерской экономической реформы конца 60-х гг. Иностранный член Британской, Шведской, Финляндской академий наук , почетный член Американской академии искусств и наук, Американской экономической ассоциации почетный доктор университетов многих стран мира . Государственная премия ВНР - 1983 г.  

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

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

• 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) } #_________________________________________________________________________________

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

Методы принятия управленческих решений

РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ

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

Алгоритм решения задачи о назначениях

(венгерский метод)

, (
, что
.

Шаг 1 . Получение нулей в каждой строке

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

Шаг 2. Получение нулей в каждом столбце.

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

Шаг 3 . Поиск оптимального решения

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

Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.

Для этого необходимо отметить:

Все строки, в которых не имеется ни одного отмеченного нуля;

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

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

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

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

Шаг 5 . Перестановка некоторых нулей.

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

ПРИМЕР

руководитель,	Время выполнения i -м научным руководителем j

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

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

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

руководитель,	Время выполнения i -м научным руководителем j -го исследовательского проекта				Минимальное

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

руководитель,	а ij
Минимальное время по графе

Вычтем минимальные элементы из соответствующих столбцов.

Сделаем назначения

руководитель,	а ij

руководитель,	а ij

руководитель,	а ij

Число отмеченных (желтым цветом) нулей равно 3, т.е. назначение не является полным (3<4).

Найдем минимальный набор строк и столбцов, содержащий все нули.

руководитель,	а ij

руководитель,	а ij

руководитель,	а ij

В оставшихся клетках минимальный элемент равен 2.

руководитель,	а ij

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

руководитель,	а ij

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

руководитель,	а ij

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

руководитель,	а ij

Это назначение является полным, так как число отмеченных (желтым цветом) нулей равно 4.

Время выполнения всех (четырех) проектов:

Т =3х1+4х1+2х1+8х1=17.

Данное назначение не единственное. Если во второй строке сначала отметить не второй, а четвертый нуль, получим следующее назначение.

руководитель,	а ij

Время на выполнение всех проектов не изменилось:

Т =3х1+5х1+2х1+7х1=17.

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