martes, 26 de junio de 2012

El problema: Weapon Target Assignment


¿Quiénes somos?
Saúl Gausin
Calificación esperada: 130
Omar Jair Montalvo Aquines
Calificación esperada: 82
David Sosa Valdes
Calificación esperada: 80
Lenguajes: Python, JAVA(Posible).
Descripción del problema: Weapon-Target Assignment Problem (WTA) consiste en buscar una asignación óptima de un conjunto de armas de varios tipos a un conjunto de objetivos en orden para maximizar el daño total esperado hacia un oponente.
Se tiene un número de armas y un número de objetivos. Las armas son de tipo i = 1, 2, ..., m. Nosotros tenemos Wi armas disponibles de tipo i. De igual manera nosotros tenemos j = 1, 2, ..., n objetivos, y cada uno con un valor VjCualquiera de estas armas se les puede asignar a cualquier objetivo. Cada tipo de arma tiene una cierta probabilidad de destruir cada objetivo, denotado por Pij.
Optimización: Se busca tener un máximo daño Pij Vj hacia un oponente dada la asignación de armas a objetivos. Esto esta formulado por medio de un problema entera no lineal.
esta sujeto a algunas limitantes,
En donde la variable Xij representa la asignacion de cuantos tipo de armas del tipo i confrontan a objetivos j y Qij es la probabilidad de supervivencia(i-Pij). La primera restricción requiere que el número de armas de cada tipo asignado no exceda el número disponible. La segunda restricción es la restricción integral.
Decisión: Si es posible lograr un daño mayor o superior a un valor establecido D.
NP-DurezaEl problema NP-completo 3-cubierta exacta se reduce a Weapon Target Assignment, lo que le hace NP duro.
Tamaño (Medida de blancos y defensas): Seleccionamos un rango de 80 a 200 armas y objetivos a base del siguiente artículo.
http://web.mit.edu/sloan-msa/Papers/1.5.pdf