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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

Формальное определение[править | править вики-текст]

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

\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 для  i = 1, \ldots, m, \,
где x_{ij} — целые неотрицательные числа для  i = 1, \ldots, m и j = 1, \ldots, n.

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

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

Алгоритмы и обобщения[править | править вики-текст]

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

Пример[править | править вики-текст]

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

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

Годным решением будет назначить цель с максимальным значением (3) для судна и самолёта. В результате ожидаемое выживание цели равно  20(0.6)(0.5)= 6 . Оставшийся самолёт и два танка можно назначить на цель 2, получив ожидаемое выживание  10 (0.4)(0.8)^2 = 2.56 . И, наконец, оставшиеся три танка послать на цель 1, и ожидаемое выживание этой цели будет  5 (0.7)^3 = 1.715 . В результате мы имеем суммарное ожидание выживания  6 + 2.56 + 1.715 = 10.275 .

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. Ahuja, R. et al. Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem. Operations Research 55(6), pp. 1136—1146, 2007

Дальнейшее чтение[править | править вики-текст]