Проблема с целеуказанием оружия

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

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

Есть несколько видов оружия и несколько целей. Оружие относится к типу $i=1,\ldots ,m$. Есть $W_{i}$ доступное оружие типа $i$. Аналогично, существуют $j=1,\ldots ,n$ цели, каждая из которых имеет значение $V_{j}$. Любое оружие можно назначить на любую цель. Каждый тип оружия имеет определенную вероятность уничтожения каждой цели, определяемую формулой $p_{ij}$.

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

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

Несмотря на название, существуют и невоенные применения ВТА. Основная из них — поиск потерянного предмета или человека с помощью разнородных активов, таких как собаки, самолеты, ходунки и т. д. Проблема состоит в том, чтобы отнести активы к разделу пространства, в котором находится объект, чтобы минимизировать вероятность его неиспользования. нахождение объекта. «Значение» каждого элемента перегородки — это вероятность того, что объект находится там.

математическое

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

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

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

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

$x_{ij}\geq 0{\text{ and integer for }}i=1,\ldots ,m{\text{ and }}j=1,\ldots ,n.$

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

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

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

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

Пример

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

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

Одно из возможных решений — направить морское судно и один самолет на наиболее ценную цель (3). Это приводит к ожидаемому значению выживаемости $20(0.6)(0.5)=6$. Затем можно было бы направить оставшиеся самолеты и 2 танка на цель №2, в результате чего ожидаемая выживаемость составит $10(0.4)(0.8)^{2}=2.56$. Наконец, оставшиеся 3 танка назначаются цели №1, ожидаемая выживаемость которой составляет $5(0.7)^{3}=1.715$. Таким образом, мы имеем общую ожидаемую ценность выживания, равную $6+2.56+1.715=10.275$. Обратите внимание, что лучшее решение может быть достигнуто, если направить 3 танка на цель №1, 2 танка и морское судно на цель №2 и 2 самолета на цель №3, что дает ожидаемую выживаемость $5(0.7)^{3}+10(0.5)(0.8)^{2}+20(0.5)^{2}=9.915$.

См. также

• Алгоритм аукциона
• Проблема закрытия
• Обобщенная задача о назначениях
• Линейная задача о назначении узких мест
• Задача квадратичного назначения
• Проблема стабильного брака

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

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