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

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

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

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

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

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

द्वैत रैखिक क्रमादेश का रूप

मान लीजिए कि हमारे पास रैखिक क्रमादेश है:

Ax ≤ b, x ≥ 0 के अधीन c^Tx उच्चतम सीमा तक बढ़ाएं।

हम समाधान पर एक ऊपरी सीमा का निर्माण करना चाहेंगे। इसलिए हम धनात्मक गुणांकों के साथ व्यवरोधों का एक रैखिक संयोजन बनाते हैं, जैसे कि व्यवरोधों में x के गुणांक कम से कम c^T हों। यह रैखिक संयोजन हमें उद्देश्य पर ऊपरी सीमा प्रदान करता है। द्वैत रैखिक क्रमादेश के चर y इस रैखिक संयोजन के गुणांक हैं। द्वैत रैखिक क्रमादेश ऐसे गुणांक पता लगाने का प्रयास करता है जो परिणामी ऊपरी सीमा को कम करता है। यह निम्नलिखित रैखिक क्रमादेश देता है:^ː81-83

स्पष्टीकरण

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

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

फिर, सीमित संप्राप्ति उच्चतम सीमा तक प्राथमिक रैखिक क्रमादेश है:

Ax ≤ b, x ≥ 0 के अधीन c^Tx उच्चतम सीमा तक बढ़ाएं।

अब एक अन्य कारखाने पर विचार करें जिसमें कोई अनिर्मित वस्तु नहीं है, और पूर्व कारखाने से अनिर्मित वस्तु का पूरा भंडारण खरीदना चाहता है। यह $y$ का मूल्य (अनिर्मित वस्तु की एक इकाई $i$ के लिए $y_{i}$) राशि प्रदान करता है। प्रस्ताव को स्वीकार करने के लिए, यह स्थिति होनी चाहिए कि $A^{T}y\geq c$, अन्यथा कारखाना अच्छे उत्पादन के लिए प्रयुक्त अनिर्मित वस्तु को बेचने की तुलना में एक निश्चित उत्पाद का उत्पादन करके अधिक नकदी प्राप्त कर सकती है। यह भी $y\geq 0$ होना चाहिए, क्योंकि कारखाना किसी भी अनिर्मित वस्तु को ऋणात्मक कीमत पर नहीं बेचेगा। फिर, दूसरी कारखाने की अनुकूलन समस्या द्वैत रैखिक क्रमादेश है:

A^Ty ≥ c, y ≥ 0 के अधीन b^Ty को न्यूनतम करें

द्वैत प्रमेय दर्शाता है कि दो रैखिक क्रमादेश समस्याओं के बीच द्वैत अंतर कम से कम शून्य है। आर्थिक रूप से, इसका तात्पर्य यह है कि यदि पहले कारखाने को अनिर्मित वस्तु के पूरे भंडारण को y के प्रति-आइटम मूल्य पर खरीदने का प्रस्ताव दिया जाता है, जैसे ATy ≥ c, y ≥ 0, तो उसे प्रस्ताव स्वीकार करना चाहिए। यह कम से कम उतना ही लाभ प्राप्त करेगा जितना कि यह निर्मित वस्तु का उत्पादन कर सकता है।

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

यह देखने के लिए, विचार करें कि क्या अनिर्मित वस्तु की कीमतें $y\geq 0$ कुछ $i$ के लिए $(A^{T}y)_{i}<c_{i}$होती है। तो कारखाना अधिक अनिर्मित वस्तु का उत्पादन करने के लिए अधिक अनिर्मित वस्तु खरीदें, क्योंकि कीमतें "बहुत कम" हैं। इसके विपरीत, यदि अनिर्मित वस्तु की कीमतें $i$ को संतुष्ट करती हैं, लेकिन $A^{T}y\geq c,y\geq 0$, को कम नहीं करती हैं, तो कारखाना अधिक लाभ प्राप्त करेगा। वस्तु के उत्पादन $y^{*}$की तुलना में अपना अनिर्मित वस्तु बेचना, क्योंकि कीमतें "बहुत अधिक" हैं। समय कीमत $b^{T}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}$
• m व्यवरोधों की एक सूचीː प्रत्येक j व्यवरोध $a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}$ है, जहां $b_{j}$ से पहले का प्रतीक $\geq$ या $\leq$ या $=$ में से एक हो सकता है।

दोहरे रैखिक क्रमादेश का निर्माण निम्नानुसार किया गया है।

• प्रत्येक मौलिक व्यवरोध एक द्वैत चर बन जाती है। तो m चर $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}$ बन जाता है

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

वेक्टर (सदिश) सूत्रीकरण

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

मौलिक	द्वैत	टिप्पणी
Ax ≤ b, x ≥ 0 के अधीन cTx को अधिकतम करें	ATy ≥ c, y ≥ 0 के अधीन bTy को न्यूनतम करें	इसे "सममित" द्वैत समस्या कहा जाता है
Ax ≤ b के अधीन cTx को अधिकतम करें	ATy ≥ c, y ≥ 0 के अधीन bTy को न्यूनतम करें	इसे "असममित" द्वैत समस्या कहा जाता है
Ax ≤ b, x ≥ 0 के अधीन cTx अधिकतम करें	ATy ≥ c के अधीन bTy न्यूनतम करें

द्वैत प्रमेय

नीचे, मान लीजिए कि प्रारंभिक रैखिक क्रमादेश "[व्यवरोध] के अधीन c^Tx को अधिकतम करता है" और द्वैत रैखिक क्रमादेश "[व्यवरोध] के अधीन b^Ty को कम से कम करता है"।

दुर्बल द्वैत

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

• c^Tx

• = x^Tc [क्योंकि यह केवल दो सदिशों का एक अदिश गुणनफल है]
• ≤ x^T(A^Ty) [चूंकि A^Ty ≥ c द्वैत व्यवरोध से, (xTAT)y [साहचर्य द्वारा]
• =(x^TA^T)y [साहचर्य द्वारा]
• = (Ax)^Ty [स्थानान्तरण के गुणों से]
• ≤ b^Ty [चूँकि Ax ≤ b प्राथमिक व्यवरोध द्वारा]

दुर्बल द्वैत का अर्थ है:

max_x c^Tx ≤ min_y b^Ty

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

प्रबल द्वैत

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

max_x c^Tx = min_y b^Ty

प्रबल द्वैत प्रमेय को सिद्ध करना कठिन है; प्रमाण सामान्य रूप से उप-रूटीन के रूप में दुर्बल द्वैत प्रमेय का उपयोग करते हैं।

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

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

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

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

अधिकतम 1

Ax ≤ b, A^Ty ≥ c, c^Tx ≥ b^Ty, x ≥ 0, y ≥ 0 के अधीन

यदि संयुक्त रैखिक क्रमादेश का एक व्यवहार्य समाधान (x, y) है तो दुर्बल द्वैत c^Tx = b^Ty द्वारा प्राप्त है। अतः x को मूल रैखिक क्रमादेश का अधिकतम हल होना चाहिए और y को द्वैत रैखिक क्रमादेश का न्यूनतम हल होना चाहिए। यदि संयुक्त रैखिक क्रमादेश का कोई संभव समाधान नहीं है, तो मूल रैखिक क्रमादेश का भी कोई संभव समाधान नहीं है।

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

• मान t के साथ प्राथमिक रैखिक क्रमादेश के लिए एक व्यवहार्य समाधान दिखाएं; इससे सिद्ध होता है कि इष्टतम कम से कम t है।
• मान t के साथ द्वैत रैखिक क्रमादेश के लिए एक व्यवहार्य समाधान दिखाएं; यह प्रमाणित करता है कि इष्टतम अधिकतम 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}}$

यह देखना आसान है कि प्रारंभिक रैखिक क्रमादेश का अधिकतम मान तब प्राप्त होता है जब 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}$ प्राप्त होता है। इसलिए, दोहरे रैखिक क्रमादेश का उद्देश्य मौलिक रैखिक क्रमादेश के उद्देश्य पर एक ऊपरी सीमा है।

किसान उदाहरण

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

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

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

अधिकतम: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(गेहूं और जौ के उत्पादन से अधिक से अधिक लाभ प्राप्त करना)
यदि:	$x_{1}+x_{2}\leq L$	(उपलब्ध भूमि से अधिक भूमि का उपयोग नहीं कर सकते)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	(उपलब्ध से अधिक उर्वरक का उपयोग नहीं कर सकते)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	(उपलब्ध से अधिक कीटनाशक का उपयोग नहीं कर सकते)
	$x_{1},x_{2}\geq 0$	(गेहूं या जौ की ऋणात्मक मात्रा का उत्पादन नहीं कर सकते हैं)।

आव्यूह रूप में यह बन जाता है:

अधिकतम करें: ${\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 इकाई मान एक योजना बोर्ड द्वारा निर्धारित किए गए हैं। योजना बोर्ड का काम किसान को उसकी प्रत्येक फसल (उत्पादन) के इकाई मूल्य पर गेहूं के लिए S₁ और जौ के लिए S₂ प्रदान करते हुए उत्पादक वस्तु की निर्धारित मात्रा की खरीद की कुल कीमत को कम करना है। यह निम्नलिखित रैखिक क्रमादेश से अनुरूप होता है:

अधिकतम: $L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}$		(उत्पादन के साधनों की कुल कीमत को "उद्देश्य फलन" के रूप में न्यूनतम करें)
यदि	$y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}$	(किसान को अपने गेहूं के लिए S1 से कम नहीं प्राप्त करना चाहिए)
	$y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}$	(किसान को अपने जौ के लिए S2 से कम नहीं प्राप्त करना चाहिए)
	$y_{L},y_{F},y_{P}\geq 0$	(कीमतें ऋणात्मक नहीं हो सकतीं)

आव्यूह रूप में यह बन जाता है:

अधिकतम: ${\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.$

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

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

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

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

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

अव्यवहार्य क्रमादेश

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

• यदि मूल अपरिबद्ध है, तो द्वैत अव्यवहार्य है;
• यदि द्वैत अबाधित है, तो मूल अव्यवहार्य है।

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

अधिकतम: $2x_{1}-x_{2}$
यदि:	$x_{1}-x_{2}\leq 1$
	$-x_{1}+x_{2}\leq -2$
	$x_{1},x_{2}\geq 0.$

अनुप्रयोग

अधिकतम प्रवाह न्यूनतम प्रतिच्छेद प्रमेय प्रबल द्वैत प्रमेय का एक विशेष स्थिति है: प्रवाह अधिकतमकरण मूल रैखिक क्रमादेश है, और प्रतिच्छेद-न्यूनीकरण द्वैत रैखिक क्रमादेश है। अधिकतम प्रवाह न्यूनतम प्रतिच्छेद प्रमेय#रैखिक क्रमादेश सूत्रीकरण देखें।

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

शून्येतर योग खेल के लिए न्यूनाधिक प्रमेय को प्रबल-द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है।

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

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

अधिकतम	$\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}$
यदि	$\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 स्थितियां हैं और सभी चर गैर-ऋणात्मक हैं। हम m + n द्वैत चर y_j और s_i परिभाषित करेंगे। हम पाते हैं:

न्यूनतम	$\sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}$
यदि	$\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$

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

अधिकतम	$\sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}$
यदि	$\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$

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