Обобщенная задача о присвоении
-
Определение и постановка задачи
- Задача о максимальном обобщенном задании является комбинаторной оптимизацией.
- Обобщает задачу назначения, где агенты и задачи имеют разные размеры.
- Агенты могут выполнять задачи с различными затратами и прибылью.
- Необходимо найти задание, в котором все агенты укладываются в бюджет, а общая прибыль максимальна.
-
Частные случаи
- При равных бюджетах и затратах задача сводится к задаче назначения.
- При равных затратах и прибыли для всех агентов задача сводится к задаче множественных рюкзаков.
- При одном агенте задача сводится к задаче рюкзака.
-
Математическая формулировка
- Используются n видов предметов и m видов мусорных баков.
- Каждый бункер имеет свой бюджет и связан с прибылью и тяжестью предметов.
- Решение — распределение предметов по ячейкам, удовлетворяющее ограничениям по весу.
- Цель — найти решение с максимальной прибылью.
-
Сложность и алгоритмы
- Задача является NP-сложной.
- Существуют линейные программирования, дающие приближение.
- Алгоритмы жадной аппроксимации используют концепцию остаточной прибыли для решения задачи.
-
Алгоритм жадной аппроксимации
- Используется для задачи, где не каждый предмет должен быть помещен в корзину.
- Построение расписания в итерациях с выбором предметов для мусорного ведра.
- Выбор предметов может изменяться на последующих итерациях.
- Остаточная прибыль рассчитывается по прибыли и весу предметов.
-
Рекомендации
- Для дальнейшего чтения предлагается список литературы.
Полный текст статьи: