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

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

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

Есть несколько видов оружия и несколько целей. Оружие типа

{ Displaystyle я = 1, ldots, м}

. Есть

{ displaystyle W_ {i}}

доступное оружие типа

{ displaystyle i}

. Точно так же есть

{ displaystyle j = 1, ldots, n}

цели, каждая из которых имеет значение

{ displaystyle V_ {j}}

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

{ displaystyle p_ {ij}}

.

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

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

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

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

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

{ displaystyle min sum _ {j = 1} ^ {n} left (V_ {j} prod _ {i = 1} ^ {m} q_ {ij} ^ {x_ {ij}} right) }

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

{ displaystyle sum _ {j = 1} ^ {n} x_ {ij} leq W_ {i} { text {for}} i = 1, ldots, m, ,}

{ displaystyle x_ {ij} geq 0 { text {и целое число для}} i = 1, ldots, m { text {and}} j = 1, ldots, n.}

Где переменная ${ displaystyle x_ {ij}}$ представляет собой присвоение как можно большего количества типов оружия ${ displaystyle i}$ к цели ${ displaystyle j}$ и ${ displaystyle q_ {ij}}$ вероятность выживания ( ${ displaystyle 1-p_ {ij}}$ ). Первое ограничение требует, чтобы количество назначенного оружия каждого типа не превышало доступное количество. Второе ограничение - это интегральное ограничение.

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

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

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

Пример

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

Тип оружия	${ displaystyle V_ {1} = 5}$	${ displaystyle V_ {2} = 10}$	${ displaystyle V_ {3} = 20}$
танк	0.3	0.2	0.5
Самолет	0.1	0.6	0.5
Морское судно	0.4	0.5	0.4

Одно из возможных решений - привязать морское судно и один самолет к наивысшей цели (3). Это приводит к ожидаемой выживаемости в размере ${ displaystyle 20 (0,6) (0,5) = 6}$ . Затем можно было бы назначить оставшийся самолет и 2 танка цели №2, в результате чего ожидаемая выживаемость составила ${ displaystyle 10 (0,4) (0,8) ^ {2} = 2,56}$ . Наконец, оставшиеся 3 танка назначаются цели №1, ожидаемая выживаемость которой составляет ${ displaystyle 5 (0,7) ^ {3} = 1,715}$ . Таким образом, общее ожидаемое значение выживаемости составляет ${ displaystyle 6 + 2,56 + 1,715 = 10,275}$ . Обратите внимание, что лучшее решение может быть достигнуто путем назначения 3 танков цели №1, двух танков и морского судна цели №2 и 2 самолетов цели №3, что дает ожидаемую выживаемость ${ displaystyle 5 (0,7) ^ {3} +10 (0,5) (0,8) ^ {2} +20 (0,5) ^ {2} = 9,915}$ .