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

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

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

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

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

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

निम्नलिखित में, हमारे पास n प्रकार के आइटम हैं, $a_{1}$से $a_{n}$ तक और m प्रकार के बिन $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.