Weapon target assignment problem
હથિયાર લક્ષ્ય સોંપણી સમસ્યા (ડબલ્યુટીએ) એ ઓપ્ટિમાઇઝેશન અને કામગીરી સંશોધનના ક્ષેત્રોમાં હાજર સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓનો એક વર્ગ છે. તેમાં વિરોધીને થયેલ કુલ અપેક્ષિત નુકસાનને મહત્તમ કરવા માટે લક્ષ્યોના સમૂહમાં વિવિધ પ્રકારના શસ્ત્રોના સમૂહની શ્રેષ્ઠ સોંપણી શોધવાનો સમાવેશ થાય છે. મૂળભૂત સમસ્યા નીચે મુજબ છેઃ સંખ્યાબંધ શસ્ત્રો અને સંખ્યાબંધ લક્ષ્યો છે. શસ્ત્રો પ્રકારનાં હોય છે. આ પ્રકારના શસ્ત્રો ઉપલબ્ધ છે. તેવી જ રીતે, ત્યાં લક્ષ્યો છે, દરેકનું મૂલ્ય છે. કોઈપણ હથિયારને કોઈપણ લક્ષ્યને સોંપવામાં આવી શકે છે. દરેક હથિયારના પ્રકારમાં દરેક લક્ષ્યનો નાશ કરવાની ચોક્કસ સંભાવના હોય છે. નોંધ લો કે ક્લાસિક સોંપણી સમસ્યા અથવા સામાન્ય સોંપણી સમસ્યાના વિરોધમાં, દરેક કાર્ય (એટલે કે લક્ષ્ય) માટે એક કરતાં વધુ એજન્ટ (એટલે કે હથિયાર) સોંપવામાં આવી શકે છે અને તમામ લક્ષ્યોને શસ્ત્રો સોંપવાની જરૂર નથી. આમ, આપણે જોઈએ છીએ કે ડબ્લ્યુ. ટી. એ. વ્યક્તિને શ્રેષ્ઠ સોંપણી સમસ્યાઓ ઘડવાની મંજૂરી આપે છે જેમાં કાર્યોને એજન્ટો વચ્ચે સહકારની જરૂર હોય છે. વધુમાં, તે ખર્ચ ઉપરાંત કાર્યોની સંભવિત પૂર્ણતાનું મોડેલ બનાવવાની ક્ષમતા પ્રદાન કરે છે. ડબ્લ્યુ. ટી. એ. ની સ્થિર અને ગતિશીલ બંને આવૃત્તિઓ પર વિચાર કરી શકાય છે. સ્થિર કિસ્સામાં, હથિયારોને એક વખત લક્ષ્યોને સોંપવામાં આવે છે. ગતિશીલ કેસમાં સોંપણીના ઘણા રાઉન્ડનો સમાવેશ થાય છે જ્યાં આગના દરેક વિનિમય (રાઉન્ડ) પછી સિસ્ટમની સ્થિતિને આગામી રાઉન્ડમાં ધ્યાનમાં લેવામાં આવે છે. જ્યારે મોટાભાગનું કામ સ્થિર ડબલ્યુટીએ સમસ્યા પર કરવામાં આવ્યું છે, ત્યારે તાજેતરમાં ગતિશીલ ડબલ્યુટીએ સમસ્યા પર વધુ ધ્યાન આપવામાં આવ્યું છે. નામ હોવા છતાં, ડબ્લ્યુ. ટી. એ. ની બિન-લશ્કરી અરજીઓ છે. કૂતરાઓ, વિમાનો, પદયાત્રીઓ વગેરે જેવી વિજાતીય સંપત્તિઓ દ્વારા ખોવાયેલી વસ્તુ અથવા વ્યક્તિની શોધ કરવી એ મુખ્ય છે. સમસ્યા એ છે કે ઑબ્જેક્ટ ન મળવાની સંભાવનાને ઘટાડવા માટે ઑબ્જેક્ટ સ્થિત છે તે જગ્યાના પાર્ટીશનને અસ્કયામતો સોંપવાની છે. પાર્ટીશનના દરેક તત્વનું "મૂલ્ય" એ સંભાવના છે કે પદાર્થ ત્યાં સ્થિત છે. ઔપચારિક ગાણિતિક વ્યાખ્યા શસ્ત્ર લક્ષ્ય સોંપણી સમસ્યાને ઘણીવાર નીચેની બિનરેખીય પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યા તરીકે ઘડવામાં આવે છેઃ અવરોધોને આધિન જ્યાં ચલ લક્ષ્ય બનાવવા માટેના પ્રકારનાં ઘણા શસ્ત્રોની સોંપણીને રજૂ કરે છે અને અસ્તિત્વની સંભાવના () છે. પ્રથમ અવરોધ માટે જરૂરી છે કે દરેક પ્રકારના હથિયારોની સંખ્યા ઉપલબ્ધ સંખ્યા કરતાં વધી ન જાય. બીજો અવરોધ એ અભિન્ન અવરોધ છે. નોંધ લો કે અપેક્ષિત અસ્તિત્વ મૂલ્યને ઘટાડવું એ અપેક્ષિત નુકસાનને મહત્તમ કરવા જેવું જ છે. અલ્ગોરિધમ્સ અને સામાન્યીકરણ શાખા અને બાઉન્ડ તકનીકોનો ઉપયોગ કરીને ચોક્કસ ઉકેલ શોધી શકાય છે જે છૂટછાટ (અંદાજ) નો ઉપયોગ કરે છે. ઘણા હ્યુરિસ્ટિક અલ્ગોરિધમ્સ પ્રસ્તાવિત કરવામાં આવ્યા છે જે બહુપદી સમયમાં લગભગ-શ્રેષ્ઠ ઉકેલો પ્રદાન કરે છે. ઉદાહરણ એક કમાન્ડર પાસે 5 ટેન્કો, 2 વિમાનો અને 1 દરિયાઈ જહાજ હોય છે અને તેને 5,10 અને 20 મૂલ્યો સાથે 3 લક્ષ્યોને નિશાન બનાવવા માટે કહેવામાં આવે છે. દરેક હથિયારના પ્રકારમાં દરેક લક્ષ્ય સામે નીચેની સફળતાની સંભાવનાઓ હોય છેઃ {| વર્ગ = "વિકિટેબલ" |-! શસ્ત્ર પ્રકાર! ! ! ! ! ! | | ટેન્ક | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | આ અપેક્ષિત અસ્તિત્વ મૂલ્યમાં પરિણમે છે. પછી કોઈ બાકી રહેલા વિમાન અને 2 ટેન્કોને #2 ને નિશાન બનાવવા માટે સોંપી શકે છે, જેના પરિણામે અપેક્ષિત અસ્તિત્વ મૂલ્ય. છેવટે, બાકીની 3 ટાંકીઓને લક્ષ્ય #1 માટે સોંપવામાં આવી છે, જેનું અપેક્ષિત અસ્તિત્વ મૂલ્ય છે. આમ, આપણી પાસે કુલ અપેક્ષિત અસ્તિત્વ મૂલ્ય છે. નોંધ લો કે લક્ષ્ય માટે 3 ટાંકીઓ #1, લક્ષ્ય માટે 2 ટાંકીઓ અને દરિયાઈ જહાજો #2 અને લક્ષ્ય માટે 2 વિમાનો #3 સોંપીને વધુ સારો ઉકેલ પ્રાપ્ત કરી શકાય છે, જે અપેક્ષિત અસ્તિત્વ મૂલ્ય આપે છે. હરાજી અલ્ગોરિધમ ક્લોઝર પ્રોબ્લેમ જનરલાઈઝ્ડ અસાઇનમેન્ટ પ્રોબ્લેમ લીનિયર બૉટલનેક અસાઇનમેન્ટ પ્રોબ્લેમ ક્વાડ્રેટિક અસાઇનમેન્ટ પ્રોબ્લેમ સ્ટેબલ મેરેજ પ્રોબ્લેમ સંદર્ભો વધુ વાંચન કોમ્બિનેટરિયલ ઓપ્ટિમાઇઝેશન મેચિંગ (ગ્રાફ થિયરી) કોમ્બેટ મોડેલિંગ જુઓ.