अशक्त द्वंद्व: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
व्यावहारिक गणित में, '''अशक्त द्वंद्व''' अनुकूलन में एक अवधारणा है जो बताती है कि द्वैत अंतर हमेशा 0 से अधिक या उसके बराबर होता है। इसका तात्पर्य है कि द्वैध (न्यूनतमीकरण) समस्या का समाधान हमेशा संबंधित प्रारंभिक समस्या के समाधान से अधिक या उसके बराबर होता है। यह प्रबल द्वंद्व का विरोध करता है जो केवल कुछ मामलों में ही लागू होता है<ref>{{citation | |||
| last1 = Boţ | first1 = Radu Ioan | | last1 = Boţ | first1 = Radu Ioan | ||
| last2 = Grad | first2 = Sorin-Mihai | | last2 = Grad | first2 = Sorin-Mihai | ||
Line 15: | Line 15: | ||
==उपयोग== | ==उपयोग== | ||
कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम | कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम अशक्त द्वैत के सिद्धांत पर आधारित हैं<ref>{{citation|title=Handbook of Approximation Algorithms and Metaheuristics|first=Teofilo F.|last=Gonzalez|authorlink= Teofilo F. Gonzalez |publisher=CRC Press|year=2007|isbn=9781420010749|page=2{{hyphen}}12<!-- this is not a page range; do not replace the hyphen by a dash-->|url=https://books.google.com/books?id=QK3_VU8ngK8C&pg=SA2-PA12}}.</ref> | ||
== | ==अशक्त द्वैत प्रमेय== | ||
मूल समस्या: | मूल समस्या: | ||
: अधिकतम करें {{math|'''c'''<sup>T</sup>'''x'''}} का विषय है {{math|''A'' '''x''' ≤ '''b''', '''x''' ≥ 0}}; | : अधिकतम करें {{math|'''c'''<sup>T</sup>'''x'''}} का विषय है {{math|''A'' '''x''' ≤ '''b''', '''x''' ≥ 0}}; | ||
द्वैध समस्या, | |||
: | : लघु करना {{math|'''b'''<sup>T</sup>'''y'''}} का विषय है {{math|''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0}}. | ||
अशक्त द्वैत प्रमेय बताता है {{math|'''c'''<sup>T</sup>'''x''' ≤ '''b'''<sup>T</sup>'''y'''}}. | |||
अर्थात्, यदि <math>(x_1,x_2,....,x_n)</math> प्रारंभिक अधिकतमकरण | अर्थात्, यदि <math>(x_1,x_2,....,x_n)</math> प्रारंभिक अधिकतमकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है और <math>(y_1,y_2,....,y_m)</math> दोहरे न्यूनीकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है, तो अशक्त द्वैत प्रमेय को इस प्रकार कहा जा सकता है | ||
<math>\sum_{j=1}^n c_j x_j \leq \sum_{i=1}^m b_i y_i </math>, कहाँ <math> c_j </math> और <math> b_i </math> संबंधित उद्देश्य कार्यों के गुणांक हैं। | |||
{{math| | |||
साक्ष्य:{{math| | |||
'''c'''<sup>T</sup>'''x''' | '''c'''<sup>T</sup>'''x''' | ||
{{=}} '''x'''<sup>T</sup>'''c''' | {{=}} '''x'''<sup>T</sup>'''c''' | ||
Line 38: | Line 38: | ||
===सामान्यीकरण=== | ===सामान्यीकरण=== | ||
अधिक सामान्यतः, यदि <math>x</math> प्रारंभिक अधिकतमीकरण समस्या के लिए एक व्यवहार्य समाधान है और <math>y</math> | अधिक सामान्यतः, यदि <math>x</math> प्रारंभिक अधिकतमीकरण समस्या के लिए एक व्यवहार्य समाधान है और <math>y</math> द्वैध न्यूनतमकरण समस्या के लिए एक व्यवहार्य समाधान है, तो अशक्त द्वैत का तात्पर्य है <math>f(x) \leq g(y)</math> कहाँ <math>f</math> और <math>g</math> क्रमशः प्रारंभिक और द्वैध समस्याओं के लिए वस्तुनिष्ठ कार्य हैं। | ||
==यह भी देखें== | ==यह भी देखें== |
Revision as of 18:36, 25 July 2023
व्यावहारिक गणित में, अशक्त द्वंद्व अनुकूलन में एक अवधारणा है जो बताती है कि द्वैत अंतर हमेशा 0 से अधिक या उसके बराबर होता है। इसका तात्पर्य है कि द्वैध (न्यूनतमीकरण) समस्या का समाधान हमेशा संबंधित प्रारंभिक समस्या के समाधान से अधिक या उसके बराबर होता है। यह प्रबल द्वंद्व का विरोध करता है जो केवल कुछ मामलों में ही लागू होता है[1]
उपयोग
कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम अशक्त द्वैत के सिद्धांत पर आधारित हैं[2]
अशक्त द्वैत प्रमेय
मूल समस्या:
- अधिकतम करें cTx का विषय है A x ≤ b, x ≥ 0;
द्वैध समस्या,
- लघु करना bTy का विषय है ATy ≥ c, y ≥ 0.
अशक्त द्वैत प्रमेय बताता है cTx ≤ bTy.
अर्थात्, यदि प्रारंभिक अधिकतमकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है और दोहरे न्यूनीकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है, तो अशक्त द्वैत प्रमेय को इस प्रकार कहा जा सकता है
, कहाँ और संबंधित उद्देश्य कार्यों के गुणांक हैं।
साक्ष्य: cTx = xTc ≤ xTATy ≤ bTy
सामान्यीकरण
अधिक सामान्यतः, यदि प्रारंभिक अधिकतमीकरण समस्या के लिए एक व्यवहार्य समाधान है और द्वैध न्यूनतमकरण समस्या के लिए एक व्यवहार्य समाधान है, तो अशक्त द्वैत का तात्पर्य है कहाँ और क्रमशः प्रारंभिक और द्वैध समस्याओं के लिए वस्तुनिष्ठ कार्य हैं।
यह भी देखें
- उत्तल अनुकूलन
- अधिकतम-न्यूनतम असमानता
संदर्भ
- ↑ Boţ, Radu Ioan; Grad, Sorin-Mihai; Wanka, Gert (2009), Duality in Vector Optimization, Berlin: Springer-Verlag, p. 1, doi:10.1007/978-3-642-02886-1, ISBN 978-3-642-02885-4, MR 2542013.
- ↑ Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749.