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

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

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

विशेष स्थितियों में

विशेष मामले में जहां सभी एजेंट के बजट और सभी कार्यों की लागत 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$-सन्निकटन कलन विधि एएलजी का उपयोग करते हुए, अवशिष्ट लाभ अवधारणा का उपयोग करके लुब्ध तरीके से सामान्यीकृत नियतनसमस्या के लिए ($\alpha +1$)-सन्निकटन का निर्माण करना संभव है। कलन विधि पुनरावृत्तियों में शेड्यूल बनाता है, जहां पुनरावृत्ति $j$ के दौरान बिन $b_{j}$ में आइटमों का अस्थायी चयन चुना जाता है। बिन $b_{j}$ के लिए चयन परिवर्तन हो सकता है क्योंकि बाद में अन्य बिनों के लिए आइटमों को फिर से चुना जा सकता है। बिन $b_{j}$के लिए किसी आइटम $x_{i}$ का अवशिष्ट लाभ $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$ के लिए करना:

अवशिष्ट लाभ फलन $P_{j}$ का उपयोग करके बिन $b_{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.