problema de asignación arma-objetivo

El problema de asignación de armas a objetivos ( WTA , por sus siglas en inglés ) es una clase de problemas de optimización combinatoria presentes en los campos de la optimización y la investigación operativa . Consiste en encontrar una asignación óptima de un conjunto de armas de diversos tipos a un conjunto de objetivos con el fin de maximizar el daño total esperado infligido al adversario.

El problema fundamental es el siguiente:

Hay varias armas y varios objetivos. Las armas son de tipo${\displaystyle i=1,\ldots ,m}$. Hay${\displaystyle W_{i}}$armas disponibles de tipo${\displaystyle i}$. De manera similar, hay${\displaystyle j=1,\ldots ,n}$objetivos, cada uno con un valor de${\displaystyle V_{j}}$. Cualquiera de las armas puede asignarse a cualquier objetivo. Cada tipo de arma tiene una cierta probabilidad de destruir cada objetivo, dada por${\displaystyle p_{ij}}$.

Nótese que, a diferencia del problema de asignación clásico o del problema de asignación generalizado , se puede asignar más de un agente (es decir, arma) a cada tarea (es decir, objetivo) y no es necesario que todos los objetivos tengan armas asignadas. Por lo tanto, vemos que el WTA permite formular problemas de asignación óptima en los que las tareas requieren cooperación entre agentes. Además, ofrece la capacidad de modelar la finalización probabilística de las tareas, además de los costos.

Se pueden considerar versiones estáticas y dinámicas del problema de asignación de armas (WTA). En el caso estático, las armas se asignan a los objetivos una sola vez. El caso dinámico implica múltiples rondas de asignación, donde el estado del sistema después de cada intercambio de fuego (ronda) se considera en la siguiente ronda. Si bien la mayor parte del trabajo se ha centrado en el problema WTA estático, recientemente el problema WTA dinámico ha recibido mayor atención.

A pesar de su nombre, el WTA tiene aplicaciones no militares. La principal es la búsqueda de un objeto o persona extraviada mediante diversos recursos, como perros, aeronaves, peatones, etc. El problema consiste en asignar los recursos a una partición del espacio donde se encuentra el objeto para minimizar la probabilidad de no encontrarlo. El "valor" de cada elemento de la partición representa la probabilidad de que el objeto se encuentre allí.

El problema de asignación de objetivos de armas se formula a menudo como el siguiente problema de programación entera no lineal:

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

sujeto a las restricciones

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

${\displaystyle x_{ij}\geq 0{\text{ y entero para }}i=1,\ldots ,m{\text{ y }}j=1,\ldots ,n.}$

Donde la variable${\displaystyle x_{ij}}$representa la asignación de tantas armas de tipo${\displaystyle i}$apuntar${\displaystyle j}$y${\displaystyle q_{ij}}$es la probabilidad de supervivencia (${\displaystyle 1-p_{ij}}$). La primera restricción requiere que el número de armas de cada tipo asignadas no exceda el número disponible. La segunda restricción es la restricción integral.

Nótese que minimizar el valor de supervivencia esperado es lo mismo que maximizar el daño esperado.

Se puede encontrar una solución exacta utilizando técnicas de ramificación y acotación que emplean relajación . ^{[ 1 ]} Se han propuesto muchos algoritmos heurísticos que proporcionan soluciones casi óptimas en tiempo polinomial . ^{[ 2 ]}

Un comandante dispone de 5 tanques, 2 aeronaves y 1 buque, y se le ordena atacar 3 objetivos con valores de 5, 10 y 20. Cada tipo de arma tiene las siguientes probabilidades de éxito contra cada objetivo:

Una solución factible es asignar el buque marítimo y una aeronave al objetivo de mayor valor (3). Esto da como resultado un valor de supervivencia esperado de${\displaystyle 20(0,6)(0,5)=6}$. Entonces se podrían asignar los aviones restantes y 2 tanques al objetivo n.° 2, lo que resultaría en un valor de supervivencia esperado de${\displaystyle 10(0,4)(0,8)^{2}=2,56}$. Finalmente, los 3 tanques restantes se asignan al objetivo n.° 1, que tiene un valor de supervivencia esperado de${\displaystyle 5(0,7)^{3}=1,715}$. Por lo tanto, tenemos un valor de supervivencia total esperado de${\displaystyle 6+2,56+1,715=10,275}$. Tenga en cuenta que se puede lograr una mejor solución asignando 3 tanques al objetivo n.° 1, 2 tanques y un buque al objetivo n.° 2 y 2 aeronaves al objetivo n.° 3, lo que da un valor de supervivencia esperado de${\displaystyle 5(0,7)^{3}+10(0,5)(0,8)^{2}+20(0,5)^{2}=9,915}$.

• Algoritmo de subasta
• Problema de cierre
• Problema de asignación generalizada
• Problema de asignación de cuello de botella lineal
• Problema de asignación cuadrática
• Problema de matrimonio estable

• Ahuja, Ravindra ; TL Magnanti; JB Orlin (1993). Flujos de red . Prentice Hall. ISBN 0-13-617549-X.