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

10.07.2019

Метод представляет собой процедуру, состоящую из следующих шагов:

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

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

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

III.Практическая часть. Задача о назначениях.

Решение венгерским методом

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

Для нахождения оптимального решения воспользоваться «венгерским методом».

Строим матрицу:

Решим ее венгерским методом.

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

68 72 74 83 0 4 6 15

56 60 58 63 Получим 0 4 2 7

38 40 35 45матрицу: 3 5 0 10

47 42 40 45 7 2 0 5

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

0 4 6 15 0 2 6 10

3 5 0 10 3 3 0 5

7 2 0 5 7 0 0 0

3.Определяем число нулей в каждой строке: 1-1, 2-1, 3-1, 4-3и в каждом столбце: 1-2, 2-1, 3-2, 4-1. Максимальное число нулей (3) содержит 4-я строка и 1-й и 3-й столбец. Минимальным числом прямых вычеркнем все нули в матрице. Среди не вычеркнутых элементов выберем минимальный (выделен полужирным курсивом и подчеркнут – 2).

0 2 6 10

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

Получим скорректированную матрицу с назначениями для нулевых клеток:

Вычеркнем из матрицы ненужные нули:

0 0 7 8

0 0 2 0

3 1 0 3

9 0 2 0

Теперь требование о размещении четырех назначений в клетки с нулевой стоимостью выполняется, следовательно полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы 1-к потребителю 1, с базы 2- к потребителю 2, с базы 3 – к потребителю 3 и с базы 4 – к потребителю 4. В результате в начальной таблице суммируются клетки, соответствующие выбранным элементам итоговой таблицы(по диагонали – 68+60+35+45=208), это и будет минимальное решение данной задачи.

Ответ: заказы по сбытовым базам распределены оптимально, общая дальность минимальна – 208 км.

ЗАКЛЮЧЕНИЕ

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

Суть венгерского метода состоит в следующем: путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. Набор нулей называется системой независимых нулей, если какие два9или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то приняв соответствующие им переменные xij равными 1, а все остальные – равными 0, получаем оптимальный план назначения.

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ И ИСТОЧНИКОВ

1. Агальцов, В.П. «Математические методы в программировании»: учебник. В.П. Агальцов, И.В. Волдайская. - М.: ИД «ФОРУМ»: ИНФРА-М, 2009 г.

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

3. Ашманов С.А. «Линейное программирование»,- М.: 2011г.

4. Балдин.К.В. «Математическое программирование»/ К.В.Балдин – М: Издательство «Дашков и К», 2009.

5. Васильев Ф.П., «Линейное программирование»/ Ф.П., Васильев, А.Ю. Иваницкий,2009.

6. Вершик А.М. «О Л.В. Канторовиче и линейном программировании»,2010г

7. Глебова Н.В. «Применение методов линейного программирования для решения экономических задач»: учебно –методическое пособие для студентов 3 курса ВВАГС, 2001 г.

8. Карасев А.Н. «Математические методы в экономике»/ А.Н.Карасев,Н.Ш.Кремер,Т.Н.Савельева,2010.

9. Лищенко А.В., «Линейное и нелинейное программирование»,2011.

10. Партыка, Т.Л. «Математические методы»: учебник. / Т.Л. Партыка, И.И.2009г.

11. Цирель, С. В. «Венгерский способ»/ С. Цирель. Москва: УРСС, 2007 г.

12. Шапкин, А.С. «Математические методы» / А. Шапкин. Учебник. Москва, 2010 г.

Вершик А.М. «О Л.В. Канторовиче и линейном программировании»,2010г.,с.45

Агальцов, В.П. «Математические методы в программировании»: учебник. В.П. Агальцов, И.В. Волдайская. - М.: ИД «ФОРУМ»: ИНФРА-М, 2009 г. - 224 с.: ил.

Шапкин, А.С. «Математические методы» / А. Шапкин. Учебник. Москва, 2010.- 104 с.

Ашманов С.А. «Линейное программирование»,- М.: 2011г,с.235

Балдин.К.В. «Математическое программирование»/ К.В.Балдин – М: Издательство «Дашков и К», 2009.с.67

Васильев Ф.П., «Линейное программирование»/ Ф.П., Васильев, А.Ю. Иваницкий,2009,с.76

Шапкин, А.С. «Математические методы» / А. Шапкин. Учебник. Москва, 2010- 100 с

Лищенко А.В., «Линейное и нелинейное программирование»,2011.С.84

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

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

Карасев А.Н. «Математические методы в экономике»/ А.Н.Карасев,Н.Ш.Кремер,Т.Н.Савельева,2010.с.35

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

Цирель, С. В. «Венгерский способ»/ С. Цирель. Москва: УРСС, 2007.- 120 с.

Цирель, С. В. Венгерский способ/ С. Цирель. Москва: УРСС, 2007.- 120 с.

Глебова Н.В. «Применение методов линейного программирования для решения экономических задач»: учебно –методическое пособие для студентов 3 курса ВВАГС, 2001.,с.53

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

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

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

3. Графы

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

Двудольный граф – граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. В нашей задаче тоже есть четкое разделение: одни вершины – это разработчики, другие – задачи, и связи (эффективность владения) есть только между разработчиками и задачами.
Паросочетанием неориентированного графа G называется подмножество M его ребер E, выбранное так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах нашей задачи синонимом этому будет «назначение» , чтобы каждый задействованный разработчик взял на себя отдельную задачу. И не получилось такого, что два разработчика прорабатывают одну проблему, или один «бедняга» отвечал за две задачи.

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

4. Максимальное паросочетание

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

Как же увеличить паросочетания (назначения)?

Выберем незадействованного разработчика, которому еще не назначена задача. Посмотрим, с чем бы он мог справиться, т.е. знакомые ему технологии. Если нашли среди них свободную – отлично, это то, что мы и искали. Назначаем. А если задача уже «занята» другим разработчиком? Попробуем занятому разработчику подыскать другую свободную технологию, ведь в таком случае эту - мы бы назначили нашему незадействованному подопечному. В общем, из вершины незадействованного разработчика или разработчика, которому мы пытаемся переназначить задачу, мы просматриваем все знакомые ему технологии на наличие свободной:

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

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

Добавим еще немного терминологии из теории графов, простыми словами:

Экспонированная вершина – это вершина, которая не участвует в текущем паросочетании. Т.е. либо «незадействованный разработчик», либо «свободная задача».
Альтернирующая цепь – это цепь, ребра которой попеременно лежат или не лежат в паросочетании. (…- владение технологией – назначенная задача – владение технологией – назначенная задача - …)
Альтернирующее дерево – дерево, состоящее из альтернирующих цепей
Аугментальная цепь – это такая альтернирующая цепь, начальная и конечная вершины которой экспонированы. Вот как называется то, что мы и ищем! =)
Аугментальное дерево – соответственно дерево, в котором хотя бы одна из веток – это аугментальная цепь.

Вот и нашли способ наращивать паросочетание, стремясь получить максимальное. Нужно строить альтенирующее дерево. Когда оно станет аугментальным, искать аугментальные цепи из «незадействованного разработчика» в «свободную задачу» и потом «переназначать» задачи вдоль них. Это выгодно, т.к. увеличивает количество «задач в обработке» на 1:

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

5. Венгерский метод.

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

Мы бы для начала всем разработчикам до упора назначили задачи в соответствии с их максимальными способностями. Если всем разработчикам удалось сразу же распределить задачи - отлично. Но такое происходит не часто. Вдруг два человека, оптимально владеют одной и той же технологией, кому она достанется и что делать в этой ситуации? Одному из разработчиков нужно будет подыскать иную свободную задачу, так же наиболее соответствующую его способностям. Если при текущих (максимальных требованиях) условиях не найдется свободной задачи, то нужно будет попробовать подыскать среди задач, предварительно немного занизив наши требования. Как бы искусственно занизить способности разработчиков в графе. Если в таких условиях обнаружим свободную задачу – получим аугментальное дерево. «Поменяем» по цепочке паросочетания, после чего будет +1. И продолжим назначать таким вот оптимальным образом, пока всем не подыщем работу.

Стратегия ясна.

Мы почти разгадали принцип Венгерского алгоритма. Но как все же построить решение по принципу «жадных алгоритмов»: до упора назначить по max способностям, потом чуть занизить способности и добавив к рассмотрению новые задач, до упора назначить их, занизить… и.т.д.? Как оценить способности и оптимальность текущего назначения?

Вся «фишка» этого алгоритма заключается в следующем. Нам дан всего один параметр в графе – эффективность решения определенной задачи разработчиком, что указано на ребрах. Эта величина присвоена парам разработчик-задача. Мы же «разделим» (отделим от пар) эти величины на две. Искусственно добавим два дополнительных параметра. Одни величины будут приписаны вершинам задач, другие - вершинам разработчиков.

Попробую привести такую интерпретацию:

у разработчиков мы укажем их «способности» , допустим в единицах «сил», просто указывающие на то, насколько эффективно мы можем их задействовать или задействовали.
у задач мы укажем их «изученность» , или, если можно так выразиться, «переизбыток внимания». Этот параметр будем так же измерять в «силе». Переизбыток внимания к задаче возникает в следующей ситуации. Если мы какого-то разработчика «недогрузили», т.е. он способен решать задачу на 5, а ему досталась всего на 3. То у него остается еще 2 «силы» которые он, в принципе, может уделить какой-то из знакомых ему задач. Бегать между кабинетов, консультировать по телефону, давать советы тем, кто занимается любимой ему технологией.

Таким образом, величины указанные на ребрах мы «разделим» на 2 значения, приписанных уже вершинам: эффективность решения задачи = способность разработчика + изученность задачи. В принципе, логично. Чем способней разработчик или чем более известна технология, тем лучше будет реализована эта часть в проекте. Эффективней.

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

6. Описание алгоритма

Инициализируем граф. Будучи «упертыми оптимистами », мы для каждого разработчика рассчитаем его максимальную «способность» по знакомым ему технологиям, и присвоим ему это число. Everyone enjoys doing the kind of work for which he is best suited . О задачах пока ничего неизвестно, поэтому их «изученность» инициализируем нулями.

При поиске «свободной задачи» для «незадействованного разработчика» мы ограничимся теперь только (назовем их) оптимальными ребрами графа, т.е. теми, для которых выполняется равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина) .

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

Удалось обнаружить свободную задачу. Дерево стало аугментальным. «Переназначаем» задачи, наращиваем паросочетание. Начинаем строить альтернирующее дерево заново, т.к. мало ли как там граф изменился
Мы не нашли (не достигли) свободную задачу по оптимальным ребрам. А она есть, т.к. начинали ведь мы со свободного разработчика, а в графе у нас одинаковое количество задач и разработчиков. Полученное альтернирующее дерево становится, так называемым, Венгерским (весь метод так же называется). В данном случае нам нужно будет немного понизить наши требования к разработчикам и начать поиски заново. Failure is simply the opportunity to begin again, this time more intelligently (с) .

Вот и подошли к последнему моменту Венгерского метода для чего все эти дополнительные параметры и «способности» задумывались. Допустим, что, наращивая альтернирующее дерево, мы в конечном итоге получили - Венгерское дерево. Рассмотрим, какие вершины попадут в это дерево:

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

Снаружи этого дерева, в оставшемся графе будут присутствовать:

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

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

После чего внутри венгерского дерева мы:

Понизим способности разработчиков на delta, чтобы «присоединить» наименее безболезненным способом, по крайней мере, одно ребро к альтернирующему дереву, по которому в следующий раз будем продолжать поиски свободной задачи
Повысим «изученность» задач на delta, чтобы внутри уже сейчас построенного аугментального графа ребра - остались оптимальными. Т.е. чтобы сохранилось равенство: эффективность решения задачи (ребро) = способность разработчика (вершина) + изученность задачи (вершина)

Мини-интерпретация: мы понижаем способности разработчикам, чтобы впоследствии «пристроить» хотя бы одного из них. Мы его пристроим, но он будет работать не в соответствии со своей квалификацией. Он бы смог большего. Поэтому у него высвобождается некоторое количество времени, чтобы проконсультировать коллег по задаче, в которой он наиболее компетентен. Она становится более изученной в команде. Ей в свою очередь наверняка занимался другой разработчик, который теперь тоже сможет подменяться в случае чего. Можно понизить и его компетенцию на изученность задачи. И так далее «по цепочке» в команде повышается «изученность» задач и немного понижаются способности разработчиков, чтобы найти им назначения.

Все. Все шаги данного метода рассмотрены. Продолжаем в том же духе… Success is not final, failure is not fatal: it is the courage to continue that counts .

7. Алгоритм словами, очень кратко

Соберем теперь все до кучи:

Инициализация. Разработчикам – max способности. Задачи – не изучены.
Пока не всем разработчикам нашли задачи.
- Пока удается построить аугментальное дерево (находить свободные задачи) по оптимальным ребрам
  - «Переназначаем» задачи, увеличивая паросочетания
- Не достигли свободной задачи. Венгерское дерево.
  - Понижаем способности разработчиков на min величину

8. Листинг

Код, конечно, будет покороче, чем все мое описание. =)

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

int n;
vector < vector > a; // Матрица эффективности a[разраб][задача]
vector xy, yx; // Паросочетания: xy[разраб], yx[задача]
vector vx, vy; // Альтернирующее дерево vx[разраб], vy[задача]
vector maxrow, mincol; // Способности, изученность
bool dotry (int i) {
if (vx[i]) return false ;
vx[i] = true ;
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0)
vy[j] = true ;
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) {
xy[i] = j;
yx[j] = i;
return true ;
}
for (int j=0; jif (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) {
xy[i] = j;
yx[j] = i;
return true ;
}
return false ;
}
int main() {
// ... чтение a ...
Mincol.assign (n, 0);
minrow.assign (n, 0);
for (int i=0; ifor (int j=0; j maxrow[i] = max (maxrow[i], a[i][j]);
Xy.assign (n, -1);
yx.assign (n, -1);
for (int c=0; c vx.assign (n, 0);
vy.assign (n, 0);
int k = 0;
for (int i=0; iif (xy[i] == -1 && dotry (i))
++k;
c += k;
if (k == 0) {
int z = INF;
for (int i=0; iif (vx[i])
for (int j=0; jif (!vy[j])
z = min (z, maxrow[i]+mincol[j]-a[i][j]);
for (int i=0; iif (vx[i]) maxrow[i] -= z;
if (vy[i]) mincol[i] += z;
}
}
}
int ans = 0;
for (int i=0; i ans += a[i]];
printf ("%d\n" , ans);
for (int i=0; i printf ("%d " , xy[i]+1);
}
* This source code was highlighted with Source Code Highlighter .

9. Итого

Если кто-то видит Венгерку впервые. И после прочтения описания, а за ним листинга – возникнет уверенное впечатление «да тут по листингу и без этих описаний все понятно, что было распинаться». Буду все же надеяться, что хоть отчасти описание добавило понимания в работу алгоритма. Буду искренне рад за Вас! а мне, в свою очередь, это немного даст почувствовать, что писал, наверное, не зря. =)

Теги:

задача о назначениях
венгерский алгоритм
алгоритм Куна

Добавить метки

Задача о назначениях

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

Задача о назначении на узкие места

ЛЕКЦИЯ 13. Задачи о назначении. Венгерский алгоритм

Эта задача решается описанным выше алгоритмом. Вот ее постановка.

Имеется n рабочих мест на некотором конвейере и n рабочих, которых нужно на эти рабочие места расставить; известна производительность c ij рабочего i на рабочем месте j . Тот факт, что при некотором распределении на рабочие места рабочий i k попадает на рабочее место j k можно описать следующей таблицей:

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

Задача состоит в том, чтобы максимизировать

Шаг 0. Фиксируем матрицу производительностей и любое назначение на рабочие места. Пусть s - минимальная производительность при этом назначении. Построим рабочую таблицу тех же размеров, что и матрица C ; в клетку с номером (ij ) в этой таблице проставим символ «´», если ; в противном случае эту клетку оставим пустой.

Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шагу, как рабочую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, минимальной производительностью. Обозначим ее снова через s и вернемся к Шагу 0. Если же число ребер окажется меньше n , то имеющееся назначение на рабочие места уже оптимально.

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

Пример 13.1 . Требуется распределить m работ (или исполнителей) по n станкам. Работа i (i =1,...,m ), выполняемая на станке j (j=1,...,n ), связана с затратами. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат c ij .

Пример 13.2. C= (c ij ) – стоимость производства детали i на станке j нужно найти распределение станков так чтобы суммарная стоимость производства была минимальной.

Пример 13.3. Транспортная задача. Заданы пункты производства товара, пункты потребления товара. Требуется определить оптимальное взаимно-однозначное соответствие между пунктами производства и пунктами потребления, исходя из матрицы стоимостей перевозок C между соответствующими пунктами (т.е. минимизировать суммарную стоимость перевозки).

Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1. Аналогично спрос в каждом пункте назначения равен 1. Стоимость «перевозки» (прикрепления) работы i к станку j равна c ij . Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость берется равной очень большому числу.

Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n .

Пусть = 0, если j -я работа не выполняется на i -м станке, = 1, если j -я работа выполняется на i -м станке. Таким образом, решение задачи может быть записано в виде двумерного массива . Допустимое решение называется назначением . Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы и ровно одного элемента в каждом столбце этой матрицы.

Замечание 1. Для заданного значения n существует n ! допустимых решений.

Математическая модель задачи:

Минимизировать функцию , при ограничениях:

, (12.1)

, (12.2)

Ограничения (12.1) необходимы для того, чтобы каждая работа выполнялась ровно один раз. Ограничения (12.2) гарантируют, что каждому станку будет приписана ровно одна работа.

Пример 13.4. Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками. Стоимость производства детали i на станке j :

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

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

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

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

Оптимальное назначение: , , , остальные , .

К сожалению, не всегда удается определить решение так просто. Для таких случаев рассмотрим следующий алгоритм.

Шаг 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 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.

Теорема 1.

Для того чтобы вариант назначения был оптимальным, необходимо и достаточно существование чисел таких, что

для из базиса

Метод потенциалов

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

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

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

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

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

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

Рассмотри задачу о назначениях с матрицей эффективностей

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

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

Теорема 2 (Эгервари).

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

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

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

Предварительный этап

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

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

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

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

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

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

Основной этап

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

Если число отмеченных звездочкой нулей равно , то процесс окончен: места, занимаемые нулями со звездочкой, соответствуют переменным равным 1, в оптимальном варианте назначения.

Если нулей со звездочкой меньше , то

2. Помечаем знаком «+» сверху столбцы матрицы, в которых есть , и считаем эти столбцы занятыми.

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

Если в матрице нет незанятых нулей, то переходим к пункту 5.

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

3. Столбец, в котором находится , лежащий в той же строке, что и только что отмеченный штрихом нуль, считаем снова незанятым и знак «+» сверху снимаем. Строку, в которой находится наш объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу пункта 2.

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

Снимаем все пометки, кроме звездочек, и возвращаемся ко второму абзацу пункта 1.

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