Задача о назначениях
Стоимость производства детали
на станке определяется коэффициентом . Найти одно из оптимальных распределений станков и суммарную стоимость
производства.
Решение Воспользуемся алгоритмом Куна (венгерским алгоритмом).
1. Преобразуем матрицу весов. Вычтем из каждой строки
минимальный элемент. В каждой строке появится по одному нулю
Если в каком-либо столбце не оказалось ни одного нуля, с ним надо проделать такую же процедуру как и со строками: найти минимальный элемент и вычесть его из этого столбца. В данном случае таких столбцов нет
2. По преобразованной матрице весов построим матрицу смежности двудольного графа , так, что , если и , если . Получим
3. Находим наибольшее паросочетание полученного двудольного графа . Для этого можно воспользоваться алгоритмом Форда-Фалкерсона. Изображаем граф (рис. 1) и одно (любое) из его наибольших паросочетаний (рис. 2)
|