ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД

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

Найти вектор (матрицу) X=(x_ij, і,j=1...,n), что минимизирует целевую функцию

L(X)= c₁₁ x₁₁ +...+ c_1n x_1n +...+ c_n1 x_n1 +...+ c_nn x_nn (14.1)

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

x_i1 + ... + x_in = 1, i=1...,n (14.2)

x_1j + ... + x_nj = 1, j=1...,n (14.3)

x_ij = 0 или 1, і,j=1...,n (14.4)

где с_іj — расходы, связанные с использованием і-го исполнителя для выполнения j-ї работы (і,j=1...,n). Элементы с_іj образуют матрицу расходов C.

Задача (14.1)–(14.4) Решается венгерским методом, что основывается на том факте, что вычитание числа a_i, i=1...,n, от каждого элемента і-го строки и числа b_j, j=1...,n, от каждого элемента j-го столбца матрицы расходов C не изменяет множества оптимальных назначений. В этом понимании можно говорить, что указанные действия превращают матрицу расходов C в эквивалентную ей. В алгоритме, что дается ниже, матрицы, эквивалентные исходной матрице расходов C, называются просто матрицами расходов.

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

1. Отнимаем в матрице C от каждого элемента і-го строки минимальный элемент этой строки (i=1...,n).