अशक्त द्वंद्व: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (4 intermediate revisions by 3 users not shown) | |||
| 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 12: | Line 12: | ||
| url = https://books.google.com/books?id=nwB0qExrF00C&pg=PA1 | | url = https://books.google.com/books?id=nwB0qExrF00C&pg=PA1 | ||
| year = 2009}}.</ref> | | year = 2009}}.</ref> | ||
==उपयोग== | ==उपयोग== | ||
कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम अशक्त | कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम अशक्त द्वंद्व के सिद्धांत पर आधारित हैं<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|'''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>(y_1,y_2,....,y_m)</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>\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| | ||
| Line 38: | Line 35: | ||
===सामान्यीकरण=== | ===सामान्यीकरण=== | ||
अधिक सामान्यतः, यदि <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> क्रमशः प्रारंभिक और द्वंद्व समस्याओं के लिए वस्तुनिष्ठ कार्य हैं। | ||
==यह भी देखें== | ==यह भी देखें== | ||
| Line 46: | Line 43: | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
[[Category:Created On 07/07/2023]] | [[Category:Created On 07/07/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:उत्तल अनुकूलन]] | |||
[[Category:रैखिक प्रोग्रामिंग]] | |||
Latest revision as of 11:21, 7 August 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.
