Problém stanovení cíle

Problém přiřazení cílů je třídou kombinatorických optimalizačních problémů . Úkolem je najít optimální rozložení sady různých zbraní k zasažení cílů s cílem způsobit nepříteli maximální poškození.

Hlavní úkol je formulován takto:

Existují druhy zbraní a pro každý typ jsou kusy vybavení. Jsou cíle, na každém záleží . K jakémukoli cíli lze přiřadit jakýkoli kus vybavení. Každý typ zařízení má určitou pravděpodobnost zasažení každého cíle, danou maticí .

i=1,\ldots ,m

i

{\displaystyle W_{i))

j=1,\ldots ,n

{\displaystyle V_{j))

{\displaystyle p_{ij))

Je třeba poznamenat, že v tomto úkolu, na rozdíl od klasického přiřazovacího problému nebo zobecněného přiřazovacího problému , lze pro každou úlohu (tj. cíl) použít více než jednoho vykonavatele (tj. typ zařízení) a nemusí být nutně všechny cíle. vyhozen. Úloha přiřazování cílů nám tedy umožňuje formulovat problém optimálního přiřazení v případě, kdy je vyžadována spolupráce agentů. Kromě toho formulace umožňuje použití pravděpodobnostního přístupu.

Existují statické a dynamické verze problému přiřazení. Ve statické verzi je zbraň použita proti cíli pouze jednou. V dynamické verzi jsou zbraně použity několikrát, v každém kole jsou cíle přeřazeny v závislosti na výsledcích předchozího kola. Přestože je většina výzkumů věnována statickému problému, roste pozornost dynamické verzi.

Formální definice

Problém přiřazení cílů je často formulován jako následující problém nelineárního celočíselného programování :

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

za podmínek

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

pro

i=1,\ldots ,m,

kde jsou nezáporná celá čísla pro a

x_{ij}

i=1,\ldots ,m

j=1,\ldots ,n.

Zde proměnná představuje přiřazení skupiny zbraní daného typu k cíli a je to pravděpodobnost přežití ( ). První omezení vyžaduje, aby počet přidělených zbraní nepřesáhl počet dostupných zbraní. Druhé omezení vyžaduje, aby řešení bylo celé číslo. $x_{ij}$ $i$ $j$ ${\displaystyle q_{ij))$ $1-p_{ij}$

Bylo pozorováno, že minimalizace očekávaného přežití je ekvivalentní maximalizaci očekávané destrukce.

Algoritmy a zobecnění

Již dlouho je známo, že problémy s přiřazením jsou NP-těžké . Přesné řešení lze přesto nalézt pomocí metody větví a vazeb s využitím problémové relaxace . Bylo navrženo mnoho heuristických algoritmů, které poskytují řešení blízké optimální v polynomiálním čase [1] .

Příklad

Velitel má 5 tanků, 2 letadla a jedno námořní plavidlo a má rozkaz zničit tři cíle s hodnotou 5, 10 a 20. Každý typ zbraně je schopen zasáhnout cíle s následující pravděpodobností:

Typ zbraní	$V_{1}=5$	$V_{2}=10$	$V_{3}=20$
Nádrž	0,3	0,2	0,05
Letoun	0,1	0,6	0,5
Plavidlo	0,4	0,5	0,4

Optimálním řešením by bylo přiřadit cíl s maximální hodnotou (3) pro obě letadla. V důsledku toho bude očekávaná očekávaná hodnota (zachování) cíle rovna . Loď a dva tanky by měly být přiřazeny k cíli 2 poté, co získaly bezpečnost . A nakonec pošlete zbývající 3 tanky na cíl 1 a bezpečnost tohoto cíle bude . Výsledkem je minimální možná celková konzervace . $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$

Viz také

Poznámky

↑ Ahuja, R. a kol. Přesné a heuristické algoritmy pro problém přiřazení cíle zbraně. Operační výzkum 55(6), pp. 1136-1146, 2007

Literatura

Ahuja, Ravindra; TL Magnanti, JB Orlin. Síťové toky (neurčité) . - Prentice Hall , 1993. - ISBN 0-13-617549-X .