У прикладній математиці під задачею про призначення найменшого числа виконавців розуміється задача комбінаторної оптимізації, що узагальнює задачу про покриття множини і схожа за постановкою з задачею про призначення.
У цій задачі множина виконавців має розмір не обов'язково рівний розміру множини робіт. При цьому виконавця можна призначити для виконання декількох робіт одночасно, а на кожну роботу призначається тільки по одному виконавцю. Є загальний бюджет на виконання всіх робіт, який є обмеженням при призначенні. Потрібно знайти таке призначення виконавців для виконання робіт, щоб кількість залучених до виконання робіт виконавців була найменшою і не було перевищено виділеного на весь комплекс робіт бюджету.
Визначення
Є n виконавців і m робіт. Для кожної пари виконавець і робота задано витрати на виконання роботи . Є загальний бюджет на виконання всього комплексу робіт. Розв'язком є підмножина виконавців U і розподіл призначення виконавців з U по роботах. Рішення допустиме, якщо призначено виконавців для всіх робіт і сума витрат не перевершує бюджету . Потрібно мінімізувати кількість призначених виконавців (L). Іншими словами, потрібно підібрати найменшу за розміром (потужністю) множину виконавців, які разом зможуть виконати всі роботи.
Задачу можна розв'язати, розбивши на дві задачі:
- Підбір найменшої за чисельністю групи виконавців, які разом зможуть виконати всі роботи і вкладуться в бюджет . Ця проблема NP-складна, оскільки є узагальненням NP-повної задачі про покриття множини.
- Призначення в підібраній групі виконавців на роботи.
Математично задачу про призначення найменшої кількості виконавців можна сформулювати так:
- мінімізувати
- при
- ;
- .
У цій постановці цільова функція задачі нелінійна, що не дозволяє безпосередньо знайти оптимального розв'язку точними методами лінійного програмування, зокрема симплекс-методом. Однак, задачу можна лінеаризувати, включивши додаткові змінні , що показують факт вибору в групу виконавця , . Потрібно також зв'язати змінні і . Тоді цільова функція матиме вигляд
- мінімізувати .
Зв'язок змінних можна задати такою умовою:
Наближені алгоритми
Для швидкого розв'язання задач великої розмірності доцільно використовувати наближені алгоритми: алгоритм максимальної кількості мінімальних елементів (МКМЕ) і алгоритм максимальної кількості допустимих елементів (МКДЕ).
Див. також
Примітки
- Катаев А.В., Катаева Т.М., Коженко Я.В. Оптимизация численного состава команды проекта: экономико-математический инструментарий / А. В. Катаев, Т. М. Катаева, Я. В. Коженко // Конкурентоспособность в глобальном мире: экономика, наука, технологии. 2016. – № 8-3 (22). – С. 101-104
- Катаев А.В., Катаева Т.М. Управление проектами на базе динамической сети партнеров: монография. – Ростов-на-Дону – Таганрог: Издательство Южного федерального университета, 2017. – 125 с.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U prikladnij matematici pid zadacheyu pro priznachennya najmenshogo chisla vikonavciv rozumiyetsya zadacha kombinatornoyi optimizaciyi sho uzagalnyuye zadachu pro pokrittya mnozhini i shozha za postanovkoyu z zadacheyu pro priznachennya U cij zadachi mnozhina vikonavciv maye rozmir ne obov yazkovo rivnij rozmiru mnozhini robit Pri comu vikonavcya mozhna priznachiti dlya vikonannya dekilkoh robit odnochasno a na kozhnu robotu priznachayetsya tilki po odnomu vikonavcyu Ye zagalnij byudzhet na vikonannya vsih robit yakij ye obmezhennyam pri priznachenni Potribno znajti take priznachennya vikonavciv dlya vikonannya robit shob kilkist zaluchenih do vikonannya robit vikonavciv bula najmenshoyu i ne bulo perevisheno vidilenogo na ves kompleks robit byudzhetu ViznachennyaYe n vikonavciv i m robit Dlya kozhnoyi pari vikonavec i robota zadano vitrati na vikonannya roboti w i j displaystyle w i j Ye zagalnij byudzhet w displaystyle w na vikonannya vsogo kompleksu robit Rozv yazkom ye pidmnozhina vikonavciv U i rozpodil priznachennya vikonavciv z U po robotah Rishennya dopustime yaksho priznacheno vikonavciv dlya vsih robit i suma vitrat ne perevershuye byudzhetu w displaystyle w Potribno minimizuvati kilkist priznachenih vikonavciv L Inshimi slovami potribno pidibrati najmenshu za rozmirom potuzhnistyu mnozhinu vikonavciv yaki razom zmozhut vikonati vsi roboti Zadachu mozhna rozv yazati rozbivshi na dvi zadachi Pidbir najmenshoyi za chiselnistyu grupi vikonavciv yaki razom zmozhut vikonati vsi roboti i vkladutsya v byudzhet w displaystyle w Cya problema NP skladna oskilki ye uzagalnennyam NP povnoyi zadachi pro pokrittya mnozhini Priznachennya v pidibranij grupi vikonavciv na roboti Matematichno zadachu pro priznachennya najmenshoyi kilkosti vikonavciv mozhna sformulyuvati tak minimizuvati L U i 1 n max j 1 m x i j displaystyle L mid U mid sum i 1 n max j 1 m x ij pri i 1 n j 1 m w i j x i j w displaystyle sum i 1 n sum j 1 m w ij x ij leq w i 1 n x i j 1 j 1 m displaystyle sum i 1 n x ij 1 qquad j 1 ldots m x i j 0 1 i 1 n j 1 m displaystyle x ij in 0 1 qquad i 1 ldots n quad j 1 ldots m dd U cij postanovci cilova funkciya zadachi nelinijna sho ne dozvolyaye bezposeredno znajti optimalnogo rozv yazku tochnimi metodami linijnogo programuvannya zokrema simpleks metodom Odnak zadachu mozhna linearizuvati vklyuchivshi dodatkovi zminni y i displaystyle y i sho pokazuyut fakt viboru v grupu vikonavcya i displaystyle i y i 0 1 i 1 n displaystyle y i in 0 1 qquad i 1 ldots n Potribno takozh zv yazati zminni y i displaystyle y i i x i j displaystyle x ij Todi cilova funkciya matime viglyad minimizuvati L U i 1 n y i displaystyle L mid U mid sum i 1 n y i Zv yazok zminnih mozhna zadati takoyu umovoyu y i j 1 m x i j m y i i 1 n displaystyle y i leq sum j 1 m x ij leq my i qquad i 1 ldots n Nablizheni algoritmiDlya shvidkogo rozv yazannya zadach velikoyi rozmirnosti docilno vikoristovuvati nablizheni algoritmi algoritm maksimalnoyi kilkosti minimalnih elementiv MKME i algoritm maksimalnoyi kilkosti dopustimih elementiv MKDE Div takozhZadacha pro priznachennya Uzagalnena zadacha pro priznachennyaPrimitkiKataev A V Kataeva T M Kozhenko Ya V Optimizaciya chislennogo sostava komandy proekta ekonomiko matematicheskij instrumentarij A V Kataev T M Kataeva Ya V Kozhenko Konkurentosposobnost v globalnom mire ekonomika nauka tehnologii 2016 8 3 22 S 101 104 Kataev A V Kataeva T M Upravlenie proektami na baze dinamicheskoj seti partnerov monografiya Rostov na Donu Taganrog Izdatelstvo Yuzhnogo federalnogo universiteta 2017 125 s