अशक्त द्वंद्व: Difference between revisions
(Created page with "अनुप्रयुक्त गणित में, कमजोर द्वैत अनुकूलन में एक अवधारणा है जो बत...") |
m (Deepak moved page कमजोर द्वैत to अशक्त द्वैत without leaving a redirect) |
(No difference)
|
Revision as of 16:09, 14 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.