ऑपरेशन अनुसंधान के 3 महत्वपूर्ण उपकरण
यह लेख ऑपरेशन अनुसंधान के तीन महत्वपूर्ण उपकरणों पर प्रकाश डालता है। उपकरण हैं: 1. रैखिक प्रोग्रामिंग 2. परिवहन समस्याएं 3. असाइनमेंट समस्या।
ऑपरेशन अनुसंधान: उपकरण # 1. रैखिक प्रोग्रामिंग:
रैखिक प्रोग्रामिंग एक गणितीय तकनीक है जिसमें निर्णय समस्याओं के लगभग सभी वर्ग के लिए आवेदन है। यह तकनीक व्यवहार्य विकल्प के एक सेट से सर्वश्रेष्ठ विकल्प के रूप में चुनने के लिए लागू की जाती है।
एलपीपी उद्देश्य समारोह में और साथ ही बाधाओं को रैखिक गणितीय फ़ंक्शन के रूप में व्यक्त किया जा सकता है, जिसका उपयोग व्यावहारिक समय-निर्धारण समस्याओं को हल करने के लिए किया जा सकता है। यह सिस्टम के व्यवहार का अध्ययन करने के लिए उपयोग की जाने वाली विधि है।
एलपी मुख्य रूप से एक प्रणाली के घटकों के आपसी संबंध का वर्णन करने के साथ संबंधित है। यह तकनीक प्रबंधकों को योजना बनाने, निर्णय लेने और संसाधनों को आवंटित करने में मदद करने के लिए डिज़ाइन की गई है। प्रबंधन में हमेशा एक संगठन संसाधन का सबसे प्रभावी उपयोग करने की प्रवृत्ति होती है। संसाधनों में मशीनरी कच्चे माल, श्रम, गोदाम, समय और धन शामिल हैं।
इन संसाधनों का उपयोग विभिन्न प्रकार के उत्पादों के उत्पादन के लिए किया जा सकता है मशीनों, भागों / घटकों, फर्नीचर और खाद्य उत्पादों आदि के लिए हो सकता है। इसी प्रकार संसाधनों का उपयोग शिपिंग, विज्ञापन नीतियों और निवेश निर्णयों के लिए अनुसूची जैसे सेवा प्रदान करने के लिए किया जा सकता है।
सभी संगठनों को अपने सीमित संसाधनों के आवंटन के बारे में निर्णय लेना होगा। इसलिए संगठन के लक्ष्यों / उद्देश्यों / लक्ष्यों को प्राप्त करने के लिए लगातार संसाधनों का आवंटन करने के लिए प्रबंधन की आवश्यकता होती है।
विशेषण रैखिक का उपयोग दो या अधिक चर के बीच संबंध का वर्णन करने के लिए किया गया है। प्रोग्रामिंग का संबंध कुछ गणितीय समीकरणों के उपयोग से है, जो सीमित / दुर्लभ संसाधनों से संबंधित समस्या का सबसे अच्छा संभव समाधान प्राप्त करने के लिए उपयोग किया जाता है।
इस प्रकार रैखिक प्रोग्रामिंग का उपयोग अनुकूलन समस्याओं के लिए किया जाता है जो निम्नलिखित स्थिति को संतुष्ट करते हैं:
(i) उद्देश्य फ़ंक्शन जिसे अनुकूलित किया जाना है उसे अच्छी तरह से परिभाषित किया जाना चाहिए और चर के रैखिक फ़ंक्शन के रूप में व्यक्त किया जाना चाहिए।
(ii) यदि इन उद्देश्यों की प्राप्ति के बारे में कोई सीमा है, तो इसे चर के रैखिक गुणों / असमानताओं के रूप में भी व्यक्त किया जाता है।
(iii) कुछ वैकल्पिक पाठ्यक्रम भी उपलब्ध हैं।
(iv) निर्णय चर परस्पर संबंधित और गैर-नकारात्मक होते हैं।
(v) संसाधन सीमित हैं।
औद्योगिक समस्याओं के लिए रैखिक प्रोग्रामिंग का अनुप्रयोग:
(i) खाद्य प्रसंस्करण उद्योगों और पेट्रोलियम रिफाइनरियों आदि के लिए शेड्यूलिंग विकसित करना।
(ii) धातु के काम करने वाले उद्योगों में इसका उपयोग दुकान लोडिंग के लिए और विभिन्न भागों को खरीदने और उत्पादन करने के बीच चुनाव का निर्धारण करने के लिए किया जाता है।
(iii) इसका उपयोग लोहे और इस्पात उद्योगों में विभिन्न लौह अयस्कों के मूल्यांकन के लिए किया जाता है।
(iv) इसका उपयोग पेपर मिलों में ट्रिम लॉस की मात्रा को कम करने के लिए किया जाता है।
(v) संचार नेटवर्क में संदेशों के इष्टतम मार्ग को खोजने के लिए इसका उपयोग किया जाता है।
रैखिक प्रोग्रामिंग परिभाषा:
रैखिक प्रोग्रामिंग एक गणितीय उपकरण / तकनीक है जो किसी संगठन के संसाधनों के सर्वोत्तम उपयोग को निर्धारित करता है। रैखिक प्रोग्रामिंग को प्रबंधकों को योजना और निर्णय लेने में मदद करने के लिए डिज़ाइन किया गया है। निर्णय लेने के उपकरण के रूप में, इसने विभिन्न क्षेत्रों जैसे उत्पादन में अपना मूल्य दिखाया है; विपणन वित्त, अनुसंधान और कार्मिक असाइनमेंट।
इष्टतम उत्पाद मिश्रण का निर्धारण, परिवहन कार्यक्रम पोर्टफोलियो चयन मशीन असाइनमेंट; संयंत्र स्थान और श्रम का आवंटन आदि कुछ प्रकार की समस्याएं हैं जिन्हें रैखिक प्रोग्रामिंग की मदद से हल किया जा सकता है।
"समस्याओं का विश्लेषण जिसमें कई चर का एक रैखिक कार्य अधिकतम किया जाना है (या कम से कम) जब ये चर समानता में रैखिक के रूप में संयम की संख्या के अधीन होते हैं, " सैमुअलसन और धीमे।
लूम्बा के अनुसार, "रैखिक प्रोग्रामिंग केवल एक पहलू है जिसे प्रबंधन के लिए एक प्रणाली दृष्टिकोण कहा जाता है, जहां सभी कार्यक्रमों को डिज़ाइन किया जाता है और व्यावसायिक उद्देश्यों की प्राप्ति में उनके अंतिम प्रभावों के संदर्भ में मूल्यांकन किया जाता है"।
रैखिक प्रोग्रामिंग समस्याएं-ग्राफिकल विधि:
आलेखीय विधि के चरणों को निम्नानुसार संक्षेपित किया जा सकता है:
1. रैखिक प्रोग्रामिंग समस्या का निरूपण करें।
2. दी गई अड़चन लाइनों को समीकरण मानते हुए प्लॉट करें।
3। उपरोक्त ग्राफ से संभव समाधान क्षेत्र की पहचान करें।
4. संभव समाधान क्षेत्र के हास्य बिंदुओं का पता लगाएं।
5. हास्य बिंदुओं पर उद्देश्य फ़ंक्शन के मूल्य की गणना करें।
6. अब उस बिंदु को चुनें जहां उद्देश्य फ़ंक्शन का इष्टतम मूल्य है।
रैखिक प्रोग्रामिंग समस्याएं-गणितीय समाधान:
यद्यपि एलपीपी को हल करने की चित्रमय विधि इसकी मूल संरचना को समझने के लिए एक मूल्यवान सहायता है। विधि औद्योगिक समस्याओं में सीमित उपयोगिता की है क्योंकि होने वाले चरों की संख्या काफी बड़ी है, इसलिए एक और गणितीय समाधान जिसे सिम्प्लेक्स विधि कहा जाता है बड़ी संख्या में चर के साथ एलपीपी को हल करने के लिए उपयुक्त है।
यह एक पुनरावृत्त प्रक्रिया है, जो या तो एलपीपी को चरणों की एक सीमित संख्या में हल करती है या एक संकेत देती है कि एलपीआर सिम्प्लेक्स विधि का एक अनभिज्ञ समाधान है रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए एक बीजीय प्रक्रिया है या पुनरावृत्ति चरणों की एक श्रृंखला से बना है। एक इष्टतम समाधान प्राप्त करें।
यह एक सबसे व्यापक रूप से और सबसे अधिक इस्तेमाल किया जाने वाला प्रोग्रामिंग एल्गोरिदम है। सैद्धांतिक रूप से यह प्रक्रिया किसी भी समस्या को हल कर सकती है जिसमें किसी भी प्रकार के चर और बाधाएं शामिल हैं। यदि समस्या में तीन से अधिक चर और तीन बाधाएँ हैं तो कंप्यूटर का उपयोग आवश्यक है। अंजीर। 31.9 सिंप्लेक्स एल्गोरिथम का योजनाबद्ध प्रतिनिधित्व दर्शाता है।
सिम्प्लेक्स प्रक्रिया के विभिन्न चरण:
इस प्रक्रिया के चरण नीचे सूचीबद्ध हैं:
1. उद्देश्य समारोह और बाधाओं का निर्धारण करके समस्या का समाधान।
2. उद्देश्य समारोह में सुस्त अधिशेष और कृत्रिम चर पेश करके मानक रूप पाने के लिए असमानताओं को समानता में परिवर्तित करें।
3. प्रारंभिक सिम्प्लेक्स टेबल तैयार करें।
4। इस समाधान के लिए z j (शुद्ध हानि प्रति इकाई) और c j - z j (शुद्ध योगदान) मान को कम करें।
5. सबसे नकारात्मक के साथ कॉलम का चयन करके प्रवेश चर (कुंजी कॉलम) का निर्धारण करें
(z j - c j )।
6. नियम 5 से अनुपात कॉलम की गणना करके और सबसे छोटा गैर नकारात्मक मान चुनकर प्रस्थान चर (कुंजी पंक्ति) का निर्धारण करें।
7. नियम 6 द्वारा सुधारित सिम्पलेक्स टेबल की रिप्लेसमेंट पंक्ति की गणना करें।
8. नियम 7 द्वारा नई तालिका की शेष पंक्तियों की गणना करें।
9. इस समाधान के लिए c j और z j मान की गणना करें।
10. यदि गैर-ऋणात्मक है (c j - z j ) मान 5 चरण में लौटाता है।
11. यदि कोई गैर-नकारात्मक (c j - z j ) मूल्य नहीं है, तो इष्टतम समाधान प्राप्त किया गया है।
उदाहरण 1:
एक किसान के पास 1000 एकड़ जमीन है, जिस पर वह मकई, गेहूं या सोयाबीन उगा सकता है, प्रत्येक एकड़ में रु। तैयारी के लिए 100, काम के 7 आदमी दिनों की आवश्यकता होती है और रुपये का लाभ प्राप्त होता है। 30 एक एकड़ गेहूं की कीमत रु। तैयार करने के लिए 120, काम के 10 आदमी दिनों की आवश्यकता होती है और रुपये का लाभ मिलता है। 40।
तैयार करने के लिए एक एकड़ में सोयाबीन की लागत रु .70 है, जिसमें 8 दिनों के काम की आवश्यकता होती है और रु। का लाभ मिलता है। 20 यदि किसान के पास रु। तैयारी के लिए 100, 000 और काम के 8000 आदमी दिनों पर गिनती। मुनाफे को अधिकतम करने के लिए प्रत्येक फसल को कितने एकड़ आवंटित किए जाने चाहिए? (गुजरात एमबीए, 1989)
उपाय:
बता दें कि मकई के लिए x एकड़ जमीन आवंटित की गई है
y एकड़ भूमि गेहूं के लिए आवंटित की जाए
z एकड़ भूमि सोयाबीन के लिए आवंटित की जाए
चूंकि मकई के लिए प्रत्येक एकड़ भूमि पर रु। का लाभ होता है। 30, गेहूं की पैदावार के लिए रु। 40 और सोयाबीन के लिए रु। 20. एलएलपी का गणितीय सूत्रीकरण है
अधिकतम Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3
का विषय है
100 x + 120y + 70z + 100000
7x + 10y + 8z + 8000
x + y + z ≤ 1000
x, y, z ≥ 0
आइए हम स्लैक वेरिएबल S 1, S 2 और S 3 को शुरू करके समीकरणों में असमानताओं को परिवर्तित करते हैं। उद्देश्य समारोह और बाधा के रूप में लिखा जा सकता है
मूल चर स्तंभ में वैक्टर चर S 1, (1, 0, 0), S 2, (1, 0, 1) और S 3 (0, 0, 1) के लिए होते हैं, प्रारंभिक व्यवहार्य समाधान चर S द्वारा दिया जाता है। 1, एस 2 और एस 3 दोनों कुल लाभ = 0
अब जेड जे और सी जे - जेड जे, की गणना नियम 1, 2 और 3 द्वारा की जाती है। मुख्य कॉलम स्टार्ट चिह्नित कॉलम के साथ निर्धारित किया जाता है और सिम्प्लेक्स टेबल II निम्नानुसार तैयार किया जाता है।
तालिका II सरल समाधान प्रदान नहीं करती है हम साधारण तालिका III को तैयार करने के लिए आगे बढ़ते हैं और निम्नानुसार समाधान में सुधार करते हैं:
बिग एम द्वारा न्यूनतमकरण समस्या: विधि:
उद्योग में ऐसे स्थान हो सकते हैं जहाँ उद्देश्य उत्पादन की लागत या विनिर्माण की अवधि को कम करना हो सकता है अर्थात उद्देश्य कार्य को ऐसे मामलों में कम से कम किया जाना है जहाँ हम अधिकतम रूप से दोनों पक्षों द्वारा गुणा करके अधिकतम समस्या के रूप में आगे बढ़ सकते हैं। वस्तुनिष्ठ कार्य 1 द्वारा ऐसी स्थितियों में Z का कम से कम (-Z) अधिकतम होना होगा।
ऐसे मामलों में चूंकि अधिशेष चर नकारात्मक मान लेते हैं जो गैर-नकारात्मकता प्रतिबंध का उल्लंघन करते हैं, इस कठिनाई को दूर करने के लिए हम नए चर को कृत्रिम चर के रूप में पेश करते हैं।
अब हम अधिशेष चर और + M को कृत्रिम चर के लिए 3000 गुणांक प्रदान करते हैं, इस स्रोत को बनाने के लिए कि इष्टतम समाधान में कृत्रिम चर मूल चर नहीं हैं, हम उन्हें बहुत उच्च लागत प्रदान करते हैं इसलिए एम को एक बहुत बड़ी संख्या यानी बिग एम के रूप में परिभाषित किया जाता है। या जुर्माना।
इस विधि का पालन निम्नलिखित की सहायता से किया जाता है:
उदाहरण 2:
ऑपरेशन अनुसंधान: टूल # 2. परिवहन समस्याएं:
परिवहन की समस्याएं एलपीपी के प्रकारों में से एक हैं, जिसका उद्देश्य एक ही सजातीय वस्तु / वस्तु की विभिन्न मात्राओं में विभिन्न स्थानों पर माल / उत्पादों को पहुंचाना है ताकि रोजमर्रा की जिंदगी में विभिन्न परिवहन संगठनों या अन्य प्रतिष्ठानों के कारण कुल परिवहन लागत को कम किया जा सके। विभिन्न कारणों से अपने अंतिम उत्पादों या वस्तुओं को मूल या वेयर, घर के रूप में कहे जाने वाले विभिन्न स्थानों पर संग्रहीत किया जाता है, जब उपयोगकर्ताओं को आपूर्ति की जानी है, तब वस्तुओं को मूल से एक या अधिक गंतव्य तक पहुंचाया जाता है, इस प्रक्रिया का समग्र उद्देश्य एक वितरण नीति तय करना है। इस तरह की कुल परिवहन लागत न्यूनतम है या लेन-देन में लगने वाला समय न्यूनतम है।
संयंत्र से मूल रूप से तैयार उत्पादों के बाद परिवहन की समस्याओं में सबसे किफायती तरीके से गोदामों में ले जाया जाता है, रैखिक प्रोग्रामिंग की विभिन्न विशेषताओं को देखा जा सकता है यहां उपलब्धता के साथ-साथ विभिन्न केंद्रों की आवश्यकताएं सीमित हैं और सीमित संसाधनों के परिवहन की समस्या है। सिंप्लेक्स विधि का।
वाल्व में आवेदन कई स्रोतों से उत्पादों के परिवहन के लिए विभिन्न गंतव्य बिंदुओं जैसे:
(i) परिवहन इकाइयाँ गंतव्य स्थान को फाड़ देती हैं। उद्देश्य परिवहन लागत को कम करना है।
(ii) इकाइयों को गंतव्य तक पहुँचाने में लाभ को अधिकतम करना।
इसमें शामिल मुख्य चरण हैं :
चरण 1:
समस्या को तैयार करें और परिवहन मैट्रिक्स के रूप में स्थापित करें।
चरण 2:
बुनियादी संभव समाधान प्राप्त करें।
चरण 3:
समाधान की अनुकूलता के लिए परीक्षण।
चरण 4:
सफलता में सुधार के माध्यम से समाधान का अद्यतन करें जब तक कि परिवहन लागत में और कमी न हो।
आमतौर पर इस्तेमाल की जाने वाली विधियाँ हैं:
1. उत्तर पश्चिम कोने की विधि।
2. कम से कम लागत विधि।
3. वोगेल की स्वीकृति विधि।
उत्तर पश्चिम कोने की विधि में शामिल कदम:
चरण 1:
पंक्तियों और स्तंभों के साथ पूरा किया गया एक अधिकतम अधिकतम मैट्रिक्स का विरोध करें।
चरण 2:
पंक्ति योग और स्तंभ योग को अंत में इंगित करें।
चरण 3:
मैट्रिक्स के नॉर्थवेस्ट कॉमर पर (11) सेल शुरू करने से अधिकतम संभव मात्रा / संख्या का ध्यान रखा जाता है जो इस बात का ध्यान रखता है कि आवंटन न तो संबंधित वेयर हाउस द्वारा आवश्यक मात्रा से अधिक हो सकता है और न ही आपूर्ति केंद्रों पर उपलब्ध मात्रा से अधिक हो सकता है।
चरण 4:
संबंधित पंक्तियों और स्तंभों के आवंटन में आपूर्ति और मांग संख्याओं का समायोजन करने के बाद, चरण 3 के पहले सेल में जाएं और पंक्ति 3 को दोहराएं।
चरण 5:
पहले कॉलम की मांग पूरी होने के बाद। दूसरा कॉलम और पहली पंक्ति में अगले सेल पर जाएं और चरण 3 पर जाएं।
चरण 6:
यदि किसी सेल सप्लाई के बराबर है तो मांग करें कि अगला आवंटन अगली पंक्तियों और स्तंभों में कोशिकाओं में मोड सकता है।
चरण 7:
आवश्यकता के अनुसार कुल उपलब्ध मात्रा पूरी तरह से कोशिकाओं को आवंटित होने तक प्रक्रिया जारी रखें
उदाहरण 3:
न्यूनतम परिवहन लागत की गणना करने के लिए NWCM द्वारा निम्नलिखित समस्या का समाधान करें:
कम से कम लागत एंट्री विधि में कदम:
यह विधि सबसे कम लागत को ध्यान में रखती है और इसलिए समस्या को हल करने में कम समय लगता है विभिन्न चरण निम्नानुसार हैं:
चरण 1:
मैट्रिक्स में सभी पंक्तियों और स्तंभों के बीच सबसे कम परिवहन लागत के साथ सेल का चयन करें। जितनी संभव हो उतनी पंक्ति या स्तंभ को समाप्त करने के लिए आवंटित करें जो स्रोत को समाप्त करते हैं या आवश्यकता को पूरा करते हैं। यदि दोनों संतुष्ट हैं तो वे दोनों में से किसी एक को खत्म कर देते हैं। यदि सबसे छोटी लागत वाली सेल अद्वितीय नहीं है, तो न्यूनतम लागत के साथ मनमाने ढंग से किसी भी सेल का चयन करें।
चरण 2:
अगली छोटी लागत वाली सेल के साथ सभी अनकवर्ड आउट रो और कॉलम के लिए प्रक्रिया दोहराएं। चरण 3: प्रक्रिया को तब तक दोहराएं जब तक सभी स्रोत समाप्त न हो जाएं या सभी गंतव्य की मांग पूरी न हो जाए।
उदाहरण 4:
निम्न समस्या को कम से कम लागत विधि द्वारा हल करें:
वोगेल एप्रिसिएशन विधि:
यह विधि एक दंड या पछतावा विधि है और अन्य दो तरीकों से अधिक पसंद की जाती है प्रारंभिक इष्टतम संभव समाधान या तो इष्टतम या इष्टतम समाधान के बहुत करीब प्राप्त होता है इसलिए इष्टतम समाधान की गणना करने के लिए आवश्यक समय कम हो जाता है।
इस पद्धति में आवंटन का आधार इकाई लागत दंड है, अर्थात वह पंक्ति या स्तंभ जो उच्चतम इकाई लागत दंड / न्यूनतम के बीच के अंतर को इंगित करता है और आवंटन के उद्देश्य के लिए अगले उच्चतम लागत को पहले चुना जाता है। इस तरह अन्य कोशिकाओं में बाद में आवंटन भी उच्चतम इकाई लागत दंड को ध्यान में रखते हुए किए जाते हैं।
आबंटन को दंड की लागत को कम करने के लिए बनाया गया है, जिसमें विभिन्न चरण शामिल हैं:
चरण 1:
प्रत्येक पंक्ति और स्तंभ के लिए दंड की गणना करें यह केवल उसी पंक्ति और स्तंभ में परिवहन की सबसे छोटी और अगली सबसे छोटी लागत के बीच का अंतर करके किया जाता है अर्थात अंतर दंड का भुगतान करने का संकेत देता है यदि आवंटन न्यूनतम लागत के लिए नहीं किया गया है कसौटी।
चरण 2:
सबसे बड़ी पेनल्टी के साथ एक पंक्ति या कॉलम चुनें और कम से कम लागत वाले सेल को जितना संभव हो उतना आवंटित करें। टाई के मामले में तब अधिकतम संभव आवंटन का एक सेल पहले चुना जाता है
चरण 3:
मांग को पूरा करने या आपूर्ति को समाप्त करने के बाद पंक्ति या स्तंभ को पार करें या शेष पंक्ति या कॉलम को शून्य आपूर्ति या मांग को सौंपा जाए। आगे की गणना के लिए शून्य आपूर्ति या मांग के साथ किसी भी पंक्ति या स्तंभ का उपयोग नहीं किया जाना चाहिए।
चरण 4:
चरण 1 और 3 तब तक दोहराएं जब तक कि सभी स्रोत समाप्त न हो जाएं या सभी आवश्यकताएं पूरी न हो जाएं।
उदाहरण 5:
एक निर्माण अपने उत्पाद के 8 भार को उत्पादन केंद्रों एक्स, वाई एंड जेड से वितरण केंद्रों ए, बी और सी के लिए भेजना चाहता है, जो कि मूल 0 से गंतव्य डी है, निम्नलिखित मैट्रिक्स है।
उदाहरण 6:
वोगेट्स सन्निकटन विधि के साथ प्रारंभिक समाधान प्राप्त करके निम्नलिखित परिवहन समस्या का इष्टतम समाधान खोजें:
उपाय:
आइए हम वोगेल के अंदाजन तरीके को लागू करें। आपूर्ति के रूप में संतुलित समस्याएं = मांग = 50 इकाइयों। आइए नीचे दिए गए तालिका में दिए गए अनुसार vogel की विधि लागू करें।
परिवहन लागत = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 इकाई।
वैकल्पिक रूप से जांचें:
यदि दो स्थितियाँ संतुष्ट हैं तो ऑप्टिमलिटी टेस्ट किया जा सकता है
1. एम + एन - 1 आवंटन हैं, जिनकी मी पंक्तियों की संख्या है, एन स्तंभों की संख्या है। यहाँ m + n - = 6. लेकिन आवंटन की संख्या पाँच है।
2. ये m + n-1 आवंटन स्वतंत्र पदों पर होना चाहिए अर्थात आवंटन की स्थिति को बदलने या पंक्ति या स्तंभ प्रतिबंधों का उल्लंघन किए बिना किसी भी आवंटन को बढ़ाना या घटाना संभव नहीं होना चाहिए।
आवंटन के लिए एक सरल नियम स्वतंत्र पदों पर है कि किसी भी आवंटन से यात्रा करना असंभव है, अपने आप में क्षैतिज और ऊर्ध्वाधर चरणों की एक श्रृंखला होती है जो मार्ग के प्रत्यक्ष उलट के बिना, दूसरे पर कब्जा किए गए सेल का निर्माण करती है। यह देखा जा सकता है कि वर्तमान उदाहरण में, आवंटन स्वतंत्र पदों पर हैं क्योंकि आवंटित कोशिकाओं पर कोई बंद लूप नहीं बनाया जा सकता है।
इसलिए पहली शर्त संतुष्ट नहीं है और इसलिए पहली शर्त को पूरा करने के लिए, हमें परिवहन की सबसे कम लागत वाली खाली कोशिकाओं पर एक छोटी राशि E आवंटित करनी होगी। यह देखा जा सकता है कि टी को 7 इकाइयों की लागत वाली सेल (2, 2) पर आवंटित किया जा सकता है और अभी भी आवंटन तालिका 2 में नीचे बताए अनुसार स्वतंत्र स्थिति में रहेगा।
अब आवंटन की संख्या m + n - 6 = 6 है और वे स्वतंत्र पदों पर हैं। आवंटित कोशिकाओं पर लागत मैट्रिक्स लिखें। (टेबल तीन)
आवंटित कोशिकाओं के लिए प्रारंभिक लागत मैट्रिक्स। U i और v j के मान भी लिखें।
यह तालिका 5 से देखा जा सकता है कि सेल (1, 4) पर सेल मूल्यांकन नकारात्मक यानी -4 है, इसलिए सेल (1, 4) में आवंटन करके परिवहन लागत को और कम किया जा सकता है।
आइए हम मूल आवंटन और प्रस्तावित नए आवंटन को लिखें।
तालिका 6 से यह देखा जा सकता है कि यदि हम सेल (1, 4) में आवंटित करते हैं तो एक लूप दिखाया जाता है और जैसा कि हम 10 इकाइयों को आवंटित करते हैं ताकि सेल (2, 4) में आवंटन तालिका 7 में नीचे दिखाए अनुसार गायब हो जाए। नया आवंटन तालिका बन जाएगी
परिवहन लागत = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 इकाइयाँ।
यानी ट्रांसपोर्टेशन कॉस्ट 475 यूनिट से घटकर 435 यूनिट रह गई है।
वैकल्पिक रूप से जांचें:
देखते हैं कि यह समाधान इष्टतम है या नहीं? उसके लिए फिर से दो शर्तों की जाँच करनी होगी
आवंटन की संख्या = m + n- 1 = 6 (संतुष्ट)
स्वतंत्र स्थान पर आवंटन (आवंटित कोशिकाओं के लिए बंद लूप के बाद से संतुष्ट नहीं है) आवंटित राशि और यू और वी जे के मूल्यों पर लागत लिखें।
ऑपरेशन अनुसंधान: टूल # 3. असाइनमेंट समस्या:
असाइनमेंट समस्या एक विशेष प्रकार की लीनियर प्रोग्रामिंग समस्या है जो विभिन्न संसाधनों के आवंटन को विभिन्न गतिविधियों के लिए एक से एक आधार पर करती है।
यह इस तरह से करता है कि प्रक्रिया में शामिल लागत या समय न्यूनतम है और लाभ या बिक्री अधिकतम है। हालांकि समस्या को सरल विधि या परिवहन विधि द्वारा हल किया जा सकता है, लेकिन असाइनमेंट मॉडल इन समस्याओं के लिए एक सरल दृष्टिकोण प्रदान करता है।
एक कारखाने में, एक पर्यवेक्षक में छह श्रमिक उपलब्ध हो सकते हैं और आग में छह काम हो सकते हैं। उसे यह निर्णय लेना होगा कि किस कर्मचारी को कौन सी नौकरी दी जानी चाहिए। समस्या एक से एक आधार बनाती है। यह असाइनमेंट की समस्या है।
असाइनमेंट मॉडल:
मान लीजिए कि वहाँ n सुविधा और n नौकरियां हैं। यह स्पष्ट है कि इस मामले में, एन असाइनमेंट होंगे। प्रत्येक सुविधा या कहें कि कार्यकर्ता एक समय में एक काम कर सकता है। लेकिन कुछ निश्चित प्रक्रिया होनी चाहिए जिसके द्वारा असाइनमेंट किया जाना चाहिए ताकि लाभ अधिकतम हो या लागत या समय कम से कम हो।
तालिका में, सह ij को लागत के रूप में परिभाषित किया गया है जब j th को ith कार्यकर्ता को सौंपा गया है। यहां यह ध्यान दिया जा सकता है कि यह परिवहन समस्या का एक विशेष मामला है जब पंक्तियों की संख्या स्तंभों की संख्या के बराबर होती है।
गणितीय सूत्रीकरण:
असाइनमेंट समस्या के किसी भी मूल संभव समाधान में (2n - 1) चर होते हैं, जिनमें से (n - 1) चर शून्य होते हैं; n नौकरियों की संख्या या सुविधाओं की संख्या।
इस उच्च पतन के कारण, यदि हम सामान्य परिवहन विधि द्वारा समस्या का समाधान करते हैं, तो यह एक जटिल और समय लेने वाला कार्य होगा। इस प्रकार एक अलग तकनीक इसके लिए व्युत्पन्न है। निरपेक्ष विधि में जाने से पहले समस्या को तैयार करना बहुत महत्वपूर्ण है।
मान लीजिए कि X i एक चर है, जिसे इस रूप में परिभाषित किया गया है
समस्या को हल करने की विधि (हंगेरियन तकनीक):
न्यूनतम प्रकार के उद्देश्य समारोह पर विचार करें।
इस असाइनमेंट की समस्या को हल करने में निम्नलिखित चरण शामिल हैं:
1. पहली पंक्ति के साथ शुरू की गई दी गई लागत तालिका की प्रत्येक पंक्ति में सबसे छोटी लागत तत्व का पता लगाएँ। अब, यह सबसे छोटा तत्व उस पंक्ति के प्रत्येक तत्व से घटाया जाता है। इसलिए, हमें इस नई तालिका की प्रत्येक पंक्ति में कम से कम एक शून्य प्राप्त होगा।
2. टेबल का निर्माण (जैसा कि स्टेप -1 द्वारा किया गया है) टेबल के कॉलम को लेती है। पहले कॉलम से शुरू करके प्रत्येक कॉलम में सबसे छोटे लागत तत्व का पता लगाएं। अब इस सबसे छोटे तत्व को उस कॉलम के प्रत्येक तत्व से घटाएं। चरण 1 और चरण 2 का प्रदर्शन करने के बाद, हमें कम लागत तालिका में प्रत्येक कॉलम में कम से कम एक शून्य प्राप्त होगा।
3. अब, निम्न तरीके से निम्न तालिका के लिए कार्य किए जाते हैं:
(i) पंक्तियों की क्रमिक रूप से जांच की जाती है, जब तक कि पंक्ति एक एकल (एक) शून्य के साथ न मिल जाए। इस एकल शून्य को इसके चारों ओर वर्ग square लगाकर और इसी कॉलम में, अन्य सभी शून्य (x) को पार कर लिया जाता है क्योंकि इनका उपयोग इस कॉलम में कोई अन्य असाइनमेंट बनाने के लिए नहीं किया जाएगा। प्रत्येक पंक्ति के लिए चरण का संचालन किया जाता है।
(ii) चरण 3 (i) अब निम्नानुसार स्तंभों पर किया जाता है: स्तंभों की क्रमिक रूप से जांच की जाती है जब तक कि एक शून्य के साथ एक कॉलम नहीं मिलता है। अब, इस एकल शून्य को इसके चारों ओर वर्ग डालकर असाइनमेंट किया जाता है और उसी समय, इसी पंक्तियों में अन्य सभी शून्य को पार किया जाता है (x) चरण प्रत्येक कॉलम के लिए आयोजित किया जाता है।
(iii) चरण 3 (i) और 3 (ii) तब तक दोहराया जाता है जब तक कि सभी शून्य या तो चिह्नित या पार नहीं हो जाते हैं। अब, यदि चिह्नित शून्य या किए गए असाइनमेंट की संख्या पंक्तियों या स्तंभों की संख्या के बराबर है, तो इष्टतम समाधान प्राप्त किया गया है। बिना किसी असाइनमेंट के प्रत्येक या कॉलम में बिल्कुल एकल असाइनमेंट होगा। इस मामले में, हम चरण 4 पर जाएंगे।
4. इस स्तर पर, चरण 3 में प्राप्त मैट्रिक्स में सभी शून्य को कवर करने के लिए आवश्यक न्यूनतम संख्या रेखाएं (क्षैतिज और ऊर्ध्वाधर) खींचें।
निम्नलिखित प्रक्रिया अपनाई जाती है:
(i) सभी पंक्तियों पर टिक मार्क (V) जिसमें कोई असाइनमेंट नहीं है।
(ii) अब इन सभी कॉलम पर टिक मार्क (V) टिक टिक पंक्तियों में शून्य है।
(iii) अब उन सभी पंक्तियों को चिन्हित करें जो पहले से चिह्नित नहीं हैं और जिन्हें चिह्नित कॉलम में असाइनमेंट है।
(iv) सभी चरणों अर्थात 4 (1), 4 (2), 4 (3) को तब तक दोहराया जाता है जब तक कि अधिक पंक्तियों या स्तंभों को चिह्नित नहीं किया जाता है,
(v) अब सीधी रेखाएँ खींचें जो सभी चिन्हित पंक्तियों और चिन्हित स्तंभों से होकर गुजरती हैं। यह भी देखा जा सकता है कि एक nxn मैट्रिक्स में, हमेशा 'n' लाइनों से कम होती है, अगर उनके बीच कोई समाधान नहीं है तो सभी शून्य को कवर किया जाएगा।
5. चरण 4 में, यदि तैयार की गई रेखाओं की संख्या n या पंक्तियों की संख्या के बराबर है, तो यह इष्टतम समाधान है यदि नहीं, तो चरण 6 पर जाएं।
6. सभी खुला तत्वों में से सबसे छोटे तत्व का चयन करें। अब, इस तत्व को सभी खुले हुए तत्वों से घटाया गया है और उस तत्व में जोड़ा गया है जो दो रेखाओं के चौराहे पर स्थित है। यह ताजा कार्य के लिए मैट्रिक्स है।
7. चरण (3) से प्रक्रिया को दोहराएं जब तक कि असाइनमेंट की संख्या पंक्तियों की संख्या या स्तंभों की संख्या के बराबर न हो जाए।
