Проблема назначения оружия цели - Weapon target assignment problem

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

Основная проблема заключается в следующем:

Есть несколько видов оружия и несколько целей. Оружие типа . Есть доступное оружие типа . Точно так же есть цели, каждая из которых имеет значение . Любое оружие можно назначить на любую цель. У каждого типа оружия есть определенная вероятность поражения каждой цели, заданная .

Обратите внимание, что в отличие от классического проблема назначения или обобщенная задача о назначении, каждому можно назначить более одного агента (например, оружие). задача (т. е. цель), и не для всех целей требуется назначенное оружие. Таким образом, мы видим, что WTA позволяет формулировать задачи оптимального назначения, в которых задачи требуют взаимодействия агентов. Кроме того, он дает возможность моделировать вероятностное завершение задач в дополнение к затратам.

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

Несмотря на название, есть невоенные приложения WTA. Основной из них - поиск потерянного объекта или человека с помощью разнородных активов, таких как собаки, самолеты, пешеходы и т. Д. Проблема состоит в том, чтобы отнести активы к разделу пространства, в котором находится объект, чтобы свести к минимуму вероятность не поиск объекта. «Ценность» каждого элемента раздела - это вероятность того, что объект находится там.

Формальное математическое определение

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

с учетом ограничений

Где переменная представляет собой присвоение как можно большего количества типов оружия к цели и вероятность выживания (). Первое ограничение требует, чтобы количество назначенного оружия каждого типа не превышало доступное количество. Второе ограничение - это интегральное ограничение.

Обратите внимание, что минимизация ожидаемой выживаемости - это то же самое, что максимизация ожидаемого ущерба.

Алгоритмы и обобщения

Точное решение можно найти, используя ветвь и переплет методы, которые используют релаксация (приближение). Много эвристические алгоритмы были предложены, которые обеспечивают почти оптимальные решения в полиномиальное время.[1]

Пример

Командир имеет 5 танков, 2 самолета и 1 морское судно, и ему приказывают поразить 3 цели со значениями 5, 10 и 20. Каждый тип оружия имеет следующие вероятности успеха против каждой цели:

Тип оружия
танк0.30.20.5
Самолет0.10.60.5
Морское судно0.40.50.4

Одно из возможных решений - привязать морское судно и один самолет к наивысшей цели (3). Это приводит к ожидаемой выживаемости в размере . Затем можно было бы назначить оставшийся самолет и 2 танка цели №2, в результате чего ожидаемая выживаемость составила . Наконец, оставшиеся 3 танка назначаются цели №1, ожидаемая выживаемость которой составляет . Таким образом, общее ожидаемое значение выживаемости составляет . Обратите внимание, что лучшее решение может быть достигнуто путем назначения 3 танков цели №1, двух танков и морского судна цели №2 и 2 самолетов цели №3, что дает ожидаемую выживаемость .

Смотрите также

Рекомендации

  1. ^ Ahuja, R. et al. Точные и эвристические алгоритмы для задачи назначения оружия цели. Исследование операций 55 (6), стр. 1136–1146, 2007 г.

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

  • Ахуджа, Равиндра; Т. Л. Маньянти; Дж. Б. Орлин (1993). Сетевые потоки. Прентис Холл. ISBN  0-13-617549-X.