Задача о назначениях

Задача о назначениях

Стоимость производства детали

на станке

определяется коэффициентом

. Найти одно из оптимальных распределений станков и суммарную стоимость производства.

Решение

Воспользуемся алгоритмом Куна (венгерским алгоритмом).

1. Преобразуем матрицу весов. Вычтем из каждой строки минимальный элемент. В каждой строке появится по одному нулю

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

2. По преобразованной матрице весов построим матрицу смежности двудольного графа , так, что , если и , если . Получим

3. Находим наибольшее паросочетание полученного двудольного графа

. Для этого можно воспользоваться алгоритмом Форда-Фалкерсона. Изображаем граф (рис. 1) и одно (любое) из его наибольших паросочетаний (рис. 2)

Рис. 1

Рис. 2

Рис. 3

Образуем множества ненасыщенных паросочетанием

вершин

. Если эти множества пустые, то задача решена, найдено оптимальное решение. Из графа

составим орграф, в котором дуги, входящие в паросочетание

, направим от

, а остальные дуги от

(рис. 3).

Найдем вершины, достижимые из множества . Эти вершины образуют два множества и (на рис. 3 помечены +). В соответствии с номерами находим минимальный элемент в строках 1,2 и столбцах матрицы . Это . Вычитаем 1 из строк и добавляем 1 к столбцу