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

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

उपयोग

कई प्रारंभिक-दोहरे सन्निकटन एल्गोरिदम कमजोर द्वैत के सिद्धांत पर आधारित हैं।

कमज़ोर द्वैत प्रमेय

मूल समस्या:

अधिकतम करें c^Tx का विषय है A x ≤ b, x ≥ 0;

दोहरी समस्या,

छोटा करना b^Ty का विषय है A^Ty ≥ c, y ≥ 0.

कमजोर द्वैत प्रमेय बताता है c^Tx ≤ b^Ty.

अर्थात्, यदि $(x_{1},x_{2},....,x_{n})$ प्रारंभिक अधिकतमकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है और $(y_{1},y_{2},....,y_{m})$ दोहरे न्यूनीकरण रैखिक कार्यक्रम के लिए एक व्यवहार्य समाधान है, तो कमजोर द्वैत प्रमेय को इस प्रकार कहा जा सकता है

$\sum _{j=1}^{n}c_{j}x_{j}\leq \sum _{i=1}^{m}b_{i}y_{i}$, कहाँ $c_{j}$ और $b_{i}$ संबंधित उद्देश्य कार्यों के गुणांक हैं।

सबूत: c^Tx = x^Tc ≤ x^TA^Ty ≤ b^Ty

सामान्यीकरण

अधिक सामान्यतः, यदि $x$ प्रारंभिक अधिकतमीकरण समस्या के लिए एक व्यवहार्य समाधान है और $y$ दोहरी न्यूनतमकरण समस्या के लिए एक व्यवहार्य समाधान है, तो कमजोर द्वैत का तात्पर्य है $f(x)\leq g(y)$ कहाँ $f$ और $g$ क्रमशः प्रारंभिक और दोहरी समस्याओं के लिए वस्तुनिष्ठ कार्य हैं।

यह भी देखें

• उत्तल अनुकूलन
• अधिकतम-न्यूनतम असमानता