अशक्त द्वंद्व: Difference between revisions
No edit summary |
m (added Category:Vigyan Ready using HotCat) |
||
Line 49: | Line 49: | ||
[[Category: Machine Translated Page]] | [[Category: Machine Translated Page]] | ||
[[Category:Created On 07/07/2023]] | [[Category:Created On 07/07/2023]] | ||
[[Category:Vigyan Ready]] |
Revision as of 17:12, 4 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.