Задача о назначении целей

Задача о назначении целей — это класс задач комбинаторной оптимизации. Задача заключается в нахождении оптимального распределения комплекта различного вооружения для поражения целей для нанесения максимального поражения противнику.

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

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

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

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

Формальное определение

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

${\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}}$ для ${\displaystyle i=1,\ldots ,m,}$

где ${\displaystyle x_{ij}}$ — целые неотрицательные числа для ${\displaystyle i=1,\ldots ,m}$ и ${\displaystyle j=1,\ldots ,n.}$

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

Замечено, что минимизация ожидаемого выживания эквивалентна максимизации ожидаемого разрушения.

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

Давно известно, что задачи о назначениях NP-сложны. Несмотря на это, точное решение может быть найдено с помощью метода ветвей и границ использующего ослабление задачи. Предложено много эвристических алгоритмов, дающих близкое к оптимальному решение за полиномиальное время^[1].

Пример

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

Вид вооружения	${\displaystyle V_{1}=5}$	${\displaystyle V_{2}=10}$	${\displaystyle V_{3}=20}$
Танк	0,3	0,2	0,05
Самолет	0,1	0,6	0,5
Судно	0,4	0,5	0,4

Оптимальным решением будет назначить цель с максимальным значением (3) для обоих целей. В результате математическое ожидание ожидаемое сохранившейся ценности (сохранность) цели будет равно ${\displaystyle 20\cdot 0{,}5^{2}=5}$. Судно и два танка следует назначить на цель 2, получив сохранность ${\displaystyle 10\cdot 0{,}5\cdot 0{,}8^{2}=3{,}2}$. И, наконец, оставшиеся 3 танка послать на цель 1, и сохранность этой цели будет ${\displaystyle 5\cdot 0{,}7^{3}=1{,}715}$. В результате мы имеем минимальную возможную суммарную сохранность ${\displaystyle 5+3{,}2+1{,}715=9{,}915}$.

См. также

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