रैखिक प्रोग्रामिंग समस्याओं में द्वंद्व
रैखिक प्रोग्रामिंग समस्याओं में द्वंद्व!
प्रत्येक रेखीय प्रोग्रामिंग समस्या के लिए, एक ही डेटा को शामिल करने वाली एक विशिष्ट अनूठी समस्या है और यह मूल समस्या का भी वर्णन करती है। मूल समस्या को मौलिक कार्यक्रम कहा जाता है और इसी अनूठी समस्या को दोहरी कार्यक्रम कहा जाता है। दो कार्यक्रम बहुत निकट से संबंधित हैं और दोहरे का इष्टतम समाधान, प्राण और इसके विपरीत के इष्टतम समाधान के बारे में पूरी जानकारी देता है।
इस संपत्ति के विभिन्न उपयोगी पहलू हैं:
(ए) यदि प्राइमल में बड़ी संख्या में अवरोध और छोटी संख्या में चर हैं, तो समस्या को दोहरे में परिवर्तित करके और फिर इसे हल करके गणना को काफी कम किया जा सकता है।
(b) रेखीय प्रोग्रामिंग में द्वैतता आर्थिक प्रकृति के परिणाम तक निश्चित रूप से पहुँचती है। यह प्रबंधकों को कार्रवाई के वैकल्पिक पाठ्यक्रमों और उनके सापेक्ष मूल्यों के बारे में सवालों के जवाब देने में मदद कर सकता है।
(c) दोहरे की गणना प्राण विलयन की सटीकता की जाँच करती है।
(d) लीनियर प्रोग्रामिंग में द्वंद्व दर्शाता है कि प्रत्येक लीनियर प्रोग्राम दो-व्यक्ति शून्य-सम गेम के बराबर है। यह इंगित करता है कि रैखिक प्रोग्रामिंग और गेम के सिद्धांत के बीच काफी करीबी संबंध मौजूद हैं।
1. द्वैध बनाने से प्राइमल कैननिकल फॉर्म में है:
उपरोक्त दो कार्यक्रमों से, निम्नलिखित बिंदु स्पष्ट हैं:
(i) प्राइमल में अधिकतमकरण समस्या दोहरे और इसके विपरीत में न्यूनतमकरण समस्या बन जाती है।
(ii) अधिकतमकरण समस्या में () अड़चनें हैं।
(iii) यदि प्राइमल में एन वेरिएबल्स और एम बाधाएँ हैं, तो ड्यूल में एम वेरिएबल्स और एन बाधाएँ होंगी।
(iv) कांस्टेंट बी 1 बी 2, बी 3 ……… बी बी प्रिमल की बाधाओं में दोहरे के उद्देश्य फ़ंक्शन में दिखाई देते हैं।
(v) प्राण के उद्देश्य फलन में स्थिरांक c 1, c 2, c 3 c n दोहरे की बाधाओं में प्रकट होते हैं।
(vi) दोनों समस्याओं में चर गैर-नकारात्मक हैं।
नीचे और नीचे की ओर प्रिमिल और ड्यूल के अवरोधक रिश्तों को दर्शाया गया है।
उदाहरण 1:
द्वैत को प्राणिक समस्या से बचाते हैं
उपाय:
सबसे पहले ≤ बाधा को -1 से दोनों ओर से गुणा करके int बाधा में परिवर्तित किया जाता है।
उदाहरण 2:
द्वैत को प्राणिक समस्या से बचाते हैं
उपाय:
बता दें कि Y 1, Y 2, V 3 और V 4 संबंधित दोहरे चर हैं, फिर दोहरी समस्या द्वारा दी गई है
चूँकि दोहरी समस्या में प्राण (4 के बजाय 2) की तुलना में बाधाओं की संख्या कम होती है, इसलिए इसे हल करने के लिए कम मेहनत और प्रयास की आवश्यकता होती है। यह इस तथ्य से निम्नानुसार है कि रैखिक प्रोग्रामिंग समस्या में कम्प्यूटेशनल कठिनाई मुख्य रूप से चर की संख्या के बजाय बाधाओं की संख्या से जुड़ी है।
उदाहरण 3:
समस्या की दोहरी रचना
उपाय:
चूंकि दी गई समस्या कम से कम है, सभी बाधाओं को> प्रकार का होना चाहिए। तीसरा कसना गुणा - 1 दोनों तरफ से हम प्राप्त करते हैं।
-8x 1 + 2x 2 + 2x 3 x -10
दी गई समस्या की दोहरी होगी
जहाँ y 1, y 2, y 3, y 4 और y 5 क्रमशः पहले, दूसरे तीसरे, चौथे और पांचवें बाधा से जुड़े दोहरे चर हैं।
