Problema de establecimiento de metas

El problema de asignación de objetivos es una clase de problemas de optimización combinatoria . La tarea es encontrar la distribución óptima de un conjunto de varias armas para alcanzar objetivos con el fin de infligir el máximo daño al enemigo.

La tarea principal se formula de la siguiente manera:

Hay tipos de armas y para cada tipo hay piezas de equipo. Hay objetivos, cada uno importa . Cualquier pieza de equipo se puede asignar a cualquier objetivo. Cada tipo de equipo tiene una cierta probabilidad de dar en cada blanco, dada por la matriz .

i=1,\ldots,m

i

{\ Displaystyle W_ {yo}}

j=1,\ldots,n

{\ Displaystyle V_ {j}}

{\ Displaystyle p_ {ij}}

Se observa que en esta tarea, en contraste con el problema de asignación clásico o el problema de asignación generalizado , para cada trabajo (es decir, objetivo) se puede usar más de un ejecutor (es decir, tipo de equipo) y no necesariamente todos los objetivos deben ser encendido. Así, la tarea de asignación de objetivos nos permite formular el problema de asignación óptima en el caso de que se requiera la cooperación de los agentes. Además, la formulación permite utilizar un enfoque probabilístico.

Hay versiones estáticas y dinámicas del problema de asignación. En la versión estática, el arma se usa contra el objetivo solo una vez. En la versión dinámica, las armas se usan varias veces, en cada ronda los objetivos se reasignan según los resultados de la ronda anterior. Aunque la mayor parte de la investigación se dedica al problema estático, la atención a la versión dinámica está creciendo.

Formal definición

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

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

bajo condiciones

{\displaystyle \sum _{j=1}^{n}x_{ij}\leq W_{i))

por

i=1,\ldots,m,

donde son enteros no negativos para y

x_{ij}

i=1,\ldots,m

j=1,\ldots,n.

Aquí la variable representa la asignación de un grupo de armas del tipo al objetivo y es la probabilidad de supervivencia ( ). La primera limitación exige que el número de armas asignadas no exceda el número de armas disponibles. La segunda restricción requiere que la solución sea entera. $x_{ij}$ $i$ $j$ ${\ Displaystyle q_ {ij}}$ ${\ Displaystyle 1-p_ {ij}}$

Se ha observado que minimizar la supervivencia esperada es equivalente a maximizar la destrucción esperada.

Algoritmos y generalizaciones

Durante mucho tiempo se ha sabido que los problemas de asignación son NP-difíciles . A pesar de esto, la solución exacta se puede encontrar utilizando el método de bifurcación y acotación utilizando la relajación del problema . Se han propuesto muchos algoritmos heurísticos que dan una solución cercana a la óptima en tiempo polinomial [1] .

Ejemplo

El comandante tiene 5 tanques, 2 aviones y un buque de guerra, y se le ordena destruir tres objetivos con un valor de 5, 10 y 20. Cada tipo de arma es capaz de alcanzar objetivos con la siguiente probabilidad:

tipo de armas	${\ estilo de visualización V_ {1} = 5}$	${\ estilo de visualización V_ {2} = 10}$	$V_{3}=20$
Tanque	0.3	0.2	0.05
Avión	0.1	0.6	0.5
Buque	0.4	0.5	0.4

La solución óptima sería asignar un objetivo con el valor máximo (3) para ambas aeronaves. Como resultado, el valor esperado esperado (preservación) del objetivo será igual a . El barco y dos tanques deben asignarse al objetivo 2, habiendo recibido seguridad . Y finalmente, envíe los 3 tanques restantes al objetivo 1, y la seguridad de este objetivo será . Como resultado, tenemos la mínima conservación total posible . $20\cdot 0{,}5^{2}=5$ $10\cdot 0{,}5\cdot 0{,}8^{2}=3{,}2$ $5\cdot 0{,}7^{3}=1{,}715$ $5+3{,}2+1{,}715=9{,}915$

Véase también

Notas

↑ Ahuja, R. et al. Algoritmos exactos y heurísticos para el problema de asignación de armas y blancos. Investigación de operaciones 55(6), págs. 1136-1146, 2007

Literatura

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