सामान्यीकृत नियतन समस्या

अनुप्रयुक्त गणित में, अधिकतम सामान्यीकृत असाइनमेंट समस्या संयोजन अनुकूलन में एक समस्या है। यह समस्या असाइनमेंट समस्या का एक सामान्यीकरण है जिसमें कार्य और एजेंट-आधारित मॉडल दोनों का एक आकार होता है। इसके अलावा, प्रत्येक कार्य का आकार एक एजेंट से दूसरे एजेंट तक भिन्न हो सकता है।

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

विशेष मामलों में

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

परिभाषा की व्याख्या

निम्नलिखित में, हमारे पास n प्रकार के आइटम हैं, $a_{1}$ द्वारा $a_{n}$ और एम प्रकार के डिब्बे $b_{1}$ द्वारा $b_{m}$. प्रत्येक बिन $b_{i}$ बजट से जुड़ा है $t_{i}$. एक डिब्बे के लिए $b_{i}$, प्रत्येक आइटम $a_{j}$ लाभ है $p_{ij}$ और एक वजन $w_{ij}$. समाधान वस्तुओं से लेकर डिब्बे तक का असाइनमेंट है। एक व्यवहार्य समाधान वह समाधान है जिसमें प्रत्येक बिन के लिए $b_{i}$ निर्दिष्ट वस्तुओं का कुल भार अधिकतम है $t_{i}$. समाधान का लाभ प्रत्येक आइटम-बिन असाइनमेंट के लिए लाभ का योग है। लक्ष्य अधिकतम लाभ संभव समाधान खोजना है।

गणितीय रूप से सामान्यीकृत असाइनमेंट समस्या को पूर्णांक प्रोग्रामिंग के रूप में तैयार किया जा सकता है:

${\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}$

जटिलता

सामान्यीकृत असाइनमेंट समस्या एनपी कठिन है, हालाँकि, रैखिक-प्रोग्रामिंग छूटें हैं जो एक देती हैं $(1-1/e)$-अनुमान.

लालची सन्निकटन एल्गोरिथ्म

समस्या संस्करण के लिए जिसमें प्रत्येक आइटम को एक बिन को नहीं सौंपा जाना चाहिए, जीएपी को हल करने के लिए एल्गोरिदम का एक परिवार है, जो कि नैपसैक समस्या के लिए किसी भी एल्गोरिदम के जीएपी के लिए एक सन्निकटन एल्गोरिदम में संयोजन अनुवाद का उपयोग करता है। किसी का उपयोग करना $\alpha$-नैपसेक समस्या के लिए सन्निकटन एल्गोरिथ्म ALG, इसका निर्माण संभव है ($\alpha +1$)-अवशिष्ट लाभ अवधारणा का उपयोग करके लालची तरीके से सामान्यीकृत असाइनमेंट समस्या का अनुमान लगाना। एल्गोरिदम पुनरावृत्तियों में एक शेड्यूल बनाता है, जहां पुनरावृत्ति के दौरान $j$ बिन में आइटमों का एक अस्थायी चयन $b_{j}$ चयनित है। बिन के लिए चयन $b_{j}$ परिवर्तन हो सकता है क्योंकि वस्तुओं को बाद के पुनरावृत्ति में अन्य डिब्बे के लिए पुनः चयनित किया जा सकता है। किसी वस्तु का अवशिष्ट लाभ $x_{i}$ बिन के लिए $b_{j}$ है $p_{ij}$ अगर $x_{i}$ किसी अन्य बिन या के लिए चयनित नहीं है $p_{ij}$ – $p_{ik}$ अगर $x_{i}$ बिन के लिए चुना गया है $b_{k}$.

औपचारिक रूप से: हम एक वेक्टर का उपयोग करते हैं $T$ एल्गोरिदम के दौरान अस्थायी शेड्यूल को इंगित करने के लिए। विशेष रूप से, $T[i]=j$ वस्तु का मतलब है $x_{i}$ बिन पर शेड्यूल किया गया है $b_{j}$ और $T[i]=-1$ मतलब वह वस्तु $x_{i}$ अनुसूचित नहीं है. पुनरावृत्ति में अवशिष्ट लाभ $j$ द्वारा निरूपित किया जाता है $P_{j}$, कहाँ $P_{j}[i]=p_{ij}$ यदि आइटम $x_{i}$ निर्धारित नहीं है (अर्थात् $T[i]=-1$) और $P_{j}[i]=p_{ij}-p_{ik}$ यदि आइटम $x_{i}$ बिन पर शेड्यूल किया गया है $b_{k}$ (अर्थात। $T[i]=k$).

औपचारिक रूप से:

तय करना $T[i]=-1{\text{ for }}i=1\ldots n$

के लिए $j=1,\ldots ,m$ करना:

बिन का समाधान खोजने के लिए ALG को कॉल करें $b_{j}$ अवशिष्ट लाभ फ़ंक्शन का उपयोग करना $P_{j}$. चयनित वस्तुओं को इससे निरूपित करें $S_{j}$.

अद्यतन $T$ का उपयोग करते हुए $S_{j}$, अर्थात।, $T[i]=j$ सभी के लिए $i\in S_{j}$.

यह भी देखें

• असाइनमेंट समस्या

अग्रिम पठन

Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2013-03-19). Knapsack Problems. ISBN 978-3-540-24777-7.