Комбинаторные алгоритмы для программистов



             

Задача о назначениях (задачи выбора)


Эта задача состоит в следующем. Пусть имеется

n
работ и
n
кандидатов для выполнения этих работ. Назначение кандидата
i
на работу
j
связано с затратами
c_{ij}
(i,j=1,2,\ldots,n)
. Требуется найти назначение кандидатов на все работы, дающее минимальные суммарные затраты; при этом каждого кандидата можно назначить только на одну работу и каждая работа может быть занята только одним кандидатом.

Иначе говоря, решение этой задачи представляет собой перестановку (

p_1,p_2,\ldots,p_n
) чисел
(1, 2, \ldots, n)
; каждое из производимых назначений описывается соответствием
i\to p_i

(

i=1,\ldots,n
). Указанные условия единственности при этом автоматически выполняются, и нашей целью является минимизация суммы

 \sum_{i=1}^n c_{ip_i}

(17.1)

по всем перестановкам (

p_1,p_2,\ldots,p_n
).

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

n
, поскольку число перестановок равно
n!=1\cdot 2\cdot 3\cdots (n-1)n
. Попытаемся свести дело к линейному программированию.

Конечное множество, на котором задана целевая функция 17.1, представляет собой множество всех перестановок чисел

(1, 2, \ldots, n)
. Как известно, каждая такая перестановка может быть описана точкой в
n^2
-мерном евклидовом пространстве; эту точку удобнее всего представить в виде
n\times n
-матрицы
X=\|x_{ij}\|
. Элементы
x_{ij}
интерпретировать следующим образом:

 x_{ij}=1
, если i-й кандидат назначается на j-ю работу,

 x_{ij}=0
, в противном случае.

Элементы матрицы должны быть подчинены двум условиям:

\sum_{j=1}^{n}x_{ij}=1,\quad i=1,2,\ldots, n,

(17.3)

\sum_{i=1}^{n}x_{ij}=1,\quad j=1,2,\ldots, n.

(17.4)

Условия 17.3 и 17.4 говорят о том, что в каждой строке и в каждом столбце матрицы

X
имеется ровно по одной единице. Говоря неформально, условие 17.3 означает, что каждый кандидат может быть назначен только на одну работу, а условие 17.4 — что каждая работа предназначена только для одного кандидата. (Матрицу перестановок можно получить из единичной матрицы путем некоторой перестановки ее строк.)

Теперь задача заключается в нахождении чисел

x_{ij}
, удовлетворяющих условиям 17.2, 17.3, 17.4 и минимизирующих суммарные затраты 17.1, которые теперь можно переписать в виде

\sum_{i=1}^{n}\sum_{j=1}^nc_{ij}x_{ij}.

(17.5)

Казалось бы, что к полученной задаче методы линейного программирования непосредственно применить нельзя, ибо в силу условий 17.2 она формально является целочисленной.


Содержание  Назад  Вперед