दोहरी रैखिक कार्यक्रम

किसी दिए गए रैखिक कार्यक्रम (एलपी) का दोहरा एक और एलपी है जो निम्नलिखित योजनाबद्ध तरीके से मूल (प्राइमल) एलपी से प्राप्त होता है:

• मौलिक एलपी में प्रत्येक चर दोहरी एलपी में बाधा बन जाता है;
• मौलिक एलपी में प्रत्येक बाधा दोहरी एलपी में एक चर बन जाती है;
• वस्तुनिष्ठ दिशा व्युत्क्रमित होती है - मूल में अधिकतम द्वैत में न्यूनतम हो जाता है और इसके विपरीत।

कमजोर द्वैत प्रमेय बताता है कि किसी भी व्यवहार्य समाधान पर दोहरे एलपी का उद्देश्य मान हमेशा किसी भी व्यवहार्य समाधान (ऊपरी या निचली सीमा पर निर्भर करता है कि यह एक अधिकतमकरण या न्यूनीकरण समस्या है) पर मूल एलपी के उद्देश्य पर एक बाध्य है। वास्तव में, यह बाउंडिंग प्रॉपर्टी दोहरे और मूल एलपी के इष्टतम मूल्यों के लिए है।

मजबूत द्वैत प्रमेय में कहा गया है कि, इसके अलावा, यदि प्राइमल का एक इष्टतम समाधान है, तो दोहरे का एक इष्टतम समाधान भी है, और दो ऑप्टिमा बराबर हैं। ये प्रमेय द्वैत (अनुकूलन) के एक बड़े वर्ग से संबंधित हैं। मजबूत द्वैत प्रमेय उन मामलों में से एक है जिसमें द्वैत अंतर (प्रारंभिक के इष्टतम और द्वैत के इष्टतम के बीच का अंतर) 0 है।

दोहरी एलपी का रूप

मान लीजिए कि हमारे पास रैखिक कार्यक्रम है: Maximize c^Tx Ax ≤ b, x ≥ 0 के अधीन है। हम समाधान पर ऊपरी सीमा बनाना चाहते हैं। इसलिए हम धनात्मक गुणांकों के साथ व्यवरोधों का एक रैखिक संयोजन बनाते हैं, जैसे कि विवशताओं में x के गुणांक कम से कम c हों^{टी</सुप>. यह रैखिक संयोजन हमें उद्देश्य पर ऊपरी सीमा प्रदान करता है। दोहरे एलपी के चर y इस रैखिक संयोजन के गुणांक हैं। दोहरी एलपी ऐसे गुणांक खोजने की कोशिश करता है जो परिणामी ऊपरी सीमा को कम से कम करते हैं। यह निम्नलिखित एलपी देता है:{{Rp|81–83}छोटा करें bटीवाई ए के अधीन। इस LP को मूल LP का द्वैत कहा जाता है।}

व्याख्या

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

एक कारखाने पर विचार करें जो माल के उत्पादन की योजना बना रहा है। होने देना $x$ इसका प्रोडक्शन शेड्यूल हो (मेक $x_{i}$ अच्छी मात्रा $i$), होने देना $c\geq 0$ बाजार मूल्यों की सूची हो (अच्छे की एक इकाई $i$ के लिए बेच सकते हैं $c_{i}$). इसकी बाधाएं हैं $x\geq 0$ (यह नकारात्मक वस्तुओं का उत्पादन नहीं कर सकता) और कच्चे माल की कमी। होने देना $b$ वह कच्चा माल हो जो उसके पास उपलब्ध है, और रहने दो $A\geq 0$ भौतिक लागतों का मैट्रिक्स बनें (अच्छे की एक इकाई का उत्पादन $i$ आवश्यक है $A_{ji}$ कच्चे माल की इकाइयां $j$).

फिर, विवश राजस्व अधिकतमकरण प्राथमिक एलपी है:Maximize c^Tx Ax ≤ b, x ≥ 0 के अधीन है। अब एक अन्य कारखाने पर विचार करें जिसमें कोई कच्चा माल नहीं है, और पिछले कारखाने से कच्चे माल का पूरा स्टॉक खरीदना चाहता है। यह का मूल्य सदिश प्रदान करता है $y$ (कच्चे माल की एक इकाई $i$ के लिए $y_{i}$). प्रस्ताव को स्वीकार करने के लिए, यह मामला होना चाहिए कि $A^{T}y\geq c$, अन्यथा फ़ैक्टरी अच्छे उत्पादन के लिए प्रयुक्त कच्चे माल को बेचने की तुलना में एक निश्चित उत्पाद का उत्पादन करके अधिक नकदी कमा सकती है। होना भी चाहिए $y\geq 0$, क्योंकि कारखाना किसी भी कच्चे माल को नकारात्मक कीमत पर नहीं बेचेगा। फिर, दूसरी फैक्ट्री की अनुकूलन समस्या दोहरी एलपी है:टीवाई ए के अधीन द्वंद्व प्रमेय बताता है कि दो एलपी समस्याओं के बीच द्वंद्व अंतर कम से कम शून्य है। आर्थिक रूप से, इसका मतलब यह है कि यदि पहले कारखाने को कच्चे माल के पूरे स्टॉक को y के प्रति-आइटम मूल्य पर खरीदने का प्रस्ताव दिया जाता है, जैसे कि ए^टीवाई ≥ सी, वाई ≥ 0, तो इसे प्रस्ताव लेना चाहिए। यह कम से कम उतना ही राजस्व कमाएगा जितना कि यह तैयार माल का उत्पादन कर सकता है।

मजबूत द्वैत प्रमेय आगे बताता है कि द्वैत अंतर शून्य है। मजबूत द्वैत के साथ, द्वैत समाधान $y^{*}$ आर्थिक रूप से बोल रहा हूँ, कच्चे माल के लिए संतुलन मूल्य (छाया मूल्य देखें) जो कि उत्पादन मैट्रिक्स वाला एक कारखाना है $A$ और कच्चे माल का स्टॉक $b$ तैयार माल के बाजार मूल्य को देखते हुए कच्चे माल के लिए स्वीकार करेंगे $c$. (ध्यान दें कि $y^{*}$ अद्वितीय नहीं हो सकता है, इसलिए संतुलन कीमत पूरी तरह से निर्धारित नहीं हो सकती है $A$, $b$, और $c$.)

यह देखने के लिए, कच्चे माल की कीमतों पर विचार करें $y\geq 0$ ऐसे हैं $(A^{T}y)_{i}<c_{i}$ कुछ के लिए $i$, तो कारखाना अधिक अच्छा उत्पादन करने के लिए अधिक कच्चा माल खरीदेगा $i$चूंकि कीमतें बहुत कम हैं। इसके विपरीत, अगर कच्चे माल की कीमतें संतुष्ट हैं $A^{T}y\geq c,y\geq 0$, लेकिन कम नहीं करता $b^{T}y$, तो कारखाने माल का उत्पादन करने की तुलना में अपना कच्चा माल बेचकर अधिक पैसा कमाएंगे, क्योंकि कीमतें बहुत अधिक हैं। संतुलन कीमत पर $y^{*}$कच्चा माल खरीदकर या बेचकर कारखाना अपना लाभ नहीं बढ़ा सकता।

द्वैत प्रमेय की भौतिक व्याख्या भी है।

दोहरी एलपी का निर्माण

सामान्य तौर पर, एक प्राथमिक एलपी दिया गया है, इसके दोहरे एलपी के निर्माण के लिए निम्न एल्गोरिथम का उपयोग किया जा सकता है। प्रारंभिक एलपी द्वारा परिभाषित किया गया है:

• एन चर का एक सेट: $x_{1},\ldots ,x_{n}$.
• प्रत्येक चर के लिए $x_{i}$, एक सांकेतिक बाधा - यह या तो गैर-नकारात्मक होनी चाहिए ($x_{i}\geq 0$), या गैर-सकारात्मक ($x_{i}\leq 0$), या अप्रतिबंधित ($x_{i}\in \mathbb {R}$).
• एक उद्देश्य समारोह: ${\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}$
• एम बाधाओं की एक सूची। प्रत्येक बाधा j है: $a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}$जहां प्रतीक से पहले $b_{j}$ में से एक हो सकता है $\geq$ या $\leq$ या $=$.

दोहरे एलपी का निर्माण निम्नानुसार किया गया है।

• प्रत्येक मौलिक बाधा एक दोहरी चर बन जाती है। तो एम चर हैं: $y_{1},\ldots ,y_{m}$.
• प्रत्येक द्वैत चर का चिह्न अवरोध इसके मौलिक अवरोध के चिह्न के विपरीत है। इसलिए$\geq b_{j}$बन जाता है $y_{j}\leq 0$ और$\leq b_{j}$बन जाता है $y_{j}\geq 0$ और$=b_{j}$बन जाता है $y_{j}\in \mathbb {R}$.
• दोहरा उद्देश्य कार्य है ${\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}$
• प्रत्येक मूल चर एक दोहरी बाधा बन जाता है। तो वहाँ n बाधाएँ हैं। दोहरी बाधा में एक दोहरे चर का गुणांक इसके मौलिक चर का गुणांक इसकी मौलिक बाधा में है। तो प्रत्येक बाधा i है: $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$, जहां प्रतीक से पहले $c_{i}$ प्रारंभिक एलपी में वेरिएबल i पर साइन बाधा के समान है। इसलिए $x_{i}\leq 0$ बन जाता है$\leq c_{i}$और $x_{i}\geq 0$ बन जाता है$\geq c_{i}$और $x_{i}\in \mathbb {R}$ बन जाता है$=c_{i}$.

इस एल्गोरिथम से, यह देखना आसान है कि द्वैत का द्वैत मौलिक है।

वेक्टर फॉर्मूलेशन

यदि सभी बाधाओं का एक ही संकेत है, तो उपरोक्त नुस्खा को मेट्रिसेस और वैक्टर का उपयोग करके कम तरीके से प्रस्तुत करना संभव है। निम्न तालिका विभिन्न प्रकार के प्राइमल्स और द्वैत के बीच के संबंध को दर्शाती है।

Primal	Dual	Note
Maximize cTx subject to Ax ≤ b, x ≥ 0	Minimize bTy subject to ATy ≥ c, y ≥ 0	This is called a "symmetric" dual problem
Maximize cTx subject to Ax ≤ b	Minimize bTy subject to ATy = c, y ≥ 0	This is called an "asymmetric" dual problem
Maximize cTx subject to Ax = b, x ≥ 0	Minimize bTy subject to ATy ≥ c

द्वैत प्रमेय

नीचे, मान लीजिए कि मौलिक एलपी अधिकतम सी है^Tx [बाधाओं] के अधीन है और दोहरी LP न्यूनतम b है^Ty [बाधाओं] के अधीन है।

कमजोर द्वैत

दुर्बल द्वैत प्रमेय कहता है कि, मूल के प्रत्येक सुसंगत हल x और द्वैत के प्रत्येक सुसंगत हल y के लिए: c^टीx ≤ ख^{टी</सुप>य। दूसरे शब्दों में, द्वैत के प्रत्येक संभव समाधान में वस्तुनिष्ठ मूल्य मूल के वस्तुनिष्ठ मूल्य पर एक ऊपरी सीमा है, और मूल के प्रत्येक व्यवहार्य समाधान में वस्तुनिष्ठ मूल्य द्वैत के वस्तुनिष्ठ मूल्य पर निचली सीमा है। यहाँ मूल LP Maximize c के लिए एक प्रमाण दिया गया हैTx Ax ≤ b, x ≥ 0 के अधीन :}

• सी^टीएक्स
• = एक्स^Tc [क्योंकि यह केवल दो सदिशों का एक अदिश गुणनफल है]
• ≤ एक्स^टी(ए^{टी</सुप>वाई) ['ए के बाद सेTy ≥ c दोहरी बाधाओं द्वारा, और x ≥ 0]}
• = (एक्स^{टी</सुप>एटी)y [साहचर्य द्वारा]}
• = (कुल्हाड़ी)^Ty [ट्रांसपोज़ के गुणों द्वारा]
• ≤ बी^Ty [चूँकि Ax ≤ b प्राथमिक बाधाओं द्वारा]

कमजोर द्वैत का अर्थ है:

max_x c^टीx ≤ मि_yबी^Ty

विशेष रूप से, यदि प्राइमल अनबाउंड (ऊपर से) है तो डुअल का कोई व्यवहार्य समाधान नहीं है, और यदि डुअल अनबाउंड (नीचे से) है तो प्राइमल का कोई व्यवहार्य समाधान नहीं है।

प्रबल द्वैत

मजबूत द्वैत प्रमेय कहता है कि यदि दो समस्याओं में से एक का इष्टतम समाधान है, तो दूसरे का भी और कमजोर द्वैत प्रमेय द्वारा दी गई सीमाएं तंग हैं, यानी:

max_x c^टीx = मिनट_yबी^Ty

मजबूत द्वैत प्रमेय को सिद्ध करना कठिन है; सबूत आमतौर पर उप-दिनचर्या के रूप में कमजोर द्वंद्व प्रमेय का उपयोग करते हैं।

एक प्रमाण सिंप्लेक्स एल्गोरिदम का उपयोग करता है और इस प्रमाण पर निर्भर करता है कि, उपयुक्त धुरी नियम के साथ, यह एक सही समाधान प्रदान करता है। प्रमाण यह स्थापित करता है कि, एक बार सिम्प्लेक्स एल्गोरिथम प्राइमल एलपी के समाधान के साथ समाप्त हो जाने पर, अंतिम झांकी से दोहरी एलपी के समाधान को पढ़ना संभव है। इसलिए, सिम्प्लेक्स एल्गोरिथम को चलाकर, हम एक साथ प्राइमल और डुअल दोनों का समाधान प्राप्त करते हैं।

एक अन्य प्रमाण भेड़िया लेम्मा का उपयोग करता है।

सैद्धांतिक निहितार्थ

1. कमजोर द्वैत प्रमेय का अर्थ है कि एक एकल व्यवहार्य समाधान खोजना उतना ही कठिन है जितना कि एक इष्टतम संभव समाधान खोजना। मान लीजिए कि हमारे पास एक ऑरेकल है, जो एक एलपी दिया गया है, एक मनमाना व्यवहार्य समाधान पाता है (यदि कोई मौजूद है)। एलपी अधिकतम 'सी' को देखते हुए^Tx Ax ≤ b, x ≥ 0 के अधीन है, हम इस LP को इसके दोहरे के साथ जोड़कर एक और LP बना सकते हैं। संयुक्त एलपी में चर के रूप में x और y दोनों हैं:

Maximize 1

Ax ≤ b, A के अधीन^{टी</सुप>वाई ≥ सी, सीटीx ≥ खTy, x ≥ 0, y ≥ 0}

यदि संयुक्त LP का एक व्यवहार्य समाधान (x,y) है, तो कमजोर द्वैत द्वारा, c^टीx = ख

टी</सुप>य। अतः x को मूल LP का अधिकतम हल होना चाहिए और y को द्वैत LP का न्यूनतम हल होना चाहिए। यदि संयुक्त एलपी का कोई संभव समाधान नहीं है, तो मूल एलपी का भी कोई संभव समाधान नहीं है।

2. मजबूत द्वैत प्रमेय एक एलपी के इष्टतम मूल्य का एक अच्छा लक्षण वर्णन प्रदान करता है जिसमें यह हमें आसानी से साबित करने की अनुमति देता है कि कुछ मूल्य 'टी' कुछ एलपी का इष्टतम है। प्रमाण दो चरणों में आगे बढ़ता है:

• वैल्यू टी के साथ प्राइमल एलपी के लिए एक व्यवहार्य समाधान दिखाएं; इससे सिद्ध होता है कि इष्टतम कम से कम t है।
• मूल्य टी के साथ दोहरी एलपी के लिए एक व्यवहार्य समाधान दिखाएं; यह साबित करता है कि इष्टतम अधिकतम टी पर है।

उदाहरण

छोटा उदाहरण

प्राथमिक एलपी पर विचार करें, दो चर और एक बाधा के साथ:

${\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}$

उपरोक्त नुस्खा को लागू करने से निम्नलिखित दोहरी एलपी मिलती है, एक चर और दो बाधाओं के साथ:

${\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{subject to }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}$

यह देखना आसान है कि प्रारंभिक LP का अधिकतम मान तब प्राप्त होता है जब x₁ इसकी निचली सीमा (0) और x तक न्यूनतम है₂ बाधा (7/6) के तहत इसकी ऊपरी सीमा तक अधिकतम है। अधिकतम 4· 7/6 = 14/3 है।

इसी प्रकार, दोहरी एलपी का न्यूनतम y होने पर प्राप्त होता है₁ बाधाओं के तहत इसकी निचली सीमा तक न्यूनतम किया जाता है: पहली बाधा 3/5 की निचली सीमा देती है जबकि दूसरी बाधा 4/6 की एक सख्त निचली सीमा देती है, इसलिए वास्तविक निचली सीमा 4/6 और न्यूनतम 7 है · 4/6 = 14/3।

प्रबल द्वैत प्रमेय के अनुसार, मूल का अधिकतम द्वैत के न्यूनतम के बराबर होता है।

हम इस उदाहरण का उपयोग कमजोर द्वैत प्रमेय के प्रमाण को दर्शाने के लिए करते हैं। मान लीजिए कि, मूल एलपी में, हम उद्देश्य पर ऊपरी सीमा प्राप्त करना चाहते हैं $3x_{1}+4x_{2}$. हम बाधा को कुछ गुणांक से गुणा करके उपयोग कर सकते हैं, कहते हैं $y_{1}$. किसी के लिए $y_{1}$ हम पाते हैं: $y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}$. अब अगर $y_{1}\cdot 5x_{1}\geq 3x_{1}$और $y_{1}\cdot 6x_{2}\geq 4x_{2}$, तब $y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}$, इसलिए $7y_{1}\geq 3x_{1}+4x_{2}$. इसलिए, दोहरे एलपी का उद्देश्य मौलिक एलपी के उद्देश्य पर एक ऊपरी सीमा है।

किसान उदाहरण

किसान उदाहरण के लिए चित्रमय समाधान - शर्तों का उल्लंघन करने वाले क्षेत्रों को छायांकित करने के बाद, शेष व्यवहार्य क्षेत्र का शीर्ष मूल से सबसे दूर धराशायी रेखा के साथ इष्टतम संयोजन देता है

एक ऐसे किसान पर विचार करें जो कुछ एल भूमि, एफ उर्वरक और पी कीटनाशक के निर्धारित प्रावधान के साथ गेहूं और जौ उगा सकता है।

एक यूनिट गेहूँ, एक यूनिट ज़मीन उगाने के लिए, $F_{1}$ उर्वरक की इकाइयां और $P_{1}$ कीटनाशी की ईकाइयों का प्रयोग करना चाहिए। इसी प्रकार, जौ की एक इकाई, भूमि की एक इकाई उगाने के लिए, $F_{2}$ उर्वरक की इकाइयां और $P_{2}$ कीटनाशी की ईकाइयों का प्रयोग करना चाहिए।

सबसे बड़ी समस्या यह होगी कि किसान यह तय करेगा कि कितना गेहूँ ($x_{1}$) और जौ ($x_{2}$) बढ़ने के लिए अगर उनके विक्रय मूल्य हैं $S_{1}$ और $S_{2}$ प्रति यूनिट।

Maximize: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(maximize the revenue from producing wheat and barley)
subject to:	$x_{1}+x_{2}\leq L$	(cannot use more land than available)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	(cannot use more fertilizer than available)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	(cannot use more pesticide than available)
	$x_{1},x_{2}\geq 0$	(cannot produce negative quantities of wheat or barley).

मैट्रिक्स रूप में यह बन जाता है:

अधिकतम करें: ${\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$

का विषय है: ${\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.$

दोहरी समस्या के लिए मान लें कि उत्पादन के इन साधनों (इनपुट्स) में से प्रत्येक के लिए y इकाई मूल्य एक योजना बोर्ड द्वारा निर्धारित किए गए हैं। योजना बोर्ड का काम किसान को उसकी प्रत्येक फसल (उत्पादन) के इकाई मूल्य पर एक फ्लोर उपलब्ध कराते हुए निविष्टियों की निर्धारित मात्रा की खरीद की कुल लागत को न्यूनतम करना है।₁ गेहूं के लिए और एस₂ जौ के लिए। यह निम्नलिखित एलपी से मेल खाता है:

Minimize: $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$		(minimize the total cost of the means of production as the "objective function")
subject to:	$y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}$	(the farmer must receive no less than S1 for his wheat)
	$y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}$	(the farmer must receive no less than S2 for his barley)
	$y_{L},y_{F},y_{P}\geq 0$	(prices cannot be negative).

मैट्रिक्स रूप में यह बन जाता है:

छोटा करना: ${\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}$

का विषय है: ${\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.$

प्राथमिक समस्या भौतिक मात्राओं से संबंधित है। सीमित मात्रा में उपलब्ध सभी इनपुट के साथ, और यह मानते हुए कि सभी आउटपुट की इकाई कीमतें ज्ञात हैं, आउटपुट की कितनी मात्रा का उत्पादन करना है ताकि कुल राजस्व को अधिकतम किया जा सके? दोहरी समस्या आर्थिक मूल्यों से संबंधित है। सभी आउटपुट यूनिट कीमतों पर फ्लोर गारंटी के साथ, और यह मानते हुए कि सभी इनपुट की उपलब्ध मात्रा ज्ञात है, कुल खर्च को कम करने के लिए कौन सी इनपुट यूनिट मूल्य निर्धारण योजना निर्धारित की जाए?

प्रारंभिक स्थान में प्रत्येक चर के लिए दोहरी स्थान में संतुष्ट करने के लिए एक असमानता से मेल खाती है, दोनों आउटपुट प्रकार द्वारा अनुक्रमित हैं। प्रारंभिक स्थान में प्रत्येक असमानता को संतुष्ट करने के लिए दोहरे स्थान में एक चर से मेल खाता है, दोनों को इनपुट प्रकार द्वारा अनुक्रमित किया गया है।

मौलिक स्थान में असमानताओं को बाध्य करने वाले गुणांकों का उपयोग इस उदाहरण में दोहरे स्थान, इनपुट मात्रा में उद्देश्य की गणना करने के लिए किया जाता है। मूल स्थान में उद्देश्य की गणना करने के लिए उपयोग किए जाने वाले गुणांक दोहरे स्थान में असमानताओं को बांधते हैं, इस उदाहरण में आउटपुट यूनिट की कीमतें।

प्राथमिक और दोहरी दोनों समस्याएं एक ही मैट्रिक्स का उपयोग करती हैं। प्रारंभिक स्थान में, यह मैट्रिक्स आउटपुट की निर्धारित मात्रा का उत्पादन करने के लिए आवश्यक इनपुट की भौतिक मात्रा की खपत को व्यक्त करता है। दोहरे स्थान में, यह सेट इनपुट यूनिट कीमतों से आउटपुट से जुड़े आर्थिक मूल्यों के निर्माण को व्यक्त करता है।

चूँकि प्रत्येक असमानता को एक समानता और एक सुस्त चर द्वारा प्रतिस्थापित किया जा सकता है, इसका मतलब है कि प्रत्येक प्राथमिक चर एक दोहरे सुस्त चर से मेल खाता है, और प्रत्येक दोहरा चर एक प्राथमिक सुस्त चर से मेल खाता है। यह संबंध हमें पूरक सुस्ती के बारे में बात करने की अनुमति देता है।

अव्यवहार्य कार्यक्रम

एक एलपी असीमित या अव्यवहार्य भी हो सकता है। द्वैत सिद्धांत हमें बताता है कि:

• यदि प्राण अबाध है, तो द्वैत अक्षम्य है;
• यदि द्वैत असीम है, तो प्राण अव्यवहार्य है।

हालाँकि, यह संभव है कि द्वैत और मौलिक दोनों ही अव्यवहार्य हों। यहाँ एक उदाहरण है:

Maximize: $2x_{1}-x_{2}$
Subject to:	$x_{1}-x_{2}\leq 1$
	$-x_{1}+x_{2}\leq -2$
	$x_{1},x_{2}\geq 0.$

अनुप्रयोग

मैक्स-फ्लो मिन-कट प्रमेय मजबूत द्वैत प्रमेय का एक विशेष मामला है: फ्लो-मैक्सिमाइजेशन प्राइमल एलपी है, और कट-मिनिमाइजेशन डुअल एलपी है। मैक्स-फ्लो मिन-कट थ्योरम#लीनियर प्रोग्राम फॉर्म्युलेशन देखें।

ग्राफ से संबंधित अन्य प्रमेयों को मजबूत द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है, विशेष रूप से, कोनिग प्रमेय (ग्राफ सिद्धांत) | कोनिग प्रमेय। जीरो-सम गेम के लिए मिनिमैक्स प्रमेय को मजबूत-द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है।

वैकल्पिक एल्गोरिदम

कभी-कभी, प्रोग्राम मैट्रिक्स को देखे बिना दोहरे प्रोग्राम को प्राप्त करना अधिक सहज हो सकता है। निम्नलिखित रैखिक कार्यक्रम पर विचार करें:

Minimize	$\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}$
subject to	$\sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geq g_{j},$		$1\leq j\leq n$
	$f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geq h_{i},$		$1\leq i\leq m$
	$x_{i}\geq 0,\,t_{j}\geq 0,$		$1\leq i\leq m,1\leq j\leq n$

हमारे पास एम + एन स्थितियां हैं और सभी चर गैर-नकारात्मक हैं। हम m+n दोहरे चर परिभाषित करेंगे: 'y'_j और एस_i. हम पाते हैं:

Minimize	$\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}$
subject to	$\sum _{i=1}^{m}a_{ij}x_{i}\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\geq g_{j}\cdot y_{j},$		$1\leq j\leq n$
	$f_{i}x_{i}\cdot s_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i},$		$1\leq i\leq m$
	$x_{i}\geq 0,\,t_{j}\geq 0,$		$1\leq i\leq m,1\leq j\leq n$
	$y_{j}\geq 0,\,s_{i}\geq 0,$		$1\leq j\leq n,1\leq i\leq m$

चूंकि यह एक न्यूनीकरण समस्या है, हम एक दोहरा कार्यक्रम प्राप्त करना चाहेंगे जो कि मूल की निचली सीमा है। दूसरे शब्दों में, हम चाहते हैं कि बाधाओं के सभी दाहिने हाथ का योग इस शर्त के तहत अधिकतम हो कि प्रत्येक मूल चर के लिए इसके गुणांकों का योग रैखिक फलन में इसके गुणांक से अधिक न हो। उदाहरण के लिए, एक्स₁ n + 1 बाधाओं में प्रकट होता है। यदि हम इसके व्यवरोधों के गुणांकों का योग करते हैं तो हमें a मिलता है_1,1y₁+ ए_1,2y₂+ ... + ए_1,;;n;;y_n+ च₁s₁. यह राशि अधिकतम सी होनी चाहिए₁. परिणामस्वरूप, हमें मिलता है:

Maximize	$\sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}$
subject to	$\sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leq c_{i},$		$1\leq i\leq m$
	$e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leq d_{j},$		$1\leq j\leq n$
	$y_{j}\geq 0,\,s_{i}\geq 0,$		$1\leq j\leq n,1\leq i\leq m$

ध्यान दें कि हम अपने गणना चरणों में मानते हैं कि कार्यक्रम मानक रूप में है। हालाँकि, किसी भी रेखीय कार्यक्रम को मानक रूप में बदला जा सकता है और इसलिए यह एक सीमित कारक नहीं है।

संदर्भ