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

व्यावहारिक गणित में, अशक्त द्वंद्व अनुकूलन में एक अवधारणा है जो बताती है कि द्वंद्व अंतर हमेशा 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$ क्रमशः प्रारंभिक और द्वंद्व समस्याओं के लिए वस्तुनिष्ठ कार्य हैं।

यह भी देखें

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