1.नियतन समस्याओं को हल करने की 3 टाॅप टिप्स (3 Top Tips to Solve Assignment Problem),इष्टतमीकरण सिद्धान्त में नियतन समस्याएं (Assignment Problems in Optimization Theory):

3 Top Tips to Solve Assignment Problem

नियतन समस्याओं को हल करने की 3 टाॅप टिप्स (3 Top Tips to Solve Assignment Problem) के इस आर्टिकल में संयत्र की उत्पादन लागत एवं विक्रय लागत की मैट्रिक्स वाले सवाल हल करके लागत को न्यूनतम करना जानेंगे।
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।

Also Read This Article:- 3 Tips to Solve Assignment Problems

2.नियतन समस्याओं को हल करने की 3 टाॅप टिप्स पर आधारित उदाहरण (Examples Based on 3 Top Tips to Solve Assignment Problem):

Example:26.व्यवस्था लागत की मैट्रिक्स निम्न अनुसार है,उत्पादन अनुक्रम कैसे रखा जाय जो प्रतिचक्र कुल व्यवस्था लागत को न्यूनतम करे?
(The matrix of setup cost is as follows,show how to sequence production so as to minimize the total set up cost per cycle):

Solution:पद (step):I.पंक्ति समानेत मैट्रिक्स (Row reduced Matrix):प्रत्येक पंक्ति के न्यूनतम अवयव को उसी पंक्ति के प्रत्येक अवयव में से घटाने पर पंक्ति समानयन निम्न मैट्रिक्स प्राप्त होती है:
सारणी 1

पद (step):II.स्तम्भ समानेत मैट्रिक्स (Column reduced Matrix):सारणी 1 के प्रत्येक स्तम्भ के न्यूनतम अवयव को उसी स्तम्भ के प्रत्येक अवयव में से घटाने पर स्तम्भ समानयन निम्न मैट्रिक्स प्राप्त होती है:
सारणी 2

\begin{array}{|c|ccccc|} \hline & A_1 & A_2 & A_3 & A_4 & A_5 \\ \hline A_1 & \infty & 1 & 3 & 6 & \fbox{0} \\ A_2 & 4 & \infty & \fbox{0} & 6 & \xcancel{0} \\ A_3 & 4 & 3 & \infty & \fbox{0} & 3 \\ A_4 & 8 & \fbox{0} & 1 & \infty & 1 \\ A_5 & \fbox{0} & 2 & \xcancel{0} & 7 & \infty \\ \hline \end{array}
पद (step):III.शून्य नियतन (निर्दिष्टीकरण) प्रथम पंक्ति से अवलोकन प्रारम्भ करते हुए उन पंक्तियों को चुनते हैं जिनमें एक और केवल एक शून्य हो।यहाँ पहली,दूसरी तीसरी,चौथी और पाँचवीं पंक्तियाँ ऐसी है।इन पंक्तियों के शून्य को वर्ग (\square) से अंकित करते हैं तथा इस शून्य से होकर जाने वाले स्तम्भ की अन्य सभी शून्यों को काट (×) देते हैं।पुनः प्रथम स्तम्भ से अवलोकन प्रारम्भ करते हुए उन स्तम्भों को चुनते हैं जिनमें अचिन्हित एक और केवल एक शून्य हो।यहाँ ऐसा कोई स्तम्भ नहीं हैं।इस प्रकार सारणी 3 में यह नियतन निम्नानुसार है:
सारणी 3
इस प्रकार सारणी 3 ऐसी प्राप्त होती है जिसमें प्रत्येक पंक्ति तथा प्रत्येक स्तम्भ में एक नियतन है।अर्थात् पूर्ण शून्य निर्दिष्टीकरण निम्न अनुसार प्राप्त होता है:
A_1 \rightarrow A_5, A_2 \rightarrow A_3, A_3 \rightarrow A_4, A_4 \rightarrow A_2, A_5 \rightarrow A_1
सुसंगत लागत=1+3+4+4+1=13

3 Top Tips to Solve Assignment Problem

Example:27.आल्फा निगम के पास 4 संयंत्र हैं जिनमें से प्रत्येक चार उत्पादन में से कोई एक उत्पादन करता है।प्रत्येक संयंत्र की उत्पादन लागत एवं विक्रय आय भिन्न-भिन्न है।निम्न आँकड़ों से ज्ञात कीजिए कि अधिकतम लाभ हेतु किस संयंत्र को कौन-सा उत्पादन करना चाहिए:
(Alpha corporation has four plants each of which can manufacture any of the four products. Production costs differ from plant to plant as do sales revenue.From the following data, obtain which product each plant should produce to maximize profit):

Solution:लाभ मैट्रिक्स निम्न प्रकार से ज्ञात की जायेगी:लाभ मैट्रिक्स=विक्रय मैट्रिक्स-लागत मैट्रिक्स
सारणी 1

समस्या को अधिकतम करने को,न्यूनतम में परिवर्तन करने के लिए मैट्रिक्स के प्रत्येक अवयव को -1 से गुणा करते हैं:
सारणी 2

पद (step):I.पंक्ति समानेत मैट्रिक्स (Row reduced Matrix):प्रत्येक पंक्ति के न्यूनतम अवयव को उसी पंक्ति के प्रत्येक अवयव में से घटाने पर पंक्ति समानयन निम्न मैट्रिक्स प्राप्त होती है:
सारणी 3

पद (step):II.स्तम्भ समानेत मैट्रिक्स (Column reduced Matrix):सारणी 3 के प्रत्येक स्तम्भ के न्यूनतम अवयव को उसी स्तम्भ के प्रत्येक अवयव में से घटाने पर स्तम्भ समानयन निम्न मैट्रिक्स प्राप्त होती है:
सारणी 4

पद (step):III.शून्य नियतन (निर्दिष्टीकरण) प्रथम पंक्ति से अवलोकन प्रारम्भ करते हुए उन पंक्तियों को चुनते हैं जिनमें एक और केवल एक शून्य हो।यहाँ पहली पंक्ति ऐसी है।इस पंक्ति के शून्य को वर्ग (\square) से अंकित करते हैं तथा इस शून्य से होकर जाने वाले स्तम्भ की अन्य सभी शून्यों को काट (×) देते हैं।पुनः प्रथम स्तम्भ से अवलोकन प्रारम्भ करते हुए उन स्तम्भों को चुनते हैं जिनमें अचिन्हित एक और केवल एक शून्य हो।यहाँ ऐसा पहला स्तम्भ हैं।इस स्तम्भ की शून्य को वर्ग (\square) से अंकित करते हैं और इस शून्य से होकर जानेवाली पंक्तियों की अन्य शून्य को काट (×) देते हैं।इस प्रकार सारणी 5 में यह नियतन निम्नानुसार है:
सारणी 5

\begin{array}{c|cccc|} & 1 & 2 & 3 & 4 \\ \hline A & 5 & \fbox{0} & 3 & 5 \\ B & \fbox{0} & \xcancel{0} & \xcancel{0} & \xcancel{0} \\ C & 10 & \xcancel{0} & 10 & 11 \\ D & 5 & \xcancel{0} & 3 & 5 \\ \hline \end{array}
पद (step):IV.अब समस्त शून्यों को कम से कम एक बार रेखाओं से ढकने के लिए न्यूनतम संख्या में रेखाएँ खींचते हैं जिसकी विधि निम्न प्रकार है:
सारणी 6

\begin{array}{c|cccc|c} & & (3) & & &\\ & 1 & 2 & 3 & 4 & \\ \hline A & 5 & \fbox{0} & 3 & 5 & (4) \\ & & \vdots & & & \\ B & \fbox{0} \cdots & \xcancel{0} \cdots & \xcancel{0} \cdots & \xcancel{0} & \\ & & \vdots & & & \\ C & 10 & \xcancel{0} & 10 & 11 & (1) \\ & & \vdots & & & \\ D & 5 & \xcancel{0} & 3 & 5 & (2) \\ \hline \end{array}
(i)सारणी 5 को पुनः बनाइये।
(ii)पंक्ति 3,4 को चिन्हित (\checkmark) कीजिए क्योंकि इनमें नियतन नहीं है।
(iii)पंक्ति 3,4 के द्वितीय स्तम्भ में शून्य है इसलिए स्तम्भ 2 को चिन्हित (\checkmark) कीजिए।
(iv)चिन्हित स्तम्भ (\checkmark) 2 की पंक्ति 1 में वर्ग (\square) अंकित है,को चिन्हित (\checkmark) कीजिए।
पद (step):V.अब हम चिन्हित स्तम्भ 2 से रेखा खींचते हैं।फिर अचिन्हित पंक्ति 2 जिनमें शून्य हैं परन्तु उनसे कोई रेखा नहीं गुजरती पर रेखा खींचते हैं।अब क्योंकि कोई ऐसी शून्य शेष नहीं है जिस पर रेखा नहीं गुजरती।
मैट्रिक्स का क्रम 4×4 है परन्तु रेखाओं की संख्या 2 है इसलिए इससे इष्टतम हल प्राप्त नहीं हो सकता।
पद (step):VI.अब उन सभी अवयवों जो रेखाओं से ढके नहीं है,का न्यूनतम अवयव 3 है।इस अवयव (अर्थात् 3) को उन सभी बिना ढके अवयवों में से घटाने तथा रेखाओं के प्रतिच्छेदन वाले अवयव में जोड़ने पर सारणी 7 प्राप्त होती है।अब स्टेप III के अनुसार शून्य निर्दिष्टीकरण कीजिए।
सारणी 7

\begin{array}{c|cccc|} & 1 & 2 & 3 & 4 \\ \hline A & 2 & \xcancel{0} & \xcancel{0} & 2 \\ B & \fbox{0} & 3 & \xcancel{0} & \xcancel{0} \\ C & 7 & \fbox{0} & 7 & 8 \\ D & 2 & \xcancel{0} & \fbox{0} & 2\\ \hline \end{array}
पद (Step):VII.अब पुनः समस्त शून्यों को कम से कम एक बार रेखाओं से ढकने के लिए स्टेप IV के अनुसार हंगेरियन विधि से रेखाएँ खींचते हैं।
सारणी 8

\begin{array}{c|cccc|c} & & (2) & (3)& &\\ & 1 & 2 & 3 & 4 & \\ \hline A & 2 & \xcancel{0} & \xcancel{0} & 2 & (1) \\ & & \vdots & \vdots & & \\ B & \fbox{0} \cdots & 3 \cdots & \xcancel{0} \cdots & \xcancel{0} \cdots & \\ & & \vdots & \vdots & & \\ C & 7 & \fbox{0} & 7 & 8 & (4) \\ & & \vdots & \vdots & & \\ D & 2 & \xcancel{0} & \fbox{0} & 2 & (5) \\ \hline \end{array}
अब कोई भी ऐसा शून्य नहीं है जिस पर रेखा नहीं गुजरती।
मैट्रिक्स का क्रम 4×4 है परन्तु रेखाओं की संख्या 3 है।अतः इससे इष्टतम हल प्राप्त नहीं हो सकता।
पद (step):VIII.अब उन सभी अवयवों जो रेखाओं से ढके नहीं है,का न्यूनतम अवयव 2 है।इस अवयव (अर्थात् 2) को उन सभी बिना ढके अवयवों में से घटाने तथा रेखाओं के प्रतिच्छेदन वाले अवयव में जोड़ने पर सारणी 9 प्राप्त होती है।अब स्टेप III के अनुसार शून्य निर्दिष्टीकरण कीजिए।
सारणी 9

\begin{array}{c|cccc|} & 1 & 2 & 3 & 4 \\ \hline A & 0 & \xcancel{0} & 0 & 0 \\ B & 0 & 5 & 2 & 0 \\ C & 5 & \fbox{0} & 7 & 6 \\ D & 0 & \xcancel{0} & 0 & 0 \\ \hline \end{array}
पद (Step):VII.अब पुनः समस्त शून्यों को कम से कम एक बार रेखाओं से ढकने के लिए स्टेप IV के अनुसार हंगेरियन विधि से रेखाएँ खींचते हैं।
सारणी 10

\begin{array}{c|cccc|c} & (4) & (5) & (6) & (7) &\\ & 1 & 2 & 3 & 4 & \\ \hline A & 0 & \xcancel{0} & 0 & 0 & (1) \\ & \vdots & \vdots & \vdots & \vdots & \\ B & 0 & 5 & 2 & 0 & (2) \\ & \vdots & \vdots & \vdots & \vdots & \\ C & 5 & \fbox{0} & 7 & 6 & (8) \\ & \vdots & \vdots & \vdots & \vdots & \\ D & 0 & \xcancel{0} & 0 & 0 & (3) \\ \hline \end{array}
अब कोई भी ऐसा शून्य नहीं है जिस पर रेखा नहीं गुजरती।
मैट्रिक्स का क्रम 4×4 है तथा रेखाओं की संख्या भी 4 है।अतः इससे इष्टतम हल प्राप्त होगा।सारणी 10 का शून्य निर्दिष्टीकरण trial and error विधि से निम्न दो प्रकार से कर सकते हैं।
सारणी 11

\begin{array}{c|cccc|} & 1 & 2 & 3 & 4 \\ \hline A & \fbox{0} & \xcancel{0} & \xcancel{0} & \xcancel{0} \\ B & \xcancel{0} & 5 & 2 & \fbox{0} \\ C & 5 & \fbox{0} & 7 & 6 \\ D & \xcancel{0} & \xcancel{0} & \fbox{0} & \xcancel{0}\\ \hline \end{array}
सारणी 12

\begin{array}{c|cccc|} & 1 & 2 & 3 & 4 \\ \hline A & \xcancel{0} & \xcancel{0} & \fbox{0} & \xcancel{0} \\ B & \fbox{0} & 5 & 2 & \xcancel{0} \\ C & 5 & \fbox{0} & 7 & 6 \\ D & \xcancel{0} & \xcancel{0} & \xcancel{0} & \fbox{0} \\ \hline \end{array}
अतः सारणी 11 व 12 से निम्न इष्टतम हल प्राप्त होता है:
(i) A \rightarrow 1, B \rightarrow 4, C \rightarrow 2, D \rightarrow 3
अधिकतम लाभ=1+5+15+6=27 हजार
(ii) A \rightarrow 3, B \rightarrow 1, C \rightarrow 2, D \rightarrow 4
अधिकतम लाभ=4+5+15+3=27 हजार
उपर्युक्त उदाहरणों के द्वारा नियतन समस्याओं को हल करने की 3 टाॅप टिप्स (3 Top Tips to Solve Assignment Problem),इष्टतमीकरण सिद्धान्त में नियतन समस्याएं (Assignment Problems in Optimization Theory) को समझ सकते हैं।

3.नियतन समस्याओं को हल करने की 3 टाॅप टिप्स के सवाल (Questions Based on 3 Top Tips to Solve Assignment Problem):

3 Top Tips to Solve Assignment Problem

(1.)पांच अलग-अलग काम करने के लिए पांच आदमी उपलब्ध हैं। पिछले रिकॉर्ड से, समय (घंटों में) जो प्रत्येक व्यक्ति प्रत्येक कार्य को करने के लिए लेता है और निम्न तालिका में दिया गया है:
(Five men are available to do five different jobs. From past records, the time (in hours) that each man takes to do each job in known and is given in the following table):
पुरुषों को उन नौकरियों के लिए असाइनमेंट खोजें जो कुल समय को कम कर देंगे।

(Find the assignment of men to jobs that will minimize the total time taken.)
(2.)5×5 असाइनमेंट समस्या के लिए न्यूनतम लागत समाधान खोजें जिसका गुणांक नीचे दिया गया है:
(Find the minimum cost solution for the 5×5 assignment problem whose coefficients given below):

उत्तर (Answers):
(1.) (i) 1 \rightarrow III, 2 \rightarrow V, 3 \rightarrow I, 4 \rightarrow IV, 5 \rightarrow II
(ii) 1 \rightarrow III, 2 \rightarrow V, 3 \rightarrow IV, 4 \rightarrow II, 5 \rightarrow I
(iii) 1 \rightarrow III, 2 \rightarrow V, 3 \rightarrow IV, 4 \rightarrow I, 5 \rightarrow II
Min. Time=13 hours
(2.)(i) 1 \rightarrow III, 2 \rightarrow II, 3 \rightarrow V, 4 \rightarrow I, 5 \rightarrow IV
(ii) 1 \rightarrow IV, 2 \rightarrow III, 3 \rightarrow II, 4 \rightarrow V, 5 \rightarrow I
minimum cost=36
उपर्युक्त सवालों को हल करने पर नियतन समस्याओं को हल करने की 3 टाॅप टिप्स (3 Top Tips to Solve Assignment Problem),इष्टतमीकरण सिद्धान्त में नियतन समस्याएं (Assignment Problems in Optimization Theory) को ठीक से समझ सकते हैं।

Also Read This Article:- 3 Tips to Solve Assignment Problem

4.नियतन समस्याओं को हल करने की 3 टाॅप टिप्स (Frequently Asked Questions Related to 3 Top Tips to Solve Assignment Problem),इष्टतमीकरण सिद्धान्त में नियतन समस्याएं (Assignment Problems in Optimization Theory) से सम्बन्धित अक्सर पूछे जाने वाले प्रश्न:

नियतन समस्याओं को हल करने की 3 टाॅप टिप्स (3 Top Tips to Solve Assignment Problem)
के इस आर्टिकल में संयत्र की उत्पादन लागत एवं विक्रय लागत की मैट्रिक्स वाले सवाल हल
करके लागत को न्यूनतम करना जानेंगे।