असाइनमेंट की समस्या

हंगेरियन पद्धति का उपयोग करके असमान संख्या में श्रमिकों को कार्य सौंपने का उदाहरण

नियतनसमस्या एक मौलिक संयोजन अनुकूलन समस्या है। अपने सबसे सामान्य रूप में, समस्या इस प्रकार है:

समस्या उदाहरण में कई अभिकर्ता और कई कार्य हैं। किसी भी अभिकर्ता को कोई भी कार्य करने के लिए सौंपा जा सकता है, जिसमें कुछ लागत लगती है जो अभिकर्ता-कार्य समनुदेशन के आधार पर भिन्न हो सकती है। प्रत्येक कार्य के लिए अधिकतम एक अभिकर्ता और प्रत्येक अभिकर्ता को अधिकतम एक कार्य सौंपकर यथासंभव अधिक से अधिक कार्य करना आवश्यक है, ताकि समनुदेशन की कुल लागत कम से कम हो।

वैकल्पिक रूप से, लेखाचित्र सिद्धांत का उपयोग करके समस्या का वर्णन करना:

नियतनसमस्या में एक भारित लेखाचित्र द्विदलीय लेखाचित्र में, किसी दिए गए आकार का एक मिलान (लेखाचित्र सिद्धांत) ढूंढना सम्मिलित है, जिसमें किनारों के भार का योग न्यूनतम है।

यदि अभिकर्ताों और कार्यों की संख्या समान है, तो समस्या को संतुलित समनुदेशन कहा जाता है। अन्यथा, इसे असंतुलित समनुदेशन कहा जाता है। यदि सभी कार्यों के लिए समनुदेशन की कुल लागत प्रत्येक अभिकर्ता के लिए लागतों के योग के बराबर है (या प्रत्येक कार्य के लिए लागतों का योग, जो इस स्तिथि में एक ही बात है), तो समस्या को रैखिक समनुदेशन कहा जाता है। सामान्यतः, जब बिना किसी अतिरिक्त योग्यता के नियतनसमस्या की बात की जाती है, तो रैखिक संतुलित नियतनसमस्या का अर्थ होता है।

उदाहरण

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

अब, मान लीजिए कि चार टैक्सी उपलब्ध हैं, लेकिन ग्राहक अभी भी केवल तीन हैं। यह एक असंतुलित नियतनसमस्या है। इसे हल करने का एक तरीका चौथे डमी कार्य का आविष्कार करना है, जिसे संभवतः बिना कुछ किए बैठे रहना कहा जाता है, जिसमें सौंपी गई टैक्सी के लिए 0 की लागत होगी। यह समस्या को एक संतुलित नियतनसमस्या में बदल देता है, जिसे सामान्य तरीके से हल किया जा सकता है और फिर भी समस्या का सबसे अच्छा समाधान दिया जा सकता है।

अभिकर्ता की तुलना में अधिक कार्यों की अनुमति देने के लिए समान समायोजन किया जा सकता है, ऐसे कार्य जिनके लिए कई अभिकर्ताों को सौंपा जाना चाहिए (उदाहरण के लिए, एक टैक्सी में फिट होने से अधिक ग्राहकों का समूह), या लागत को कम करने के स्थान पर लाभ को अधिकतम करता है।

औपचारिक परिभाषा

नियतनसमस्या (या रैखिक नियतनसमस्या) की औपचारिक परिभाषा है

दो सम्मुच्चय a और t दिए गए हैं, एक भार फलन c के साथ: a × t → R। एक आक्षेप f : A → T इस प्रकार खोजें कि हानि फलन निम्न है:

$\sum _{a\in A}C(a,f(a))$

न्यूनतम किया गया है।

सामान्यतः भार फलन को एक वर्ग वास्तविक-मूल्य वाले आव्यूह (गणित) c के रूप में देखा जाता है, ताकि लागत फलन को इस प्रकार लिखा जा सके:

$\sum _{a\in A}C_{a,f(a)}$

समस्या रैखिक है क्योंकि लागत फलन को अनुकूलित करने के साथ-साथ सभी बाधाओं में केवल रैखिक शब्द सम्मिलित हैं।

कलन विधि

नियतनसमस्या का एक सरल समाधान सभी समनुदेशन की जांच करना और प्रत्येक की लागत की गणना करना है। यह बहुत अकुशल हो सकता है क्योंकि, n अभिकर्ता और n कार्यों के साथ, n (n का तथ्यात्मक) अलग-अलग समनुदेशन होते हैं। सौभाग्य से, n में बहुपद समय की समस्या को हल करने के लिए कई कलन विधि हैं।

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

संतुलित समनुदेशन

संतुलित नियतनसमस्या में, द्विदलीय लेखाचित्र के दोनों हिस्सों में शीर्षों की संख्या समान है, जिसे n द्वारा दर्शाया गया है।

संतुलित समनुदेशन के लिए पहले बहुपद-समय कलन विधि में से एक हंगेरियन कलन विधि था। यह एक वैश्विक कलन विधि है - यह संवर्धित पथों (बेजोड़ शीर्षों के बीच वैकल्पिक पथ) के साथ मिलान में सुधार करने पर आधारित है। फाइबोनैचि हीप्स का उपयोग करते समय इसकी कार्यावधि जटिलता $O(mn+n^{2}\log n)$ होती है, जहाँ m किनारों की संख्या है। यह वर्तमान में इस समस्या के लिए एक सशक्त बहुपद कलन विधि का सबसे तेज़ कार्यावधि है। यदि सभी भार पूर्णांक हैं, तो कार्यावधि $O(mn+n^{2}\log \log n)$ में सुधार किया जा सकता है, लेकिन परिणामी कलन विधि केवल शक्तिहीन-बहुपद है। यदि भार पूर्णांक हैं, और सभी भार अधिकतम C हैं (जहाँ C>1 कुछ पूर्णांक है), तो समस्या $O(m{\sqrt {n}}\log(n\cdot C))$ वेट स्केलिंग नामक विधि में शक्तिहीन-बहुपद समय को हल किया जा सकता है।

वैश्विक तरीकों के अतिरिक्त, स्थानीय तरीके भी हैं जो स्थानीय अपडेट खोजने पर आधारित हैं (पूर्ण संवर्द्धन पथों के स्थान पर)। इन तरीकों में बदतर स्पर्शोन्मुख कार्यावधि गारंटी है, लेकिन वे प्रायः व्यवहार में बेहतर काम करते हैं। इन एल्गोरिदम को नीलामी एल्गोरिदम कहा जाता है, वर्धन-पुन: वर्गीकरण कलन विधि या परफ्लो-वर्धन कलन विधि कहा जाता है। इनमें से कुछ कलन विधि को समतुल्य दिखाया गया था। कुछ स्थानीय विधियाँ मानती हैं कि लेखाचित्र पूर्ण मिलान स्वीकार करता है; यदि ऐसा नहीं है, तो इनमें से कुछ विधियाँ हमेशा के लिए चल सकती हैं। इस समस्या को हल करने का एक सरल तकनीकी तरीका बहुत बड़े भार के साथ कृत्रिम किनारों को जोड़कर, निविष्ट लेखाचित्र को पूर्ण द्विदलीय लेखाचित्र तक विस्तारित करना है। संभावित समाधान में कृत्रिम किनारों की उपस्थिति को रोकने के लिए, ये भार सभी उपस्थिता मिलानों के भार से अधिक होना चाहिए।

जैसा कि मुलमुले, वज़ीरानी और वज़ीरानी द्वारा दिखाया गया है, न्यूनतम भार पूर्ण मिलान की समस्या को लेखाचित्र के आसन्न आव्यूह में नाबालिगों को खोजने में बदल दिया जाता है। अलगाव लेम्मा का उपयोग करके, लेखाचित्र में न्यूनतम भार का सही मिलान कम से कम 1⁄2 संभावना के साथ पाया जा सकता है। n शीर्षों वाले लेखाचित्र के लिए, इसकी आवश्यकता $O(\log ^{2}(n))$ समय होती है।

असंतुलित समनुदेशन

असंतुलित नियतनसमस्या में, द्विदलीय लेखाचित्र के बड़े भाग में n शीर्ष हैं और छोटे भाग में r<n शीर्ष हैं। एक स्थिरांक s भी है जो लेखाचित्र में अधिकतम मिलान की प्रमुखता है। लक्ष्य बिल्कुल आकार का न्यूनतम-लागत मिलान ढूंढना है। सबसे सामान्य स्तिथि वह स्तिथि है जिसमें लेखाचित्र एक तरफा-पूर्ण मिलान (यानी, आकार r का मिलान), और s = r को स्वीकार करता है।

असंतुलित समनुदेशन को संतुलित समनुदेशन में घटाया जा सकता है। सरल कटौती छोटे हिस्से में n - r नए कोने जोड़ना और लागत 0 के किनारों का उपयोग करके उन्हें बड़े हिस्से से जोड़ना है। हालाँकि, इसके लिए $n(n-r)$ नए किनारों की आवश्यकता होती है। अधिक कुशल कटौती को दोहरीकरण तकनीक कहा जाता है। यहां, एक नया लेखाचित्र G' मूल लेखाचित्र G की दो प्रतियों से बनाया गया है: एक आग्रवर्ती अनुकरण Gf और एक बैकवर्ड अनुकरण Gb है। पिछली प्रतिलिपि को प्रतिवर्न किया गया है, ताकि, G' के प्रत्येक पक्ष में, अब n+r शीर्ष हों। प्रतियों के बीच, हमें दो प्रकार के संयोजन किनारे जोड़ने होंगे:

• बड़े से बड़े: जीएफ के बड़े हिस्से में प्रत्येक शीर्ष से, जीबी में संबंधित शीर्ष पर एक शून्य-लागत किनारा जोड़ें।
• छोटे से छोटे: यदि मूल लेखाचित्र में एक तरफा-पूर्ण मिलान नहीं है, तो जीएफ के छोटे हिस्से में प्रत्येक शीर्ष से, जीबी में संबंधित शीर्ष पर एक बहुत ही उच्च लागत वाला किनारा जोड़ें।

कुल मिलाकर, अधिक से अधिक $n+r$ नए किनारों की आवश्यकता है। परिणामी लेखाचित्र में हमेशा आकार का सही मिलान $n+r$ होता है। इस लेखाचित्र में न्यूनतम-लागत पूर्ण मिलान में जीएफ और जीबी में न्यूनतम-लागत अधिकतम-गणनांक मिलान सम्मिलित होना चाहिए। इस दोहरीकरण तकनीक के साथ मुख्य समस्या यह है कि इसमें गति $r\ll n$ नहीं बढ़ती है।

कटौती का उपयोग करने के स्थान पर, संतुलित समनुदेशन के लिए उपस्थिता कलन विधि को सीधे सामान्यीकृत करके असंतुलित नियतनसमस्या को हल किया जा सकता है। समस्या को हल करने के लिए हंगेरियन कलन विधि $O(ms+s^{2}\log r)$ दृढ़तापूर्वक-बहुपद समय को सामान्यीकृत किया जा सकता है। विशेष रूप से, यदि s=r तो कार्यावधि $O(mr+r^{2}\log r)$ है। यदि भार पूर्णांक हैं, तो कार्यावधि प्राप्त करने के लिए थोरुप की विधि $O(ms+s^{2}\log \log r)$ का उपयोग किया जा सकता है।

रैखिक प्रोग्रामिंग द्वारा समाधान

नियतनसमस्या को एक रैखिक प्रोग्राम के रूप में प्रस्तुत करके हल किया जा सकता है। सुविधा के लिए हम अधिकतमीकरण समस्या प्रस्तुत करेंगे। प्रत्येक किनारा (i,j), जहां i, A में है और j, T में है, उसका एक भार ${\textstyle w_{ij}}$ है। प्रत्येक किनारे $(i,j)$ के लिए हमारे पास एक परिवर्ती ${\textstyle x_{ij}}$ है। यदि मिलान में किनारा समाहित है तो चर 1 है और अन्यथा 0 है, इसलिए हम कार्यछेत्र बाधाएँ निर्धारित करते हैं:

$$0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,$$

$$x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.$$

मिलान का कुल भार $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ है। लक्ष्य अधिकतम भार का सही मिलान ढूंढना है।

यह प्रत्याभुति देने के लिए कि चर वास्तव में एक पूर्ण मिलान का प्रतिनिधित्व करते हैं, हम यह कहते हुए बाधाएँ जोड़ते हैं कि प्रत्येक शीर्ष मिलान में बिल्कुल एक किनारे से सटा हुआ है, अर्थात,

$$\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T,\,$$

.

कुल मिलाकर हमारे पास निम्नलिखित एलपी है:

$${\text{maximize}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$$

$${\text{subject to}}~~\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T$$

$$0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,$$

$$x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.$$

यह एक पूर्णांक रैखिक क्रमानुदेश है। हालाँकि, हम निरंतर रैखिक कार्यक्रमों को हल करने के लिए मानक तरीकों का उपयोग करके, अभिन्नता बाधाओं के बिना इसे हल कर सकते हैं (यानी, अंतिम बाधा को छोड़ दें)। हालांकि यह सूत्रीकरण भिन्नात्मक चर मानों की भी अनुमति देता है, इस विशेष स्तिथि में, एलपी के पास हमेशा एक इष्टतम समाधान होता है जहां चर पूर्णांक मान लेते हैं। ऐसा इसलिए है क्योंकि फ्रैक्शनल एलपी का बाधा आव्यूह यूनिमॉड्यूलर आव्यूह#टोटल यूनिमॉड्यूलरिटी है - यह हॉफमैन और गेल की चार शर्तों को पूरा करता है।

अन्य विधियाँ और सन्निकटन कलन विधि

नियतनसमस्या के लिए अन्य दृष्टिकोण उपस्थित हैं और डुआन और पेटी द्वारा उनकी समीक्षा की गई है (तालिका II देखें)। उनका काम नियतनसमस्या (और अधिक सामान्य अधिकतम भार मिलान समस्या) के लिए एक सन्निकटन कलन विधि का प्रस्ताव करता है, जो किसी भी निश्चित त्रुटि सीमा के लिए रैखिक समय में चलता है।

सामान्यीकरण

जब लेखाचित्र सिद्धांत समस्या के रूप में व्यक्त किया जाता है, तो नियतनसमस्या को द्विदलीय लेखाचित्र से मनमाना लेखाचित्र तक बढ़ाया जा सकता है। एक भारित लेखाचित्र में मिलान (लेखाचित्र सिद्धांत) खोजने की संबंधित समस्या, जहां भार का योग अधिकतम होता है, को अधिकतम भार मिलान कहा जाता है।

नियतनसमस्या का एक और सामान्यीकरण मिलान किए जाने वाले सम्मुच्चयों की संख्या को दो से कई तक बढ़ाना है। इसलिए, अभिकर्ताों को कार्यों से मिलान करने के स्थान पर, समस्या को कार्यों से मिलान करने वाले अभिकर्ताों से लेकर समय अंतराल और स्थानों तक बढ़ा दिया जाता है। इसके परिणामस्वरूप बहुआयामी नियतनसमस्या (एमएपी) उत्पन्न होती है।

यह भी देखें

• नीलामी कलन विधि
• सामान्यीकृत नियतनसमस्या
• रैखिक बाधा नियतनसमस्या
• मोंगे-कांटोरोविच अभिगमन समस्या, एक अधिक सामान्य सूत्रीकरण
• राष्ट्रीय निवासी मिलान कार्यक्रम
• द्विघात नियतनसमस्या
• रैंक-अधिकतम मिलान
• सचिव समस्या
• स्थिर गठ बंधन समस्या
• स्थिर रूममेट्स की समस्या
• हथियार लक्ष्य निर्धारण समस्या
• आवास आवंटन की समस्या
• बहुआयामी नियतनसमस्या (एमएपी)

सन्दर्भ और आगे पढ़ना

• Brualdi, Richard A. (2006). कॉम्बिनेटोरियल मैट्रिक्स कक्षाएं. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.
• Burkard, Rainer; M. Dell'Amico; S. Martello (2012). असाइनमेंट समस्याएँ (संशोधित पुनर्मुद्रण). SIAM. ISBN 978-1-61197-222-1.
• Bertsekas, Dimitri (1998). नेटवर्क अनुकूलन: सतत और असतत मॉडल. Athena Scientific. ISBN 978-1-886529-02-1.

श्रेणी:संयुक्त अनुकूलन श्रेणी:मिलान (लेखाचित्र सिद्धांत) श्रेणी:बहुपद-समय की समस्याएँ श्रेणी:रैखिक प्रोग्रामिंग