बेसिक फीज़बल सलूशन: Difference between revisions

Latest revision as of 11:26, 9 August 2023

लीनियर प्रोग्रामिंग के सिद्धांत में, बेसिक फीज़बल सलूशन (BFS/BFS) या बेसिकभूत सुसंगत हल गैर-शून्य चर के न्यूनतम समुच्चय वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक BFS फीज़बल सलूशन केबहुतल के एक कोने से मेल खाता है। यदि कोई ऑप्टीमल (इष्टतम) समाधान उपस्थित है, तो एक ऑप्टीमल BFS भी उपस्थित है। इसलिए, एक ऑप्टीमल समाधान खोजने के लिए, BFS-s पर विचार करना पर्याप्त है। इस तथ्य का उपयोग सिम्प्लेक्स एल्गोरिथ्म द्वारा किया जाता है, जो अनिवार्य रूप से एक ऑप्टीमल समाधान मिलने तक एक BFS से दूसरे तक यात्रा करता है।^[1]

परिभाषाएँ

प्रारंभिक: लीनियर-इंडिपेंडेंट रोव के साथ समीकरणात्मक रूप

नीचे दी गई परिभाषाओं के लिए, हम पहले लीनियर प्रोग्राम को तथाकथित समीकरणात्मक रूप में प्रस्तुत करते हैं:

अधिकतम करें

{\textstyle \mathbf {c^{T}} \mathbf {x} }

का विषय है

A\mathbf {x} =\mathbf {b}

और

\mathbf {x} \geq 0

जहाँ:

$\mathbf {c^{T}}$ और $\mathbf {x}$ आकार n (चरों की संख्या) के सदिश हैं;
$\mathbf {b}$ आकार m (बाधाओं की संख्या) का एक सदिश है;
$A$ एक m-बाय-n आव्यूह है;
$\mathbf {x} \geq 0$ इसका मतलब है कि सभी चर गैर-नकारात्मक हैं।

किसी भी लीनियर प्रोग्राम को स्लैक चर जोड़कर समीकरणीय रूप में परिवर्तित किया जा सकता है।

प्रारंभिक सफ़ाई कदम के रूप में, हम सत्यापित करते हैं कि:

प्रणाली $A\mathbf {x} =\mathbf {b}$ कम से कम एक समाधान है (अन्यथा पूरे LP के पास कोई समाधान नहीं है और करने के लिए और कुछ नहीं है);
आव्यूह की सभी m रोव $A$ रैखिक रूप से स्वतंत्र हैं, यानी, इसकी रैंक m है (अन्यथा हम LP को बदले बिना अनावश्यक रोव को हटा सकते हैं)।

संभव समाधान

LP का एक फीज़बल सलूशन कोई भी वेक्टर है $\mathbf {x} \geq 0$ ऐसा है कि $A\mathbf {x} =\mathbf {b}$ . हम मानते हैं कि कम से कम एक फीज़बल सलूशन है। यदि m = n, तो केवल एक ही फीज़बल सलूशन है। सामान्यतः m < n, इसलिए सिस्टम $A\mathbf {x} =\mathbf {b}$ कई समाधान हैं; ऐसे प्रत्येक समाधान को LP का फीज़बल सलूशन कहा जाता है।

बेसिक (आधारभूत)

LP का बेसिक A का एक इनवेर्टीबल आव्यूह उपाव्यूह है जिसमें सभी m पंक्तियां और केवल m<n कॉलम हैं।

कभी-कभी, बेसिक शब्द का प्रयोग उपाव्यूह के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के समुच्चय के लिए किया जाता है। मान लीजिए B {1,...,n} से m सूचकांकों का एक उपसमुच्चय है। द्वारा निरूपित करें $A_{B}$ वर्ग m-by-m आव्यूह, m कॉलम से बना है $A$ B द्वारा अनुक्रमित यदि $A_{B}$ बीजगणितीय वक्र एकवचन है, बी द्वारा अनुक्रमित स्तंभ स्तंभ स्थान का एक बेसिक (रैखिक बीजगणित) हैं $A$ . इस स्थिति में, हम B को 'LP का बेसिक' कहते हैं।

के पद से $A$ m है, इसका कम से कम एक बेसिक है; तब से $A$ इसमें n कॉलम हैं, इसमें अधिकतम है ${\binom {n}{m}}$ बेसिक.

बेसिक फीज़बल सलूशन

बेसिक B दिए जाने पर, हम कहते हैं कि फीज़बल सलूशन $\mathbf {x}$ बेसिक B के साथ एक बेसिक फीज़बल सलूशन है यदि इसके सभी गैर-शून्य चर को B द्वारा अनुक्रमित किया जाता है, अर्थात सभी के लिए $j\not \in B:~~x_{j}=0$ .

गुण

1. BFS केवल LP (आव्यूह) की बाधाओं से निर्धारित होता है $A$ और वेक्टर $\mathbf {b}$ ); यह अनुकूलन उद्देश्य पर निर्भर नहीं है.

2. परिभाषा के अनुसार, BFS में अधिकतम m गैर-शून्य चर और कम से कम n-m शून्य चर होते हैं। एक BFS में m से कम गैर-शून्य चर हो सकते हैं; उस स्थिति में, इसके कई अलग-अलग बेसिक हो सकते हैं, जिनमें से सभी में इसके गैर-शून्य चर के सूचकांक सम्मिलित हैं।

3. फीज़बल सलूशन $\mathbf {x}$ यदि-और-केवल-यदि आव्यूह के कॉलम बेसिक हैं $A_{K}$ रैखिक रूप से स्वतंत्र हैं, जहां K गैर-शून्य तत्वों के सूचकांकों का समूह है $\mathbf {x}$ .^[1]

4. प्रत्येक बेसिक एक अद्वितीय BFS निर्धारित करता है: एम सूचकांकों के प्रत्येक बेसिक B के लिए, अधिकतम एक BFS होता है $\mathbf {x_{B}}$ बेसिक B के साथ ऐसा इसलिए है क्योंकि $\mathbf {x_{B}}$ बाधा को पूरा करना होगा $A_{B}\mathbf {x_{B}} =b$ , और बेसिक आव्यूह की परिभाषा के अनुसार $A_{B}$ गैर-एकवचन है, इसलिए बाधा का एक अद्वितीय समाधान है: <ब्लॉककोट> $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ विपरीत सत्य नहीं है: प्रत्येक BFS कई अलग-अलग बेसिकों से आ सकता है। यदि का अनोखा समाधान $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ गैर-नकारात्मकता बाधाओं को संतुष्ट करता है $\mathbf {x_{B}} \geq 0$ , तो B को 'संभाव्य बेसिक' कहा जाता है।

5. यदि एक रैखिक प्रोग्राम का एक ऑप्टीमल समाधान है (अर्थात, इसका एक फीज़बल सलूशन है, और फीज़बल सलूशन का समुच्चय घिरा हुआ है), तो इसमें एक ऑप्टीमल BFS है। यह बाउर अधिकतम सिद्धांत का परिणाम है: एक रैखिक कार्यक्रम का उद्देश्य उत्तल है; फीज़बल सलूशन का समुच्चय उत्तल है (यह हाइपरस्पेस का प्रतिच्छेदन है); इसलिए उद्देश्य फीज़बल सलूशन के समुच्चय के चरम बिंदु पर अपनी अधिकतम सीमा प्राप्त करता है।

चूँकि BFS-s की संख्या सीमित और परिबद्ध है ${\binom {n}{m}}$ किसी भी LP के लिए एक ऑप्टीमल समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है ${\binom {n}{m}}$ BFS-s. LP को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम BFS-s की अधिक कुशल तरीके से जांच करता है।

उदाहरण

निम्नलिखित बाधाओं वाले एक रैखिक कार्यक्रम पर विचार करें:

${\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}$

आव्यूह A है:

$A={\begin{pmatrix}1&5&3&4&6\\0&1&3&5&6\end{pmatrix}}~~~~~\mathbf {b} =(14~~7)$

यहां, m=2 और 2 सूचकांकों के 10 उपसमुच्चय हैं, हालांकि, उनमें से सभी बेसिक नहीं हैं: समुच्चय {3,5} कोई बेसिक नहीं है क्योंकि कॉलम 3 और 5 रैखिक रूप से निर्भर हैं।

आव्यूह के बाद से समुच्चय B={2,4} एक बेसिक है $A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}$ गैर-एकवचन है.

इस बेसिक के अनुरूप अद्वितीय BFS है $x_{B}=(0~~2~~0~~1~~0)$ .

ज्यामितीय व्याख्या

100x100 पिक्सल

सभी फीज़बल सलूशन का समुच्चय आयाम का प्रतिच्छेदन है। इसलिए, यह एक उत्तल बहुफलक है। यदि यह घिरा हुआ है, तो यह एक उत्तल पॉलीटॉप है। प्रत्येक BFS इस पॉलीटोप के एक शीर्ष से मेल खाता है।^[1]

दोहरी समस्या के लिए बेसिक फीज़बल सलूशन

जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक बेसिक B एक अद्वितीय बेसिक फीज़बल सलूशन को परिभाषित करता है $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ . इसी प्रकार, प्रत्येक बेसिक दोहरे रैखिक कार्यक्रम के समाधान को परिभाषित करता है:

छोटा करना

{\textstyle \mathbf {b^{T}} \mathbf {y} }

का विषय है

A^{T}\mathbf {y} \geq \mathbf {c}

.

समाधान है $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ .

एक ऑप्टीमल BFS ढूँढना

BFS खोजने के लिए कई तरीके हैं जो ऑप्टीमल भी हैं।

सिम्प्लेक्स एल्गोरिथ्म का उपयोग करना

व्यवहार में, ऑप्टीमल BFS खोजने का सबसे आसान तरीका सिंप्लेक्स एल्गोरिदम का उपयोग करना है। यह अपने निष्पादन के प्रत्येक बिंदु पर, एक वर्तमान बेसिक B (n चर में से m का एक उपसमूह), एक वर्तमान BFS और एक वर्तमान झांकी रखता है। झांकी रैखिक कार्यक्रम का प्रतिनिधित्व है जहां बेसिक चर को गैर-बेसिक के संदर्भ में व्यक्त किया जाता है:^[1]

{\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}

जहाँ

x_{B}

m मूल चर का वेक्टर है,

x_{N}

n गैर-बेसिक चर का वेक्टर है, और

z

अधिकतमीकरण उद्देश्य है. चूंकि गैर-बेसिक चर 0 के बराबर हैं, वर्तमान BFS है

p

, और वर्तमान अधिकतमीकरण उद्देश्य है

z_{0}

.

यदि सभी गुणांक में $r$ तो फिर, नकारात्मक हैं $z_{0}$ एक ऑप्टीमल समाधान है, क्योंकि सभी चर (सभी गैर-बेसिक चर सहित) कम से कम 0 होने चाहिए, इसलिए दूसरी पंक्ति का तात्पर्य है $z\leq z_{0}$ .

यदि कुछ गुणांक में $r$ सकारात्मक हैं, तो अधिकतमीकरण लक्ष्य को बढ़ाना संभव हो सकता है। उदाहरण के लिए, यदि $x_{5}$ गैर-बेसिक है और इसका गुणांक है $r$ सकारात्मक है, तो इसे 0 से ऊपर बढ़ाने पर बन सकता है $z$ बड़ा. यदि अन्य बाधाओं का उल्लंघन किए बिना ऐसा करना संभव है, तो बढ़ा हुआ चर बेसिक हो जाता है (यह बेसिक में प्रवेश करता है), जबकि समानता की बाधाओं को बनाए रखने के लिए कुछ बेसिक चर को घटाकर 0 कर दिया जाता है और इस प्रकार गैर-बेसिक बन जाता है (यह बेसिक से बाहर हो जाता है)।

यदि यह प्रक्रिया सावधानीपूर्वक की जाए तो इसकी गारंटी संभव है $z$ तब तक बढ़ता है जब तक यह ऑप्टीमल BFS तक नहीं पहुंच जाता।

किसी भी ऑप्टीमल समाधान को ऑप्टीमल BFS में परिवर्तित करना

सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। अशक्त बहुपद समय एल्गोरिदम में LP को हल करने के लिए एल्गोरिदम हैं | अशक्त-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे सामान्यतः ऑप्टीमल समाधान लौटाते हैं जो बेसिक नहीं होते हैं।

हालाँकि, LP के किसी भी ऑप्टीमल समाधान को देखते हुए, एक ऑप्टीमल फीज़बल सलूशन ढूंढना आसान है जो बेसिक भी हो।^[2]

एक ऐसा बेसिक ढूंढना जो प्रारंभिक-ऑप्टीमल और दोहरे-ऑप्टीमल दोनों हो

यदि समाधान हो तो LP के बेसिक बी को 'दोहरा-ऑप्टीमल' कहा जाता है $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ दोहरे रैखिक कार्यक्रम का एक ऑप्टीमल समाधान है, अर्थात यह न्यूनतम करता है ${\textstyle \mathbf {b^{T}} \mathbf {y} }$ . सामान्य तौर पर, एक प्रारंभिक-ऑप्टीमल बेसिक आवश्यक रूप से दोहरे-ऑप्टीमल नहीं होता है, और एक दोहरे-ऑप्टीमल बेसिक आवश्यक रूप से प्रारंभिक-ऑप्टीमल नहीं होता है (वास्तव में, एक प्रारंभिक-ऑप्टीमल बेसिक का समाधान दोहरे के लिए भी अव्यवहार्य हो सकता है, और इसके विपरीत)।

अगर दोनों $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ प्राइमल LP का एक ऑप्टीमल BFS है, और $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ दोहरी LP का एक ऑप्टीमल BFS है, तो बेसिक बी को 'PD-ऑप्टीमल' कहा जाता है। ऑप्टीमल समाधान वाले प्रत्येक LP में PD-ऑप्टीमल बेसिक होता है, और यह सिम्प्लेक्स एल्गोरिदम द्वारा पाया जाता है। हालाँकि, सबसे खराब स्थिति में इसका रन-टाइम तेजी से बढ़ता है। निम्रोद मेगिद्दो ने निम्नलिखित प्रमेय सिद्ध किये:^[2]

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

यदि एक सशक्त बहुपद समय एल्गोरिथ्म उपस्थित है जो केवल प्रारंभिक LP (या केवल दोहरी LP) के लिए एक ऑप्टीमल समाधान इनपुट करता है और एक ऑप्टीमल बेसिक देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम उपस्थित है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।

मेगिद्दो के एल्गोरिदम को सिम्प्लेक्स एल्गोरिदम की तरह ही एक झांकी का उपयोग करके निष्पादित किया जा सकता है।

बाहरी संबंध

How to move from an optimal feasible solution to an optimal basic feasible solution. Paul Robin, Operations Research Stack Exchange.

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.^: 44–48
↑ ^2.0 ^2.1 Megiddo, Nimrod (1991-02-01). "प्रारंभिक और दोहरे इष्टतम आधार खोजने पर". ORSA Journal on Computing. 3 (1): 63–65. doi:10.1287/ijoc.3.1.63. ISSN 0899-1499.

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

[:0-2] 2.0 ^2.1 Megiddo, Nimrod (1991-02-01). "प्रारंभिक और दोहरे इष्टतम आधार खोजने पर". ORSA Journal on Computing. 3 (1): 63–65. doi:10.1287/ijoc.3.1.63. ISSN 0899-1499.

[1]

[2]

@@ Line 1: / Line 1: @@
-{{one source|date=December 2018}}
+[[रैखिक प्रोग्रामिंग|लीनियर प्रोग्रामिंग]] के सिद्धांत में, '''बेसिक''' '''फीज़बल सलूशन''' ('''BFS/BFS)''' या '''बेसिकभूत सुसंगत हल'''   गैर-शून्य चर के न्यूनतम समुच्चय वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक BFS फीज़बल सलूशन के[[ बहुतल ]]के एक कोने से मेल खाता है। यदि कोई ऑप्टीमल (इष्टतम) समाधान उपस्थित है, तो एक ऑप्टीमल BFS भी उपस्थित है। इसलिए, एक ऑप्टीमल समाधान खोजने के लिए, BFS-s पर विचार करना पर्याप्त है। इस तथ्य का उपयोग [[सिम्प्लेक्स एल्गोरिथ्म]] द्वारा किया जाता है, जो अनिवार्य रूप से एक ऑप्टीमल समाधान मिलने तक एक BFS से दूसरे तक यात्रा करता है।<ref name=gm06>{{Cite Gartner Matousek 2006}}{{rp|44–48}}</ref>
-[[रैखिक प्रोग्रामिंग]] के सिद्धांत में, एक बुनियादी व्यवहार्य समाधान (बीएफएस) गैर-शून्य चर के न्यूनतम सेट वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक बीएफएस व्यवहार्य समाधानों के [[ बहुतल ]] के एक कोने से मेल खाता है। यदि कोई इष्टतम समाधान मौजूद है, तो एक इष्टतम बीएफएस भी मौजूद है। इसलिए, एक इष्टतम समाधान खोजने के लिए, बीएफएस-एस पर विचार करना पर्याप्त है। इस तथ्य का उपयोग [[सिम्प्लेक्स एल्गोरिथ्म]] द्वारा किया जाता है, जो अनिवार्य रूप से एक इष्टतम समाधान मिलने तक एक बीएफएस से दूसरे तक यात्रा करता है।<ref name=gm06>{{Cite Gartner Matousek 2006}}{{rp|44–48}}</ref>
 == परिभाषाएँ ==
-=== प्रारंभिक: रैखिक-स्वतंत्र पंक्तियों के साथ समीकरणात्मक रूप ===
+=== प्रारंभिक: लीनियर-इंडिपेंडेंट रोव के साथ समीकरणात्मक रूप ===
-नीचे दी गई परिभाषाओं के लिए, हम पहले रैखिक कार्यक्रम को तथाकथित समीकरणात्मक रूप में प्रस्तुत करते हैं:
+नीचे दी गई परिभाषाओं के लिए, हम पहले लीनियर प्रोग्राम को तथाकथित ''समीकरणात्मक रूप'' में प्रस्तुत करते हैं:
 :अधिकतम करें <math display="inline">\mathbf{c^T} \mathbf{x}</math>
 :का विषय है <math>A\mathbf{x} = \mathbf{b}</math> और <math>\mathbf{x} \ge 0</math>
-कहाँ:
+जहाँ:
-* <math>\mathbf{c^T}</math> और <math>\mathbf{x}</math> आकार n (चरों की संख्या) के सदिश हैं;
+* <math>\mathbf{c^T}</math> और <math>\mathbf{x}</math> आकार ''n'' (चरों की संख्या) के सदिश हैं;
-* <math>\mathbf{b}</math> आकार m (बाधाओं की संख्या) का एक वेक्टर है;
+* <math>\mathbf{b}</math> आकार ''m'' (बाधाओं की संख्या) का एक सदिश है;
-* <math>A</math> एक एम-बाय-एन मैट्रिक्स है;
+* <math>A</math> एक ''m''-बाय-''n'' आव्यूह है;
 * <math>\mathbf{x} \ge 0</math> इसका मतलब है कि सभी चर गैर-नकारात्मक हैं।
-किसी भी रैखिक प्रोग्राम को [[ सुस्त चर ]]्स जोड़कर समीकरणीय रूप में परिवर्तित किया जा सकता है।
+किसी भी लीनियर प्रोग्राम को [[ सुस्त चर | स्लैक चर]] जोड़कर समीकरणीय रूप में परिवर्तित किया जा सकता है।
 प्रारंभिक सफ़ाई कदम के रूप में, हम सत्यापित करते हैं कि:
-* प्रणाली <math>A\mathbf{x} = \mathbf{b}</math> कम से कम एक समाधान है (अन्यथा पूरे एलपी के पास कोई समाधान नहीं है और करने के लिए और कुछ नहीं है);
+* प्रणाली <math>A\mathbf{x} = \mathbf{b}</math> कम से कम एक समाधान है (अन्यथा पूरे LP के पास कोई समाधान नहीं है और करने के लिए और कुछ नहीं है);
-* मैट्रिक्स की सभी एम पंक्तियाँ <math>A</math> रैखिक रूप से स्वतंत्र हैं, यानी, इसकी रैंक एम है (अन्यथा हम एलपी को बदले बिना अनावश्यक पंक्तियों को हटा सकते हैं)।
+* आव्यूह की सभी ''m'' रोव <math>A</math> रैखिक रूप से स्वतंत्र हैं, यानी, इसकी रैंक ''m'' है (अन्यथा हम LP को बदले बिना अनावश्यक रोव को हटा सकते हैं)।
 ===संभव समाधान===
-एलपी का एक व्यवहार्य समाधान कोई भी वेक्टर है <math>\mathbf{x} \ge 0</math> ऐसा है कि <math>A\mathbf{x} = \mathbf{b}</math>. हम मानते हैं कि कम से कम एक व्यवहार्य समाधान है। यदि m = n, तो केवल एक ही व्यवहार्य समाधान है। आमतौर पर m < n, इसलिए सिस्टम <math>A\mathbf{x} = \mathbf{b}</math> कई समाधान हैं; ऐसे प्रत्येक समाधान को एलपी का व्यवहार्य समाधान कहा जाता है।
+LP का एक फीज़बल सलूशन कोई भी वेक्टर है <math>\mathbf{x} \ge 0</math> ऐसा है कि <math>A\mathbf{x} = \mathbf{b}</math>. हम मानते हैं कि कम से कम एक फीज़बल सलूशन है। यदि m = n, तो केवल एक ही फीज़बल सलूशन है। सामान्यतः m < n, इसलिए सिस्टम <math>A\mathbf{x} = \mathbf{b}</math> कई समाधान हैं; ऐसे प्रत्येक समाधान को LP का फीज़बल सलूशन कहा जाता है।
-=== आधार ===
+=== '''बेसिक (आधारभूत''') ===
-एलपी का आधार ''ए'' का एक [[उलटा मैट्रिक्स]] सबमैट्रिक्स है जिसमें सभी ''एम'' पंक्तियां और केवल ''एम''<''एन'' कॉलम हैं।
+LP का बेसिक ''A'' का एक [[उलटा मैट्रिक्स|इनवेर्टीबल आव्यूह]]  उपाव्यूह है जिसमें सभी ''m'' पंक्तियां और केवल ''m''<''n'' कॉलम हैं।
-कभी-कभी, आधार शब्द का प्रयोग सबमैट्रिक्स के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के सेट के लिए किया जाता है। मान लीजिए ''B'' {1,...,''n''} से ''m'' सूचकांकों का एक उपसमुच्चय है। द्वारा निरूपित करें <math>A_B</math> वर्ग m-by-m मैट्रिक्स, m कॉलम से बना है <math>A</math> बी द्वारा अनुक्रमित यदि <math>A_B</math> बीजगणितीय वक्र#एकवचन है, बी द्वारा अनुक्रमित स्तंभ [[स्तंभ स्थान]] का एक [[आधार (रैखिक बीजगणित)]] हैं <math>A</math>. इस मामले में, हम बी को 'एलपी का आधार' कहते हैं।
+कभी-कभी, बेसिक शब्द का प्रयोग उपाव्यूह के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के समुच्चय के लिए किया जाता है। मान लीजिए ''B'' {1,...,''n''} से ''m'' सूचकांकों का एक उपसमुच्चय है। द्वारा निरूपित करें <math>A_B</math> वर्ग ''m''-by-''m'' आव्यूह, m कॉलम से बना है <math>A</math> ''B'' द्वारा अनुक्रमित यदि <math>A_B</math> बीजगणितीय वक्र एकवचन है, बी द्वारा अनुक्रमित स्तंभ [[स्तंभ स्थान]] का एक [[आधार (रैखिक बीजगणित)|बेसिक (रैखिक बीजगणित)]] हैं <math>A</math>. इस स्थिति में, हम ''B'' को ''''LP''' '''का बेसिक'''<nowiki/>' कहते हैं।
-के पद से <math>A</math> एम है, इसका कम से कम एक आधार है; तब से <math>A</math> इसमें n कॉलम हैं, इसमें अधिकतम है <math>\binom{n}{m}</math> आधार.
+के पद से <math>A</math> ''m'' है, इसका कम से कम एक बेसिक है; तब से <math>A</math> इसमें ''n'' कॉलम हैं, इसमें अधिकतम है <math>\binom{n}{m}</math> बेसिक.
-=== बुनियादी व्यवहार्य समाधान ===
+=== '''बेसिक''' फीज़बल सलूशन ===
-आधार बी दिए जाने पर, हम कहते हैं कि एक व्यवहार्य समाधान <math>\mathbf{x}</math> आधार बी के साथ एक बुनियादी व्यवहार्य समाधान है यदि इसके सभी गैर-शून्य चर को ''बी'' द्वारा अनुक्रमित किया जाता है, अर्थात सभी के लिए <math>j\not\in B: ~~ x_j = 0</math>.
+बेसिक ''B'' दिए जाने पर, हम कहते हैं कि फीज़बल सलूशन <math>\mathbf{x}</math> '''बेसिक ''B'' के साथ एक बेसिक फीज़बल सलूशन''' है यदि इसके सभी गैर-शून्य चर को ''B'' द्वारा अनुक्रमित किया जाता है, अर्थात सभी के लिए <math>j\not\in B: ~~ x_j = 0</math>.
 == गुण ==
-. एक बीएफएस केवल एलपी (मैट्रिक्स) की बाधाओं से निर्धारित होता है <math>A</math> और वेक्टर <math>\mathbf{b}</math>); यह अनुकूलन उद्देश्य पर निर्भर नहीं है.
+. BFS केवल LP (आव्यूह) की बाधाओं से निर्धारित होता है <math>A</math> और वेक्टर <math>\mathbf{b}</math>); यह अनुकूलन उद्देश्य पर निर्भर नहीं है.
-. परिभाषा के अनुसार, एक BFS में अधिकतम m गैर-शून्य चर और कम से कम n-m शून्य चर होते हैं। एक BFS में m से कम गैर-शून्य चर हो सकते हैं; उस स्थिति में, इसके कई अलग-अलग आधार हो सकते हैं, जिनमें से सभी में इसके गैर-शून्य चर के सूचकांक शामिल हैं।
+. परिभाषा के अनुसार, BFS में अधिकतम ''m'' गैर-शून्य चर और कम से कम n-m शून्य चर होते हैं। एक BFS में m से कम गैर-शून्य चर हो सकते हैं; उस स्थिति में, इसके कई अलग-अलग बेसिक हो सकते हैं, जिनमें से सभी में इसके गैर-शून्य चर के सूचकांक सम्मिलित हैं।
-. एक व्यवहार्य समाधान <math>\mathbf{x}</math> यदि-और-केवल-यदि मैट्रिक्स के कॉलम बुनियादी हैं <math>A_K</math> रैखिक रूप से स्वतंत्र हैं, जहां K गैर-शून्य तत्वों के सूचकांकों का समूह है <math>\mathbf{x}</math>.<ref name="gm06" />{{rp|45}}
+. फीज़बल सलूशन <math>\mathbf{x}</math> यदि-और-केवल-यदि आव्यूह के कॉलम बेसिक हैं <math>A_K</math> रैखिक रूप से स्वतंत्र हैं, जहां K गैर-शून्य तत्वों के सूचकांकों का समूह है <math>\mathbf{x}</math>.<ref name="gm06" />
-. प्रत्येक आधार एक अद्वितीय बीएफएस निर्धारित करता है: एम सूचकांकों के प्रत्येक आधार बी के लिए, अधिकतम एक बीएफएस होता है  <math>\mathbf{x_B}</math> आधार बी के साथ ऐसा इसलिए है क्योंकि <math>\mathbf{x_B}</math> बाधा को पूरा करना होगा <math>A_B \mathbf{x_B} = b</math>, और आधार मैट्रिक्स की परिभाषा के अनुसार <math>A_B</math> गैर-एकवचन है, इसलिए बाधा का एक अद्वितीय समाधान है: <ब्लॉककोट><math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> </blockquote>विपरीत सत्य नहीं है: प्रत्येक बीएफएस कई अलग-अलग आधारों से आ सकता है। यदि का अनोखा समाधान <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> गैर-नकारात्मकता बाधाओं को संतुष्ट करता है <math>\mathbf{x_B} \geq 0</math>, तो B को 'संभाव्य आधार' कहा जाता है।
+. प्रत्येक बेसिक एक अद्वितीय BFS निर्धारित करता है: एम सूचकांकों के प्रत्येक बेसिक ''B'' के लिए, अधिकतम एक BFS होता है  <math>\mathbf{x_B}</math> बेसिक ''B'' के साथ ऐसा इसलिए है क्योंकि <math>\mathbf{x_B}</math> बाधा को पूरा करना होगा <math>A_B \mathbf{x_B} = b</math>, और बेसिक आव्यूह की परिभाषा के अनुसार <math>A_B</math> गैर-एकवचन है, इसलिए बाधा का एक अद्वितीय समाधान है: <ब्लॉककोट><math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> विपरीत सत्य नहीं है: प्रत्येक BFS कई अलग-अलग बेसिकों से आ सकता है। यदि का अनोखा समाधान <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> गैर-नकारात्मकता बाधाओं को संतुष्ट करता है <math>\mathbf{x_B} \geq 0</math>, तो B को 'संभाव्य बेसिक' कहा जाता है।
-. यदि एक रैखिक प्रोग्राम का एक इष्टतम समाधान है (अर्थात, इसका एक व्यवहार्य समाधान है, और व्यवहार्य समाधानों का सेट घिरा हुआ है), तो इसमें एक इष्टतम बीएफएस है। यह [[बाउर अधिकतम सिद्धांत]] का परिणाम है: एक रैखिक कार्यक्रम का उद्देश्य उत्तल है; व्यवहार्य समाधानों का सेट उत्तल है (यह हाइपरस्पेस का प्रतिच्छेदन है); इसलिए उद्देश्य व्यवहार्य समाधानों के सेट के चरम बिंदु पर अपनी अधिकतम सीमा प्राप्त करता है।
+. यदि एक रैखिक प्रोग्राम का एक ऑप्टीमल समाधान है (अर्थात, इसका एक फीज़बल सलूशन है, और फीज़बल सलूशन का समुच्चय घिरा हुआ है), तो इसमें एक ऑप्टीमल BFS है। यह [[बाउर अधिकतम सिद्धांत]] का परिणाम है: एक रैखिक कार्यक्रम का उद्देश्य उत्तल है; फीज़बल सलूशन का समुच्चय उत्तल है (यह हाइपरस्पेस का प्रतिच्छेदन है); इसलिए उद्देश्य फीज़बल सलूशन के समुच्चय के चरम बिंदु पर अपनी अधिकतम सीमा प्राप्त करता है।
-चूँकि BFS-s की संख्या सीमित और परिबद्ध है <math>\binom{n}{m}</math>किसी भी एलपी के लिए एक इष्टतम समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>बीएफएस-एस. एलपी को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम बीएफएस-एस की अधिक कुशल तरीके से जांच करता है।
+चूँकि BFS-s की संख्या सीमित और परिबद्ध है <math>\binom{n}{m}</math>किसी भी LP के लिए एक ऑप्टीमल समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>BFS-s. LP को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम BFS-s की अधिक कुशल तरीके से जांच करता है।
 == उदाहरण ==
@@ Line 57: / Line 56: @@
 \forall i\in\{1,\ldots,5\}: x_i&\geq 0
 \end{align}</math>
-मैट्रिक्स ए है:
+आव्यूह ''A'' है:
 <math>A =
@@ Line 67: / Line 67: @@
 ~~~~~
 \mathbf{b} = (14~~7)</math>
-यहां, m=2 और 2 सूचकांकों के 10 उपसमुच्चय हैं, हालांकि, उनमें से सभी आधार नहीं हैं: सेट {3,5} कोई आधार नहीं है क्योंकि कॉलम 3 और 5 रैखिक रूप से निर्भर हैं।
-मैट्रिक्स के बाद से सेट B={2,4} एक आधार है  <math>A_B =
+यहां, m=2 और 2 सूचकांकों के 10 उपसमुच्चय हैं, हालांकि, उनमें से सभी बेसिक नहीं हैं: समुच्चय {3,5} कोई बेसिक नहीं है क्योंकि कॉलम 3 और 5 रैखिक रूप से निर्भर हैं।
+आव्यूह के बाद से समुच्चय B={2,4} एक बेसिक है  <math>A_B =
 \begin{pmatrix}
 & 4
@@ Line 77: / Line 78: @@
 </math> गैर-एकवचन है.
-इस आधार के अनुरूप अद्वितीय बीएफएस है <math>x_B = (0~~2~~0~~1~~0)
+इस बेसिक के अनुरूप अद्वितीय BFS है <math>x_B = (0~~2~~0~~1~~0)
 </math>.
 ==ज्यामितीय व्याख्या==
-[[File:Elongated pentagonal orthocupolarotunda.png|thumb|100x100 पिक्सल]]सभी व्यवहार्य समाधानों का समुच्चय [[आयाम]] का प्रतिच्छेदन है। इसलिए, यह एक [[उत्तल बहुफलक]] है। यदि यह घिरा हुआ है, तो यह एक उत्तल पॉलीटॉप है। प्रत्येक बीएफएस इस पॉलीटोप के एक शीर्ष से मेल खाता है।<ref name="gm06" />{{rp|53–56}}
+[[File:Elongated pentagonal orthocupolarotunda.png|thumb|100x100 पिक्सल]]सभी फीज़बल सलूशन का समुच्चय [[आयाम]] का प्रतिच्छेदन है। इसलिए, यह एक [[उत्तल बहुफलक]] है। यदि यह घिरा हुआ है, तो यह एक उत्तल पॉलीटॉप है। प्रत्येक BFS इस पॉलीटोप के एक शीर्ष से मेल खाता है।<ref name="gm06" />
-== दोहरी समस्या के लिए बुनियादी व्यवहार्य समाधान ==
+== दोहरी समस्या के लिए बेसिक फीज़बल सलूशन ==
-जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक आधार बी एक अद्वितीय बुनियादी व्यवहार्य समाधान को परिभाषित करता है <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> . इसी प्रकार, प्रत्येक आधार दोहरे रैखिक कार्यक्रम के समाधान को परिभाषित करता है:
+जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक बेसिक B एक अद्वितीय बेसिक फीज़बल सलूशन को परिभाषित करता है <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> . इसी प्रकार, प्रत्येक बेसिक दोहरे रैखिक कार्यक्रम के समाधान को परिभाषित करता है:
 :छोटा करना <math display="inline">\mathbf{b^T} \mathbf{y}</math>
 :का विषय है <math>A^T\mathbf{y} \geq \mathbf{c}</math>.
 समाधान है <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math>.
-== एक इष्टतम बीएफएस ढूँढना ==
+== एक ऑप्टीमल BFS ढूँढना ==
-बीएफएस खोजने के लिए कई तरीके हैं जो इष्टतम भी हैं।
+BFS खोजने के लिए कई तरीके हैं जो ऑप्टीमल भी हैं।
 === सिम्प्लेक्स एल्गोरिथ्म का उपयोग करना ===
-व्यवहार में, इष्टतम बीएफएस खोजने का सबसे आसान तरीका सिंप्लेक्स एल्गोरिदम का उपयोग करना है। यह अपने निष्पादन के प्रत्येक बिंदु पर, एक वर्तमान आधार बी (एन चर में से एम का एक उपसमूह), एक वर्तमान बीएफएस और एक वर्तमान झांकी रखता है। झांकी रैखिक कार्यक्रम का प्रतिनिधित्व है जहां बुनियादी चर को गैर-बुनियादी के संदर्भ में व्यक्त किया जाता है:<ref name="gm06" />{{rp|65}}<math display="block">\begin{align}
+व्यवहार में, ऑप्टीमल BFS खोजने का सबसे आसान तरीका सिंप्लेक्स एल्गोरिदम का उपयोग करना है। यह अपने निष्पादन के प्रत्येक बिंदु पर, एक वर्तमान बेसिक ''B'' (''n'' चर में से ''m'' का एक उपसमूह), एक वर्तमान BFS और एक वर्तमान झांकी रखता है। झांकी रैखिक कार्यक्रम का प्रतिनिधित्व है जहां बेसिक चर को गैर-बेसिक के संदर्भ में व्यक्त किया जाता है:<ref name="gm06" /><math display="block">\begin{align}
 x_B &= p + Q x_N
 \\
 z &= z_0 + r^T x_N
-\end{align}</math>कहाँ <math>x_B</math> एम मूल चर का वेक्टर है, <math>x_N</math> n गैर-बुनियादी चर का वेक्टर है, और <math>z</math> अधिकतमीकरण उद्देश्य है. चूंकि गैर-बुनियादी चर 0 के बराबर हैं, वर्तमान बीएफएस है <math>p</math>, और वर्तमान अधिकतमीकरण उद्देश्य है <math>z_0</math>.
+\end{align}</math>जहाँ <math>x_B</math> ''m'' मूल चर का वेक्टर है, <math>x_N</math> n गैर-बेसिक चर का वेक्टर है, और <math>z</math> अधिकतमीकरण उद्देश्य है. चूंकि गैर-बेसिक चर 0 के बराबर हैं, वर्तमान BFS है <math>p</math>, और वर्तमान अधिकतमीकरण उद्देश्य है <math>z_0</math>.
+यदि सभी गुणांक में <math>r</math> तो फिर, नकारात्मक हैं <math>z_0</math> एक ऑप्टीमल समाधान है, क्योंकि सभी चर (सभी गैर-बेसिक चर सहित) कम से कम 0 होने चाहिए, इसलिए दूसरी पंक्ति का तात्पर्य है <math>z\leq z_0</math>.
+यदि कुछ गुणांक में <math>r</math> सकारात्मक हैं, तो अधिकतमीकरण लक्ष्य को बढ़ाना संभव हो सकता है। उदाहरण के लिए, यदि <math>x_5</math> गैर-बेसिक है और इसका गुणांक है  <math>r</math> सकारात्मक है, तो इसे 0 से ऊपर बढ़ाने पर बन सकता है <math>z</math> बड़ा. यदि अन्य बाधाओं का उल्लंघन किए बिना ऐसा करना संभव है, तो बढ़ा हुआ चर बेसिक हो जाता है (यह बेसिक में प्रवेश करता है), जबकि समानता की बाधाओं को बनाए रखने के लिए कुछ बेसिक चर को घटाकर 0 कर दिया जाता है और इस प्रकार गैर-बेसिक बन जाता है (यह बेसिक से बाहर हो जाता है)।
-यदि सभी गुणांक में <math>r</math> तो फिर, नकारात्मक हैं <math>z_0</math> एक इष्टतम समाधान है, क्योंकि सभी चर (सभी गैर-बुनियादी चर सहित) कम से कम 0 होने चाहिए, इसलिए दूसरी पंक्ति का तात्पर्य है <math>z\leq z_0</math>.
+यदि यह प्रक्रिया सावधानीपूर्वक की जाए तो इसकी गारंटी संभव है <math>z</math> तब तक बढ़ता है जब तक यह ऑप्टीमल BFS तक नहीं पहुंच जाता।
-यदि कुछ गुणांक में <math>r</math> सकारात्मक हैं, तो अधिकतमीकरण लक्ष्य को बढ़ाना संभव हो सकता है। उदाहरण के लिए, यदि <math>x_5</math> गैर-बुनियादी है और इसका गुणांक है  <math>r</math> सकारात्मक है, तो इसे 0 से ऊपर बढ़ाने पर बन सकता है <math>z</math> बड़ा. यदि अन्य बाधाओं का उल्लंघन किए बिना ऐसा करना संभव है, तो बढ़ा हुआ चर बुनियादी हो जाता है (यह आधार में प्रवेश करता है), जबकि समानता की बाधाओं को बनाए रखने के लिए कुछ बुनियादी चर को घटाकर 0 कर दिया जाता है और इस प्रकार गैर-बुनियादी बन जाता है (यह आधार से बाहर हो जाता है)।
+=== किसी भी ऑप्टीमल समाधान को ऑप्टीमल BFS में परिवर्तित करना ===
+सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। अशक्त बहुपद समय एल्गोरिदम में LP को हल करने के लिए एल्गोरिदम हैं | अशक्त-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे सामान्यतः ऑप्टीमल समाधान लौटाते हैं जो बेसिक नहीं होते हैं।
-यदि यह प्रक्रिया सावधानीपूर्वक की जाए तो इसकी गारंटी संभव है <math>z</math> तब तक बढ़ता है जब तक यह इष्टतम बीएफएस तक नहीं पहुंच जाता।
+हालाँकि, LP के किसी भी ऑप्टीमल समाधान को देखते हुए, एक ऑप्टीमल फीज़बल सलूशन ढूंढना आसान है जो बेसिक भी हो।<ref name=":0" />
-=== किसी भी इष्टतम समाधान को इष्टतम बीएफएस में परिवर्तित करना ===
+=== एक ऐसा बेसिक ढूंढना जो प्रारंभिक-ऑप्टीमल और दोहरे-ऑप्टीमल दोनों हो ===
-सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में एलपी को हल करने के लिए एल्गोरिदम हैं | कमजोर-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे आम तौर पर इष्टतम समाधान लौटाते हैं जो बुनियादी नहीं होते हैं।
+यदि समाधान हो तो LP के बेसिक बी को 'दोहरा-ऑप्टीमल' कहा जाता है <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> दोहरे रैखिक कार्यक्रम का एक ऑप्टीमल समाधान है, अर्थात यह न्यूनतम करता है <math display="inline">\mathbf{b^T} \mathbf{y}</math>. सामान्य तौर पर, एक प्रारंभिक-ऑप्टीमल बेसिक आवश्यक रूप से दोहरे-ऑप्टीमल नहीं होता है, और एक दोहरे-ऑप्टीमल बेसिक आवश्यक रूप से प्रारंभिक-ऑप्टीमल नहीं होता है (वास्तव में, एक प्रारंभिक-ऑप्टीमल बेसिक का समाधान दोहरे के लिए भी अव्यवहार्य हो सकता है, और इसके विपरीत)।
-हालाँकि, एलपी के किसी भी इष्टतम समाधान को देखते हुए, एक इष्टतम व्यवहार्य समाधान ढूंढना आसान है जो बुनियादी भी हो।<ref name=":0" />{{Rp|page=see also "external links" below.}}
+अगर दोनों <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> प्राइमल LP का एक ऑप्टीमल BFS है, और <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> दोहरी LP का एक ऑप्टीमल BFS है, तो बेसिक बी को 'PD-ऑप्टीमल' कहा जाता है। ऑप्टीमल समाधान वाले प्रत्येक LP में PD-ऑप्टीमल बेसिक होता है, और यह सिम्प्लेक्स एल्गोरिदम द्वारा पाया जाता है। हालाँकि, सबसे खराब स्थिति में इसका रन-टाइम तेजी से बढ़ता है। [[निम्रोद मेगिद्दो]] ने निम्नलिखित प्रमेय सिद्ध किये:<ref name=":0">{{Cite journal |last=Megiddo |first=Nimrod |date=1991-02-01 |title=प्रारंभिक और दोहरे इष्टतम आधार खोजने पर|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63 |journal=ORSA Journal on Computing |volume=3 |issue=1 |pages=63–65 |doi=10.1287/ijoc.3.1.63 |issn=0899-1499}}</ref>
-=== एक ऐसा आधार ढूंढना जो प्रारंभिक-इष्टतम और दोहरे-इष्टतम दोनों हो ===
+* एक सशक्त बहुपद समय एल्गोरिदम उपस्थित है जो प्रारंभिक LP के लिए एक ऑप्टीमल समाधान और दोहरे LP के लिए एक ऑप्टीमल समाधान इनपुट करता है, और एक ऑप्टीमल बेसिक देता है।
-यदि समाधान हो तो एलपी के आधार बी को 'दोहरा-इष्टतम' कहा जाता है <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> दोहरे रैखिक कार्यक्रम का एक इष्टतम समाधान है, अर्थात यह न्यूनतम करता है <math display="inline">\mathbf{b^T} \mathbf{y}</math>. सामान्य तौर पर, एक प्रारंभिक-इष्टतम आधार आवश्यक रूप से दोहरे-इष्टतम नहीं होता है, और एक दोहरे-इष्टतम आधार आवश्यक रूप से प्रारंभिक-इष्टतम नहीं होता है (वास्तव में, एक प्रारंभिक-इष्टतम आधार का समाधान दोहरे के लिए भी अव्यवहार्य हो सकता है, और इसके विपरीत)।
-अगर दोनों <math>\mathbf{x_B} = {A_B}^{-1}\cdot b</math> प्राइमल एलपी का एक इष्टतम बीएफएस है, और <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> दोहरी एलपी का एक इष्टतम बीएफएस है, तो आधार बी को 'पीडी-इष्टतम' कहा जाता है। इष्टतम समाधान वाले प्रत्येक एलपी में पीडी-इष्टतम आधार होता है, और यह सिम्प्लेक्स एल्गोरिदम द्वारा पाया जाता है। हालाँकि, सबसे खराब स्थिति में इसका रन-टाइम तेजी से बढ़ता है। [[निम्रोद मेगिद्दो]] ने निम्नलिखित प्रमेय सिद्ध किये:<ref name=":0">{{Cite journal |last=Megiddo |first=Nimrod |date=1991-02-01 |title=प्रारंभिक और दोहरे इष्टतम आधार खोजने पर|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.1.63 |journal=ORSA Journal on Computing |volume=3 |issue=1 |pages=63–65 |doi=10.1287/ijoc.3.1.63 |issn=0899-1499}}</ref> * एक सशक्त बहुपद समय एल्गोरिदम मौजूद है जो प्रारंभिक एलपी के लिए एक इष्टतम समाधान और दोहरे एलपी के लिए एक इष्टतम समाधान इनपुट करता है, और एक इष्टतम आधार देता है।
+* यदि एक सशक्त बहुपद समय एल्गोरिथ्म उपस्थित है जो केवल प्रारंभिक LP (या केवल दोहरी LP) के लिए एक ऑप्टीमल समाधान इनपुट करता है और एक ऑप्टीमल बेसिक देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम उपस्थित है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।
-* यदि एक सशक्त बहुपद समय एल्गोरिथ्म मौजूद है जो केवल प्रारंभिक एलपी (या केवल दोहरी एलपी) के लिए एक इष्टतम समाधान इनपुट करता है और एक इष्टतम आधार देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम मौजूद है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।
 मेगिद्दो के एल्गोरिदम को सिम्प्लेक्स एल्गोरिदम की तरह ही एक झांकी का उपयोग करके निष्पादित किया जा सकता है।
@@ Line 124: / Line 128: @@
 == संदर्भ ==
 {{reflist}}
-[[Category: रैखिक प्रोग्रामिंग]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 25/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:रैखिक प्रोग्रामिंग]]

Anonymous

Search

बेसिक फीज़बल सलूशन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:26, 9 August 2023

Contents

परिभाषाएँ