Задача про призначення найменшого числа виконавців

У прикладній математиці під задачею про призначення найменшого числа виконавців розуміється задача комбінаторної оптимізації, що узагальнює задачу про покриття множини і схожа за постановкою з задачею про призначення.

У цій задачі множина виконавців має розмір не обов'язково рівний розміру множини робіт. При цьому виконавця можна призначити для виконання декількох робіт одночасно, а на кожну роботу призначається тільки по одному виконавцю. Є загальний бюджет на виконання всіх робіт, який є обмеженням при призначенні. Потрібно знайти таке призначення виконавців для виконання робіт, щоб кількість залучених до виконання робіт виконавців була найменшою і не було перевищено виділеного на весь комплекс робіт бюджету.

Визначення

Є n виконавців і m робіт. Для кожної пари виконавець і робота задано витрати на виконання роботи $w_{i,j}$. Є загальний бюджет $w$ на виконання всього комплексу робіт. Розв'язком є підмножина виконавців U і розподіл призначення виконавців з U по роботах. Рішення допустиме, якщо призначено виконавців для всіх робіт і сума витрат не перевершує бюджету $w$. Потрібно мінімізувати кількість призначених виконавців (L). Іншими словами, потрібно підібрати найменшу за розміром (потужністю) множину виконавців, які разом зможуть виконати всі роботи.

Задачу можна розв'язати, розбивши на дві задачі:

1. Підбір найменшої за чисельністю групи виконавців, які разом зможуть виконати всі роботи і вкладуться в бюджет $w$. Ця проблема NP-складна, оскільки є узагальненням NP-повної задачі про покриття множини.
2. Призначення в підібраній групі виконавців на роботи.

Математично задачу про призначення найменшої кількості виконавців можна сформулювати так:

мінімізувати $L=\mid U\mid =\sum _{i=1}^n{\max }_{j=1}^m{x}_{ij}$

при $\sum _{i=1}^n\sum _{j=1}^m{w}_{ij}{x}_{ij}\le w.$

$\sum _{i=1}^n{x}_{ij}=1j=1,\dots ,m$;

$x_{ij}\in \{0,1\}i=1,\dots ,n,j=1,\dots ,m$.

У цій постановці цільова функція задачі нелінійна, що не дозволяє безпосередньо знайти оптимального розв'язку точними методами лінійного програмування, зокрема симплекс-методом. Однак, задачу можна лінеаризувати, включивши додаткові змінні $y_i$, що показують факт вибору в групу виконавця $i$, $y_i\in \{0,1\}i=1,\dots ,n$. Потрібно також зв'язати змінні $y_i$ і $x_{ij}$. Тоді цільова функція матиме вигляд

мінімізувати $L=\mid U\mid =\sum _{i=1}^n{y}_i$.

Зв'язок змінних можна задати такою умовою:

$y_i\le \sum _{j=1}^m{x}_{ij}\le m{y}_{i}i=1,\dots ,n$

Наближені алгоритми

Для швидкого розв'язання задач великої розмірності доцільно використовувати наближені алгоритми: алгоритм максимальної кількості мінімальних елементів (МКМЕ) і алгоритм максимальної кількості допустимих елементів (МКДЕ).

Див. також

• Задача про призначення
• Узагальнена задача про призначення