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

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

Особливі випадки

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

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

Якщо є всього один агент, задача зводиться до задачі про рюкзак.

Визначення

Є n робіт і m виконавців . Кожен виконавець має бюджет . Для кожної пари виконавець і робота задано дохід і вагу . Розв'язком є підмножина робіт U і розподіл робіт з U за виконавцями. Розв'язок допустимий, якщо сума витрат на призначені роботи виконавця не перевершує бюджету . Доходом від розв'язку є сума всіх доходів усіх розподілів робота-виконавець.

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

максимізувати
при ;
;
;

Узагальнена задача про призначення є NP-складною і навіть APX-складною.

Фляйшер, Гоманс, Мірокні і Свириденко запропонували комбінаторний алгоритм локального пошуку з апроксимацією та алгоритм на основі лінійного програмування з апроксимацією [1].

Апроксимація є кращою відомою апроксимацією узагальненої задачі про призначення.

Жадібний апроксимаційний алгоритм

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

Формально: Використаємо вектор для попереднього вибору і в цьому векторі

означає, що на роботу передбачається призначити виконавця ,
означає, що на роботу нікого не призначено.

Залишок доходу на ітерації позначається через , де

, якщо роботу не обрано (тобто )
, якщо роботу передбачається віддати виконавцю (тобто ).

Отже, алгоритм виглядає так:

Присвоюються початкові значення для всіх
Для всіх виконати:
Використовується алгоритм апроксимації для отримання розподілу робіт для виконавця , використовуючи функцію залишку доходу . Позначаються вибрані роботи .
Підправляється , використовуючи , тобто для всіх .
кінець циклу

Див. також

Примітки

  1. L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems. In SODA'06: Proc

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.