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

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

$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 она формально является целочисленной.

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