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

Задача о назначениях — задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей при условии взаимно однозначного соответствия между множествами работ и исполнителей [МакКоннелл, 2004]. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. Производительность каждого исполнителя при выполнении каждой из имеющихся работ задается заранее. Задача сводится к задаче линейного программирования. Задача о назначениях представляет собой частный случай транспортной задачи. Данная задача имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т. д. [МакКоннелл, 2004 [, [Каляев и др., 2009].

В математической модели задача представляется в виде двудольного графа, разбитого на два подмножества вершин X и Y одинаковой мощности n и множеством ребер U, соединяющих вершины из разных подмножеств. Информация о графе хранится в матрице чисел D_ij, где i, j 1, 2,…, n, представляющих собой стоимость выполнения j-й работы i-м исполнителем. Требуется найти перестановку ц из элементов множества X, такую, что значение ЦФ равно: