Célbeállítási probléma

A cél-hozzárendelési probléma a kombinatorikus optimalizálási problémák egy osztálya . A feladat az, hogy megtaláljuk a különféle fegyverek optimális eloszlását a célpontok eltalálásához, hogy maximális sebzést okozzanak az ellenségnek.

A fő feladat a következőképpen fogalmazódik meg:

Vannak fegyvertípusok, és minden típushoz vannak felszerelések. Vannak célok, mindegyik számít . Bármilyen felszerelés hozzárendelhető bármely célponthoz. Minden típusú felszerelésnek van egy bizonyos valószínűsége az egyes célpontok eltalálására, amelyet a mátrix ad meg .

i=1,\ldots ,m

én

{\displaystyle W_{i))

j=1,\ldots ,n

{\displaystyle V_{j))

p_{ij}

Megjegyzendő, hogy ebben a feladatban a klasszikus hozzárendelési problémával vagy az általánosított hozzárendelési problémával ellentétben minden munkához (azaz célhoz) egynél több végrehajtó (azaz eszköztípus) használható, és nem feltétlenül kell minden célpontot használni. kirúgott. A célok kijelölésének feladata tehát lehetővé teszi, hogy megfogalmazzuk az optimális hozzárendelés problémáját abban az esetben, ha az ágensek együttműködésére van szükség. Ezenkívül a megfogalmazás lehetővé teszi a valószínűségi megközelítés alkalmazását.

A hozzárendelési problémának létezik statikus és dinamikus változata. A statikus változatban a fegyvert csak egyszer használják a célpont ellen. A dinamikus változatban a fegyverek többször használatosak, minden körben a célpontokat az előző kör eredményétől függően újraosztják. Bár a kutatások nagy részét a statikus problémának szentelik, a figyelem a dinamikus változatra növekszik.

Formális definíció

A cél hozzárendelési problémát gyakran a következő nemlineáris egész programozási problémaként fogalmazzák meg :

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

feltételek mellett

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

számára

i=1,\ldots ,m,

ahol nem negatív egész számok vannak az és számára

x_{ij}

i=1,\ldots ,m

j=1,\ldots ,n.

Itt a változó az ilyen típusú fegyverek célponthoz való hozzárendelését jelenti, és a túlélés valószínűsége ( ). Az első korlátozás megköveteli, hogy a hozzárendelt fegyverek száma ne haladja meg a rendelkezésre álló fegyverek számát. A második megszorítás megköveteli, hogy a megoldás egész szám legyen. $x_{ij}$ $én$ $j$ $q_{ij}$ $1-p_{ij}$

Megfigyelték, hogy a várható túlélés minimalizálása egyenértékű a várható pusztulás maximalizálásával.

Algoritmusok és általánosítások

Régóta ismert, hogy a hozzárendelési problémák NP-nehézek . Ennek ellenére a probléma relaxációt alkalmazó elágazó és kötött módszerrel a pontos megoldás megtalálható . Számos heurisztikus algoritmust javasoltak, amelyek polinomidőben az optimálishoz közeli megoldást adnak [1] .

Példa

A parancsnoknak 5 harckocsija, 2 repülőgépe és egy haditengerészeti hajója van, és három célpont megsemmisítésére kapott parancsot 5, 10 és 20 értékkel. Mindegyik fegyvertípus a következő valószínűséggel képes célokat eltalálni:

A fegyverek típusa	$V_{1}=5$	$V_{2}=10$	$V_{3}=20$
Tartály	0.3	0.2	0,05
Repülőgép	0.1	0.6	0.5
Hajó	0.4	0.5	0.4

Az optimális megoldás az lenne, ha mindkét repülőgéphez a maximális értékű (3) célpontot rendelnénk hozzá. Ennek eredményeként a cél várható várható értéke (megőrzése) egyenlő lesz . A hajót és két tankot a 2. célponthoz kell rendelni, miután megkapták a biztonságot . És végül küldje el a maradék 3 tankot az 1-es célpontra, és ennek a célpontnak a biztonsága . Ennek eredményeként a lehető legkisebb teljes megőrzést biztosítjuk . $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$

Lásd még

Jegyzetek

↑ Ahuja, R. et al. Pontos és heurisztikus algoritmusok a fegyver-célpont hozzárendelési problémához. Operations Research 55 (6), pp. 1136-1146, 2007

Irodalom

Ahuja, Ravindra; TL Magnanti, JB Orlin. Hálózati áramlások (határozatlan) . - Prentice Hall , 1993. - ISBN 0-13-617549-X .