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

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

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

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

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

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

при ${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}w_{ij}x_{ij}\leq w.}$

${\displaystyle \sum _{i=1}^{n}x_{ij}=1\qquad j=1,\ldots ,m}$;

${\displaystyle x_{ij}\in \{0,1\}\qquad i=1,\ldots ,n,\quad j=1,\ldots ,m}$.

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

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

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

${\displaystyle y_{i}\leq \sum _{j=1}^{m}x_{ij}\leq my_{i}\qquad i=1,\ldots ,n}$

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

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