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

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

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

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

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

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

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

उदाहरण

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

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

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

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

असाइनमेंट समस्या (या रैखिक असाइनमेंट समस्या) की औपचारिक परिभाषा है

दो सेट दिए गए हैं, ए और टी, एक वजन समारोह सी के साथ: ए × टी → वास्तविक संख्या। एक आक्षेप f : A → T इस प्रकार खोजें कि हानि फलन:

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

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

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

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

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

एल्गोरिदम

असाइनमेंट समस्या का एक सरल समाधान सभी असाइनमेंट की जांच करना और प्रत्येक की लागत की गणना करना है। यह बहुत अप्रभावी हो सकता है, क्योंकि 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 भी है जो ग्राफ़ में अधिकतम मिलान की प्रमुखता है। लक्ष्य बिल्कुल आकार का न्यूनतम-लागत मिलान ढूंढना है। सबसे आम मामला वह मामला है जिसमें ग्राफ़ एक तरफा-पूर्ण मिलान (यानी, आकार आर का मिलान), और एस = आर को स्वीकार करता है।

असंतुलित असाइनमेंट को संतुलित असाइनमेंट में घटाया जा सकता है। भोली कमी जोड़ना है $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.

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