- हंगेरियन विधि क्या है?
- चरण 1: प्रत्येक पंक्ति की मिनीमा घटाएं
- चरण 2: प्रत्येक कॉलम से न्यूनतम को घटाएं
- चरण 3: सभी शून्य को कम से कम लाइनों के साथ कवर करें
- चरण 4: अतिरिक्त शून्य बनाएं
- इष्टतम आवंटन
- उदाहरण
- चरण 1: प्रत्येक पंक्ति की मिनीमा घटाएं
- चरण 2: प्रत्येक कॉलम से न्यूनतम को घटाएं
- चरण 3: सभी शून्य को कम से कम लाइनों के साथ कवर करें
- चरण 4: अतिरिक्त शून्य बनाएं
- चरण 3 (दोहराएं)
- इष्टतम आवंटन
- संदर्भ
हंगेरी विधि एक एल्गोरिथ्म है कि आवंटन की समस्याओं में प्रयोग किया जाता है जब आप लागत को कम करना चाहते हैं। यही है, इसका उपयोग कम से कम लागत के आधार पर कई लोगों को विभिन्न गतिविधियों को निर्दिष्ट करके न्यूनतम लागत खोजने के लिए किया जाता है। प्रत्येक गतिविधि को एक अलग व्यक्ति को सौंपा जाना चाहिए।
एक आवंटन समस्या एक विशेष प्रकार की रैखिक प्रोग्रामिंग समस्या है, जहां लक्ष्य कई लोगों द्वारा कई नौकरियों को पूरा करने की लागत या समय को कम करना है।
स्रोत: pixabay.com
आवंटन समस्या की एक महत्वपूर्ण विशेषता यह है कि केवल एक काम (या कार्यकर्ता) एक मशीन (या परियोजना) को सौंपा जाता है।
इस पद्धति को हंगरी के गणितज्ञ डी। कोनिग द्वारा विकसित किया गया था। इस कारण से, इसे असाइनमेंट समस्याओं के लिए हंगेरियन विधि के रूप में जाना जाता है। इसे कुहन-मुनरेस आवंटन एल्गोरिथ्म के रूप में भी जाना जाता है।
इस पद्धति को लागू करके किसी भी आवंटन समस्या को आसानी से हल किया जा सकता है जिसमें दो चरण होते हैं:
- पहले चरण के साथ पंक्ति में कटौती और कॉलम में कटौती की जाती है।
- दूसरे चरण में समाधान को पुनरावृत्त आधार पर अनुकूलित किया जाता है।
हंगेरियन विधि क्या है?
हंगेरियन विधि में चार चरण होते हैं। पहले दो चरणों को केवल एक बार निष्पादित किया जाता है, जबकि चरण 3 और 4 दोहराए जाते हैं जब तक कि एक इष्टतम आवंटन नहीं मिलता है।
N द्वारा n के क्रम के एक वर्ग मैट्रिक्स को इनपुट डेटा के रूप में माना जाता है, जिसमें केवल गैर-नकारात्मक तत्व शामिल होने चाहिए।
किसी दिए गए समस्या के लिए, यदि मैट्रिक्स में पंक्तियों की संख्या स्तंभों की संख्या के बराबर नहीं है, तो डमी पंक्ति या डमी कॉलम को केस के आधार पर जोड़ा जाना चाहिए। उन डमी कोशिकाओं के लिए आवंटन लागत हमेशा शून्य के रूप में आवंटित की जाती है।
चरण 1: प्रत्येक पंक्ति की मिनीमा घटाएं
सरणी में प्रत्येक पंक्ति के लिए, उस पंक्ति के प्रत्येक तत्व से सबसे कम मान वाला तत्व चयनित और घटाया जाता है।
चरण 2: प्रत्येक कॉलम से न्यूनतम को घटाएं
इसी तरह, प्रत्येक कॉलम के लिए न्यूनतम मान वाली वस्तु का चयन किया जाता है और उस कॉलम के प्रत्येक आइटम से घटाया जाता है।
चरण 3: सभी शून्य को कम से कम लाइनों के साथ कवर करें
चरण 2 से उत्पन्न मैट्रिक्स में सभी शून्य को क्षैतिज या ऊर्ध्वाधर लाइनों की एक न्यूनतम संख्या का उपयोग करके कवर किया जाना चाहिए, या तो पंक्तियों या स्तंभों द्वारा।
यदि सभी शून्य को कवर करने के लिए कुल एन लाइनों की आवश्यकता होती है, जहां n मैट्रिक्स के आकार n n n के बराबर है, तो शून्य के बीच एक इष्टतम आवंटन होगा और इसलिए एल्गोरिथ्म बंद हो जाता है।
अन्यथा, यदि सरणी में सभी शून्य को कवर करने के लिए n से कम लाइनों की आवश्यकता होती है, तो चरण 4 पर आगे बढ़ें।
चरण 4: अतिरिक्त शून्य बनाएं
मैट्रिक्स का सबसे छोटा तत्व (जिसे k कहा जाता है) जो चरण 3 में बनाई गई लाइनों में से एक द्वारा कवर नहीं किया गया है।
K का मान उन सभी तत्वों से घटाया जाता है जो लाइनों द्वारा कवर नहीं किए गए हैं। इसके बाद, का का मान उन सभी तत्वों में जोड़ा जाता है जो दो लाइनों के प्रतिच्छेदन द्वारा कवर होते हैं।
एकल पंक्ति द्वारा कवर किए गए आइटम को वैसे ही छोड़ दिया जाता है। इस चरण को करने के बाद, आप चरण 3 पर लौट आते हैं।
इष्टतम आवंटन
एल्गोरिथ्म को चरण 3 में बंद करने के बाद, शून्य का एक सेट इस तरह चुना जाता है कि प्रत्येक पंक्ति और प्रत्येक कॉलम में केवल एक शून्य चुना गया हो।
यदि इस चयन प्रक्रिया में एक पंक्ति या स्तंभ में एक भी शून्य नहीं है, तो उन शून्य में से एक को चुना जाएगा। उस कॉलम या पंक्ति में शेष शून्य हटा दिए जाते हैं, साथ ही साथ अन्य असाइनमेंट के लिए भी इसे दोहराते हैं।
यदि कोई एकल शून्य असाइनमेंट नहीं है, तो कई समाधान हैं। हालांकि, विभिन्न असाइनमेंट के लिए लागत समान रहेगी।
जो भी डमी रो या कॉलम जोड़े गए हैं, उन्हें हटा दिया गया है। इस अंतिम मैट्रिक्स में चुने गए शून्य इस प्रकार मूल मैट्रिक्स में आवश्यक आदर्श असाइनमेंट के अनुरूप हैं।
उदाहरण
आइए एक कंपनी पर विचार करें जहां चार गतिविधियां हैं (ए 1, ए 2, ए 3, ए 4) जिन्हें चार श्रमिकों (टी 1, टी 2, टी 3, टी 4) द्वारा किया जाना चाहिए। प्रति कार्यकर्ता एक गतिविधि सौंपी जानी चाहिए।
निम्नलिखित मैट्रिक्स एक निश्चित कार्यकर्ता को एक निश्चित गतिविधि को निर्दिष्ट करने की लागत को दर्शाता है। उद्देश्य इन चार गतिविधियों से बने कार्य की कुल लागत को कम करना है।
चरण 1: प्रत्येक पंक्ति की मिनीमा घटाएं
आप उस पंक्ति में अन्य तत्वों से प्रत्येक पंक्ति में न्यूनतम मूल्य के साथ तत्व को घटाकर शुरू करते हैं। उदाहरण के लिए, पहली पंक्ति में सबसे छोटा तत्व 69 है। इसलिए, पहली पंक्ति में प्रत्येक तत्व से 69 घटाया जाता है। परिणामी मैट्रिक्स है:
चरण 2: प्रत्येक कॉलम से न्यूनतम को घटाएं
उसी तरह, प्रत्येक स्तंभ के न्यूनतम मूल्य के साथ तत्व उस मैट्रिक्स के अन्य तत्वों से घटाया जाता है, जो निम्नलिखित मैट्रिक्स प्राप्त करता है:
चरण 3: सभी शून्य को कम से कम लाइनों के साथ कवर करें
अब हम लाइनों की न्यूनतम संख्या (क्षैतिज या ऊर्ध्वाधर) निर्धारित करेंगे जो मैट्रिक्स में सभी शून्य को कवर करने के लिए आवश्यक हैं। सभी शून्य को 3 लाइनों का उपयोग करके कवर किया जा सकता है:
चूंकि आवश्यक लाइनों की संख्या तीन है और यह मैट्रिक्स के आकार (n = 4) से कम है, हम चरण 4 के साथ जारी रखते हैं।
चरण 4: अतिरिक्त शून्य बनाएं
लाइनों द्वारा कवर नहीं किए जाने वाले सबसे छोटे तत्व का चयन किया जाता है, जिसका मूल्य 6. है। यह मान कवर नहीं किए गए सभी तत्वों से घटाया जाता है और इसी मूल्य को दो रेखाओं के प्रतिच्छेदन द्वारा कवर किए गए सभी तत्वों में जोड़ा जाता है। इसका परिणाम निम्न मैट्रिक्स में है:
जैसा कि हंगेरियन पद्धति में संकेत दिया गया है, चरण तीन को फिर से किया जाना चाहिए।
चरण 3 (दोहराएं)
फिर से मैट्रिक्स में सभी शून्य को कवर करने के लिए आवश्यक लाइनों की न्यूनतम संख्या निर्धारित की जाती है। इस समय चार लाइनें आवश्यक हैं:
क्योंकि आवश्यक लाइनों की संख्या मैट्रिक्स के आकार (n = 4) के बराबर है, हमारे पास मैट्रिक्स में शून्य के बीच एक इष्टतम आवंटन है। इसलिए, एल्गोरिथ्म बंद हो जाता है।
इष्टतम आवंटन
जैसा कि विधि इंगित करती है, निम्नलिखित शून्य से बना चयन एक इष्टतम असाइनमेंट से मेल खाता है:
शून्य का यह चयन मूल लागत मैट्रिक्स में निम्नलिखित इष्टतम आवंटन से मेल खाता है:
इसलिए, वर्कर 1 को एक्टिविटी 3, वर्कर 2, एक्टिविटी 2, वर्कर 3, एक्टिविटी 1, और वर्कर 4 को एक्टिविटी 4 करनी चाहिए। इस इष्टतम असाइनमेंट की कुल लागत 69 + 37 + है। ११ + २३ = १४०।
संदर्भ
- हंगेरियन एल्गोरिथम (2019)। हंगरी एल्गोरिथ्म। से लिया गया:।
- अध्ययन (2019)। असाइनमेंट समस्याओं को हल करने के लिए हंगेरियन एल्गोरिथम का उपयोग करना। से लिया गया: study.com।
- बुद्धि नौकरियां (2018)। असाइनमेंट समस्या के समाधान के लिए हंगेरियन विधि - प्रबंधन के लिए मात्रात्मक तकनीक। से लिया गया: knowledgejobs.com
- Geeks for Geeks (2019)। असाइनमेंट की समस्या के लिए हंगेरियन एल्गोरिथम। से लिया गया: geeksforgeeks.org
- कार्लेघ मूर, नाथन लैंडमैन (2019)। हंगरी अधिकतम मिलान एल्गोरिथ्म। प्रतिभाशाली। से लिया गया: Bright.org।