असाइनमेंट समस्या क्या है?

असाइनमेंट समस्या एक क्लासिक कॉम्बिनेटोरियल ऑप्टिमाइजेशन समस्या है: कर्मचारियों और कार्यों का एक सेट दिया गया है, प्रत्येक के साथ एक संबंधित लागत है, ऐसी एक-से-एक जोड़ी खोजें जो कुल लागत को कम करे। यह शेड्यूलिंग, लॉजिस्टिक्स, संसाधन आवंटन और संचालन अनुसंधान में स्वाभाविक रूप से दिखाई देता है — कोई भी स्थिति जहां आपको दो समूहों को सबसे कुशल तरीके से मिलान करने की आवश्यकता है।

समस्या को हंगेरियन एल्गोरिदम (जिसे Munkres एल्गोरिदम भी कहा जाता है) के साथ हल किया जाता है, एक कुशल विधि जो 1950 के दशक में विकसित की गई थी। ब्रूट-फोर्स दृष्टिकोण के विपरीत जिसे हर क्रमचय का मूल्यांकन करना चाहिए, हंगेरियन एल्गोरिदम बहुपद समय में इष्टतम समाधान खोजता है, जिससे यह मध्यम आकार के मैट्रिक्स के लिए भी व्यावहारिक है।

टूल विवरण

एक लागत मैट्रिक्स दर्ज करें जो दर्शाता है कि प्रत्येक कर्मचारी को प्रत्येक कार्य असाइन करने में कितनी लागत आती है, फिर इष्टतम असाइनमेंट तुरंत खोजने के लिए Solve पर क्लिक करें। टूल हाइलाइट करता है कि कौन सी कर्मचारी-कार्य जोड़ी कुल लागत को कम करती है और परिणाम को इष्टतम कुल लागत के साथ एक स्पष्ट तालिका में प्रदर्शित करता है।

उदाहरण

इनपुट मैट्रिक्स (3 कर्मचारी × 3 कार्य):

कार्य 1 कार्य 2 कार्य 3
कर्मचारी 1 400 150 400
कर्मचारी 2 400 450 600
कर्मचारी 3 300 225 300

इष्टतम असाइनमेंट:

कर्मचारी कार्य लागत
कर्मचारी 1 कार्य 2 150
कर्मचारी 2 कार्य 1 400
कर्मचारी 3 कार्य 3 300

कुल लागत: 850

विशेषताएं

  • संपादन योग्य मैट्रिक्स — किसी भी सेल या कॉलम हेडर पर क्लिक करें ताकि कर्मचारियों, कार्यों और लागतों का नाम सीधे तालिका में बदला जा सके
  • कॉन्फ़िगर करने योग्य आकार — 2×2 से 8×8 तक के मैट्रिक्स का समर्थन करता है
  • तत्काल परिणाम — हंगेरियन एल्गोरिदम ब्राउज़र में चलता है कोई सर्वर राउंड-ट्रिप नहीं

यह कैसे काम करता है

टूल असाइनमेंट समस्या को इष्टतम रूप से हल करने के लिए Munkres (हंगेरियन) एल्गोरिदम का उपयोग करता है। यह आपके इनपुट से एक लागत मैट्रिक्स बनाता है, पंक्ति और स्तंभ में कमी के चरणों की एक श्रृंखला लागू करता है, और पुनरावृत्ति रूप से शून्य का अधिकतम मिलान खोजता है जब तक कि एक पूर्ण इष्टतम असाइनमेंट की पहचान नहीं हो जाती। समय जटिलता $O(n^3)$ है, जहां $n$ मैट्रिक्स आयाम है।

गैर-वर्गाकार मैट्रिक्स के लिए (अधिक कर्मचारी या इसके विपरीत), एल्गोरिदम मैट्रिक्स को शून्य के साथ पैड करता है ताकि हर कर्मचारी और हर कार्य का मिलान हो।

विकल्प समझाया गया

  • कर्मचारियों की संख्या / पंक्तियां — नियंत्रित करता है कि लागत मैट्रिक्स में कितनी पंक्तियां दिखाई देती हैं (2–8)
  • कार्यों की संख्या / स्तंभ — नियंत्रित करता है कि लागत मैट्रिक्स में कितने स्तंभ दिखाई देते हैं (2–8)
  • लागत मैट्रिक्स सेल — एक विशिष्ट कर्मचारी को एक विशिष्ट कार्य असाइन करने की लागत दर्ज करें; कोई भी संख्यात्मक मान स्वीकार किया जाता है

सीमाएं

  • मैट्रिक्स आकार 8×8 (64 सेल) पर सीमित है
  • एल्गोरिदम कुल लागत को कम करता है; अधिकतम करने के लिए (उदाहरण के लिए, लाभ मैट्रिक्स के लिए), उन्हें दर्ज करने से पहले मानों को नकारें
  • गैर-संख्यात्मक सेल मान शून्य के रूप में माने जाते हैं