Weapon target assignment problem
অস্ত্র টার্গেট অ্যাসাইনমেন্ট সমস্যা (ডব্লিউ. টি. এ) হল অপ্টিমাইজেশন এবং অপারেশন গবেষণার ক্ষেত্রে উপস্থিত সমন্বিত অপ্টিমাইজেশন সমস্যার একটি শ্রেণী। এটি প্রতিপক্ষের মোট প্রত্যাশিত ক্ষতি সর্বাধিক করার জন্য লক্ষ্যগুলির একটি সেটের জন্য বিভিন্ন ধরনের অস্ত্রের একটি সর্বোত্তম বরাদ্দ খুঁজে বের করা নিয়ে গঠিত। মূল সমস্যাটি নিম্নরূপঃ বেশ কয়েকটি অস্ত্র এবং বেশ কয়েকটি লক্ষ্য রয়েছে। অস্ত্রগুলো এক ধরনের। এই ধরনের অস্ত্র পাওয়া যায়। একইভাবে, লক্ষ্য রয়েছে, যার প্রত্যেকটির একটি মান রয়েছে। যে কোনও অস্ত্র যে কোনও লক্ষ্যে স্থাপন করা যেতে পারে। প্রতিটি অস্ত্রের প্রকারের দ্বারা প্রদত্ত প্রতিটি লক্ষ্য ধ্বংস করার একটি নির্দিষ্ট সম্ভাবনা রয়েছে। লক্ষ্য করুন যে ক্লাসিক অ্যাসাইনমেন্ট সমস্যা বা সাধারণ অ্যাসাইনমেন্ট সমস্যার বিপরীতে, প্রতিটি কাজে একাধিক এজেন্ট (অর্থাৎ, অস্ত্র) নিযুক্ত করা যেতে পারে (অর্থাৎ, লক্ষ্য) এবং সমস্ত লক্ষ্যের জন্য অস্ত্র বরাদ্দ করার প্রয়োজন হয় না। এইভাবে, আমরা দেখতে পাই যে ডব্লিউটিএ একজনকে সর্বোত্তম অ্যাসাইনমেন্ট সমস্যা তৈরি করার অনুমতি দেয় যেখানে কাজগুলির জন্য এজেন্টদের মধ্যে সহযোগিতা প্রয়োজন। উপরন্তু, এটি খরচ ছাড়াও কাজগুলির সম্ভাব্য সমাপ্তির মডেল করার ক্ষমতা প্রদান করে। ডব্লিউ. টি. এ-র স্থির এবং গতিশীল উভয় সংস্করণই বিবেচনা করা যেতে পারে। স্থির ক্ষেত্রে, অস্ত্রগুলি একবার লক্ষ্যবস্তুতে বরাদ্দ করা হয়। গতিশীল ক্ষেত্রে অনেক রাউন্ডের অ্যাসাইনমেন্ট জড়িত থাকে যেখানে পরবর্তী রাউন্ডে প্রতিটি গুলি বিনিময়ের (রাউন্ড) পরে সিস্টেমের অবস্থা বিবেচনা করা হয়। যদিও বেশিরভাগ কাজ স্ট্যাটিক ডব্লিউ. টি. এ সমস্যা নিয়ে করা হয়েছে, সম্প্রতি গতিশীল ডব্লিউ. টি. এ সমস্যা আরও বেশি মনোযোগ পেয়েছে। নাম সত্ত্বেও, ডব্লিউ. টি. এ-র অসামরিক প্রয়োগ রয়েছে। প্রধানটি হল কুকুর, বিমান, ওয়াকার ইত্যাদির মতো বৈচিত্র্যময় সম্পদ দ্বারা হারিয়ে যাওয়া বস্তু বা ব্যক্তির সন্ধান করা। সমস্যাটি হ 'ল বস্তুটিকে খুঁজে না পাওয়ার সম্ভাবনা হ্রাস করার জন্য বস্তুটিকে যে স্থানে অবস্থিত তার একটি বিভাজনে সম্পদ বরাদ্দ করা। বিভাজনের প্রতিটি উপাদানের "মান" হল বস্তুটির সেখানে অবস্থিত হওয়ার সম্ভাবনা। আনুষ্ঠানিক গাণিতিক সংজ্ঞা অস্ত্রের টার্গেট অ্যাসাইনমেন্ট সমস্যাটি প্রায়শই নিম্নলিখিত অরৈখিক পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা হিসাবে প্রণয়ন করা হয়ঃ সীমাবদ্ধতার সাপেক্ষে যেখানে পরিবর্তনশীলটি লক্ষ্য করার জন্য যতগুলি অস্ত্রের বরাদ্দকে উপস্থাপন করে এবং বেঁচে থাকার সম্ভাবনা ()। প্রথম সীমাবদ্ধতার জন্য প্রয়োজন যে নির্ধারিত প্রতিটি ধরনের অস্ত্রের সংখ্যা উপলব্ধ সংখ্যার বেশি হবে না। দ্বিতীয় সীমাবদ্ধতা হল অবিচ্ছেদ্য সীমাবদ্ধতা। লক্ষ্য করুন যে প্রত্যাশিত বেঁচে থাকার মান হ্রাস করা প্রত্যাশিত ক্ষতি সর্বাধিক করার মতোই। অ্যালগরিদম এবং সাধারণীকরণ শাখা এবং আবদ্ধ কৌশল ব্যবহার করে একটি সঠিক সমাধান খুঁজে পাওয়া যায় যা শিথিলকরণ (আনুমানিক) ব্যবহার করে। অনেক হিউরিস্টিক অ্যালগরিদম প্রস্তাব করা হয়েছে যা বহুপদী সময়ে প্রায়-সর্বোত্তম সমাধান প্রদান করে। উদাহরণ একজন কমান্ডারের 5টি ট্যাঙ্ক, 2টি বিমান এবং 1টি সামুদ্রিক জাহাজ থাকে এবং তাকে 5,10 এবং 20 মানের 3টি লক্ষ্যবস্তুতে আঘাত হানতে বলা হয়। প্রতিটি অস্ত্রের প্রকারের প্রতিটি লক্ষ্যের বিরুদ্ধে নিম্নলিখিত সাফল্যের সম্ভাবনা রয়েছেঃ {। শ্রেণী = "উইকিটেবল"।-! অস্ত্রের ধরণ! ! ! ! ! ! ।-। ট্যাঙ্ক।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।।। এর ফলে একটি প্রত্যাশিত বেঁচে থাকার মান পাওয়া যায়। তারপরে কেউ অবশিষ্ট বিমান এবং 2টি ট্যাঙ্ককে #2 লক্ষ্য করার জন্য বরাদ্দ করতে পারে, যার ফলে প্রত্যাশিত বেঁচে থাকার মান। অবশেষে, বাকি 3টি ট্যাঙ্ককে #1 লক্ষ্য করার জন্য বরাদ্দ করা হয় যার একটি প্রত্যাশিত বেঁচে থাকার মান রয়েছে। সুতরাং, আমাদের মোট প্রত্যাশিত বেঁচে থাকার মান রয়েছে। লক্ষ্য করুন যে, 3টি ট্যাঙ্ক #1,2টি ট্যাঙ্ক এবং সমুদ্র জাহাজ #2 লক্ষ্য করার জন্য এবং 2টি বিমান #3 লক্ষ্য করার জন্য বরাদ্দ করে একটি ভাল সমাধান অর্জন করা যেতে পারে, যা একটি প্রত্যাশিত বেঁচে থাকার মান দেয়। আরও দেখুন নিলাম অ্যালগরিদম ক্লোজার প্রবলেম জেনারেলাইজড অ্যাসাইনমেন্ট প্রবলেম লিনিয়ার বাটলনেক অ্যাসাইনমেন্ট প্রবলেম কোয়াড্রাটিক অ্যাসাইনমেন্ট প্রবলেম স্টেবল ম্যারিজ প্রবলেম রেফারেন্স আরও পড়ুন কম্বিনেটোরিয়াল অপ্টিমাইজেশন ম্যাচিং (গ্রাফ থিওরি) কমব্যাট মডেলিং