Задача о назначении целей
Задача о назначении целей — это класс задач комбинаторной оптимизации. Задача заключается в нахождении оптимального распределения комплекта различного вооружения для поражения целей для нанесения максимального поражения противнику.
Основная задача формулируется следующим образом:
- Имеется видов вооружения и для каждого вида имеется единиц техники. Есть целей, каждая имеет значение . Любая единица техники может быть назначена на любую цель. Каждый вид техники имеет определённую вероятность поражения каждой цели, задаваемую матрицей .
Замечено, что в этой задаче, в отличие от классической задачи о назначениях или обобщенной задачи о назначениях, для каждой работы (то есть цели) может быть использовано более одного исполнителя (то есть вида техники) и не обязательно все цели должны быть обстреляны. Таким образом, задача о назначении целей позволяет сформулировать задачу оптимального назначения в случае, когда требуется кооперация агентов. Кроме того, постановка позволяет использовать вероятностный подход.
Существуют статическая и динамическая версии задачи о назначениях. В статическом варианте оружие применяется против цели только один раз. В динамическом варианте орудия применяются несколько раз, каждый раунд происходит переназначение целей в зависимости от результатов предыдущего раунда. Хотя большая часть исследований посвящена статической задаче, внимание к динамической версии растёт.
Формальное определение
Задача о назначении целей часто формулируется в виде следующей нелинейной задачи целочисленного программирования:
при условиях
- для
- где — целые неотрицательные числа для и
Здесь переменная представляет назначение группы орудий типа для цели и является вероятностью выживания (). Первое ограничение требует, чтобы число назначенных орудий не превышало число имеющихся. Второе ограничение требует целочисленность решения.
Замечено, что минимизация ожидаемого выживания эквивалентна максимизации ожидаемого разрушения.
Алгоритмы и обобщения
Давно известно, что задачи о назначениях NP-сложны. Несмотря на это, точное решение может быть найдено с помощью метода ветвей и границ использующего ослабление задачи. Предложено много эвристических алгоритмов, дающих близкое к оптимальному решение за полиномиальное время[1].
Пример
Командир имеет 5 танков, 2 самолета и одно морское судно, и ему приказано уничтожить три цели с ценностью 5, 10 и 20. Каждый вид вооружения способен поразить цели со следующей вероятностью:
Вид вооружения | |||
---|---|---|---|
Танк | 0,3 | 0,2 | 0,05 |
Самолет | 0,1 | 0,6 | 0,5 |
Судно | 0,4 | 0,5 | 0,4 |
Оптимальным решением будет назначить цель с максимальным значением (3) для обоих самолётов. В результате математическое ожидание ожидаемое сохранившейся ценности (сохранность) цели будет равно . Судно и два танка следует назначить на цель 2, получив сохранность . И, наконец, оставшиеся 3 танка послать на цель 1, и сохранность этой цели будет . В результате мы имеем минимальную возможную суммарную сохранность .
См. также
- Алгоритм аукциона
- Обобщенная задача о назначениях
- Линейная задача о назначениях в узких местах
- Квадратичная задача о назначениях
- Задача о марьяже
- Задача о соседях по комнате
Примечания
- ↑ Ahuja, R. et al. Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem. Operations Research 55(6), pp. 1136—1146, 2007
Литература
- Ahuja, Ravindra[англ.]; T. L. Magnanti, J. B. Orlin. Network Flows (неопр.). — Prentice Hall, 1993. — ISBN 0-13-617549-X.