Сайт о телевидении

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

Предположим, что у нас имеются $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$ и к полученной матрице применяется вышеописанный алгоритм.

• 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

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

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

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

2 Решение задачи о назначениях с помощью венгерского метода 15

Заключение 20

Список использованной литературы 21

Задача о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.

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

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

Предположим, что имеется п различных работ, каждую из которых может выполнить любой из п привлеченных испол­нителей. Стоимость выполнения і-й работы j - м исполнителем известна и равна C і j (в условных денежных единицах). Необхо­димо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

В исследовании операций задача, сформулированная выше, известна как задача о назначениях. Введем переменные X ij , где X ij принимает значение 1 в случае, когда і-ю работу выполняет j-й исполнитель, и значение 0 во всех остальных случаях, i,j = 1, п . Тогда ограничение

гарантирует выполнение каждой работы лишь одним исполни­телем, ограничение

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

Таким образом, задачу о назначениях можно записать следую­щим образом:

Задача о назначениях (1) является частным случаем классической транспортной задачи, в которой надо положить При этом условие означает выполнение требова­ния целочисленности переменных x і j . Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.

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

В задаче о назначениях переменное х і j может принимать значение 0 или 1. При этом, согласно (1), в любом допусти­мом решении лишь п переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.

На практике встречаются задачи о назначениях, в поста­новках которых параметр понимается как эффективность выполнения і-й работы j - м исполнителем. В этих случаях нужно так распределить работы между исполни­телями, чтобы суммарная эффективность их выполнения была бы максимальной, т.е.

(2)

где максимум ищется при ограничениях, указанных в (1).

Параметры задачи о назначениях (1) удобно представлять матрицей , которую называют матрицей стоимости. Предположим, что и С = (c і j) - две матрицы стоимости, элементы которых связаны следующим образом:

где - некоторые постоянные. Таким образом, для получения матрицы С* нужно к элементам каждой і-й строки матрицы С прибавить число d,-, а к элементам ее каждого j - г o столбца - число Ц. В этом случае, если X - допустимое решение, удовлетворяющее ограничениям из (1), и

то с учетом ограничений из (1) типа равенства имеем

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

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

(3)

формально нельзя отнести к задачам о назначениях, поскольку коэффициенты ее целевой функции не являются положитель­ными. Это несоответствие можно преодолеть, заменив (3) эквивалентной задачей

(4)

в которой

так как в этом случае для всех имеет место неравен­ство .

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

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

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

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

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

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

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

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

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

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

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

Содержательная постановка задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Q i тонн груза (i = 1,2,…, n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве R j тонн в месяц (j = 1,2,…, n).
Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составляется матрицу С, характеризующую издержки i-го автомобиля, в случае, если он будет назначен на j-й маршрут.

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

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

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

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

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