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

Первый шаг алгоритма состоит в подборе вычитаемых параметров q_i и r_j (i,j ⁼ 1,2,...,5). Подбор постоянных q_i и r_j можно осуществлять как по строкам q_i так и по столбцам r_j. Начнем со строк. Максимально возможное число q_i которое можно вычесть из стоимостей С_ij какой-либо строки i (i = 1,2,...,5), равно минимальному значению стоимости С_ij в этой строке: q_i = min {c_i1 , c_i2, c_i3, c_i4, c_i5}. Полученные значения q_i приведены в правом столбце табл. 1. Результат S_ij вычитания q_i, s_ij = c_ij - q_i, i= 1,2,...,5, помещен в табл. 2, каждая строка которой теперь содержит хотя бы одно нулевое значение S_ij. Аналогично определяем максимально возможное число r_j которое можно вычесть из стоимостей С_ij какого-либо столбца. j (j = 1,2,3,4,5), r_j= тin{ c_1j, c_2j, c_3j, c_4j, c_5j}. В табл. 2 только последний столбец B5 не содержит нулевых S_ij. Вычтем из элементов s_i5 значение r₅ = 1 и результат запишем в табл. 3. В результате каждая строка и каждый столбец содержат хотя бы по одному нулевому значению S_ij = 0, которые можно использовать для получения допустимого решения, помня, что каждая строка и столбец должны содержать только одну клетку с Х_ij = 1.

Таблица 2

Выбор min с_ij в столбце

I \ j	B1	B2	B3	B4	B5
A1	0	1	3	0	2
A2	1	2	0	1	2
A3	1	0	1	0	1
A4	0	1	2	1	2
A5	2	2	1	0	1
Min cij	0	0	0	0	1

Таблица 3

Допустимое решение

I \ j	B1	B2	B3	B4	B5
A1	0	1	3	0	1
A2	1	2	0	1	1
A3	1	0	1	0	0
A4	0	1	2	1	1
A5	2	0	1	0	0

Второй шаг алгоритма заключается в том, чтобы найти допустимое решение {Х_ij = 1}, соответствующее нулевым значениям {s_ij= 0}. Чтобы найти такое решение, рассмотрим, например, сначала строки (или столбцы), содержащие наименьшее число нулей. В каждой такой строке (или столбце) выберем и выделим один из нулей. Далее, не будем рассматривать строку (и столбец), в которых находится выделенный нуль. Продолжим эту процедуру, рассматривая оставшиеся строки (и столбцы) с наименьшим числом нулей, пока не будут выделены все возможные нули (по одному в каждой строке и в каждом столбце).

В табл. 3 строки A2 и А4, содержат по одному нулю: s₂₃ и s₄₁, поэтому выделим эти нули и положим х₂₃ = x₄₁ = 1. Строки A2 и А4 и столбцы B1 и B3 исключаем из дальнейшего рассмотрения. Затем среди оставшихся строк найдем строку с наименьшим числом нулей и повторим тот же процесс. В строке A1 остался один нуль: s₁₄ ⁼0, выделим его, положим х₁₄ = 1 и исключим строку A1 и столбец В4 из дальнейшего рассмотрения. В оставшихся строках А3 и A5 осталось по два нуля. Выберем в строке A3 клетку s₃₂ =0, выделим нуль и положим Х₃₂ = 1. Тогда в оставшейся строке А5 имеем s₅₅ = 0 и х₅₅= 1. Переменные х₁₄, x₂₃, х₃₂, х₄₁ и х₅₅ показывают оптимальную расстановку работников, которой соответствуют затраты f=4+5+5+5+6= 25. Заметим, что можно было в строке A3 выбрать s₃₅ = 0 и х₃₅ = 1, а в строке А5 - s₅₂ = 0 и x₅₂ = 1 и это не изменило бы значение f.

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

Таблица 4

Параметры задачи и выбор min c_ij в строке

i\J	B1	B2	B3	B4	B5	min cij
A1	7	8	10	8	9	7
A2	7	3	5	5	6	3
A3	6	4	6	7	8	4
A4	7	3	6	6	7	3
A5	8	5	6	7	9	5

Первый шаг алгоритма аналогичен описанному выше, и его результат представлен в табл. 5-6. На втором шаге попытаемся получить допустимое решение, выделив по одному нулевому значению S_ij = 0 в каждой строке и в каждом столбце табл. 6. В соответствии с алгоритмом в допустимое решение могут входить переменные Х₁₁, X₂₁ и X₅₃, определяемые единственным нулевым значением S_ij в соответствующих столбцах или строках. Понятно, что используя только нулевые значения Sij, нельзя построить допустимого решения.

Таблица 5

Выбор min c_ij в столбце

i\J	B1	В2	В3	В4	B5
А1	0	1	3	1	2
А2	4	0	2	2	3
А3	2	0	2	3	4
А4	4	0	3	3	4
a5	3	0	1	2	4
Min cij	0	0	1	1	2

Таблица 6

Результат 2-го шага

i\J	В1	B2	B3	B4	В5
A1	0	1	2	0	0
А2	4	0	1	1	1	!!!
А3	2	0	1	2	2	!
А4	4	0	2	2	2	!
A5	3	0	0	1	2
		!!

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

1) строки, не содержащие выделенных нулей (один !);

2) столбцы, содержащие невыделенные нули в помеченных строках (два !!);

3) строки, содержащие выделенный нуль в помеченных столбцах (три !!!).

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

В рассматриваемом примере (табл. 6) отмечены восклицательными знаками сначала строки A3 и A4 (п. 1) затем столбец В2 (п. 2) и, наконец, строка А2 (п. 3). На этом этапе больше нельзя пометить какую-либо строку или столбец. Выделим (жирной рамкой) непомеченные строки A1 и A5 и помеченный столбец В2 (табл. 7). Это минимальная совокупность строк и столбцов, содержащих все нулевые клетки.

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

Таблица 7

Результат 3-го шага

i\J	В1	В2	В3	В4	В5
A1	0	1	2	0	0
А2	4	0	1	1	1
А3	2	0	1	2	2
А4	4	0	2	2	2
А5	3	0	0	1	2

Таблица 8

Результат 4-го шага

I\j	B1	B2	B3	B4	B5
A1	0	2	2	0	0
A2	3	0	0	0	0
A3	1	0	0	1	1	!
A4	3	0	1	1	1	!!!
A5	3	1	0	1	2	!!!
		!!	!!

Используя нулевые клетки табл. 8, попытаемся найти допустимое решение, повторяя второй шаг рассмотренного выше алгоритма. В результате в допустимое решение могут войти только переменные х₁₁, х₄₂, х₅₃ и х₂₄. Так как не удается подобрать допустимое решение, то следует повторять третий, четвертый и второй шаги алгоритма до тех пор, пока не будет получено допустимое решение, соответствующее нулевым клеткам.

В решении, представленном табл. 8, на третьем шаге второй итерации отметим строку A3 затем столбцы В2 и В3 и потом строки A4, и A5. Далее выделим рамкой строки А1, А2 и столбцы В2, B3 и поместим результат в табл. 9. Элемент р=1 является наименьшим среди невыделенных элементов. Вычтем р из невыделенных элементов s_ij, прибавим р к элементам, стоящим на пересечении выделенных строк и столбцов, и запишем результат четвёртого шага в табл. 10.

Таблица 9

Результат 3-го шага

i\J	B1	B2	В3	В4	B5
A1	0	2	2	0	0
A2	3	0	0	0	0
A3	1	0	0	1	1
A4	3	0	1	1	1
А5	3	1	0	1	2

Таблица 10

Оптимальное решение

i\J	В1	В2	B3	B4	B5
A1	0	3	3	6	0
A2	3	1	1	0	0
A3	0	0	0	0	0
A4	2	0	1	0	0
А5	2	1	0	0	1

С нулевыми значениями {Sij} этого решения можно связать допустимое решение х₂₅, х₁₁, х₄₂, х₃₃ и х₅₄, причем переменные указаны в порядке их определения. Суммарные затраты f при таких назначениях определяются исходными затратами:

ЗАДАЧА 2