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

РЕФЕРАТ

по Теории игр и исследованию операций

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

Преподаватель Семенкина О.Э.

Студент ИМ0903б Бурцев Н.Н.

Красноярск 2013

Описание задачи

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

Математическая постановка задачи

Дана неотрицательная матрица размера n×n, где элемент в i-й строке и j-ом столбце соответствует стоимости выполнения j-ого вида работ i-м работником. Требуется так распределить работников по видам работ, чтобы суммарный эффект от их использования был максимален.

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

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

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

Запишем задачу в матричном виде:

A1	A2	A3	A4
B1	B2	B3	B4
C1	C2	C3	C4
D1	D2	D3	D4

A, B, C, D – работники, которые должны выполнить работы 1, 2, 3, 4. Элементы таблицы обозначают стоимость выполнения i-ым работником j-ой работы.

Шаг 1

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

	A2’		A4’
B1’	B2’	B3’
	C2’	C3’	C4’
D1’		D3’	D4’

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

Шаг 2

Часто на первом шаге нельзя произвести назначение. Пример:

	A2’	A3’	A4’
B1’	B2’	B3’
	C2’	C3’	C4’
D1’		D3’	D4’

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

Шаг 3

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

	A2’	A3’	A4’
B1’	B2’	B3’
	C2’	C3’	C4’
D1’			D4’

Если работник d выполняет работу 2, некому выполнять работу 3, и наоборот.

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

	A2’	A3’	A4’
B1’	B2’	B3’
	C2’	C3’	C4’
D1’			D4’

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

x
	A2’	A3’	A4’	x
B1’	B2’	B3’
	C2’	C3’	C4’	x
D1’			D4’

Теперь проводим линии через все отмеченные столбцы и неотмеченные строки.

x
	A2’	A3’	A4’	x
B1’	B2’	B3’
	C2’	C3’	C4’	x
D1’			D4’

Наша цель была: провести наименьшее количество линий (вертикалей и горизонталей), чтобы покрыть все нули-назначения.

Шаг 4

Из непокрытых линиями элементов матрицы (в данном случае это A2', A3', A4', C2', C3', C4') найти наименьший. Вычесть его из всех не отмеченных строк и прибавить ко всем пересечениям отмеченных строк и столбцов. Так, например, если наименьший элемент из перечисленных равен A2', мы получим:

x
		A3’-A2’	A4’-A2’	x
B1’+A2’	B2’	B3’
	C2’-A2’	C3’-A2’	C4’-A2’	x
D1’+A2’			D4’

Повторять процедуру (шаги 1-4) до тех пор, пока назначение не станет возможным.

Пример

2
	4
			11
4

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

0
	0
		5	0

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

x
				x
				x

3) Назначение произвести нельзя. Выполняем алгоритм из шага 4. Минимальный элемент из невычеркнуых – 2. Вычтем его из всех неотмеченных. И прибавим к элементам, стоящим на пересечении выделенных строк и столбцов.

4) В полученной матрице выполняем назначения.

Дата добавления: 2015-09-06