असाइनमेंट समस्या समाधानकर्ता

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

असाइनमेंट समस्या एक मूलभूत संयोजी अनुकूलन समस्या है: n एजेंट और n कार्यों के साथ लागत मैट्रिक्स C दिया गया, कुल लागत को न्यूनतम करने वाला एक-से-एक असाइनमेंट खोजें।

हंगेरियन एल्गोरिथम (Kuhn-Munkres, 1955) O(n³) में हल करता है। पंक्ति और स्तंभ घटाव द्वारा लागत मैट्रिक्स को पुनरावृत्त रूप से कम करता है।

आयताकार मैट्रिक्स के लिए 0 लागत की डमी पंक्तियाँ/स्तंभ जोड़े जाते हैं। असाइन न किए गए एजेंट/कार्य अलग से रिपोर्ट किए जाते हैं।

Formula: न्यूनतम करें Σ C[i][σ(i)] सभी i के लिए शर्त: σ एक क्रमचय (एक-से-एक मैपिंग) हो Hungarian चरण: 1. पंक्ति न्यूनतम घटाएँ 2. स्तंभ न्यूनतम घटाएँ 3. न्यूनतम रेखाओं से शून्यों को ढकें 4. मैट्रिक्स समायोजित करें, इष्टतम होने तक दोहराएँ

गणना उदाहरण

लागत मैट्रिक्स: [[9,2,7],[6,4,3],[5,8,1]]। पंक्ति न्यूनीकरण → [[7,0,5],[3,1,0],[4,7,0]]। स्तंभ न्यूनीकरण → [[4,0,5],[0,1,0],[1,7,0]]। शून्य वाले खाने हर एजेंट को एक कार्य देते हैं: एजेंट 1→कार्य 2 (लागत 2), एजेंट 2→कार्य 1 (लागत 6), एजेंट 3→कार्य 3 (लागत 1)। कुल लागत = 9 — आकर्षक दिखने वाली जोड़ी एजेंट 2→कार्य 3, एजेंट 3→कार्य 1 (10) से कम।

इस कैलकुलेटर का उपयोग कब करें

• कोई उत्पादन पर्यवेक्षक जो कुल प्रसंस्करण समय या लागत न्यूनतम करने के लिए कार्यकर्ताओं को मशीनों पर नियुक्त कर रहा हो
• कोई प्रोजेक्ट प्रबंधक जो कौशल मिलान और प्रयास अनुमानों के आधार पर टीम सदस्यों को कार्यों में आवंटित कर रहा हो
• कोई लॉजिस्टिक्स समन्वयक जो कुल यात्रा दूरी न्यूनतम करने के लिए डिलीवरी वाहनों को मार्गों पर नियुक्त कर रहा हो
• कोई विश्वविद्यालय प्रशासक जो टकराव या पैदल दूरी न्यूनतम करने के लिए पाठ्यक्रमों हेतु परीक्षा कक्ष निर्धारित कर रहा हो

बचने योग्य सामान्य गलतियाँ

• लागतें असंगत रूप से दर्ज करना — लागत मैट्रिक्स के सभी मान एक ही इकाई (डॉलर, घंटे, दूरी) में होने चाहिए; इकाइयाँ मिलाने से अर्थहीन असाइनमेंट बनते हैं
• न्यूनतम और अधिकतम मोड के बीच बदलना भूल जाना — यदि आप लाभ या वरीयता (जितना अधिक उतना बेहतर) के आधार पर असाइन कर रहे हैं तो maximize चुनें; लागत या समय (जितना कम उतना बेहतर) के लिए minimize चुनें
• प्रति एजेंट कई असाइनमेंट वाली समस्याओं के लिए असाइनमेंट का उपयोग करना — Hungarian एल्गोरिद्म प्रत्येक एजेंट को ठीक एक कार्य देता है; यदि एजेंट कई कार्य संभाल सकते हैं तो भिन्न मॉडल उपयोग करें
• असंभव युग्मों को न संभालना — यदि कुछ एजेंट-कार्य संयोजन असंभव हैं, तो उनकी लागत को शून्य छोड़ने के बजाय बहुत बड़ी संख्या पर सेट करें

परिणामों की व्याख्या कैसे करें

• कुल लागत वैश्विक इष्टतम दर्शाती है — कोई अन्य एक-से-एक असाइनमेंट इससे कम (या अधिकतमकरण में अधिक) कुल प्राप्त नहीं कर सकता
• यदि कुछ पंक्तियाँ या स्तंभ अनिर्धारित दिखाए गए हैं, तो एजेंट कार्यों से अधिक हैं (या इसके विपरीत) — ये एजेंट/कार्य मुक्त रहते हैं
• इष्टतम कुल की तुलना सरल असाइनमेंट (उदा., पंक्ति 1 को स्तंभ 1) से करें ताकि देख सकें कि एल्गोरिद्म कितना सुधार देता है

संबंधित मानक और संदर्भ

• Kuhn, H. W. (1955), 'The Hungarian Method for the Assignment Problem', Naval Research Logistics Quarterly — एल्गोरिथम का मूल प्रकाशन
• Munkres, J. (1957), 'Algorithms for the Assignment and Transportation Problems', Journal of the SIAM — वह परिष्करण जिसने बहुपद-समय निष्पादन स्थापित किया
• Burkard, Dell'Amico & Martello (2009), Assignment Problems (SIAM) — असाइनमेंट मॉडलों और एल्गोरिथमों पर व्यापक आधुनिक संदर्भ

अक्सर पूछे जाने वाले प्रश्न

क्या अधिकतमीकरण संभव है?

हाँ। सभी लागतों को नकारें या अधिकतम से घटाएं, फिर न्यूनतमीकरण हल करें। इष्टतम असाइनमेंट समान रहता है।

यदि कर्मचारी और कार्य संख्या असमान हो?

एल्गोरिथम 0 लागत की डमी पंक्तियाँ/स्तंभ जोड़ता है। डमी प्रविष्टियों का असाइनमेंट असाइन न किए गए कर्मचारी/कार्य दर्शाता है।

क्या असाइनमेंट समस्या कार्यकर्ता कौशल या उपलब्धता जैसी वास्तविक बाधाओं को संभाल सकती है?

मूल सूत्रीकरण में सीधे नहीं। हालाँकि, असंभव असाइनमेंट की लागत को बहुत बड़ी संख्या (उदा., 999999) पर सेट करके आप उन्हें एन्कोड कर सकते हैं, जिससे एल्गोरिद्म प्रभावी रूप से उन्हें चुनने से रुक जाता है। जटिल बाधाओं के लिए इंटीजर लीनियर प्रोग्रामिंग सॉल्वर पर विचार करें।