Проблема назначения оружия цели - Weapon target assignment problem
В проблема назначения оружия (WTA) является классом комбинаторная оптимизация проблемы, существующие в области оптимизация и исследование операций. Он состоит в нахождении оптимального назначения набора оружие различных типов к набору целей, чтобы максимизировать общий ожидаемый урон, нанесенный противнику.
Основная проблема заключается в следующем:
- Есть несколько видов оружия и несколько целей. Оружие типа . Есть доступное оружие типа . Точно так же есть цели, каждая из которых имеет значение . Любое оружие можно назначить на любую цель. У каждого типа оружия есть определенная вероятность поражения каждой цели, заданная .
Обратите внимание, что в отличие от классического проблема назначения или обобщенная задача о назначении, каждому можно назначить более одного агента (например, оружие). задача (т. е. цель), и не для всех целей требуется назначенное оружие. Таким образом, мы видим, что WTA позволяет формулировать задачи оптимального назначения, в которых задачи требуют взаимодействия агентов. Кроме того, он дает возможность моделировать вероятностное завершение задач в дополнение к затратам.
Можно рассматривать как статические, так и динамические версии WTA. В статическом случае оружие назначается целям один раз. Динамический случай включает в себя множество раундов присвоения, где состояние системы после каждой перестрелки (раунда) рассматривается в следующем раунде. Хотя большая часть работы была проделана над проблемой статического WTA, в последнее время проблеме динамического WTA уделяется больше внимания.
Несмотря на название, есть невоенные приложения WTA. Основной из них - поиск потерянного объекта или человека с помощью разнородных активов, таких как собаки, самолеты, пешеходы и т. Д. Проблема состоит в том, чтобы отнести активы к разделу пространства, в котором находится объект, чтобы свести к минимуму вероятность не поиск объекта. «Ценность» каждого элемента раздела - это вероятность того, что объект находится там.
Формальное математическое определение
В проблема назначения оружия часто формулируется как следующая нелинейная целочисленное программирование проблема:
с учетом ограничений
Где переменная представляет собой присвоение как можно большего количества типов оружия к цели и вероятность выживания (). Первое ограничение требует, чтобы количество назначенного оружия каждого типа не превышало доступное количество. Второе ограничение - это интегральное ограничение.
Обратите внимание, что минимизация ожидаемой выживаемости - это то же самое, что максимизация ожидаемого ущерба.
Алгоритмы и обобщения
Точное решение можно найти, используя ветвь и переплет методы, которые используют релаксация (приближение). Много эвристические алгоритмы были предложены, которые обеспечивают почти оптимальные решения в полиномиальное время.[1]
Пример
Командир имеет 5 танков, 2 самолета и 1 морское судно, и ему приказывают поразить 3 цели со значениями 5, 10 и 20. Каждый тип оружия имеет следующие вероятности успеха против каждой цели:
Тип оружия танк 0.3 0.2 0.5 Самолет 0.1 0.6 0.5 Морское судно 0.4 0.5 0.4
Одно из возможных решений - привязать морское судно и один самолет к наивысшей цели (3). Это приводит к ожидаемой выживаемости в размере . Затем можно было бы назначить оставшийся самолет и 2 танка цели №2, в результате чего ожидаемая выживаемость составила . Наконец, оставшиеся 3 танка назначаются цели №1, ожидаемая выживаемость которой составляет . Таким образом, общее ожидаемое значение выживаемости составляет . Обратите внимание, что лучшее решение может быть достигнуто путем назначения 3 танков цели №1, двух танков и морского судна цели №2 и 2 самолетов цели №3, что дает ожидаемую выживаемость .
Смотрите также
- Алгоритм аукциона
- Проблема закрытия
- Обобщенная проблема присваивания
- Задача о линейном назначении узких мест
- Квадратичная задача о назначении
- Проблема стабильного брака
Рекомендации
- ^ Ahuja, R. et al. Точные и эвристические алгоритмы для задачи назначения оружия цели. Исследование операций 55 (6), стр. 1136–1146, 2007 г.
дальнейшее чтение
- Ахуджа, Равиндра; Т. Л. Маньянти; Дж. Б. Орлин (1993). Сетевые потоки. Прентис Холл. ISBN 0-13-617549-X.