सामान्यीकृत नियतन समस्या: Difference between revisions

Latest revision as of 11:50, 25 August 2023

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

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

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

विशेष मामले में जहां सभी एजेंट के बजट और सभी कार्यों की लागत 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-1/e)$ -अनुमान देती हैं^[2]

लुब्ध सन्निकटन कलन विधि

समस्या संस्करण के लिए जिसमें प्रत्येक आइटम को एक बिन को नहीं सौंपा जाना चाहिए, जीएपी को हल करने के लिए कलन विधि का वर्ग है, जो कि नैपसकसमस्या के लिए किसी भी कलन विधि के जीएपी के लिए सन्निकटन कलन विधि में संयोजन अंतरण का उपयोग करता है।^[3]

नैपसकसमस्या के लिए किसी भी $\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}

के लिए।

यह भी देखें

नियतनसमस्या

संदर्भ

↑ Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Bees algorithm for generalized assignment problem, Applied Mathematics and Computation, vol. 215, Elsevier, pp. 3782–3795, doi:10.1016/j.amc.2009.11.018.
↑ Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). "अधिकतम सामान्य असाइनमेंट समस्याओं के लिए चुस्त सन्निकटन एल्गोरिदम". {{cite journal}}: Cite journal requires |journal= (help)
↑ Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "सामान्यीकृत असाइनमेंट समस्या के लिए एक कुशल सन्निकटन". Information Processing Letters. 100 (4): 162–166. doi:10.1016/j.ipl.2006.06.003.

अग्रिम पठन

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

[1] Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Bees algorithm for generalized assignment problem, Applied Mathematics and Computation, vol. 215, Elsevier, pp. 3782–3795, doi:10.1016/j.amc.2009.11.018.

[2] Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). "अधिकतम सामान्य असाइनमेंट समस्याओं के लिए चुस्त सन्निकटन एल्गोरिदम". {{cite journal}}: Cite journal requires |journal= (help)

[3] Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "सामान्यीकृत असाइनमेंट समस्या के लिए एक कुशल सन्निकटन". Information Processing Letters. 100 (4): 162–166. doi:10.1016/j.ipl.2006.06.003.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{short description|Combinatorial optimization problem}}
-व्यावहारिक गणित में, अधिकतम '''सामान्यीकृत [[असाइनमेंट समस्या|नियतनसमस्या]]''' संयोजन अनुकूलन में एक समस्या है। यह समस्या नियतनसमस्या का सामान्यीकरण है जिसमें कार्य और [[एजेंट-आधारित मॉडल]] दोनों का एक आकार होता है। इसके अलावा, प्रत्येक कार्य का आकार एक एजेंट से दूसरे एजेंट तक भिन्न हो सकता है।
+व्यावहारिक गणित में, अधिकतम '''सामान्यीकृत [[असाइनमेंट समस्या|नियतन समस्या]]''' संयोजन अनुकूलन में एक समस्या है। यह समस्या नियतन समस्या का सामान्यीकरण है जिसमें कार्य और [[एजेंट-आधारित मॉडल]] दोनों का एक आकार होता है। इसके अतिरिक्त, प्रत्येक कार्य का आकार एक एजेंट से दूसरे एजेंट तक भिन्न हो सकता है।
-यह समस्या अपने सबसे सामान्य रूप में इस प्रकार है: इसमें बहुत सारे एजेंट और बहुत सारे कार्य हैं। किसी भी एजेंट को कोई भी कार्य करने के लिए सौंपा जा सकता है, जिसमें कुछ लागत और लाभ शामिल होता है जो एजेंट-कार्य नियतन के आधार पर भिन्न हो सकता है। इसके अलावा, प्रत्येक एजेंट के पास एक बजट होता है और उसे सौंपे गए कार्यों की लागत का योग इस बजट से अधिक नहीं हो सकता है। ऐसा नियतन ढूंढना आवश्यक है जिसमें सभी एजेंट अपने बजट से अधिक न हों और नियतन का कुल लाभ अधिकतम हो।
+अपने सबसे सामान्य रूप में यह समस्या इस प्रकार है: इसमें बहुत एजेंट और बहुत कार्य हैं। किसी भी एजेंट को कोई भी कार्य करने के लिए सौंपा जा सकता है, जिसमें कुछ लागत और लाभ सम्मिलित होता है जो एजेंट-कार्य नियतन के आधार पर भिन्न हो सकता है। इसके अतिरिक्त, प्रत्येक एजेंट के पास एक बजट होता है और उसे सौंपे गए कार्यों की लागत का योग इस बजट से अधिक नहीं हो सकता है। ऐसा नियतन ढूंढना आवश्यक है जिसमें सभी एजेंट अपने बजट से अधिक न हों और नियतन का कुल लाभ अधिकतम हो।
-==विशेष मामलों में==
+==विशेष स्थितियों में==
-विशेष स्थिति में जिसमें सभी एजेंटों के बजट और सभी कार्यों की लागत 1 के बराबर है, यह समस्या नियतनसमस्या में बदल जाती है। जब विभिन्न एजेंटों के बीच सभी कार्यों की लागत और मुनाफा भिन्न नहीं होता है, तो यह समस्या विविध नैपसेक समस्या में बदल जाती है। यदि एक ही एजेंट है, तो यह समस्या कम होकर नैपसैक समस्या बन जाती है।
+विशेष मामले में जहां सभी एजेंट के बजट और सभी कार्यों की लागत 1 के बराबर है, यह समस्या नियतन समस्या में बदल जाती है। जब विभिन्न एजेंट के बीच सभी कार्यों की लागत और मुनाफा भिन्न नहीं होता है, तो यह समस्या विविध नैपसकसमस्या में बदल जाती है। यदि एक ही एजेंट है, तो यह समस्या कम होकर नैपसकसमस्या बन जाती है।
 ==परिभाषा की व्याख्या==
-निम्नलिखित में, हमारे पास ''n'' प्रकार के आइटम हैं, <math>a_1</math>से <math>a_n</math> तक और ''m'' प्रकार के बिन <math>b_1</math> से <math>b_m</math>तक। प्रत्येक बिन <math>b_i</math> बजट <math>t_i</math> से जुड़ा है। एक बिन <math>b_i</math> के लिए, प्रत्येक आइटम <math>a_j</math> को लाभ  <math>p_{ij}</math> और वजन <math>w_{ij}</math> होता है समाधान वस्तुओं से लेकर बिन तक का नियतन है। एक व्यवहार्य समाधान वह समाधान है जिसमें प्रत्येक बिन <math>b_i</math> के लिए निर्दिष्ट वस्तुओं का कुल भार अधिकतम <math>t_i</math> है, समाधान का लाभ प्रत्येक आइटम-बिन नियतन के लिए लाभ का योग है। लक्ष्य अधिकतम लाभ संभव समाधान खोजना है।
+निम्नलिखित में, हमारे पास ''n'' प्रकार के आइटम हैं, <math>a_1</math>से <math>a_n</math> तक और ''m'' प्रकार के बिन <math>b_1</math>से <math>b_m</math>तक हैं। प्रत्येक बिन <math>b_i</math> बजट <math>t_i</math> से जुड़ा है। बिन <math>b_i</math> के लिए, प्रत्येक आइटम <math>a_j</math> को लाभ  <math>p_{ij}</math> और वजन <math>w_{ij}</math> होता है समाधान वस्तुओं से लेकर बिन तक का नियतन है। एक व्यवहार्य समाधान वह समाधान है जिसमें प्रत्येक बिन <math>b_i</math> के लिए निर्दिष्ट वस्तुओं का कुल भार अधिकतम <math>t_i</math> है, समाधान का लाभ प्रत्येक आइटम-बिन नियतन के लिए लाभ का योग है। लक्ष्य अधिकतम लाभ संभव समाधान खोजना है।
 गणितीय रूप से सामान्यीकृत नियतनसमस्या को [[पूर्णांक प्रोग्रामिंग]] के रूप में तैयार किया जा सकता है:
@@ Line 23: / Line 23: @@
-'''<big>जटिलता</big>'''
+== <big>जटिलता</big> ==
 सामान्यीकृत नियतनसमस्या[[ एनपी कठिन | एनपी-कठोरता]] है,<ref>{{citation
   | last1 = Özbakir | first1 = Lale
@@ Line 37: / Line 36: @@
   | issue = 11
   | year = 2010}}.</ref> हालाँकि, रैखिक-प्रोग्रामिंग विश्रांति हैं जो <math>(1 - 1/e)</math>-अनुमान देती हैं<ref>{{cite journal |last=Fleischer |first=Lisa |last2=Goemans |first2=Michel X. |last3=Mirrokni |first3=Vahab S. |last4=Sviridenko |first4=Maxim |title=अधिकतम सामान्य असाइनमेंट समस्याओं के लिए चुस्त सन्निकटन एल्गोरिदम|date=2006}}</ref>
-==लुब्ध सन्निकटन एल्गोरिथ्म==
+==लुब्ध सन्निकटन कलन विधि==
-समस्या संस्करण के लिए जिसमें प्रत्येक आइटम को एक बिन को नहीं सौंपा जाना चाहिए, जीएपी को हल करने के लिए एल्गोरिदम का एक परिवार है, जो कि नैपसैक समस्या के लिए किसी भी एल्गोरिदम के जीएपी के लिए एक सन्निकटन एल्गोरिदम में संयोजन अनुवाद का उपयोग करता है।<ref>{{cite journal |doi=10.1016/j.ipl.2006.06.003|title=सामान्यीकृत असाइनमेंट समस्या के लिए एक कुशल सन्निकटन|journal=Information Processing Letters|volume=100|issue=4|pages=162–166|year=2006|last1=Cohen|first1=Reuven|last2=Katzir|first2=Liran|last3=Raz|first3=Danny}}</ref>
+समस्या संस्करण के लिए जिसमें प्रत्येक आइटम को एक बिन को नहीं सौंपा जाना चाहिए, जीएपी को हल करने के लिए कलन विधि का वर्ग है, जो कि नैपसकसमस्या के लिए किसी भी कलन विधि के जीएपी के लिए सन्निकटन कलन विधि में संयोजन अंतरण का उपयोग करता है।<ref>{{cite journal |doi=10.1016/j.ipl.2006.06.003|title=सामान्यीकृत असाइनमेंट समस्या के लिए एक कुशल सन्निकटन|journal=Information Processing Letters|volume=100|issue=4|pages=162–166|year=2006|last1=Cohen|first1=Reuven|last2=Katzir|first2=Liran|last3=Raz|first3=Danny}}</ref>
-किसी का उपयोग करना <math>\alpha</math>-नैपसेक समस्या के लिए सन्निकटन एल्गोरिथ्म ALG, इसका निर्माण संभव है (<math>\alpha + 1</math>)-अवशिष्ट लाभ अवधारणा का उपयोग करके लुब्ध तरीके से सामान्यीकृत नियतनसमस्या का अनुमान लगाना।
-एल्गोरिदम पुनरावृत्तियों में एक शेड्यूल बनाता है, जहां पुनरावृत्ति के दौरान <math>j</math> बिन में आइटमों का एक अस्थायी चयन <math>b_j</math> चयनित है।
+नैपसकसमस्या के लिए किसी भी <math>\alpha</math>-सन्निकटन कलन विधि एएलजी का उपयोग करते हुए, अवशिष्ट लाभ अवधारणा का उपयोग करके लुब्ध तरीके से सामान्यीकृत नियतनसमस्या के लिए (<math>\alpha + 1</math>)-सन्निकटन का निर्माण करना संभव है। कलन विधि पुनरावृत्तियों में शेड्यूल बनाता है, जहां पुनरावृत्ति <math>j</math> के दौरान बिन <math>b_j</math> में आइटमों का अस्थायी चयन चुना जाता है। बिन <math>b_j</math> के लिए चयन परिवर्तन हो सकता है क्योंकि बाद में अन्य बिनों के लिए आइटमों को फिर से चुना जा सकता है। बिन <math>b_j</math>के लिए किसी आइटम <math>x_i</math> का अवशिष्ट लाभ <math>p_{ij}</math>है यदि <math>x_i</math> को किसी अन्य बिन के लिए नहीं चुना गया है या <math> p_{ij}</math> – <math>p_{ik} </math> है यदि <math>x_i</math> को बिन <math>b_k</math> के लिए चुना गया है।
-बिन के लिए चयन <math>b_j</math> परिवर्तन हो सकता है क्योंकि वस्तुओं को बाद के पुनरावृत्ति में अन्य बिन के लिए पुनः चयनित किया जा सकता है।
-किसी वस्तु का अवशिष्ट लाभ <math>x_i</math> बिन के लिए <math>b_j</math> है <math>p_{ij}</math> अगर <math>x_i</math> किसी अन्य बिन या के लिए चयनित नहीं है <math> p_{ij}</math> – <math>p_{ik} </math> अगर <math>x_i</math> बिन के लिए चुना गया है <math>b_k</math>.
-औपचारिक रूप से: हम एक वेक्टर का उपयोग करते हैं <math>T</math> एल्गोरिदम के दौरान अस्थायी शेड्यूल को इंगित करने के लिए। विशेष रूप से, <math>T[i]=j</math> वस्तु का मतलब है <math>x_i</math> बिन पर शेड्यूल किया गया है <math>b_j</math> और <math>T[i]=-1</math> मतलब वह वस्तु <math>x_i</math> अनुसूचित नहीं है. पुनरावृत्ति में अवशिष्ट लाभ <math>j</math> द्वारा निरूपित किया जाता है <math>P_j</math>, कहाँ <math>P_j[i]=p_{ij}</math> यदि आइटम <math>x_i</math> निर्धारित नहीं है (अर्थात् <math>T[i]=-1</math>) और <math>P_j[i]=p_{ij}-p_{ik}</math> यदि आइटम <math>x_i</math> बिन पर शेड्यूल किया गया है <math>b_k</math> (अर्थात। <math>T[i]=k</math>).
+औपचारिक रूप से: हम कलन विधि के दौरान अस्थायी शेड्यूल को इंगित करने के लिए एक सदिश <math>T</math> का उपयोग करते हैं। विशेष रूप से, <math>T[i]=j</math> का अर्थ है कि आइटम <math>x_i</math> बिन <math>b_j</math> पर शेड्यूल किया गया है और <math>T[i]=-1</math> का अर्थ है कि आइटम <math>x_i</math> शेड्यूल नहीं किया गया है। पुनरावृत्ति <math>j</math> में अवशिष्ट लाभ को <math>P_j</math> द्वारा दर्शाया जाता है, जहां <math>P_j[i]=p_{ij}</math> यदि आइटम <math>x_i</math> निर्धारित नहीं है (अर्थात् <math>T[i]=-1</math>) और <math>P_j[i]=p_{ij}-p_{ik}</math> यदि आइटम <math>x_i</math> बिन <math>b_k</math> (अर्थात। <math>T[i]=k</math>) पर शेड्यूल किया गया है।
 औपचारिक रूप से:
 : तय करना <math>T[i]=-1 \text{ for } i = 1\ldots n</math>
-: के लिए <math>j=1,\ldots,m</math> करना:
+: <math>j=1,\ldots,m</math> के लिए करना:
-:: बिन का समाधान खोजने के लिए ALG को कॉल करें <math>b_j</math> अवशिष्ट लाभ फ़ंक्शन का उपयोग करना <math>P_j</math>. चयनित वस्तुओं को इससे निरूपित करें <math>S_j</math>.
+:: अवशिष्ट लाभ फलन <math>P_j</math> का उपयोग करके बिन <math>b_j</math> का समाधान खोजने के लिए एएलजी को कॉल करें। चयनित वस्तुओं को <math>S_j</math> का उपयोग करके <math>T</math> को अद्यतन करें, अर्थात, <math>S_j</math>, अर्थात, <math>T[i]=j</math> सभी <math>i \in S_j</math> के लिए।
-:: अद्यतन <math>T</math> का उपयोग करते हुए <math>S_j</math>, अर्थात।, <math>T[i]=j</math> सभी के लिए <math>i \in S_j</math>.
 ==यह भी देखें==
@@ Line 61: / Line 57: @@
 ==अग्रिम पठन==
 {{cite book |isbn=978-3-540-24777-7|title=Knapsack Problems|last1=Kellerer|first1=Hans|last2=Pferschy|first2=Ulrich|last3=Pisinger|first3=David|date=2013-03-19}}
-[[Category: एनपी-पूर्ण समस्याएँ]] [[Category: संयुक्त अनुकूलन]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 errors]]
 [[Category:Created On 11/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:एनपी-पूर्ण समस्याएँ]]
+[[Category:संयुक्त अनुकूलन]]

Anonymous

Search

सामान्यीकृत नियतन समस्या: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:50, 25 August 2023

Contents

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

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

जटिलता

लुब्ध सन्निकटन कलन विधि

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सामान्यीकृत नियतन समस्या: Difference between revisions

Latest revision as of 11:50, 25 August 2023

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

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

जटिलता

लुब्ध सन्निकटन कलन विधि

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories