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

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

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

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

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

# Підбір найменшої за чисельністю групи виконавців, які разом зможуть виконати всі роботи і вкладуться в бюджет <math>w</math>. Ця проблема NP-складна, оскільки є узагальненням NP-повної [[Задача про покриття множини|задачі про покриття множини]].
# Призначення в підібраній групі виконавців на роботи.

Математично задачу про призначення найменшої кількості виконавців можна сформулювати так<ref>Катаев А.В., Катаева Т.М., Коженко Я.В. Оптимизация численного состава команды проекта: экономико-математический инструментарий / А. В. Катаев, Т. М. Катаева, Я. В. Коженко // Конкурентоспособность в глобальном мире: экономика, наука, технологии. 2016. – № 8-3 (22). – С. 101-104</ref>:

: мінімізувати <math>L = \mid U \mid = \sum_{i=1}^n \max_{j=1}^m x_{ij}</math>
: при <math>\sum_{i=1}^n\sum_{j=1}^m w_{ij} x_{ij} \le w.</math>
:: <math> \sum_{i=1}^n x_{ij}=1 \qquad j=1, \ldots, m</math>;
:: <math> x_{ij} \in \{0,1\} \qquad i=1, \ldots, n, \quad j=1, \ldots, m</math>.

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

: мінімізувати <math>L = \mid U \mid = \sum_{i=1}^n y_{i}</math>.

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

: <math> y_{i} \le \sum_{j=1}^m x_{ij} \le my_{i} \qquad i=1, \ldots, n</math>

== Наближені алгоритми ==
Для швидкого розв'язання задач великої розмірності доцільно використовувати наближені алгоритми: алгоритм максимальної кількості мінімальних елементів (МКМЕ) і алгоритм максимальної кількості допустимих елементів (МКДЕ)<ref>Катаев А.В., Катаева Т.М. Управление проектами на базе динамической сети партнеров: монография. – Ростов-на-Дону – Таганрог: Издательство Южного федерального университета, 2017. – 125 с.</ref>.

== Див. також ==

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

== Примітки ==
{{Reflist}}
[[Категорія:Дослідження операцій]]
[[Категорія:Комбінаторика]]
[[Категорія:NP-повні задачі]]