रैखिक प्रोग्रामिंग में असाइनमेंट समस्या: परिचय और असाइनमेंट मॉडल

असाइनमेंट समस्या एक विशेष प्रकार की लीनियर प्रोग्रामिंग समस्या है जो विभिन्न संसाधनों के आवंटन को विभिन्न गतिविधियों के लिए एक से एक आधार पर करती है। यह इस तरह से करता है कि प्रक्रिया में शामिल लागत या समय न्यूनतम है और लाभ या बिक्री अधिकतम है। हालांकि समस्याओं को सरल विधि या परिवहन विधि द्वारा हल किया जा सकता है लेकिन असाइनमेंट मॉडल इन समस्याओं के लिए एक सरल दृष्टिकोण प्रदान करता है।

एक कारखाने में, एक पर्यवेक्षक में छह श्रमिक उपलब्ध हो सकते हैं और आग में छह काम हो सकते हैं। उसे यह निर्णय लेना होगा कि किस कर्मचारी को कौन सी नौकरी दी जानी चाहिए। समस्या एक से एक आधार बनाती है। यह असाइनमेंट की समस्या है।

1. असाइनमेंट मॉडल:

मान लीजिए कि एन सुविधा और एन नौकरियां हैं, तो यह स्पष्ट है कि इस मामले में, एन असाइनमेंट होंगे। प्रत्येक सुविधा या कहें कि कार्यकर्ता एक समय में एक काम कर सकता है। लेकिन कुछ निश्चित प्रक्रिया होनी चाहिए जिसके द्वारा असाइनमेंट किया जाना चाहिए ताकि लाभ अधिकतम हो या लागत या समय कम से कम हो।

तालिका में, सह _ij को लागत के रूप में परिभाषित किया गया है जब j ^th job i ^वें कार्यकर्ता को सौंपा गया है। यह शायद यहाँ उल्लेख किया है कि यह परिवहन समस्या का एक विशेष मामला है जब पंक्तियों की संख्या स्तंभों की संख्या के बराबर होती है।

गणितीय सूत्रीकरण:

असाइनमेंट समस्या के किसी भी मूल संभव समाधान में (2n - 1) चर होते हैं, जिनमें से (n - 1) चर शून्य होते हैं, n नौकरियों की संख्या या सुविधाओं की संख्या होती है। इस उच्च पतन के कारण, यदि हम सामान्य परिवहन विधि द्वारा समस्या का समाधान करते हैं, तो यह एक जटिल और समय लेने वाला कार्य होगा। इस प्रकार एक अलग तकनीक इसके लिए व्युत्पन्न है। निरपेक्ष विधि में जाने से पहले समस्या को तैयार करना बहुत महत्वपूर्ण है।

मान लीजिए कि x _jj एक वैरिएबल है जिसे परिभाषित किया गया है

1 यदि i ^th जॉब j मशीन या सुविधा को सौंपा गया है

0 यदि i ^th जॉब j मशीन या सुविधा को नहीं सौंपा गया है।

अब चूंकि समस्या एक से एक आधार के रूप में है या एक नौकरी एक सुविधा या मशीन को सौंपी जानी है।

कुल असाइनमेंट लागत द्वारा दिया जाएगा

उपरोक्त परिभाषा को गणितीय मॉडल में निम्नानुसार विकसित किया जा सकता है:

क्रम में x _ij > 0 (i, j = 1, 2, 3… n) निर्धारित करें

विवश करने के लिए अधीन

और x _ij या तो शून्य या एक है।

समस्या को हल करने की विधि (हंगेरियन तकनीक):

न्यूनतम प्रकार के उद्देश्य समारोह पर विचार करें। निम्नलिखित कदम इस असाइनमेंट समस्या को हल करने में शामिल हैं,

1. पहली पंक्ति से शुरू होने वाली दी गई लागत तालिका की प्रत्येक पंक्ति में सबसे छोटी लागत तत्व का पता लगाएँ। अब, यह सबसे छोटा तत्व उस पंक्ति के प्रत्येक तत्व को घटाया जाता है। इसलिए, हमें इस नई तालिका की प्रत्येक पंक्ति में कम से कम एक शून्य प्राप्त होगा।

2. तालिका का निर्माण (चरण -1 के अनुसार) तालिका के स्तंभों को लें। पहले कॉलम से शुरू करके प्रत्येक कॉलम में सबसे छोटे लागत तत्व का पता लगाएं। अब इस सबसे छोटे तत्व को उस कॉलम के प्रत्येक तत्व से घटाएं। चरण 1 और चरण 2 का प्रदर्शन करने के बाद, हमें कम लागत तालिका में प्रत्येक कॉलम में कम से कम एक शून्य प्राप्त होगा।

3. अब, असाइनमेंट निम्न तरीके से निम्न तालिका के लिए किए गए हैं।

(i) पंक्तियों की क्रमिक रूप से जांच की जाती है, जब तक कि पंक्ति एक एकल (एक) शून्य के साथ न मिल जाए। इस एकल शून्य को इसके चारों ओर वर्ग square लगाकर और इसी कॉलम में, अन्य सभी शून्य (x) को पार कर लिया जाता है क्योंकि इनका उपयोग इस कॉलम में कोई अन्य असाइनमेंट बनाने के लिए नहीं किया जाएगा। प्रत्येक पंक्ति के लिए चरण का संचालन किया जाता है।

(ii) चरण 3 (i) अब निम्नानुसार स्तंभों पर किया जाता है: - स्तंभों की क्रमिक रूप से तब तक जांच की जाती है जब तक कि एक शून्य के साथ एक स्तंभ न मिल जाए। अब, इस एकल शून्य को इसके चारों ओर वर्ग डालकर असाइनमेंट किया जाता है और उसी समय, इसी पंक्तियों में अन्य सभी शून्य को पार किया जाता है (x) चरण प्रत्येक कॉलम के लिए आयोजित किया जाता है।

(iii) चरण 3, (i) और 3 (ii) तब तक दोहराया जाता है जब तक कि सभी शून्य या तो चिह्नित या पार नहीं हो जाते हैं। अब, यदि चिह्नित शून्य या किए गए असाइनमेंट की संख्या पंक्तियों या स्तंभों की संख्या के बराबर है, तो इष्टतम समाधान प्राप्त किया गया है। बिना किसी असाइनमेंट के प्रत्येक या कॉलम में बिल्कुल एकल असाइनमेंट होगा। इस मामले में, हम चरण 4 पर जाएंगे।

4. इस स्तर पर, चरण 3 में प्राप्त मैट्रिक्स में सभी शून्य को कवर करने के लिए आवश्यक न्यूनतम संख्या की रेखाएं (क्षैतिज और ऊर्ध्वाधर) ड्रा करें, निम्नलिखित प्रक्रिया अपनाई गई है:

(i) टिक मार्क (

(ii) अब टिक मार्क (

(iii) अब उन सभी पंक्तियों को चिह्नित करें जो पहले से चिह्नित नहीं हैं और जिनका चिह्नित कॉलम में असाइनमेंट है।

(iv) सभी चरणों अर्थात (4 (i), 4 (ii), 4 (iii) को तब तक दोहराया जाता है जब तक कि अधिक पंक्तियों या स्तंभों को चिह्नित नहीं किया जा सकता है।

(v) अब सीधी रेखाएँ खींचिए जो सभी चिन्हित पंक्तियों और चिन्हित स्तंभों से होकर गुजरती हैं। यह भी देखा जा सकता है कि एक nxn मैट्रिक्स में, हमेशा 'n' लाइनों से कम सभी शून्य को कवर करेगा यदि उनके बीच कोई समाधान नहीं है।

5. चरण 4 में, यदि तैयार की गई रेखाओं की संख्या n या पंक्तियों की संख्या के बराबर है, तो यह इष्टतम समाधान है यदि नहीं, तो चरण 6 पर जाएं।

6. सभी खुला तत्वों में से सबसे छोटे तत्व का चयन करें। अब, इस तत्व को सभी खुले हुए तत्वों से घटाया गया है और उस तत्व में जोड़ा गया है जो दो रेखाओं के चौराहे पर स्थित है। यह ताजा कार्य के लिए मैट्रिक्स है।

7. चरण (3) से प्रक्रिया को दोहराएं जब तक कि असाइनमेंट की संख्या पंक्तियों की संख्या या स्तंभों की संख्या के बराबर न हो जाए।