Weapon target assignment problem
ہتھیاروں کی ہدف تفویض کا مسئلہ (ڈبلیو ٹی اے) اصلاح اور کارروائیوں کی تحقیق کے شعبوں میں موجود مشترکہ اصلاح کے مسائل کی ایک کلاس ہے۔ اس میں حریف کو ہونے والے کل متوقع نقصان کو زیادہ سے زیادہ کرنے کے لیے اہداف کے ایک سیٹ کے لیے مختلف قسم کے ہتھیاروں کے ایک سیٹ کی زیادہ سے زیادہ تفویض تلاش کرنا شامل ہے۔ بنیادی مسئلہ مندرجہ ذیل ہے: کئی ہتھیار اور کئی اہداف ہیں۔ ہتھیار قسم کے ہوتے ہیں۔ اس قسم کے ہتھیار دستیاب ہیں۔ اسی طرح، اہداف ہیں، جن میں سے ہر ایک کی قیمت ہے۔ کسی بھی ہتھیار کو کسی بھی ہدف کو تفویض کیا جا سکتا ہے۔ ہر قسم کے ہتھیار میں ہر ہدف کو تباہ کرنے کا ایک خاص امکان ہوتا ہے۔ نوٹ کریں کہ کلاسک اسائنمنٹ کے مسئلے یا عمومی اسائنمنٹ کے مسئلے کے برخلاف، ہر کام (یعنی ہدف) کے لیے ایک سے زیادہ ایجنٹ (یعنی ہتھیار) تفویض کیے جا سکتے ہیں اور تمام اہداف کو ہتھیار تفویض کرنے کی ضرورت نہیں ہے۔ اس طرح، ہم دیکھتے ہیں کہ ڈبلیو ٹی اے کسی کو زیادہ سے زیادہ تفویض کے مسائل وضع کرنے کی اجازت دیتا ہے جس میں کاموں کے لیے ایجنٹوں کے درمیان تعاون کی ضرورت ہوتی ہے۔ مزید برآں، یہ اخراجات کے علاوہ کاموں کی ممکنہ تکمیل کا نمونہ بنانے کی صلاحیت فراہم کرتا ہے۔ ڈبلیو ٹی اے کے جامد اور متحرک دونوں ورژن پر غور کیا جا سکتا ہے۔ جامد صورت میں، ہتھیار ایک بار اہداف کو تفویض کیے جاتے ہیں۔ متحرک کیس میں تفویض کے کئی دور شامل ہوتے ہیں جہاں اگلے دور میں آگ کے ہر تبادلے (گول) کے بعد نظام کی حالت پر غور کیا جاتا ہے۔ اگرچہ زیادہ تر کام جامد ڈبلیو ٹی اے کے مسئلے پر کیا گیا ہے، حال ہی میں متحرک ڈبلیو ٹی اے کے مسئلے پر زیادہ توجہ دی گئی ہے۔ نام کے باوجود، ڈبلیو ٹی اے کی غیر فوجی ایپلی کیشنز موجود ہیں۔ اہم بات یہ ہے کہ کتوں، ہوائی جہاز، پیدل چلنے والوں وغیرہ جیسے متنوع اثاثوں کے ذریعے گمشدہ شے یا شخص کی تلاش کی جائے۔ مسئلہ یہ ہے کہ اثاثوں کو اس جگہ کی تقسیم کے لیے تفویض کیا جائے جس میں شے واقع ہے تاکہ شے کو نہ ملنے کے امکان کو کم سے کم کیا جا سکے۔ تقسیم کے ہر عنصر کی "قدر" اس بات کا امکان ہے کہ شے وہاں واقع ہے۔ رسمی ریاضیاتی تعریف ہتھیاروں کے ہدف کی تفویض کا مسئلہ اکثر مندرجہ ذیل غیر لکیری عدد پروگرامنگ کے مسئلے کے طور پر وضع کیا جاتا ہے: ان رکاوٹوں کے تابع جہاں متغیر ہدف بنانے کے لیے زیادہ سے زیادہ قسم کے ہتھیاروں کی تفویض کی نمائندگی کرتا ہے اور بقا کا امکان ہے ()۔ پہلی رکاوٹ یہ ہے کہ تفویض کردہ ہر قسم کے ہتھیاروں کی تعداد دستیاب تعداد سے زیادہ نہ ہو۔ دوسری رکاوٹ لازمی رکاوٹ ہے۔ نوٹ کریں کہ متوقع بقا کی قیمت کو کم کرنا متوقع نقصان کو زیادہ سے زیادہ کرنے کے مترادف ہے۔ الگورتھم اور عامیاں برانچ اور باؤنڈ تکنیکوں کا استعمال کرتے ہوئے ایک درست حل پایا جا سکتا ہے جو نرمی (تخمینہ) کا استعمال کرتے ہیں۔ بہت سے ہیورسٹک الگورتھم تجویز کیے گئے ہیں جو کثیر الجہتی وقت میں قریب ترین حل فراہم کرتے ہیں۔ مثال ایک کمانڈر کے پاس 5 ٹینک، 2 ہوائی جہاز، اور 1 سمندری جہاز ہوتا ہے اور اسے 5، 10، اور 20 اقدار کے ساتھ 3 اہداف کو نشانہ بنانے کے لیے کہا جاتا ہے۔ ہر ہتھیار کی قسم میں ہر ہدف کے خلاف کامیابی کے درج ذیل امکانات ہوتے ہیں: {| کلاس = "ویکیٹیبل" |-! ہتھیاروں کی قسم! ! ! ! ! ! |-| ٹینک | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | اس کے نتیجے میں بقا کی متوقع قیمت ہوتی ہے۔ اس کے بعد کوئی بھی بقیہ طیارے اور 2 ٹینکوں کو #2 کو نشانہ بنانے کے لیے تفویض کر سکتا ہے، جس کے نتیجے میں بقا کی متوقع قیمت. آخر میں، باقی 3 ٹینکوں کو ہدف #1 کے لیے تفویض کیا جاتا ہے جس کی بقا کی قیمت متوقع ہے۔ اس طرح، ہمارے پاس بقا کی کل متوقع قیمت ہے۔ نوٹ کریں کہ #1 کو نشانہ بنانے کے لیے 3 ٹینک، #2 کو نشانہ بنانے کے لیے 2 ٹینک اور سمندری جہاز اور #3 کو نشانہ بنانے کے لیے 2 طیارے تفویض کر کے ایک بہتر حل حاصل کیا جا سکتا ہے، جس سے بقا کی متوقع قیمت مل سکتی ہے۔ نیلامی الگورتھم بندش مسئلہ عمومی تفویض مسئلہ لکیری رکاوٹ تفویض مسئلہ کواڈریٹک اسائنمنٹ مسئلہ مستحکم شادی کا مسئلہ حوالہ جات مزید پڑھنا مشترکہ اصلاح ملاپ (گراف تھیوری) جنگی ماڈلنگ