1.नियतन (अधिन्यासन) समस्याएं (Assignment Problems):

Assignment Problems

नियतन (अधिन्यासन) समस्याएं (Assignment Problems) का जनक दिन प्रतिदिन की समस्याएं हैं।नियतन की समस्याओं में व्यक्तियों को उनकी क्षमता के अनुरूप अलग-अलग कार्यों पर लगाना, व्यक्तियों द्वारा अलग-अलग कार्य करने से आई लागत को न्यूनतम करना विक्रेताओं द्वारा अलग-अलग क्षेत्र के इस प्रकार ब्रिकी करना की अधिअतम लाभ हो इत्यादि।
(1.)नियतन (अधिन्यासन) समस्या का गणितीय गठन (Mathematical Formulation of Assignment Problem):
कुल लागत Z को न्यूनतम करना (Min Z)=\sum_{i=1}^{n} \sum_{j=1}^{n} c_{i j} x_{ij}
जहाँ x_{ij} =\left\{\begin{array}{l}1 ,\text {यदि iवें व्यक्ति को jवां कार्य नियत किया जाएगा } \\0 , \text { यदि iवें व्यक्ति को jवां कार्य नियत नहीं किया जाएगा }\end{array}\right. 
प्रतिबन्ध सहित
(i) \sum_{i=1}^{n} x_{i j}=1, j=1,2,3, \ldots n

अर्थात् iवें व्यक्ति द्वारा केवल एक ही कार्य किया जाए, i=1,2,3,…,n
(ii) \sum_{j=1}^{n} x_{i j}=1, i=1,2,3, \ldots n

अर्थात् jवां कार्य केवल एक व्यक्ति को नियत किया जाएगा, j=1,2,3,…,n
(2.)नियतन (अधिन्यासन या निर्दिष्ट) कलन विधि (Assignment Algorithm):
हंगरी (Hungary) के गणितज्ञ डी.कोनिंग (D.Kanning) ने सिद्ध किया था और इनके द्वारा निम्न नियतन कलन विधि को अपनाया था इसीलिए प्राय: इस कलन विधि को हंगेरियन नियतन विधि से जाना जाता है।इस विधि के पद (Steps) निम्न प्रकार हैं:
I.सर्वप्रथम लागत मैट्रिक्स C_{i j} की प्रत्येक पंक्ति के न्यूनतम अवयव को उसके संगत पंक्ति के प्रत्येक अवयव में से घटाकर पंक्ति समानीत (संकुचित) मैट्रिक्स (Row Reduced Matrix) प्राप्त कीजिए।
II.पंक्ति समानीत (संकुचित) मैट्रिक्स के प्रत्येक स्तम्भ के न्यूनतम अवयव को उसके संगत स्तम्भ के प्रत्येक अवयव में से घटाकर दूसरीओर स्तम्भ समानीत (संकुचित) मैट्रिक्स (Column Reduced Matrix) प्राप्त कीजिए।
III.शून्य नियतन (या निर्दिष्टीकरण) (Zero Assignment):
(a)पद (Step) II से प्राप्त मैट्रिक्स की प्रथम पंक्ति से प्रारम्भ करते हुए इनका अवलोकन इस प्रकार करिए कि उन पंक्तियों को चुनिए जिनमें एक और केवल एक शून्य है।इस शून्य को एक वर्ग (🔲) से अंकित करिए चूँकि एक नियतन उस अवयव पर करना है।इसके पश्चात् इस अंकित शून्य के स्तम्भ में यदि कोई ओर शून्य हो तो उस शून्य को काट (×) दीजिए जिससे उन्हें अन्य प्रकार से नियतन नहीं किया जाए।
(b)पुनः प्रथम स्तम्भ से प्रारम्भ करते हुए इनका अवलोकन इस प्रकार करिए कि उन स्तम्भों को चुनिए जिनमें एक और केवल एक अचिन्हित (unmarked) शून्य है।इस शून्य को एक वर्ग (🔲) से अंकित करिए चूँकि एक नियतन इस अवयव पर करना है अब इस शून्य की पंक्ति में यदि कोई ओर शून्य हो तो उस शून्य को काट (×) दीजिए जिससे उन्हें अन्य प्रकार से नियतन नहीं किया जाए।
(c)उपर्युक्त (a) तथा (b) प्रक्रिया की पुनरावृत्ति तब तक करते रहिए जब तक कि निम्न दो स्थितियों में से एक स्थिति प्राप्त न हो जाए।
(i)मैट्रिक्स की शून्य अवयव या तो वर्ग (🔲) से अंकित हो या काट (×) दिया जाए।या
(ii)प्रत्येक पंक्ति या स्तम्भ में शेष अचिन्हित कम से कम दो शून्य हों।
अब (i) स्थिति में अधिकतम नियतन हो गया है और स्थिति (ii)में कुछ ओर शून्यों का नियतन Trial and Error विधि से करते हैं जो इस प्रकार है।स्वेच्छा से एक अचिन्हित शून्य को वर्ग (🔲) से अंकित करिए और इस शून्य वाली पंक्ति तथा स्तम्भ में शेष शून्यों को काट (×) दीजिए।इस विधि की पुनरावृत्ति तब तक करिए जब तक कि मैट्रिक्स में कोई भी अचिन्हित शून्य नहीं रहे।
अब दो सम्भावनाएँ हैं।
(i)यदि प्रत्येक पंक्ति तथा प्रत्येक स्तम्भ में एक एक नियतन है अर्थात् वर्ग (🔲) से ठीक n शून्य अंकित हैं तो पूर्ण इष्टतम नियतन प्राप्त हो गया है।
(ii)यदि प्रत्येक पंक्ति तथा प्रत्येक स्तम्भ में नियतन नहीं है एवं वर्ग (🔲) से अंकित शून्यों की संख्या n से कम है तो कुछ जोड़ या घटाकर और शून्य प्राप्त लागत (प्रभावी) मैट्रिक्स को ओर सुधार (Modify) करना है इस हेतु निम्न विधि अपनाइए।
IV.मैट्रिक्स के सभी शून्यों को कम से कम एक बार ढकने (Cover) के लिए न्यूनतम संख्या में क्षैतिज अथवा उर्ध्वाधर रेखाएं खींचिए इसके लिए निम्न विधि अपनाइए:
(a)उन सभी पंक्तियों को चिन्हित (✓) कीजिए जिनमें नियतन अर्थात् वर्ग (🔲) से अंकित नहीं किया गया है।
(b)इन चिन्हित (✓) पंक्तियों में शून्य वाले स्तम्भों को चिन्हित (✓) कीजिए।
(c)उपर्युक्त चिन्हित (✓) स्तम्भों में उन पंक्तियों को चिन्हित (✓) कीजिए जिनमें अवयव वर्ग (🔲) से अंकित है तथा अभी तक चिन्हित नहीं किया गया है।
(d)उक्त (b) तथा (c) की पुनरावृत्ति करते रहिए जब तक कि चिन्हित (✓) की प्रक्रिया समाप्त नहीं हो जाए।
(e)न्यूनतम संख्या में सर्वप्रथम चिन्हित स्तम्भों पर रेखाएँ खींचिए फिर अचिन्हित पंक्तियों पर रेखाएं खींचिए जब तक की सभी शून्य इन रेखाओं से ढ़क न जाएं।यदि शून्य को ढ़कने वाली रेखाओं की संख्या n के बराबर है तो यह इष्टतम नियतन की स्थिति है अन्यथा अगले पद (Step) की विधि अपनाइए।
V.उन सभी अवयवों में से न्यूनतम अवयव चुनिए जिनसे रेखा नहीं गुजरती है।इस न्यूनतम अवयव को उन सभी अवयवों में से घटाइए जिनमें से रेखाएं नहीं गुजरती है तथा उन अवयवों में जोड़िये जिन पर दो रेखाएँ प्रतिच्छेदन करती है।इनके अतिरिक्त सभी अवयवों को अपरिवर्तित रखिए।
VI.पद V से प्राप्त मैट्रिक्स में शून्यों की संख्या बढ़ाई गई है, इस प्राप्त मैट्रिक्स को पद III की सहायता से शून्य नियतन कर वांछित हल प्राप्त कीजिए।
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके ।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए ।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।

Also Read This Article:-Improved Basic Feasible Solution

2.नियतन (अधिन्यासन) समस्याएं के उदाहरण (Assignment Problems Examples):

निम्न नियतन समस्याएँ हल कीजिए:
(Solve the following assignment problems):
Example:1.

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

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

पद (Step):III.शून्य निर्दिष्टीकरण (Zero Assignment)
अब प्रथम पंक्ति से अवलोकन प्रारम्भ करते हुए उन पंक्तियों को चुनते हैं जिनमें एक और केवल एक शून्य हो।इन पंक्तियों की शून्यों को वर्ग से (🔲) अंकित करते हैं तथा इन शून्यों से गुजरने वाले स्तम्भ की अन्य शून्यों को × (काट) देते हैं।
सारणी (Table) 3

पुनः प्रथम स्तम्भ से अवलोकन प्रारम्भ करते हुए उन स्तम्भों को चुनते हैं जिनमें अचिन्हित एक और केवल एक शून्य हो।इन शून्यों को वर्ग से (🔲) अंकित करिए तथा इस शून्य से होकर जानेवाली पंक्ति की अन्य शून्यों को × (काट) देते हैं।
सारणी (Table) 4

इस प्रकार हमें एक नई सारणी प्राप्त होती है जिसमें प्रत्येक पंक्ति तथा प्रत्येक स्तम्भ में एक नियतन है।अर्थात् पूर्ण शून्य निर्दिष्टीकरण निम्न अनुसार प्राप्त होता है।

A \rightarrow 2,B \rightarrow 3,C \rightarrow 4,D \rightarrow 1
न्यूनतम Z=12+7+11+8=38
Example:2.

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

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

पद (Step):III.शून्य निर्दिष्टीकरण (Zero Assignment)
अब प्रथम पंक्ति से अवलोकन प्रारम्भ करते हुए उन पंक्तियों को चुनते हैं जिनमें एक और केवल एक शून्य हो।इन पंक्तियों की शून्यों को वर्ग से (🔲) अंकित करते हैं तथा इन शून्यों से गुजरने वाले स्तम्भ की अन्य शून्यों को × (काट) देते हैं।
सारणी (Table) 3

पुनः प्रथम स्तम्भ से अवलोकन प्रारम्भ करते हुए उन स्तम्भों को चुनते हैं जिनमें अचिन्हित एक और केवल एक शून्य हो।इन शून्यों को वर्ग से (🔲) अंकित करिए तथा इस शून्य से होकर जानेवाली पंक्ति की अन्य शून्यों को × (काट) देते हैं।
सारणी (Table) 4

इस प्रकार हमें एक नई सारणी प्राप्त होती है जिसमें प्रत्येक पंक्ति तथा प्रत्येक स्तम्भ में एक नियतन है।अर्थात् पूर्ण शून्य निर्दिष्टीकरण निम्न अनुसार प्राप्त होता है।

I \rightarrow 1,II \rightarrow 3,III \rightarrow 2,IV \rightarrow 4

Assignment Problems

Example:3.

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

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

पद (Step):III.शून्य निर्दिष्टीकरण (Zero Assignment)
अब प्रथम पंक्ति से अवलोकन प्रारम्भ करते हुए उन पंक्तियों को चुनते हैं जिनमें एक और केवल एक शून्य नहीं है।
अतः हंगेरियन विधिनुसार
एक बार रेखाओं को ढकने के लिए न्यूनतम संख्या में रेखाएँ खींचते हैं।इन रेखाओं की संख्या 4 हैं तथा मैट्रिक्स 4×4 क्रम का है अतः 4=4 है।इसलिए सारणी से इष्टतम हल प्राप्त हो सकता है।
सारणी (Table) 3

\left|\begin{array}{llllll} \hline & \quad I \quad I I \quad I I I \quad I V \\ A & \cdots 0 \cdots 0 \cdots 0 \cdots 2 \\B & \cdots 0 \cdots 0 \cdots 0 \cdots 2 \\ C & \cdots 0 \cdots 0 \cdots 0 \cdots 2 \\ D &\cdots 0 \cdots 1 \cdots 3 \cdots 0 \\ \hline \end{array}\right|

अब शून्यों का नियतन Trial and Error विधि से करते हैं:
सारणी (Table) 4

अथवा

इस प्रकार हमें एक नई सारणी प्राप्त होती है जिसमें प्रत्येक पंक्ति तथा प्रत्येक स्तम्भ में एक नियतन है।अर्थात् पूर्ण शून्य निर्दिष्टीकरण निम्न अनुसार प्राप्त होता है।

A \rightarrow I,B \rightarrow II,C \rightarrow III,D \rightarrow IV \\ A \rightarrow II,B \rightarrow III,C \rightarrow IV,D \rightarrow I
Example:4.

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

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

पद (Step):III.शून्य निर्दिष्टीकरण (Zero Assignment)

अब प्रथम पंक्ति से अवलोकन प्रारम्भ करते हुए उन पंक्तियों को चुनते हैं जिनमें एक और केवल एक शून्य हो।इन पंक्तियों की शून्यों को वर्ग से (🔲) अंकित करते हैं तथा इन शून्यों से गुजरने वाले स्तम्भ की अन्य शून्यों को × (काट) देते हैं।
सारणी (Table) 3

पुनः प्रथम स्तम्भ से अवलोकन प्रारम्भ करते हुए उन स्तम्भों को चुनते हैं जिनमें अचिन्हित एक और केवल एक शून्य हो।इन शून्यों को वर्ग से (🔲) अंकित करिए तथा इस शून्य से होकर जानेवाली पंक्ति की अन्य शून्यों को × (काट) देते हैं।
सारणी (Table) 4

पद (Step):IV.अब समस्त शून्यों को ढकने के लिए न्यूनतम संख्या में रेखाएँ खींचते हैं जिसकी विधि निम्नानुसार है:
पंक्ति III व IV को (✓) चिन्हित कीजिए क्योंकि इनमें कोई भी शून्य वर्ग से (🔲) अंकित नहीं है।अब पंक्ति III व IV में स्तम्भ 2 व 4 में शून्य है इसलिए स्तम्भ 2 व 4 को चिन्हित किया।
अब हम चिन्हित स्तम्भ 2 व 4 पर रेखा खींचते हैं फिर अचिन्हित पंक्तियों अर्थात् III व V पर रेखाएं खींचते हैं।अब कोई भी ऐसा शून्य नहीं है जो रेखाओं से ढ़का हुआ नहीं है।रेखाओं की संख्या 5 है जो 5 (=n) के बराबर है (मैट्रिक्स 5×5 क्रम की है इसलिए n=5)।इसलिए सारणी 4 से इष्टतम नियतन प्राप्त हो सकता है।
सारणी (Table) 5

Trial and Error विधि से इसके दो इष्टतम नियतन निम्न प्राप्त होते हैं:
सारणी (Table) 6

सारणी (Table) 7

इस प्रकार हमें एक नई सारणी प्राप्त होती है जिसमें प्रत्येक पंक्ति तथा प्रत्येक स्तम्भ में एक नियतन है।अर्थात् पूर्ण शून्य निर्दिष्टीकरण निम्न अनुसार प्राप्त होता है।
प्रथम नियतन (हल):I \rightarrow 3,II \rightarrow 1,III \rightarrow 2,IV \rightarrow 4,V \rightarrow 5
द्वितीय नियतन (हल): I \rightarrow 3,II \rightarrow 1,III \rightarrow 4,IV \rightarrow 2,V \rightarrow 5
उपर्युक्त उदाहरणों के द्वारा नियतन (अधिन्यासन) समस्याएं (Assignment Problems) को समझ सकते हैं।

3.नियतन (अधिन्यासन) समस्याएं के सवाल (Assignment Problems Questions):

Assignment Problems

(1.)निम्न नियतन समस्या को हल कीजिए।
(Solve the following assignment problem):

(2.)निम्न नियतिकरण की समस्या को हल कीजिए।
(Solve the following assignment problem):

उत्तर (Answers):(1.)(i)ईष्टतम हल न्यूनतम लागत=11+43+33+27+11+17=Rs.142
(ii)न्यूनतम लागत=11+48+28+27+25+3=Rs.142
(3.)दी हुई समस्या का ईष्टतम हल है:
न्यूनतम समय=27+10+12=49 इकाई
उपर्युक्त सवालों को हल करने पर नियतन (अधिन्यासन) समस्याएं (Assignment Problems) को ठीक से समझ सकते हैं।

Also Read This Article:-Theory of Simplex Method

4.नियतन (अधिन्यासन) समस्याएं (Assignment Problems) के सम्बन्ध में अक्सर पूछे जाने वाले प्रश्न:

नियतन (अधिन्यासन) समस्याएं (Assignment Problems) का जनक दिन प्रतिदिन की समस्याएं हैं।नियतन
की समस्याओं में व्यक्तियों को उनकी क्षमता के अनुरूप अलग-अलग कार्यों पर लगाना, व्यक्तियों द्वारा
अलग-अलग कार्य करने से आई लागत को न्यूनतम करना विक्रेताओं द्वारा अलग-अलग क्षेत्र के इस
प्रकार ब्रिकी करना की अधिअतम लाभ हो इत्यादि।