दोहरी रैखिक कार्यक्रम: Difference between revisions

Latest revision as of 17:05, 25 May 2023

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

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

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

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

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

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

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

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

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

स्पष्टीकरण

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

ऐसे कारखाने पर विचार करें जो अपने समान के उत्पादन की योजना बना रहा है। मान लीजिए $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$ , पर, कारखाना अनिर्मित वस्तु खरीदकर या बेचकर कारखाना अपना लाभ नहीं बढ़ा सकता।

द्वैत प्रमेय की भौतिक व्याख्या भी है।^[1]^: 86–87

द्वैत रैखिक क्रमादेश का निर्माण

सामान्य रूप से, प्राथमिक रैखिक क्रमादेश दिया गया है, इसके द्वैत रैखिक क्रमादेश के निर्माण के लिए निम्न एल्गोरिथम का उपयोग किया जा सकता है।^[1]^: 85 प्रारंभिक रैखिक क्रमादेश द्वारा परिभाषित किया गया है:

चर का एक समुच्चय: $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 के अधीन c^Tx को अधिकतम करें	A^Ty ≥ c, y ≥ 0 के अधीन b^Ty को न्यूनतम करें	इसे "सममित" द्वैत समस्या कहा जाता है
Ax ≤ b के अधीन c^Tx को अधिकतम करें	A^Ty ≥ c, y ≥ 0 के अधीन b^Ty को न्यूनतम करें	इसे "असममित" द्वैत समस्या कहा जाता है
Ax ≤ b, x ≥ 0 के अधीन c^Tx अधिकतम करें	A^Ty ≥ c के अधीन b^Ty न्यूनतम करें

द्वैत प्रमेय

नीचे, मान लीजिए कि प्रारंभिक रैखिक क्रमादेश "[व्यवरोध] के अधीन 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]^: 87–89

एक अन्य प्रमाण फ़र्कस लेम्मा का उपयोग करता है।^[1]^: 94

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

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' कुछ रैखिक क्रमादेश का इष्टतम है। प्रमाण दो चरणों में आगे बढ़ता है:^[5]^{: 260–261}

मान 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}$	(किसान को अपने गेहूं के लिए S₁ से कम नहीं प्राप्त करना चाहिए)
	$y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}$	(किसान को अपने जौ के लिए S₂ से कम नहीं प्राप्त करना चाहिए)
	$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.$

अनुप्रयोग

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

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

शून्येतर योग खेल के लिए न्यूनाधिक प्रमेय को प्रबल-द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है।^[1]^: sub.8.1

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

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

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

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

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. Pages 81–104.
↑ https://en.wikipedia.org/wiki/Dual_linear_program#:~:text=the%20following%20LP-,%3A%5B1%5D,-%3A%E2%80%8A81%E2%80%9383
↑ Sakarovitch, Michel (1983), "Complements on Duality: Economic Interpretation of Dual Variables", Springer Texts in Electrical Engineering, New York, NY: Springer New York, pp. 142–155, ISBN 978-0-387-90829-8, retrieved 2022-12-23
↑ Dorfman, Robert (1987). रैखिक प्रोग्रामिंग और आर्थिक विश्लेषण. Paul A. Samuelson, Robert M. Solow. New York: Dover Publications. ISBN 0-486-65491-5. OCLC 16577541.
↑ Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
↑ A. A. Ahmadi (2016). "Lecture 6: linear programming and matching" (PDF). Princeton University.

[gm06-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. Pages 81–104.

[2] ttps://en.wikipedia.org/wiki/Dual_linear_program#:~:text=the%20following%20LP-,%3A%5B1%5D,-%3A%E2%80%8A81%E2%80%9383

[3] Sakarovitch, Michel (1983), "Complements on Duality: Economic Interpretation of Dual Variables", Springer Texts in Electrical Engineering, New York, NY: Springer New York, pp. 142–155, ISBN 978-0-387-90829-8, retrieved 2022-12-23

[4] Dorfman, Robert (1987). रैखिक प्रोग्रामिंग और आर्थिक विश्लेषण. Paul A. Samuelson, Robert M. Solow. New York: Dover Publications. ISBN 0-486-65491-5. OCLC 16577541.

[lp-5] Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[6] A. A. Ahmadi (2016). "Lecture 6: linear programming and matching" (PDF). Princeton University.

[1]

[2]

[3]

[4]

[5]

[6]

Anonymous

Search

दोहरी रैखिक कार्यक्रम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:05, 25 May 2023

Contents

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

स्पष्टीकरण

द्वैत रैखिक क्रमादेश का निर्माण

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

द्वैत प्रमेय

दुर्बल द्वैत

प्रबल द्वैत

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

उदाहरण

छोटा उदाहरण

किसान उदाहरण

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

अनुप्रयोग

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{Short description|Mathematical optimization concept}}
-किसी दिए गए [[ रैखिक कार्यक्रम ]] (एलपी) का दोहरा एक और एलपी है जो निम्नलिखित योजनाबद्ध तरीके से मूल (प्राइमल) एलपी से प्राप्त होता है:
+किसी दिए गए रैखिक क्रमादेश (एलपी) का '''द्वैत''' एक अन्य रैखिक क्रमादेश है जो निम्नलिखित योजनाबद्ध तरीके से '''मूल (प्राइमल)''' रैखिक क्रमादेश से प्राप्त होता है:
-* मौलिक एलपी में प्रत्येक चर दोहरी एलपी में बाधा बन जाता है;
+* मौलिक रैखिक क्रमादेश में प्रत्येक चर द्वैत रैखिक क्रमादेश में व्यवरोध बन जाता है;
-* मौलिक एलपी में प्रत्येक बाधा दोहरी एलपी में एक चर बन जाती है;
+* मौलिक रैखिक क्रमादेश में प्रत्येक व्यवरोध द्वैत रैखिक क्रमादेश में एक चर बन जाता है;
-* वस्तुनिष्ठ दिशा व्युत्क्रमित होती है - मूल में अधिकतम द्वैत में न्यूनतम हो जाता है और इसके विपरीत।
+* वस्तुनिष्ठ दिशा व्युत्क्रमित होती है - प्रारंभिक में अधिकतम द्वैत और इसके विपरीत में न्यूनतम हो जाता है।
-कमजोर द्वैत प्रमेय बताता है कि किसी भी व्यवहार्य समाधान पर दोहरे एलपी का उद्देश्य मान हमेशा किसी भी व्यवहार्य समाधान (ऊपरी या निचली सीमा पर निर्भर करता है कि यह एक अधिकतमकरण या न्यूनीकरण समस्या है) पर मूल एलपी के उद्देश्य पर एक बाध्य है। वास्तव में, यह बाउंडिंग प्रॉपर्टी दोहरे और मूल एलपी के इष्टतम मूल्यों के लिए है।
+दुर्बल द्वैत प्रमेय बताता है कि किसी भी व्यवहार्य समाधान पर दोहरे रैखिक क्रमादेश का उद्देश्य मान सदैव किसी भी व्यवहार्य समाधान (ऊपरी या निचली सीमा पर निर्भर करता है कि यह एक उच्चतम सीमा तक या न्यूनीकरण समस्या है) पर मूल रैखिक क्रमादेश के उद्देश्य पर सीमित है। वास्तव में, यह परिसीमन गुण दोहरे और मौलिक रैखिक क्रमादेश के इष्टतम मानो के लिए है।
-मजबूत द्वैत प्रमेय में कहा गया है कि, इसके अलावा, यदि प्राइमल का एक इष्टतम समाधान है, तो दोहरे का एक इष्टतम समाधान भी है, ''और दो ऑप्टिमा बराबर हैं''।<ref name="gm06">{{Cite Gartner Matousek 2006}} Pages 81–104.</ref>
+प्रबल द्वैत प्रमेय में कहा गया है कि, इसके अतिरिक्त, यदि मूल का एक इष्टतम समाधान है, तो द्वैत का एक इष्टतम समाधान भी है, और दो ऑप्टिमा ( इष्टतम) समान होती हैं।<ref name="gm06">{{Cite Gartner Matousek 2006}} Pages 81–104.</ref>
-ये प्रमेय [[द्वैत (अनुकूलन)]] के एक बड़े वर्ग से संबंधित हैं। मजबूत द्वैत प्रमेय उन मामलों में से एक है जिसमें द्वैत अंतर (प्रारंभिक के इष्टतम और द्वैत के इष्टतम के बीच का अंतर) 0 है।
-== दोहरी एलपी का रूप ==
+ये प्रमेय [[द्वैत (अनुकूलन)]] के एक बड़े वर्ग से संबंधित हैं। प्रबल द्वैत प्रमेय उन स्थितियों में से एक है जिसमें द्वैत अंतर (प्रारंभिक के इष्टतम और द्वैत के इष्टतम के बीच का अंतर) 0 होता है।
-मान लीजिए कि हमारे पास रैखिक कार्यक्रम है: <blockquote>Maximize c<sup>T</sup>x ''A''x ≤ b, x ≥ 0 के अधीन है। </blockquote>हम समाधान पर ऊपरी सीमा बनाना चाहते हैं। इसलिए हम धनात्मक गुणांकों के साथ व्यवरोधों का एक रैखिक संयोजन बनाते हैं, जैसे कि विवशताओं में x के गुणांक कम से कम c हों<sup>टी</सुप>. यह रैखिक संयोजन हमें उद्देश्य पर ऊपरी सीमा प्रदान करता है। दोहरे एलपी के चर y इस रैखिक संयोजन के गुणांक हैं। दोहरी एलपी ऐसे गुणांक खोजने की कोशिश करता है जो परिणामी ऊपरी सीमा को '' कम से कम '' करते हैं। यह निम्नलिखित एलपी देता है:<ref name="gm06" />{{Rp|81–83}<blockquote>छोटा करें b<sup>टी</sup>वाई ''ए'' के अधीन<sup>T</sup>y ≥ c, y ≥ 0 </blockquote> इस LP को मूल LP का ''द्वैत'' कहा जाता है।
-=== व्याख्या ===
+== द्वैत रैखिक क्रमादेश का रूप ==
-द्वैत प्रमेय की आर्थिक व्याख्या है।<ref>{{Citation |last=Sakarovitch |first=Michel |title=Complements on Duality: Economic Interpretation of Dual Variables |date=1983 |url=http://dx.doi.org/10.1007/978-1-4757-4106-3_9 |work=Springer Texts in Electrical Engineering |pages=142–155 |place=New York, NY |publisher=Springer New York |isbn=978-0-387-90829-8 |access-date=2022-12-23}}</ref><ref>{{Cite book |last=Dorfman |first=Robert |url=https://www.worldcat.org/oclc/16577541 |title=रैखिक प्रोग्रामिंग और आर्थिक विश्लेषण|date=1987 |publisher=Dover Publications |others=Paul A. Samuelson, Robert M. Solow |isbn=0-486-65491-5 |location=New York |oclc=16577541}}</ref> यदि हम प्रारंभिक एलपी को शास्त्रीय संसाधन आवंटन समस्या के रूप में समझते हैं, तो इसकी दोहरी एलपी को संसाधन मूल्यांकन समस्या के रूप में व्याख्या किया जा सकता है।
+मान लीजिए कि हमारे पास रैखिक क्रमादेश है:
-एक कारखाने पर विचार करें जो माल के उत्पादन की योजना बना रहा है। होने देना <math>x</math> इसका प्रोडक्शन शेड्यूल हो (मेक <math>x_i</math> अच्छी मात्रा <math>i</math>), होने देना <math>c \geq 0</math> बाजार मूल्यों की सूची हो (अच्छे की एक इकाई <math>i</math> के लिए बेच सकते हैं <math>c_i</math>). इसकी बाधाएं हैं <math>x \geq 0</math> (यह नकारात्मक वस्तुओं का उत्पादन नहीं कर सकता) और कच्चे माल की कमी। होने देना <math>b</math> वह कच्चा माल हो जो उसके पास उपलब्ध है, और रहने दो <math>A\geq 0</math> भौतिक लागतों का मैट्रिक्स बनें (अच्छे की एक इकाई का उत्पादन <math>i</math> आवश्यक है <math>A_{ji}</math> कच्चे माल की इकाइयां <math>j</math>).
+''A'''''x''' ≤ '''b''', '''x''' ≥ 0 के अधीन '''c'''<sup>T</sup>'''x''' उच्चतम सीमा तक बढ़ाएं।
-फिर, विवश राजस्व अधिकतमकरण प्राथमिक एलपी है:<blockquote>Maximize c<sup>T</sup>x ''A''x ≤ b, x ≥ 0 के अधीन है। </blockquote>अब एक अन्य कारखाने पर विचार करें जिसमें कोई कच्चा माल नहीं है, और पिछले कारखाने से कच्चे माल का पूरा स्टॉक खरीदना चाहता है। यह का मूल्य सदिश प्रदान करता है <math>y</math> (कच्चे माल की एक इकाई <math>i</math> के लिए <math>y_i</math>). प्रस्ताव को स्वीकार करने के लिए, यह मामला होना चाहिए कि <math>A^T y \geq c</math>, अन्यथा फ़ैक्टरी अच्छे उत्पादन के लिए प्रयुक्त कच्चे माल को बेचने की तुलना में एक निश्चित उत्पाद का उत्पादन करके अधिक नकदी कमा सकती है। होना भी चाहिए <math>y \geq 0</math>, क्योंकि कारखाना किसी भी कच्चे माल को नकारात्मक कीमत पर नहीं बेचेगा। फिर, दूसरी फैक्ट्री की अनुकूलन समस्या दोहरी एलपी है:<blockquote>Minimize b<sup>टी</sup>वाई ''ए'' के अधीन<sup>T</sup>y ≥ c, y ≥ 0</blockquote>द्वंद्व प्रमेय बताता है कि दो एलपी समस्याओं के बीच द्वंद्व अंतर कम से कम शून्य है। आर्थिक रूप से, इसका मतलब यह है कि यदि पहले कारखाने को कच्चे माल के पूरे स्टॉक को y के प्रति-आइटम मूल्य पर खरीदने का प्रस्ताव दिया जाता है, जैसे कि ''ए''<sup>टी</sup>वाई ≥ सी, वाई ≥ 0, तो इसे प्रस्ताव लेना चाहिए। यह कम से कम उतना ही राजस्व कमाएगा जितना कि यह तैयार माल का उत्पादन कर सकता है।
+हम समाधान पर एक ऊपरी सीमा का निर्माण करना चाहेंगे। इसलिए हम धनात्मक गुणांकों के साथ व्यवरोधों का एक रैखिक संयोजन बनाते हैं, जैसे कि व्यवरोधों में '''x''' के गुणांक कम से कम '''c'''<sup>T</sup> हों। यह रैखिक संयोजन हमें उद्देश्य पर ऊपरी सीमा प्रदान करता है। द्वैत रैखिक क्रमादेश के चर y इस रैखिक संयोजन के गुणांक हैं। द्वैत रैखिक क्रमादेश ऐसे गुणांक पता लगाने का प्रयास करता है जो परिणामी ऊपरी सीमा को कम करता है। यह निम्नलिखित रैखिक क्रमादेश देता है:<ref>https://en.wikipedia.org/wiki/Dual_linear_program#:~:text=the%20following%20LP-,%3A%5B1%5D,-%3A%E2%80%8A81%E2%80%9383</ref><sup>ː81-83</sup>
-मजबूत द्वैत प्रमेय आगे बताता है कि द्वैत अंतर शून्य है। मजबूत द्वैत के साथ, द्वैत समाधान <math>y^*</math> आर्थिक रूप से बोल रहा हूँ, कच्चे माल के लिए संतुलन मूल्य (छाया मूल्य देखें) जो कि उत्पादन मैट्रिक्स वाला एक कारखाना है <math>A</math> और कच्चे माल का स्टॉक <math>b</math> तैयार माल के बाजार मूल्य को देखते हुए कच्चे माल के लिए स्वीकार करेंगे <math>c</math>. (ध्यान दें कि <math>y^*</math> अद्वितीय नहीं हो सकता है, इसलिए संतुलन कीमत पूरी तरह से निर्धारित नहीं हो सकती है <math>A</math>, <math>b</math>, और <math>c</math>.)
+=== स्पष्टीकरण ===
+द्वैत प्रमेय की आर्थिक व्याख्या है।<ref>{{Citation |last=Sakarovitch |first=Michel |title=Complements on Duality: Economic Interpretation of Dual Variables |date=1983 |url=http://dx.doi.org/10.1007/978-1-4757-4106-3_9 |work=Springer Texts in Electrical Engineering |pages=142–155 |place=New York, NY |publisher=Springer New York |isbn=978-0-387-90829-8 |access-date=2022-12-23}}</ref><ref>{{Cite book |last=Dorfman |first=Robert |url=https://www.worldcat.org/oclc/16577541 |title=रैखिक प्रोग्रामिंग और आर्थिक विश्लेषण|date=1987 |publisher=Dover Publications |others=Paul A. Samuelson, Robert M. Solow |isbn=0-486-65491-5 |location=New York |oclc=16577541}}</ref> यदि हम प्रारंभिक रैखिक क्रमादेश को उत्कृष्ट <nowiki>''संसाधन नियतन समस्या'' के रूप में समझते हैं, तो इसकी द्वैत रैखिक क्रमादेश को ''संसाधन मूल्यांकन समस्या''</nowiki> के रूप में व्याख्या किया जा सकता है।
-यह देखने के लिए, कच्चे माल की कीमतों पर विचार करें <math>y \geq 0</math> ऐसे हैं <math>(A^Ty)_i < c_i</math> कुछ के लिए <math>i</math>, तो कारखाना अधिक अच्छा उत्पादन करने के लिए अधिक कच्चा माल खरीदेगा <math>i</math>चूंकि कीमतें बहुत कम हैं। इसके विपरीत, अगर कच्चे माल की कीमतें संतुष्ट हैं <math>A^Ty \geq c, y\geq 0</math>, लेकिन कम नहीं करता <math>b^T y</math>, तो कारखाने माल का उत्पादन करने की तुलना में अपना कच्चा माल बेचकर अधिक पैसा कमाएंगे, क्योंकि कीमतें बहुत अधिक हैं। संतुलन कीमत पर <math>y^*</math>कच्चा माल खरीदकर या बेचकर कारखाना अपना लाभ नहीं बढ़ा सकता।
+ऐसे कारखाने पर विचार करें जो अपने समान के उत्पादन की योजना बना रहा है। मान लीजिए <math>x</math> इसकी उत्पादन ( <math>x_i</math>को वस्तु <math>i</math> की मात्रा बनाइए) समय-सारणी है, मान लीजिए <math>c \geq 0</math> विक्रय मानो (वस्तु की एक इकाई <math>i</math> जिसे <math>c_i</math> मे विक्रय कर सकते है) की सूची हो। इसका व्यवरोध <math>x \geq 0</math> है। यह ऋणात्मक वस्तुओं का उत्पादन नहीं कर सकता और अनिर्मित वस्तु की कमी हैं। मान लीजिए कि <math>b</math> वह अनिर्मित वस्तु हो जो उसके पास उपलब्ध है, और मन लीजिए <math>A\geq 0</math> को भौतिक कीमतों का मैट्रिक्स (आव्यूह) हो वस्तु <math>i</math> की एक इकाई का उत्पादन करने के लिए अनिर्मित वस्तु <math>j</math> की <math>A_{ji}</math> इकाइयों की आवश्यकता होती है।
+फिर, सीमित संप्राप्ति उच्चतम सीमा तक प्राथमिक रैखिक क्रमादेश है:
+''A'''''x''' ≤ '''b''', '''x''' ≥ 0 के अधीन '''c'''<sup>T</sup>'''x''' उच्चतम सीमा तक बढ़ाएं।
+अब एक अन्य कारखाने पर विचार करें जिसमें कोई अनिर्मित वस्तु नहीं है, और पूर्व कारखाने से अनिर्मित वस्तु का पूरा भंडारण खरीदना चाहता है। यह <math>y</math> का मूल्य (अनिर्मित वस्तु की एक इकाई <math>i</math> के लिए <math>y_i</math>) राशि प्रदान करता है। प्रस्ताव को स्वीकार करने के लिए, यह स्थिति होनी चाहिए कि <math>A^T y \geq c</math>, अन्यथा कारखाना अच्छे उत्पादन के लिए प्रयुक्त अनिर्मित वस्तु को बेचने की तुलना में एक निश्चित उत्पाद का उत्पादन करके अधिक नकदी प्राप्त कर सकती है। यह भी <math>y \geq 0</math> होना चाहिए, क्योंकि कारखाना किसी भी अनिर्मित वस्तु को ऋणात्मक कीमत पर नहीं बेचेगा। फिर, दूसरी कारखाने की अनुकूलन समस्या द्वैत रैखिक क्रमादेश है:
+''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0 के अधीन '''b'''<sup>T</sup>'''y''' को न्यूनतम करें
+द्वैत प्रमेय दर्शाता है कि दो रैखिक क्रमादेश समस्याओं के बीच द्वैत अंतर कम से कम शून्य है। आर्थिक रूप से, इसका तात्पर्य यह है कि यदि पहले कारखाने को अनिर्मित वस्तु के पूरे भंडारण को y के प्रति-आइटम मूल्य पर खरीदने का प्रस्ताव दिया जाता है, जैसे ATy ≥ c, y ≥ 0, तो उसे प्रस्ताव स्वीकार करना चाहिए। यह कम से कम उतना ही लाभ प्राप्त करेगा जितना कि यह निर्मित वस्तु का उत्पादन कर सकता है।
+प्रबल द्वैत प्रमेय आगे बताता है कि द्वैत अंतर शून्य है। प्रबल द्वैत के साथ, द्वैत समाधान <math>y^*</math> आर्थिक रूप से अनिर्मित वस्तु के लिए "साम्य कीमत" (कल्पित कीमत देखें) है, जो उत्पादन आव्यूह <math>A</math> और अनिर्मित वस्तु के भंडारण <math>b</math> के साथ एक कारखाना अनिर्मित वस्तु के लिए स्वीकार करेंगे निर्मित वस्तु <math>c</math> के लिए विक्रय कीमत दी गई है। ध्यान दें कि <math>y^*</math> अद्वितीय नहीं हो सकता है, इसलिए समय कीमत पूरी तरह से <math>A</math>, <math>b</math>, और <math>c</math> द्वारा निर्धारित नहीं की जा सकती है।
+यह देखने के लिए, विचार करें कि क्या अनिर्मित वस्तु की कीमतें <math>y \geq 0</math> कुछ <math>i</math> के लिए <math>(A^Ty)_i < c_i</math>होती है। तो कारखाना अधिक अनिर्मित वस्तु का उत्पादन करने के लिए अधिक अनिर्मित वस्तु खरीदें, क्योंकि कीमतें "बहुत कम" हैं। इसके विपरीत, यदि अनिर्मित वस्तु की कीमतें <math>i</math> को संतुष्ट करती हैं, लेकिन <math>A^Ty \geq c, y\geq 0</math>, को कम नहीं करती हैं, तो कारखाना अधिक लाभ प्राप्त करेगा। वस्तु के उत्पादन <math>y^*</math>की तुलना में अपना अनिर्मित वस्तु बेचना, क्योंकि कीमतें "बहुत अधिक" हैं। समय कीमत <math>b^T y</math>, पर, कारखाना अनिर्मित वस्तु खरीदकर या बेचकर कारखाना अपना लाभ नहीं बढ़ा सकता।
 द्वैत प्रमेय की भौतिक व्याख्या भी है।<ref name="gm06" />{{Rp|86–87}}
-== दोहरी एलपी का निर्माण ==
-सामान्य तौर पर, एक प्राथमिक एलपी दिया गया है, इसके दोहरे एलपी के निर्माण के लिए निम्न एल्गोरिथम का उपयोग किया जा सकता है।<ref name="gm06" />{{Rp|85}} प्रारंभिक एलपी द्वारा परिभाषित किया गया है:
-* एन चर का एक सेट:       <math>x_1 ,\ldots, x_n</math>.
-* प्रत्येक चर के लिए <math>x_i</math>, एक सांकेतिक बाधा - यह या तो गैर-नकारात्मक होनी चाहिए (<math>x_i \geq 0</math>), या गैर-सकारात्मक (<math>x_i \leq 0</math>), या अप्रतिबंधित (<math>x_i \in \mathbb{R}</math>).
-* एक उद्देश्य समारोह:    <math>\text{maximize} ~~~ c_1 x_1 +\cdots + c_n x_n</math>
-* एम बाधाओं की एक सूची। प्रत्येक बाधा j है:   <math>a_{j 1} x_1 +\cdots + a_{j n} x_n \lesseqqgtr b_j</math>जहां प्रतीक से पहले <math>b_j</math> में से एक हो सकता है <math>\geq</math> या <math>\leq</math> या <math>=</math>.
-दोहरे एलपी का निर्माण निम्नानुसार किया गया है।
-* प्रत्येक मौलिक बाधा एक दोहरी चर बन जाती है। तो एम चर हैं: <math>y_1 ,\ldots, y_m</math>.
-*प्रत्येक द्वैत चर का चिह्न अवरोध इसके मौलिक अवरोध के चिह्न के विपरीत है। इसलिए<math>\geq b_j </math>बन जाता है  <math>y_j \leq 0 </math> और<math>\leq b_j </math>बन जाता है  <math>y_j \geq 0 </math> और<math>= b_j </math>बन जाता है <math>y_j \in \mathbb{R} </math>.
-* दोहरा उद्देश्य कार्य है    <math>\text{minimize } ~~~ b_1 y_1 +\cdots + b_m y_m</math>
-* प्रत्येक मूल चर एक दोहरी बाधा बन जाता है। तो वहाँ n बाधाएँ हैं। दोहरी बाधा में एक दोहरे चर का गुणांक इसके मौलिक चर का गुणांक इसकी मौलिक बाधा में है। तो प्रत्येक बाधा i है: <math>a_{1 i} y_1 +\cdots + a_{m i} y_m \lesseqqgtr c_i</math>, जहां प्रतीक से पहले <math>c_i</math> प्रारंभिक एलपी में वेरिएबल i पर साइन बाधा के समान है। इसलिए <math>x_i \leq 0 </math> बन जाता है<math>\leq c_i </math>और <math>x_i \geq 0 </math> बन जाता है<math>\geq c_i </math>और <math>x_i \in \mathbb{R} </math> बन जाता है<math>= c_i </math>.
+== द्वैत रैखिक क्रमादेश का निर्माण ==
+सामान्य रूप से, प्राथमिक रैखिक क्रमादेश दिया गया है, इसके द्वैत रैखिक क्रमादेश के निर्माण के लिए निम्न एल्गोरिथम का उपयोग किया जा सकता है।<ref name="gm06" />{{Rp|85}} प्रारंभिक रैखिक क्रमादेश द्वारा परिभाषित किया गया है:
+* चर का एक समुच्चय: <math>x_1 ,\ldots, x_n</math>.
+* प्रत्येक चर <math>x_i</math> के लिए, एक सांकेतिक व्यवरोध - यह या तो गैर-ऋणात्मक (<math>x_i \geq 0</math>), या गैर-धनात्मक (<math>x_i \leq 0</math>), या अप्रतिबंधित (<math>x_i \in \mathbb{R}</math>) होना चाहिए।
+* उद्देश्‍य फलन: <math>\text{maximize} ~~~ c_1 x_1 +\cdots + c_n x_n</math>
+* m व्यवरोधों की एक सूचीː प्रत्येक j व्यवरोध <math>a_{j 1} x_1 +\cdots + a_{j n} x_n \lesseqqgtr b_j</math> है, जहां <math>b_j</math> से पहले का प्रतीक <math>\geq</math> या <math>\leq</math> या <math>=</math> में से एक हो सकता है।
+दोहरे रैखिक क्रमादेश का निर्माण निम्नानुसार किया गया है।
+* प्रत्येक मौलिक व्यवरोध एक द्वैत चर बन जाती है। तो m चर <math>y_1 ,\ldots, y_m</math> हैं।
+*प्रत्येक द्वैत चर का चिह्न व्यवरोध इसके मौलिक व्यवरोध के चिह्न के "विपरीत" है। तो <math>\geq b_j </math> बन जाता है, इसीलिए <math>y_j \leq 0 </math> और<math>\leq b_j </math>बन जाता है। यदि <math>y_j \geq 0 </math> और<math>= b_j </math> है तब <math>y_j \in \mathbb{R} </math> बन जाता है।
+* दोहरा उद्देश्य फलन <math>\text{minimize } ~~~ b_1 y_1 +\cdots + b_m y_m</math> है।
+* प्रत्येक मूल चर एक द्वैत व्यवरोध बन जाता है। तो वहाँ n व्यवरोध हैं। द्वैत व्यवरोध में एक दोहरे चर का गुणांक इसके मौलिक चर का गुणांक इसकी मौलिक व्यवरोध में है। तो प्रत्येक i व्यवरोध: <math>a_{1 i} y_1 +\cdots + a_{m i} y_m \lesseqqgtr c_i</math> होता है, जहां <math>c_i</math> से पहले प्रतीक प्रारंभिक रैखिक क्रमादेश में चर i पर चिन्ह व्यवरोध के समान है। इसलिए <math>x_i \leq 0 </math> बन जाता है और <math>\leq c_i </math> के समान <math>x_i \geq 0 </math> बन जाता है, अतः <math>\geq c_i </math>के लिए <math>x_i \in \mathbb{R} </math> और <math>= c_i </math> बन जाता है
 इस एल्गोरिथम से, यह देखना आसान है कि द्वैत का द्वैत मौलिक है।
-== वेक्टर फॉर्मूलेशन ==
+== वेक्टर (सदिश) सूत्रीकरण ==
-यदि सभी बाधाओं का एक ही संकेत है, तो उपरोक्त नुस्खा को मेट्रिसेस और वैक्टर का उपयोग करके कम तरीके से प्रस्तुत करना संभव है। निम्न तालिका विभिन्न प्रकार के प्राइमल्स और द्वैत के बीच के संबंध को दर्शाती है।
+यदि सभी व्यवरोधों का समान संकेत है, तो उपरोक्त विधि को आव्यूह और वैक्टर का उपयोग करके कम तरीके से प्रस्तुत करना संभव है। निम्न तालिका विभिन्न प्रकार के मौलिक और द्वैत के बीच के संबंध को दर्शाती है।
 {| class="wikitable"
-!Primal
+!मौलिक
-!Dual
+!द्वैत
-!Note
+!टिप्पणी
 |-
-|Maximize '''c'''<sup>T</sup>'''x'''  subject to ''A'''''x''' ≤ '''b''', '''x''' ≥ 0
+|''A'''''x''' ≤ '''b''', '''x''' ≥ 0 के अधीन '''c'''<sup>T</sup>'''x''' को अधिकतम करें
-|Minimize  '''b'''<sup>T</sup>'''y'''  subject to ''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0
+|''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0 के अधीन '''b'''<sup>T</sup>'''y''' को न्यूनतम करें
-|This is called a "symmetric" dual problem
+|इसे "सममित" द्वैत समस्या कहा जाता है
 |-
-|Maximize '''c'''<sup>T</sup>'''x''' subject to ''A'''''x''' ≤ '''b'''
+|''A'''''x''' ≤ '''b''' के अधीन '''c'''<sup>T</sup>'''x''' को अधिकतम करें
-|Minimize  '''b'''<sup>T</sup>'''y''' subject to ''A''<sup>T</sup>'''y''' = '''c''', '''y''' ≥ 0
+|''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0 के अधीन '''b'''<sup>T</sup>'''y''' को न्यूनतम करें
-|This is called an "asymmetric" dual problem
+|इसे "असममित" द्वैत समस्या कहा जाता है
 |-
-|Maximize '''c'''<sup>T</sup>'''x'''  subject to ''A'''''x''' = '''b''', '''x''' ≥ 0
+|''A'''''x''' ≤ '''b''', '''x''' ≥ 0 के अधीन '''c'''<sup>T</sup>'''x''' अधिकतम करें
-|Minimize  '''b'''<sup>T</sup>'''y'''  subject to ''A''<sup>T</sup>'''y''' ≥ '''c'''
+|''A''<sup>T</sup>'''y''' ≥ '''c''' के अधीन '''b'''<sup>T</sup>'''y''' न्यूनतम करें
 |
 |}
@@ Line 66: / Line 90: @@
 == द्वैत प्रमेय ==
-नीचे, मान लीजिए कि मौलिक एलपी अधिकतम सी है<sup>T</sup>x [बाधाओं] के अधीन है और दोहरी LP न्यूनतम b है<sup>T</sup>y [बाधाओं] के अधीन है।
+नीचे, मान लीजिए कि प्रारंभिक रैखिक क्रमादेश "[व्यवरोध] के अधीन '''c'''<sup>T</sup>'''x''' को अधिकतम करता है" और द्वैत रैखिक क्रमादेश "[व्यवरोध] के अधीन '''b'''<sup>T</sup>'''y''' को कम से कम करता है"।
+=== दुर्बल द्वैत ===
+दुर्बल द्वैत प्रमेय का कहना है कि प्रत्येक संभव समाधान '''x''' के लिए मौलिक और प्रत्येक संभव समाधान '''y''' के लिए द्वैत '''c'''<sup>T</sup>'''x''' ≤ '''b'''<sup>T</sup>'''y''' है। दूसरे शब्दों में, द्वैत के प्रत्येक संभव समाधान में वस्तुनिष्ठ मान मूल के वस्तुनिष्ठ मान पर एक ऊपरी सीमा है, और मूल के प्रत्येक व्यवहार्य समाधान में वस्तुनिष्ठ मान द्वैत के वस्तुनिष्ठ मान पर निचली सीमा है। यहाँ प्रारंभिक रैखिक क्रमादेश के लिए एक प्रमाण दिया गया है जिसे "''A'''''x''' ≤ '''b''', '''x''' ≥ 0 के अधीन '''c'''<sup>T</sup>'''x''' को अधिकतम करें":
+* '''c'''<sup>T</sup>'''x'''
+* = '''x<sup>T</sup>c''' [क्योंकि यह केवल दो सदिशों का एक अदिश गुणनफल है]
+* ≤ '''x<sup>T</sup>'''('''''A'''''<sup>'''T'''</sup>'''y''') [चूंकि ''A''<sup>T</sup>'''y''' ≥ '''c''' द्वैत व्यवरोध से, (xTAT)y [साहचर्य द्वारा]
+*=('''x<sup>T</sup>''A''<sup>T</sup>''')'''y''' [साहचर्य द्वारा]
+* = ('''Ax''')<sup>'''T'''</sup>'''y''' [स्थानान्तरण के गुणों से]
+* ≤ '''b<sup>T</sup>y''' [चूँकि ''A'''''x''' ≤ '''b''' प्राथमिक व्यवरोध द्वारा]
+दुर्बल द्वैत का अर्थ है:
+max<sub>'''x'''</sub> '''c'''<sup>T</sup>'''x''' ≤ min'''<sub>y</sub>''' '''b'''<sup>T</sup>'''y'''
+विशेष रूप से, यदि मूल अपरिबद्ध (ऊपर से) है तो द्वैत का कोई संभव समाधान नहीं है, और यदि द्वैत अपरिबद्ध (नीचे से) है तो प्राथमिक का कोई व्यवहार्य समाधान नहीं है।
-=== कमजोर द्वैत ===
-दुर्बल द्वैत प्रमेय कहता है कि, मूल के प्रत्येक सुसंगत हल x और द्वैत के प्रत्येक सुसंगत हल y के लिए: c<sup>टी</sup>x ≤ ख<sup>टी</सुप>य। दूसरे शब्दों में, द्वैत के प्रत्येक संभव समाधान में वस्तुनिष्ठ मूल्य मूल के वस्तुनिष्ठ मूल्य पर एक ऊपरी सीमा है, और मूल के प्रत्येक व्यवहार्य समाधान में वस्तुनिष्ठ मूल्य द्वैत के वस्तुनिष्ठ मूल्य पर निचली सीमा है। यहाँ मूल LP Maximize c के लिए एक प्रमाण दिया गया है<sup>T</sup>x ''A''x ≤ b, x ≥ 0 के अधीन :
-* सी<sup>टी</sup>एक्स
-* = एक्स<sup>T</sup>c [क्योंकि यह केवल दो सदिशों का एक अदिश गुणनफल है]
-* ≤ एक्स<sup>टी</sup>(''ए''<sup>टी</सुप>वाई) ['ए'' के बाद से<sup>T</sup>y ≥ c दोहरी बाधाओं द्वारा, और x ≥ 0]
-* = (एक्स<sup>टी</सुप>ए<sup>टी</sup>)y [साहचर्य द्वारा]
-* = (कुल्हाड़ी)<sup>T</sup>y [ट्रांसपोज़ के गुणों द्वारा]
-* ≤ बी<sup>T</sup>y [चूँकि ''A''x ≤ b प्राथमिक बाधाओं द्वारा]
-कमजोर द्वैत का अर्थ है:<blockquote>max<sub>'''x'''</sub> c<sup>टी</sup>x ≤ मि<sub>y</sub>बी<sup>T</sup>y</blockquote>विशेष रूप से, यदि प्राइमल अनबाउंड (ऊपर से) है तो डुअल का कोई व्यवहार्य समाधान नहीं है, और यदि डुअल अनबाउंड (नीचे से) है तो प्राइमल का कोई व्यवहार्य समाधान नहीं है।
 === प्रबल द्वैत ===
-मजबूत द्वैत प्रमेय कहता है कि यदि दो समस्याओं में से एक का इष्टतम समाधान है, तो दूसरे का भी और कमजोर द्वैत प्रमेय द्वारा दी गई सीमाएं तंग हैं, यानी:<blockquote>max<sub>'''x'''</sub> c<sup>टी</sup>x = मिनट<sub>y</sub>बी<sup>T</sup>y</blockquote>मजबूत द्वैत प्रमेय को सिद्ध करना कठिन है; सबूत आमतौर पर उप-दिनचर्या के रूप में कमजोर द्वंद्व प्रमेय का उपयोग करते हैं।
+प्रबल द्वैत प्रमेय कहता है कि यदि दो समस्याओं में से एक का इष्टतम समाधान है, तो दूसरे का भी और दुर्बल द्वैत प्रमेय द्वारा दी गई सीमाएं कठिन हैं, अर्थात:<blockquote>max<sub>'''x'''</sub> '''c'''<sup>T</sup>'''x''' = min'''<sub>y</sub>''' '''b'''<sup>T</sup>'''y'''</blockquote>प्रबल द्वैत प्रमेय को सिद्ध करना कठिन है; प्रमाण सामान्य रूप से उप-रूटीन के रूप में दुर्बल द्वैत प्रमेय का उपयोग करते हैं।
-एक प्रमाण [[ सिंप्लेक्स एल्गोरिदम ]] का उपयोग करता है और इस प्रमाण पर निर्भर करता है कि, उपयुक्त धुरी नियम के साथ, यह एक सही समाधान प्रदान करता है। प्रमाण यह स्थापित करता है कि, एक बार सिम्प्लेक्स एल्गोरिथम प्राइमल एलपी के समाधान के साथ समाप्त हो जाने पर, अंतिम झांकी से दोहरी एलपी के समाधान को पढ़ना संभव है। इसलिए, सिम्प्लेक्स एल्गोरिथम को चलाकर, हम एक साथ प्राइमल और डुअल दोनों का समाधान प्राप्त करते हैं।<ref name="gm06" />{{Rp|87–89}}
+प्रमाण [[ सिंप्लेक्स एल्गोरिदम |प्रसमुच्चय एल्गोरिदम]] का उपयोग करता है और इस प्रमाण पर निर्भर करता है कि, उपयुक्त मुख्य नियम के साथ, यह एक सही समाधान प्रदान करता है। प्रमाण यह स्थापित करता है कि, एक बार प्रसमुच्चय एल्गोरिथम मूल रैखिक क्रमादेश के समाधान के साथ समाप्त हो जाने पर, अंतिम सारणी से द्वैत रैखिक क्रमादेश के समाधान को पढ़ना संभव है। इसलिए, प्रसमुच्चय एल्गोरिथम को निरंतर, हम एक साथ मौलिक और द्वैत दोनों का समाधान प्राप्त करते हैं।<ref name="gm06" />{{Rp|87–89}}
-एक अन्य प्रमाण [[भेड़िया लेम्मा]] का उपयोग करता है।<ref name="gm06" />{{Rp|94}}
+एक अन्य प्रमाण फ़र्कस लेम्मा का उपयोग करता है।<ref name="gm06" />{{Rp|94}}
 === सैद्धांतिक निहितार्थ ===
-. कमजोर द्वैत प्रमेय का अर्थ है कि एक एकल व्यवहार्य समाधान खोजना उतना ही कठिन है जितना कि एक इष्टतम संभव समाधान खोजना। मान लीजिए कि हमारे पास एक ऑरेकल है, जो एक एलपी दिया गया है, एक मनमाना व्यवहार्य समाधान पाता है (यदि कोई मौजूद है)। एलपी अधिकतम 'सी' को देखते हुए<sup>T</sup>x ''A''x ≤ b, x ≥ 0 के अधीन है, हम इस LP को इसके दोहरे के साथ जोड़कर एक और LP बना सकते हैं। संयुक्त एलपी में चर के रूप में x और y दोनों हैं:<blockquote>Maximize 1 </blockquote><blockquote>''A''x ≤ b, ''A'' के अधीन<sup>टी</सुप>वाई ≥ सी, सी<sup>टी</sup>x ≥ ख<sup>T</sup>y, x ≥ 0, y ≥ 0 </blockquote>यदि संयुक्त LP का एक व्यवहार्य समाधान (x,y) है, तो कमजोर द्वैत द्वारा, c<sup>टी</sup>x = ख<sup>टी</सुप>य। अतः x को मूल LP का अधिकतम हल होना चाहिए और y को द्वैत LP का न्यूनतम हल होना चाहिए। यदि संयुक्त एलपी का कोई संभव समाधान नहीं है, तो मूल एलपी का भी कोई संभव समाधान नहीं है।
+. दुर्बल द्वैत प्रमेय का अर्थ है कि एकल व्यवहार्य समाधान खोजना उतना ही कठिन है जितना कि एक इष्टतम संभव समाधान खोजना। मान लीजिए कि हमारे पास एक ऑरेकल है, जो एक रैखिक क्रमादेश दिया गया है, एक यादृच्छिक व्यवहार्य (यदि सम्मिलित है) समाधान पाता है। रैखिक क्रमादेश को देखते हुए "''A'''''x''' ≤ '''b''', '''x''' ≥ 0 के अधीन '''c'''<sup>T</sup>'''x''' को अधिकतम करें", हम इस रैखिक क्रमादेश को इसके द्वैत के साथ जोड़कर एक अन्य रैखिक क्रमादेश बना सकते हैं। संयुक्त रैखिक क्रमादेश में चर के रूप में '''x''' और '''y''' दोनों हैं:
+अधिकतम '''1'''
+''A'''''x''' ≤ '''b''', ''A''<sup>T</sup>'''y''' ≥ '''c''', '''c'''<sup>T</sup>'''x''' ≥ '''b'''<sup>T</sup>'''y''', '''x''' ≥ 0, '''y''' ≥ 0 के अधीन
+यदि संयुक्त रैखिक क्रमादेश का एक व्यवहार्य समाधान ('''x, y''') है तो दुर्बल द्वैत '''c'''<sup>T</sup>'''x''' = '''b'''<sup>T</sup>'''y''' द्वारा प्राप्त है। अतः '''x''' को मूल रैखिक क्रमादेश का अधिकतम हल होना चाहिए और y को द्वैत रैखिक क्रमादेश का न्यूनतम हल होना चाहिए। यदि संयुक्त रैखिक क्रमादेश का कोई संभव समाधान नहीं है, तो मूल रैखिक क्रमादेश का भी कोई संभव समाधान नहीं है।
+. प्रबल द्वैत प्रमेय एक रैखिक क्रमादेश के इष्टतम मूल्य का एक अच्छा विशेषीकरण प्रदान करता है जिसमें यह हमें आसानी से प्रमाणित करने की स्वीकृति देता है कि कुछ मूल्य 't' कुछ रैखिक क्रमादेश का इष्टतम है। प्रमाण दो चरणों में आगे बढ़ता है:<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{rp|260–261}}
+* मान t के साथ प्राथमिक रैखिक क्रमादेश के लिए एक व्यवहार्य समाधान दिखाएं; इससे सिद्ध होता है कि इष्टतम कम से कम t है।
+* मान t के साथ द्वैत रैखिक क्रमादेश के लिए एक व्यवहार्य समाधान दिखाएं; यह प्रमाणित करता है कि इष्टतम अधिकतम t पर है।
-. मजबूत द्वैत प्रमेय एक एलपी के इष्टतम मूल्य का एक अच्छा लक्षण वर्णन प्रदान करता है जिसमें यह हमें आसानी से साबित करने की अनुमति देता है कि कुछ मूल्य 'टी' कुछ एलपी का इष्टतम है। प्रमाण दो चरणों में आगे बढ़ता है:<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{rp|260–261}}
-* वैल्यू टी के साथ प्राइमल एलपी के लिए एक व्यवहार्य समाधान दिखाएं; इससे सिद्ध होता है कि इष्टतम कम से कम t है।
-* मूल्य टी के साथ दोहरी एलपी के लिए एक व्यवहार्य समाधान दिखाएं; यह साबित करता है कि इष्टतम अधिकतम टी पर है।
 == उदाहरण ==
@@ Line 100: / Line 157: @@
 === छोटा उदाहरण ===
-प्राथमिक एलपी पर विचार करें, दो चर और एक बाधा के साथ:
+प्राथमिक रैखिक क्रमादेश पर विचार करें, दो चर और एक व्यवरोध के साथ:
 : <math>\begin{align}
@@ Line 110: / Line 167: @@
 \end{align}
 </math>
-उपरोक्त नुस्खा को लागू करने से निम्नलिखित दोहरी एलपी मिलती है, एक चर और दो बाधाओं के साथ:
+उपरोक्त पद्धति को प्रयुक्त करने से निम्नलिखित द्वैत रैखिक क्रमादेश मिलती है, एक चर और दो व्यवरोध के साथ:
 : <math>\begin{align}
@@ Line 123: / Line 180: @@
 \end{align}
 </math>
-यह देखना आसान है कि प्रारंभिक LP का अधिकतम मान तब प्राप्त होता है जब x<sub>1</sub> इसकी निचली सीमा (0) और x तक न्यूनतम है<sub>2</sub> बाधा (7/6) के तहत इसकी ऊपरी सीमा तक अधिकतम है। अधिकतम 4· 7/6 = 14/3 है।
+यह देखना आसान है कि प्रारंभिक रैखिक क्रमादेश का अधिकतम मान तब प्राप्त होता है जब x<sub>1</sub> इसकी निचली सीमा (0) और x<sub>2</sub> तक न्यूनतम है, व्यवरोध (7/6) के अंतर्गत इसकी ऊपरी सीमा तक अधिकतम है। अधिकतम 4· 7/6 = 14/3 है।
-इसी प्रकार, दोहरी एलपी का न्यूनतम y होने पर प्राप्त होता है<sub>1</sub> बाधाओं के तहत इसकी निचली सीमा तक न्यूनतम किया जाता है: पहली बाधा 3/5 की निचली सीमा देती है जबकि दूसरी बाधा 4/6 की एक सख्त निचली सीमा देती है, इसलिए वास्तविक निचली सीमा 4/6 और न्यूनतम 7 है · 4/6 = 14/3।
+इसी प्रकार, द्वैत रैखिक क्रमादेश का न्यूनतम y<sub>1</sub> होने पर प्राप्त होता है, व्यवरोध के अंतर्गत इसकी निचली सीमा तक न्यूनतम किया जाता है: पहली व्यवरोध 3/5 की निचली सीमा देती है जबकि दूसरी व्यवरोध 4/6 की एक स्थिर निचली सीमा देती है, इसलिए वास्तविक निचली सीमा 4/6 और न्यूनतम 7· 4/6 = 14/3 है।
 प्रबल द्वैत प्रमेय के अनुसार, मूल का अधिकतम द्वैत के न्यूनतम के बराबर होता है।
-हम इस उदाहरण का उपयोग कमजोर द्वैत प्रमेय के प्रमाण को दर्शाने के लिए करते हैं। मान लीजिए कि, मूल एलपी में, हम उद्देश्य पर ऊपरी सीमा प्राप्त करना चाहते हैं <math>3 x_1 + 4 x_2</math>. हम बाधा को कुछ गुणांक से गुणा करके उपयोग कर सकते हैं, कहते हैं <math>y_1</math>. किसी के लिए <math>y_1</math> हम पाते हैं:   <math>y_1\cdot (5 x_1 + 6 x_2) = 7 y_1</math>. अब अगर  <math>y_1\cdot 5 x_1 \geq 3 x_1</math>और <math>y_1\cdot 6 x_2 \geq 4 x_2</math>, तब <math>y_1\cdot (5 x_1 + 6 x_2) \geq 3 x_1 + 4 x_2</math>, इसलिए <math>7 y_1 \geq 3 x_1 + 4 x_2</math>. इसलिए, दोहरे एलपी का उद्देश्य मौलिक एलपी के उद्देश्य पर एक ऊपरी सीमा है।
+हम इस उदाहरण का उपयोग दुर्बल द्वैत प्रमेय के प्रमाण को दर्शाने के लिए करते हैं। मान लीजिए कि मूल रैखिक क्रमादेश में, हम उद्देश्य <math>3 x_1 + 4 x_2</math> पर ऊपरी सीमा प्राप्त करना चाहते हैं। हम व्यवरोध को किसी गुणांक <math>y_1</math>से गुणा करके उपयोग कर सकते हैं। किसी भी <math>y_1</math>के लिए हमें: <math>y_1\cdot (5 x_1 + 6 x_2) = 7 y_1</math>प्राप्त होता है। तब, यदि <math>y_1\cdot 5 x_1 \geq 3 x_1</math>और <math>y_1\cdot 6 x_2 \geq 4 x_2</math> तब <math>y_1\cdot (5 x_1 + 6 x_2) \geq 3 x_1 + 4 x_2</math> के समान <math>7 y_1 \geq 3 x_1 + 4 x_2</math> प्राप्त होता है। इसलिए, दोहरे रैखिक क्रमादेश का उद्देश्य मौलिक रैखिक क्रमादेश के उद्देश्य पर एक ऊपरी सीमा है।
 === किसान उदाहरण ===
-[[File:linear_programming_feasible_region_farmer_example.svg|thumb|किसान उदाहरण के लिए चित्रमय समाधान - शर्तों का उल्लंघन करने वाले क्षेत्रों को छायांकित करने के बाद, शेष व्यवहार्य क्षेत्र का शीर्ष मूल से सबसे दूर धराशायी रेखा के साथ इष्टतम संयोजन देता है]]एक ऐसे किसान पर विचार करें जो कुछ एल भूमि, एफ उर्वरक और पी कीटनाशक के निर्धारित प्रावधान के साथ गेहूं और जौ उगा सकता है।
+[[File:linear_programming_feasible_region_farmer_example.svg|thumb|किसान उदाहरण के लिए चित्रमय समाधान - शर्तों का उल्लंघन करने वाले क्षेत्रों को छायांकित करने के बाद, शेष व्यवहार्य क्षेत्र का शीर्ष मूल से सबसे दूर असतत रेखा के साथ इष्टतम संयोजन देता है]]एक ऐसे किसान पर विचार करें जो कुछ L भूमि, F उर्वरक और P कीटनाशक के निर्धारित प्रावधान के साथ गेहूं और जौ उगा सकता है। एक इकाई गेहूँ उगाने के लिए एक इकाई ज़मीन <math>F_1</math> उर्वरक की इकाइयां और <math>P_1</math> कीटनाशी की ईकाइयों का प्रयोग करना चाहिए। इसी प्रकार, जौ की एक इकाई, भूमि की एक इकाई उगाने के लिए <math>F_2</math> उर्वरक की इकाइयां और <math>P_2</math> कीटनाशी की ईकाइयों का प्रयोग करना चाहिए।
-एक यूनिट गेहूँ, एक यूनिट ज़मीन उगाने के लिए, <math>F_1</math> उर्वरक की इकाइयां और <math>P_1</math> कीटनाशी की ईकाइयों का प्रयोग करना चाहिए। इसी प्रकार, जौ की एक इकाई, भूमि की एक इकाई उगाने के लिए, <math>F_2</math> उर्वरक की इकाइयां और <math>P_2</math> कीटनाशी की ईकाइयों का प्रयोग करना चाहिए।
-सबसे बड़ी समस्या यह होगी कि किसान यह तय करेगा कि कितना गेहूँ (<math>x_1</math>) और जौ (<math>x_2</math>) बढ़ने के लिए अगर उनके विक्रय मूल्य हैं <math>S_1</math> और <math>S_2</math> प्रति यूनिट।
+सबसे बड़ी समस्या यह होगी कि किसान यह निर्धारित करेगा कि कितना गेहूँ (<math>x_1</math>) और जौ (<math>x_2</math>) बढ़ने के लिए यदि उनके विक्रय मूल्य <math>S_1</math> और <math>S_2</math> प्रति इकाई हैं।
 {|
 |-
-| colspan="2" | Maximize: <math>S_1 \cdot x_1 + S_2 \cdot x_2</math>
+| colspan="2" | अधिकतम: <math>S_1 \cdot x_1 + S_2 \cdot x_2</math>
-| (maximize the revenue from producing wheat and barley)
+| (गेहूं और जौ के उत्पादन से अधिक से अधिक लाभ प्राप्त करना)
 |-
-| subject to:
+| यदि:
 |<math>x_1 + x_2 \leq L</math>
-| (cannot use more land than available)
+| (उपलब्ध भूमि से अधिक भूमि का उपयोग नहीं कर सकते)
 |-
 |
 |<math>F_1 \cdot x_1 + F_2 \cdot x_2 \leq F</math>
-| (cannot use more fertilizer than available)
+| (उपलब्ध से अधिक उर्वरक का उपयोग नहीं कर सकते)
 |-
 |
 |<math>P_1 \cdot x_1 + P_2 \cdot x_2 \leq P</math>
-| (cannot use more pesticide than available)
+| (उपलब्ध से अधिक कीटनाशक का उपयोग नहीं कर सकते)
 |-
 |
 |<math>x_1, x_2 \geq 0</math>
-| (cannot produce negative quantities of wheat or barley).
+| (गेहूं या जौ की ऋणात्मक मात्रा का उत्पादन नहीं कर सकते हैं)।
 |}
-मैट्रिक्स रूप में यह बन जाता है:
+आव्यूह रूप में यह बन जाता है:
 : अधिकतम करें: <math>\begin{bmatrix}S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} </math>
-: का विषय है: <math>\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} \ge 0. </math>
+: यदि: <math>\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} \ge 0. </math>
-दोहरी समस्या के लिए मान लें कि उत्पादन के इन साधनों (इनपुट्स) में से प्रत्येक के लिए y इकाई मूल्य एक योजना बोर्ड द्वारा निर्धारित किए गए हैं। योजना बोर्ड का काम किसान को उसकी प्रत्येक फसल (उत्पादन) के इकाई मूल्य पर एक फ्लोर उपलब्ध कराते हुए निविष्टियों की निर्धारित मात्रा की खरीद की कुल लागत को न्यूनतम करना है।<sub>1</sub> गेहूं के लिए और एस<sub>2</sub> जौ के लिए। यह निम्नलिखित एलपी से मेल खाता है:
+द्वैत समस्या के लिए मान लें कि उत्पादन के इन साधनों (उत्पादक वस्तु) में से प्रत्येक के लिए y इकाई मान एक योजना बोर्ड द्वारा निर्धारित किए गए हैं। योजना बोर्ड का काम किसान को उसकी प्रत्येक फसल (उत्पादन) के इकाई मूल्य पर गेहूं के लिए ''S''<sub>1</sub> और जौ के लिए ''S''<sub>2</sub> प्रदान करते हुए उत्पादक वस्तु की निर्धारित मात्रा की खरीद की कुल कीमत को कम करना है। यह निम्नलिखित रैखिक क्रमादेश से अनुरूप होता है:
 {|
 |-
-| colspan="2" | Minimize: <math>L\cdot y_L + F\cdot y_F + P\cdot y_P</math>
+| colspan="2" | अधिकतम: <math>L\cdot y_L + F\cdot y_F + P\cdot y_P</math>
-| (minimize the total cost of the means of production as the "objective function")
+| (उत्पादन के साधनों की कुल कीमत को "उद्देश्य फलन" के रूप में न्यूनतम करें)
 |-
-| subject to:
+| यदि
 |<math>y_L+F_1\cdot y_F+P_1\cdot y_P\geq S_1</math>
-| (the farmer must receive no less than ''S''<sub>1</sub> for his wheat)
+| (किसान को अपने गेहूं के लिए ''S''<sub>1</sub> से कम नहीं प्राप्त करना चाहिए)
 |-
 |
 |<math>y_L+F_2\cdot y_F+P_2\cdot y_P\geq S_2</math>
-| (the farmer must receive no less than ''S''<sub>2</sub> for his barley)
+| (किसान को अपने जौ के लिए ''S''<sub>2</sub> से कम नहीं प्राप्त करना चाहिए)
 |-
 |
 |<math>y_L, y_F, y_P\geq 0</math>
-| (prices cannot be negative).
+| (कीमतें ऋणात्मक नहीं हो सकतीं)
 |}
-मैट्रिक्स रूप में यह बन जाता है:
+आव्यूह रूप में यह बन जाता है:
-: छोटा करना: <math>\begin{bmatrix} L & F & P \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} </math>
+: अधिकतम: <math>\begin{bmatrix} L & F & P \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} </math>
-: का विषय है: <math>\begin{bmatrix} 1 & F_1 & P_1 \\ 1 & F_2 & P_2 \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \ge \begin{bmatrix} S_1 \\ S_2 \end{bmatrix}, \, \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \ge 0. </math>
+: यदि: <math>\begin{bmatrix} 1 & F_1 & P_1 \\ 1 & F_2 & P_2 \end{bmatrix} \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \ge \begin{bmatrix} S_1 \\ S_2 \end{bmatrix}, \, \begin{bmatrix} y_L \\ y_F \\ y_P \end{bmatrix} \ge 0. </math>
-प्राथमिक समस्या भौतिक मात्राओं से संबंधित है। सीमित मात्रा में उपलब्ध सभी इनपुट के साथ, और यह मानते हुए कि सभी आउटपुट की इकाई कीमतें ज्ञात हैं, आउटपुट की कितनी मात्रा का उत्पादन करना है ताकि कुल राजस्व को अधिकतम किया जा सके? दोहरी समस्या आर्थिक मूल्यों से संबंधित है। सभी आउटपुट यूनिट कीमतों पर फ्लोर गारंटी के साथ, और यह मानते हुए कि सभी इनपुट की उपलब्ध मात्रा ज्ञात है, कुल खर्च को कम करने के लिए कौन सी इनपुट यूनिट मूल्य निर्धारण योजना निर्धारित की जाए?
+प्राथमिक समस्या भौतिक मात्राओं से संबंधित है। सीमित मात्रा में उपलब्ध सभी उत्पादक वस्तु के साथ, और यह मानते हुए कि सभी उत्पादन की इकाई कीमतें ज्ञात हैं, उत्पादन की कितनी मात्रा का उत्पादन करना है ताकि कुल लाभ को अधिकतम किया जा सके? द्वैत समस्या आर्थिक मानो से संबंधित है। सभी उत्पादन इकाई कीमतों पर निम्न प्रत्याभूति के साथ, और यह मानते हुए कि सभी उत्पादक वस्तु की उपलब्ध मात्रा ज्ञात है, कुल खर्च को कम करने के लिए कौन सी उत्पादक वस्तु इकाई मूल्य निर्धारण योजना निर्धारित की जाए?
-प्रारंभिक स्थान में प्रत्येक चर के लिए दोहरी स्थान में संतुष्ट करने के लिए एक असमानता से मेल खाती है, दोनों आउटपुट प्रकार द्वारा अनुक्रमित हैं। प्रारंभिक स्थान में प्रत्येक असमानता को संतुष्ट करने के लिए दोहरे स्थान में एक चर से मेल खाता है, दोनों को इनपुट प्रकार द्वारा अनुक्रमित किया गया है।
+प्रारंभिक समष्‍टि में प्रत्येक चर के लिए द्वैत समष्‍टि में संतुष्ट करने के लिए एक असमानता से समान है, दोनों उत्पादन प्रकार द्वारा अनुक्रमित हैं। प्रारंभिक समष्‍टि में प्रत्येक असमानता को संतुष्ट करने के लिए द्वैत-समष्‍टि में एक चर से समान है, दोनों को उत्पादक वस्तु प्रकार द्वारा अनुक्रमित किया गया है।
-मौलिक स्थान में असमानताओं को बाध्य करने वाले गुणांकों का उपयोग इस उदाहरण में दोहरे स्थान, इनपुट मात्रा में उद्देश्य की गणना करने के लिए किया जाता है। मूल स्थान में उद्देश्य की गणना करने के लिए उपयोग किए जाने वाले गुणांक दोहरे स्थान में असमानताओं को बांधते हैं, इस उदाहरण में आउटपुट यूनिट की कीमतें।
+मौलिक समष्‍टि में असमानताओं को सीमित करने वाले गुणांकों का उपयोग इस उदाहरण में द्वैत-समष्‍टि, उत्पादक वस्तु मात्रा में उद्देश्य की गणना करने के लिए किया जाता है। मूल समष्‍टि में उद्देश्य की गणना करने के लिए उपयोग किए जाने वाले गुणांक द्वैत-समष्‍टि में असमानताओं को सीमित हैं, इस उदाहरण में उत्पादन इकाई की कीमतें सीमित होती है।
-प्राथमिक और दोहरी दोनों समस्याएं एक ही मैट्रिक्स का उपयोग करती हैं। प्रारंभिक स्थान में, यह मैट्रिक्स आउटपुट की निर्धारित मात्रा का उत्पादन करने के लिए आवश्यक इनपुट की भौतिक मात्रा की खपत को व्यक्त करता है। दोहरे स्थान में, यह सेट इनपुट यूनिट कीमतों से आउटपुट से जुड़े आर्थिक मूल्यों के निर्माण को व्यक्त करता है।
+प्राथमिक और द्वैत दोनों समस्याएं समान आव्यूह का उपयोग करती हैं। प्रारंभिक समष्‍टि में, यह आव्यूह उत्पादन की निर्धारित मात्रा का उत्पादन करने के लिए आवश्यक उत्पादक वस्तु की भौतिक मात्रा के उपभोग को व्यक्त करता है। द्वैत-समष्‍टि में, यह समूह उत्पादक वस्तु इकाई कीमतों से उत्पादन से जुड़े आर्थिक मानो के निर्माण को व्यक्त करता है।
-चूँकि प्रत्येक असमानता को एक समानता और एक सुस्त चर द्वारा प्रतिस्थापित किया जा सकता है, इसका मतलब है कि प्रत्येक प्राथमिक चर एक दोहरे सुस्त चर से मेल खाता है, और प्रत्येक दोहरा चर एक प्राथमिक सुस्त चर से मेल खाता है। यह संबंध हमें पूरक सुस्ती के बारे में बात करने की अनुमति देता है।
+चूँकि प्रत्येक असमानता को एक समानता और एक न्यूनतापूरक चर द्वारा प्रतिस्थापित किया जा सकता है, इसका तात्पर्य है कि प्रत्येक प्राथमिक न्यूनतापूरक चर एक द्वैत न्यूनतापूरक चर से समान है, और प्रत्येक द्वैत न्यूनतापूरक चर एक प्राथमिक न्यूनतापूरक चर से समान है। यह संबंध हमें पूरक मंदी के बारे में बात करने की स्वीकृति देता है।
-=== अव्यवहार्य कार्यक्रम ===
+=== अव्यवहार्य क्रमादेश ===
-एक एलपी असीमित या अव्यवहार्य भी हो सकता है। द्वैत सिद्धांत हमें बताता है कि:
+रैखिक क्रमादेश असीमित या अव्यवहार्य भी हो सकता है। द्वैत सिद्धांत हमें बताता है कि:
-* यदि प्राण अबाध है, तो द्वैत अक्षम्य है;
+* यदि मूल अपरिबद्ध है, तो द्वैत अव्यवहार्य है;
-* यदि द्वैत असीम है, तो प्राण अव्यवहार्य है।
+* यदि द्वैत अबाधित है, तो मूल अव्यवहार्य है।
-हालाँकि, यह संभव है कि द्वैत और मौलिक दोनों ही अव्यवहार्य हों। यहाँ एक उदाहरण है:
+हालाँकि, यह संभव है कि द्वैत और मूल दोनों ही अव्यवहार्य हों। यहाँ एक उदाहरण है:
 {|
 |-
-| colspan="2" | Maximize: <math>2x_1 -x_2</math>
+| colspan="2" | अधिकतम: <math>2x_1 -x_2</math>
 |-
-| Subject to:
+| यदि:
 |<math>x_1 -x_2 \le 1</math>
 |-
@@ Line 216: / Line 272: @@
 == अनुप्रयोग ==
-मैक्स-फ्लो मिन-कट प्रमेय मजबूत द्वैत प्रमेय का एक विशेष मामला है: फ्लो-मैक्सिमाइजेशन प्राइमल एलपी है, और कट-मिनिमाइजेशन डुअल एलपी है। मैक्स-फ्लो मिन-कट थ्योरम#लीनियर प्रोग्राम फॉर्म्युलेशन देखें।
+अधिकतम प्रवाह न्यूनतम प्रतिच्छेद प्रमेय प्रबल द्वैत प्रमेय का एक विशेष स्थिति है: प्रवाह अधिकतमकरण मूल रैखिक क्रमादेश है, और प्रतिच्छेद-न्यूनीकरण द्वैत रैखिक क्रमादेश है। अधिकतम प्रवाह न्यूनतम प्रतिच्छेद प्रमेय#रैखिक क्रमादेश सूत्रीकरण देखें।
+ग्राफ से संबंधित अन्य प्रमेयों को विशेष रूप से कोनिग के प्रमेय में प्रबल द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है।<ref>{{Cite web|url=http://www.princeton.edu/~amirali/Public/Teaching/ORF523/S16/ORF523_S16_Lec6_gh.pdf|title=Lecture 6: linear programming and matching|last=A. A. Ahmadi|date=2016|website=Princeton University}}</ref>
-ग्राफ से संबंधित अन्य प्रमेयों को मजबूत द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है, विशेष रूप से, कोनिग प्रमेय (ग्राफ सिद्धांत) | कोनिग प्रमेय।<ref>{{Cite web|url=http://www.princeton.edu/~amirali/Public/Teaching/ORF523/S16/ORF523_S16_Lec6_gh.pdf|title=Lecture 6: linear programming and matching|last=A. A. Ahmadi|date=2016|website=Princeton University}}</ref>
+शून्येतर योग खेल के लिए [[मिनिमैक्स प्रमेय|न्यूनाधिक प्रमेय]] को प्रबल-द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है।<ref name="gm06" />{{Rp|sub.8.1}}
-जीरो-सम गेम के लिए [[मिनिमैक्स प्रमेय]] को मजबूत-द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है।<ref name="gm06" />{{Rp|sub.8.1}}
 == वैकल्पिक एल्गोरिदम ==
-कभी-कभी, प्रोग्राम मैट्रिक्स को देखे बिना दोहरे प्रोग्राम को प्राप्त करना अधिक सहज हो सकता है। निम्नलिखित रैखिक कार्यक्रम पर विचार करें:
+कभी-कभी, क्रमादेश आव्यूह को देखे बिना दोहरे क्रमादेश को प्राप्त करना अधिक सामान्य हो सकता है। निम्नलिखित रैखिक क्रमादेश पर विचार करें:
 {| cellspacing="10"
 |-
-| Minimize
+| अधिकतम
 | colspan="2" |<math> \sum_{i=1}^m c_i x_i + \sum_{j=1}^n d_j t_j </math>
 |-
-| subject to
+| यदि
 |<math> \sum_{i=1}^m a_{ij} x_i + e_j t_j \ge g_j,</math>
 |
@@ Line 243: / Line 300: @@
 |<math> 1 \le i \le m, 1 \le j \le n </math>
 |}
-हमारे पास एम + एन स्थितियां हैं और सभी चर गैर-नकारात्मक हैं। हम m+n दोहरे चर परिभाषित करेंगे: 'y'<sub>j</sub> और एस<sub>''i''</sub>. हम पाते हैं:
+हमारे पास m +n स्थितियां हैं और सभी चर गैर-ऋणात्मक हैं। हम m + n द्वैत चर '''y'''<sub>j</sub> और '''s'''<sub>''i''</sub> परिभाषित करेंगे। हम पाते हैं:
 {| cellspacing="10"
 |-
-| Minimize
+| न्यूनतम
 | colspan="2" |<math> \sum_{i=1}^m c_i x_i + \sum_{j=1}^n d_j t_j </math>
 |-
-| subject to
+| यदि
 |<math> \sum_{i=1}^m a_{ij} x_i  \cdot y_j + e_j t_j \cdot y_j \ge g_j \cdot y_j, </math>
 |
@@ Line 269: / Line 326: @@
 |<math> 1 \le j \le n, 1 \le i \le m </math>
 |}
-चूंकि यह एक न्यूनीकरण समस्या है, हम एक दोहरा कार्यक्रम प्राप्त करना चाहेंगे जो कि मूल की निचली सीमा है। दूसरे शब्दों में, हम चाहते हैं कि बाधाओं के सभी दाहिने हाथ का योग इस शर्त के तहत अधिकतम हो कि प्रत्येक मूल चर के लिए इसके गुणांकों का योग रैखिक फलन में इसके गुणांक से अधिक न हो। उदाहरण के लिए, एक्स<sub>1</sub> n + 1 बाधाओं में प्रकट होता है। यदि हम इसके व्यवरोधों के गुणांकों का योग करते हैं तो हमें a मिलता है<sub>1,1</sub>y<sub>1</sub>+ ए<sub>1,2</sub>y<sub>2</sub>+ ... + ए<sub>1,;;n;;</sub>y<sub>''n''</sub>+ च<sub>1</sub>s<sub>1</sub>. यह राशि अधिकतम सी होनी चाहिए<sub>1</sub>. परिणामस्वरूप, हमें मिलता है:
+चूंकि यह एक न्यूनीकरण समस्या है, हम एक दोहरा क्रमादेश प्राप्त करना चाहेंगे जो कि मूल की निचली सीमा है। दूसरे शब्दों में, हम चाहते हैं कि व्यवरोध के सभी दाहिने हाथ का योग इस शर्त के अंतर्गत अधिकतम हो कि प्रत्येक मूल चर के लिए इसके गुणांकों का योग रैखिक फलन में इसके गुणांक से अधिक न हो। उदाहरण के लिए, x<sub>1</sub> n + 1 व्यवरोध में प्रकट होता है। यदि हम इसके व्यवरोध गुणांकों का योग करते हैं तो हमें ''a''<sub>1,1</sub>'''y'''<sub>1</sub> + ''a''<sub>1,2</sub>'''y'''<sub>2</sub> + ... + ''a''<sub>1,;;n;;</sub>'''y'''<sub>''n''</sub> + ''f''<sub>1</sub>'''s'''<sub>1</sub> प्राप्त होता है। यह राशि अधिक से अधिक '''c'''<sub>1</sub> होनी चाहिए। परिणामस्वरूप, हमें मिलता है:
 {| cellspacing="10"
 |-
-| Maximize
+| अधिकतम
 | colspan="2" |<math> \sum_{j=1}^n g_j y_j + \sum_{i=1}^m h_i s_i </math>
 |-
-| subject to
+| यदि
 |<math> \sum_{j=1}^n a_{ij} y_j + f_i s_i \le c_i,</math>
 |
@@ Line 291: / Line 348: @@
 |<math> 1 \le j \le n, 1 \le i \le m </math>
 |}
-ध्यान दें कि हम अपने गणना चरणों में मानते हैं कि कार्यक्रम मानक रूप में है। हालाँकि, किसी भी रेखीय कार्यक्रम को मानक रूप में बदला जा सकता है और इसलिए यह एक सीमित कारक नहीं है।
+ध्यान दें कि हम अपने गणना चरणों में मानते हैं कि क्रमादेश मानक रूप में है। हालाँकि, किसी भी रेखीय क्रमादेश को मानक रूप में बदला जा सकता है और इसलिए यह एक सीमित कारक नहीं है।
 == संदर्भ ==
 {{reflist}}
-[[Category: रैखिक प्रोग्रामिंग]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 06/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with maths render errors]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Template documentation pages|Short description/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:रैखिक प्रोग्रामिंग]]

Anonymous

Search

दोहरी रैखिक कार्यक्रम: Difference between revisions

Latest revision as of 17:05, 25 May 2023

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

स्पष्टीकरण

द्वैत रैखिक क्रमादेश का निर्माण

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

द्वैत प्रमेय

दुर्बल द्वैत

प्रबल द्वैत

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

उदाहरण

छोटा उदाहरण

किसान उदाहरण

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

अनुप्रयोग

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories