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

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

Найти вектор (матрицу) 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).

2. Отнимаем от каждого элемента j-го столбца преобразованной матрицы расходов его минимальный элемент (j=1...,n). В результате выполнения двух пунктов каждая строка и каждый столбец матрицы расходов имеют по крайней мере один 0.

3. Просматриваем последовательно строки матрицы расходов, начиная с первого. Если строка имеет лишь один необозначенный 0, помечаем его отметкой * но зачеркиваем (с помощью отметки ^) остальных нулей в этом же столбце. 0 считается обозначенным, если он имеет отметку*. Повторяем эти действия, пока каждая строка не будет иметь необозначенных нулей, или будет иметь их по крайней мере два.

4. Действия п. 3 повторяем для всех столбцов матрицы расходов.

5. Действия п.п. 3 и 4 повторяем последовательно (если необходимо) пока не случится один из трех возможных случаев:

i) каждая строка имеет назначение (имеет 0 с отметкой *);

ii) есть по крайней мере два необозначенных нуля в некоторых строках и некоторых столбцах матрицы расходов;

iii) нет необозначенных нулей и полное назначение еще не получено (число нулей с отметкой * меньше n).

В случае и) задача об оптимальных назначениях развязана: xij, что отвечают 0*, равняются 1, остальные — 0, конец. В случае ii) произвольно выбираем один из необозначенных нулей, помечаем его отметкой *, зачеркиваем остальных нулей в той же строке и в том же столбце и возвращаемся к п. 3. В случае iii) переходим к п. 7.

7. Помечаем отметкой # строки, для которых не полученное назначение (в которых нет 0*). Такие строки считаем обозначенными, остальные — необозначенными. Аналогично называются и столбцы матрицы расходов.

8. Помечаем отметкой # еще необозначенные столбцы, которые имеют зачеркнутый 0 (обозначен отметкой ^) в обозначенных строках.

9. Помечаем отметкой # еще необозначенные строки, которые имеют назначение (то есть 0*) в обозначенных столбцах.

10. Повторяем действия п.п. 8 и 9 до тех пор, пока больше нельзя будет пометить ни одну строку и столбец матрицы расходов.

11. Вычеркиваем (с помощью отметки &) необозначенные строки и обозначенные столбцы матрицы расходов.

12. Находим минимальный невычеркнутый элемент матрицы расходов, отнимаем его от элементов каждой из невычеркнутых строк, добавляем к элементам всех вычеркнутых столбцов и переходим к п. 3. При этом отметки элементов матрицы расходов (* но ^) теряют свою силу.

Замечание.

1. Если в задаче об оптимальных назначениях (14.1)–(14.4) целевую функцию (14.1) нужно максимизировать, то для ее решения можно применить венгерский метод, заменив матрицу C на – C.

2. За определением в задаче об оптимальных назначениях матрица расходов квадратная. Если матрица C не является квадратной, то она превращается к такой добавлением необходимого числа дополнительных строк или столбцов с соответствующими элементами cij=0. В 1-м случае работы, что получили оптимальные назначения в дополнительных строках, остаются без исполнителей. В 2-м — исполнители, которые получили оптимальные назначения в дополнительных столбцах, остаются без работы.

Программное обеспечение.

Обучающий модуль, с помощью которого задача об оптимальных назначениях решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО – МО.