Обобщенная задача о назначениях

В прикладной математике задача о максимальном обобщенном назначении является задачей комбинаторной оптимизации . Эта проблема является обобщением проблемы назначения , в которой и задачи, и агенты имеют размер. Более того, размер каждой задачи может варьироваться от одного агента к другому.

В самом общем виде эта проблема такова: имеется ряд агентов и ряд задач. Любой агент может быть назначен для выполнения любой задачи, что потребует определенных затрат и прибыли, которые могут варьироваться в зависимости от назначения задачи агенту. При этом у каждого агента есть бюджет и сумма затрат порученных ему задач не может превышать этот бюджет. Требуется найти задание, в котором все агенты не превышают свой бюджет и общая прибыль от задания максимизируется.

В особых случаях

В частном случае, когда бюджеты всех агентов и затраты всех задач равны 1, эта задача сводится к задаче о назначениях . Когда затраты и прибыль от всех задач не различаются у разных агентов, эта проблема сводится к задаче о множественном рюкзаке. Если агент один, то эта задача сводится к задаче о рюкзаке .

Пояснение определения

Далее у нас есть n видов предметов, $a_{1}$ через $a_{n}$ и m видов контейнеров $b_{1}$ через $b_{m}$. Каждый контейнер $b_{i}$ связано с бюджетом $t_{i}$. Для мусорного ведра $b_{i}$, каждый предмет $a_{j}$ имеет прибыль $p_{ij}$ и вес $w_{ij}$. Решением является распределение товаров по ячейкам. Допустимое решение — это решение, в котором для каждого интервала $b_{i}$ общий вес назначенных предметов не превышает $t_{i}$. Прибыль от решения — это сумма прибылей для каждого назначения корзины с товарами. Цель состоит в том, чтобы найти решение с максимальной прибылью.

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

${\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}$

Сложность

Обобщенная задача о назначениях NP-трудна . Однако существуют релаксации линейного программирования, которые дают $(1-1/e)$-аппроксимация.

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

Для варианта задачи, в котором не каждый предмет должен быть помещен в корзину, существует семейство алгоритмов решения GAP с использованием комбинаторного перевода любого алгоритма задачи о рюкзаке в аппроксимационный алгоритм для GAP.

Используя любой $\alpha$-аппроксимационного алгоритма АЛГ для задачи о рюкзаке , можно построить ( $\alpha +1$)-аппроксимация обобщенной задачи назначения жадным способом с использованием концепции остаточной прибыли. Алгоритм строит расписание за итерации, где в течение итерации $j$ предварительный выбор предметов для мусорной корзины $b_{j}$ выбран. Выбор для мусорного ведра $b_{j}$ может измениться, поскольку элементы могут быть повторно выбраны в более поздней итерации для других ячеек. Остаточная прибыль от предмета $x_{i}$ для пчел $b_{j}$ является $p_{ij}$ если $x_{i}$ не выбран для какой-либо другой ячейки или $p_{ij}$ – $p_{ik}$ если $x_{i}$ выбрано для корзины $b_{k}$.

Формально: мы используем вектор $T$ для указания предварительного расписания во время работы алгоритма. Конкретно, $T[i]=j$ означает предмет $x_{i}$ запланировано на корзину $b_{j}$ и $T[i]=-1$ означает, что предмет $x_{i}$ не запланировано. Остаточная прибыль за итерацию $j$ обозначается $P_{j}$, где $P_{j}[i]=p_{ij}$ если предмет $x_{i}$ не запланировано (т. $T[i]=-1$) и $P_{j}[i]=p_{ij}-p_{ik}$ если предмет $x_{i}$ запланировано на корзину $b_{k}$ (т.е. $T[i]=k$).

Формально:

Набор $T[i]=-1{\text{ for }}i=1\ldots n$

Для $j=1,\ldots ,m$ делать:

Позвоните в ALG, чтобы найти решение проблемы. $b_{j}$ используя функцию остаточной прибыли $P_{j}$. Обозначим выбранные элементы через $S_{j}$.

Обновлять $T$ с использованием $S_{j}$, то есть, $T[i]=j$ для всех $i\in S_{j}$.

См. также

• Проблема с назначением

Дальнейшее чтение

Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (19 марта 2013 г.). Проблемы с рюкзаком . Спрингер. ISBN  978-3-540-24777-7 .