Задача о назначениях (задачи выбора)
Эта задача состоит в следующем. Пусть имеется
работ и
кандидатов для выполнения этих работ. Назначение кандидата
на работу
связано с затратами
. Требуется найти назначение кандидатов на все работы, дающее минимальные суммарные затраты; при этом каждого кандидата можно назначить только на одну работу и каждая работа может быть занята только одним кандидатом.
Иначе говоря, решение этой задачи представляет собой перестановку (
) чисел
; каждое из производимых назначений описывается соответствием
(
). Указанные условия единственности при этом автоматически выполняются, и нашей целью является минимизация суммы
по всем перестановкам (
).
Перед нами типичная экстремальная комбинаторная задача. Ее решение путем прямого перебора, то есть вычисления значений функции 17.1 на всех перестановках и сравнения, практически невозможно при сколько-нибудь больших
, поскольку число перестановок равно
. Попытаемся свести дело к линейному программированию.
Конечное множество, на котором задана целевая функция 17.1, представляет собой множество всех перестановок чисел
. Как известно, каждая такая перестановка может быть описана точкой в
-мерном евклидовом пространстве; эту точку удобнее всего представить в виде
-матрицы
. Элементы
интерпретировать следующим образом:
, если i-й кандидат назначается на j-ю работу,
, в противном случае.
Элементы матрицы должны быть подчинены двум условиям:
Условия 17.3 и 17.4 говорят о том, что в каждой строке и в каждом столбце матрицы
имеется ровно по одной единице. Говоря неформально, условие 17.3 означает, что каждый кандидат может быть назначен только на одну работу, а условие 17.4 — что каждая работа предназначена только для одного кандидата. (Матрицу перестановок можно получить из единичной матрицы путем некоторой перестановки ее строк.)
Теперь задача заключается в нахождении чисел
, удовлетворяющих условиям 17.2, 17.3, 17.4 и минимизирующих суммарные затраты 17.1, которые теперь можно переписать в виде
Казалось бы, что к полученной задаче методы линейного программирования непосредственно применить нельзя, ибо в силу условий 17.2 она формально является целочисленной.
Содержание Назад Вперед