अशक्त द्वंद्व: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
अनुप्रयुक्त गणित में, कमजोर द्वैत [[अनुकूलन]] में एक अवधारणा है जो बताती है कि द्वंद्व का अंतर हमेशा 0 से अधिक या उसके बराबर होता है। इसका मतलब है कि दोहरी (न्यूनतम) समस्या का समाधान 'हमेशा' समाधान से बड़ा या उसके बराबर होता है। किसी संबद्ध [[मौलिक समस्या]] के लिए है । यह मजबूत द्वंद्व का विरोध करता है जो केवल कुछ मामलों में ही लागू होता है।<ref>{{citation
व्यावहारिक गणित में, '''अशक्त द्वंद्व''' अनुकूलन में एक अवधारणा है जो बताती है कि द्वैत अंतर हमेशा 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>
कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम अशक्त द्वैत के सिद्धांत पर आधारित हैं<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|'''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> c_j </math> और <math> b_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|
'''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>f(x) \leq g(y)</math> कहाँ <math>f</math> और <math>g</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

सामान्यीकरण

अधिक सामान्यतः, यदि प्रारंभिक अधिकतमीकरण समस्या के लिए एक व्यवहार्य समाधान है और द्वैध न्यूनतमकरण समस्या के लिए एक व्यवहार्य समाधान है, तो अशक्त द्वैत का तात्पर्य है कहाँ और क्रमशः प्रारंभिक और द्वैध समस्याओं के लिए वस्तुनिष्ठ कार्य हैं।

यह भी देखें

संदर्भ

  1. ↑ 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.
  2. ↑ Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अशक्त_द्वंद्व&oldid=237474’