अशक्त द्वंद्व

From Vigyanwiki
Revision as of 11:21, 7 August 2023 by Manidh (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

व्यावहारिक गणित में, अशक्त द्वंद्व अनुकूलन में एक अवधारणा है जो बताती है कि द्वंद्व अंतर हमेशा 0 से अधिक या उसके बराबर होता है। इसका तात्पर्य है कि द्वंद्व (न्यूनतमीकरण) समस्या का समाधान हमेशा संबंधित प्रारंभिक समस्या के समाधान से अधिक या उसके बराबर होता है। यह प्रबल द्वंद्व का विरोध करता है जो केवल कुछ मामलों में ही लागू होता है[1]

उपयोग

कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम अशक्त द्वंद्व के सिद्धांत पर आधारित हैं[2]

अशक्त द्वंद्व प्रमेय

मूल समस्या:

अधिकतम करें cTx का विषय है A xb, x ≥ 0;

द्वंद्व समस्या,

लघु करना bTy का विषय है ATyc, y ≥ 0.

अशक्त द्वंद्व प्रमेय बताता है cTxbTy.

अर्थात्, यदि प्रारंभिक अधिकतमकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है और दोहरे न्यूनीकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है, तो अशक्त द्वंद्व प्रमेय को इस प्रकार कहा जा सकता है

, जहाँ और संबंधित उद्देश्य कार्यों के गुणांक हैं।

साक्ष्य: cTx = xTcxTATybTy

सामान्यीकरण

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

यह भी देखें

संदर्भ

  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.