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

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

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

3. Оптимальным назначениям будут соответствовать нулевые элементы, полученные на предыдущем шаге.

4. Если не получено оптимальное решение, то нужно выполнить действия:

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

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

в) Если новое распределение нулевых элементов не позволяет построить решение, повторить шаг 4 а).

Пример 2.7.2. Решить задачу о назначениях 2.7.1. венгерским методом.

места исполнители	B1	B2	B3	B4	B5
А1	10	13	9	11	2
А2	9	12	8	3	4
А3	7	5	4	5	8
А4	4	6	4	7	9
А5	8	1	3	2	6

Решение. В строке А₁ минимальное число 2, вычтем его из всех элементов этой стоки. Аналогично, в строке А₂ – 3, А₃ – 4, А₄ – 4, А₅ – 1. В результате получим таблицу 2.7.3.

Таблица 2.7.3.

места исполнители	B1	B2	B3	B4	B5
А1	8	11	7	9	0
А2	7	9	5	0	1
А3	3	1	0	1	4
А4	0	2	0	3	5
А5	7	0	2	1	5

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

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

места исполнители	B1	B2	B3	B4	B5	B6	B7
А1	2	3	4	1	5	6	7
А2	4	3	1	2	5	6	9
А3	3	3	9	10	5	5	4
А4	4	5	4	6	7	9	10
А5	3	4	4	5	6	9	8
А6	4	5	5	7	8	1	2
А7	4	3	4	1	2	3	5

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

Таблица 2.7.4

места исполнители	B1	B2	B3	B4	B5	B6	B7
А1	1	2	3	0	4	5	6
А2	3	2	0	1	4	5	8
А3	0	0	6	7	2	2	1
А4	0	1	0	2	3	5	6
А5	0	1	1	2	3	6	5
А6	3	4	4	6	7	0	1
А7	3	2	3	0	1	2	4

В столбцах, которые не содержат нулевых значений, найдем минимальные числа, и, вычтем их из элементов соответствующего столбца. Это столбцы B₅ и B₇. В результате получим таблицу 2.7.5, в которой не получено оптимальное решение. В таблице 2.7.5 выделим минимальное число горизонтальных и вертикальных строк и столбцов с тем, чтобы выделить все нулевые элементы. Это столбцы B₁, B₃, B₄, и, строки А₃, А₆, А₇.

Таблица 2.7.5

места исполнители	B1	B2	B3	B4	B5	B6	B7
А1	1	2	3	0	3	5	5
А2	3	2	0	1	3	5	7
А3	0	0	6	7	1	2	0
А4	0	1	0	2	2	5	5
А5	0	1	1	2	2	6	4
А6	3	4	4	6	6	0	0
А7	3	2	3	0	0	2	3

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

Таблица 2.7.6

места исполнители	B1	B2	B3	B4	B5	B6	B7
А1	1	1	3	0	2	4	4
А2	3	1	0	1	2	4	6
А3	1	0	7	8	1	2	0
А4	0	0	0	2	1	4	4
А5	0	0	1	2	1	5	3
А6	4	4	5	7	6	0	0
А7	4	2	4	1	0	2	3

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

z = 1 + 1 + 4 + 4 + 4 + 1 + 2 = 17.