Задача о назначениях

Рассмотрим такую задачу. Фирме необходимо заполнить m вакантных должностей, на которые имеются n претендентов. Каждый из них может занять любую, но одну из предлагаемых должностей. Пусть претенденты и должности пронумерованы соответственно последовательными числами от 0 до n-1 и от 0 до m-1 (см. рис.7). В силу многих обстоятельств (способности, образование, опыт, коммуникабельность и т.п.) полезность каждого кандидата для фирмы зависит от должности, на которую он будет назначен. Пусть возможный доход фирмы за конкретный промежуток времени при принятии претендента j (j=0,1,…,n-1) на должность i (i=0,1,…,m-1) известен и равен U_i,j. Матрицу U = || U_i,j|| (i = 0,1,…,m-1; j = 0,1,…,n-1) назовем матрицей доходов. Если n<m, то при любых назначениях m-n должностей останутся нераспределенными. Если n>m, то n-m претендентов работу не получат. Определить такое назначение работников на должности, при котором фирма будет иметь наибольший доход. Подобное назначение называют оптимальным, а саму задачу - задачей о назначении [53, с.219-223]. Ясно, что оптимальное решение может оказаться не единственным.

адача 9. Одно решение задачи о назначениях. Написать рекурсивную программу-функцию, находящую одно из оптимальных решений задачи о назначениях при n претендентах, m должностях и матрице доходов U = || U_i,j|| (i = 0,1,…,m-1; j = 0,1,…,n-1).

Решение. Пусть матрица доходов U определена вне программы, то есть искомые функции могут считать её глобальным параметром.

Рассмотрим сначала случай n£m. Решением задачи могут служить функция assign() с рекурсией по номерам работников и программа-константа assign. Поскольку в данной ситуации и рекурсия, и возвраты назад реализуются по той же самой схеме, что и в предыдущих задачах, ограничимся лишь описанием параметров функции assign() и их начальных значений, подготавливаемых программой-константой assign. Решение задачи возвращается в виде вектора ot = (ot₀, ot₁ ,..., ot_n_-1, ot_n)^T, где ot_j - номер должности для работника с номером j (j = 0, 1, …, n-1), а ot_n- доход от данного оптимального назначения.

Рис. 7. Опорная схема для описания рекурсии в задаче о назначениях

Головная программа assign по размеру матрицы доходов U подготавливает фактические аргументы для рекурсивной функции assign():

n, m - количество претендентов (n) и должностей (m);

ne = (0, 0, …, 0) - нулевой вектор длины n+1 для формирования конкретного назначения и соответствующего ему дохода;

	po = (0, 0 , …, 0) - нулевой вектор меток длины n для указания в процессе формирования назначения уже занятых должностей;
	ot = (0, 0, …, 0, - ¥ ) - вектор длины n+1 для запоминания оптимального на текущий момент назначения;
	j = 0 - номер рекурсивного вызова.

Параметры функции assign(n, m, ne, po, ot, j) имеют следующий смысл:

n, m - количество претендентов (n) и должностей (m);

ne = (ne₀, ne₁ ,..., ne_n_-1, ne_n)^T - вектор, в котором последовательно формируется очередное назначение: ne_j- номер должности работника с номером j (j = 0, 1, …, n-1), ne_n - доход фирмы от данного назначения;

po - вектор меток. Если должность i в j-м рекурсивном вызове назначается работнику с номером j, то в векторе меток этот факт фиксируется следующим образом: po_i¬1. При переходе к предыдущему рекурсивному уровню или завершению построения одного из возможных назначений последняя из рассмотренных должностей высвобождается: po_i=0;

	ot - вектор, в котором при ot_n<ne_n запоминается очередное найденное назначение и соответствующий ему доход: ot¬ne;
	j - уровень рекурсивного вызова.

Для решения задачи о назначениях при n>m можно предложить любой из следующих двух способов.

Ввести n-m дополнительных фиктивных должностей с номерами m+1, m+2, …, n-1 и положить

U_i,j = -c (i = m+1, m+2,…,n-1; j = 0,1,…,n-1)

где с>0 - достаточно большое число: c>max(U_i,j). Решив вновь полученную “квадратную” задачу, получим назначение m претендентов на реальные m должностей.

Решить с помощью функции assign() и программы-константы assign задачу о назначениях для матрицы U = U^T. Фактически рекурсия будет организована не по номерам претендентов, а по номерам должностей. Поэтому полученный ответ необходимо будет интерпретировать так: ot_j- номер работника с номером должности j (j = 0, 1, …, m-1), ne_m- доход фирмы от данного назначения.

Контрольный пример. Для приведенной выше матрицы доходов U поиск какого-либо одного из оптимальных решений задачи о назначениях проводится так: assign^T = [1 0 4 5 3 2 93]. Иными словами, получено следующее назначение c доходом 93:

Номер претендента:	0	1	2	3	4	5
Номер должности:	1	0	4	5	3	2

адача 10. Все решения задачи о назначениях. Написать рекурсивную программу-функцию, находящую все оптимальные решения задачи о назначениях при n претендентах, m должностях и матрице доходов U = || U_i,j|| (i = 0,1,…,m-1; j = 0,1,…,n-1).

Решение. Пусть, как и раньше, матрица доходов U определена вне программы, то есть искомые функции могут рассматривать её как глобальный параметр. Пусть вначале n£m.

Решением задачи могут служить рекурсивная функция assi() и программа-константа assi, являющиеся аналогами соответствующих программ предыдущей задачи. Более того, здесь те же самые параметры и их начальные значения. При вычислениях по assi() в матрице ot в виде столбцов запоминаются все найденные назначения с одним и тем же доходом. При получении назначения с большим доходом матрица ot начинает формироваться заново.

Решение задачи о назначениях при n>m в данном случае проводится точно так же, как и в предыдущей задаче.

Контрольный пример. Для приведенной выше матрицы доходов U поиск всех оптимальных решений задачи о назначениях проводится так: