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

Revision as of 20:17, 30 July 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: @@
-[[रैखिक प्रोग्रामिंग|लीनियर प्रोग्रामिंग]] के सिद्धांत में, एक '''बेसिक''' '''फीज़बल सलूशन''' ('''BFS/BFS)''' या '''बेसिकभूत सुसंगत हल'''   गैर-शून्य चर के न्यूनतम सेट वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक BFS फीज़बल सलूशन के[[ बहुतल ]]के एक कोने से मेल खाता है। यदि कोई इष्टतम समाधान उपस्थित है, तो एक इष्टतम BFS भी उपस्थित है। इसलिए, एक इष्टतम समाधान खोजने के लिए, BFS-s पर विचार करना पर्याप्त है। इस तथ्य का उपयोग [[सिम्प्लेक्स एल्गोरिथ्म]] द्वारा किया जाता है, जो अनिवार्य रूप से एक इष्टतम समाधान मिलने तक एक BFS से दूसरे तक यात्रा करता है।<ref name=gm06>{{Cite Gartner Matousek 2006}}{{rp|44–48}}</ref>
+[[रैखिक प्रोग्रामिंग|लीनियर प्रोग्रामिंग]] के सिद्धांत में, '''बेसिक''' '''फीज़बल सलूशन''' ('''BFS/BFS)''' या '''बेसिकभूत सुसंगत हल'''   गैर-शून्य चर के न्यूनतम समुच्चय वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक BFS फीज़बल सलूशन के[[ बहुतल ]]के एक कोने से मेल खाता है। यदि कोई ऑप्टीमल (इष्टतम) समाधान उपस्थित है, तो एक ऑप्टीमल BFS भी उपस्थित है। इसलिए, एक ऑप्टीमल समाधान खोजने के लिए, BFS-s पर विचार करना पर्याप्त है। इस तथ्य का उपयोग [[सिम्प्लेक्स एल्गोरिथ्म]] द्वारा किया जाता है, जो अनिवार्य रूप से एक ऑप्टीमल समाधान मिलने तक एक BFS से दूसरे तक यात्रा करता है।<ref name=gm06>{{Cite Gartner Matousek 2006}}{{rp|44–48}}</ref>
@@ Line 26: / Line 26: @@
 LP का बेसिक ''A'' का एक [[उलटा मैट्रिक्स|इनवेर्टीबल आव्यूह]]  उपाव्यूह है जिसमें सभी ''m'' पंक्तियां और केवल ''m''<''n'' कॉलम हैं।
-कभी-कभी, बेसिक शब्द का प्रयोग उपाव्यूह के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के सेट के लिए किया जाता है। मान लीजिए ''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/>' कहते हैं।
+कभी-कभी, बेसिक शब्द का प्रयोग उपाव्यूह के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के समुच्चय के लिए किया जाता है। मान लीजिए ''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> ''m'' है, इसका कम से कम एक बेसिक है; तब से <math>A</math> इसमें ''n'' कॉलम हैं, इसमें अधिकतम है <math>\binom{n}{m}</math> बेसिक.
 === '''बेसिक''' फीज़बल सलूशन ===
-बेसिक ''B'' दिए जाने पर, हम कहते हैं कि एक फीज़बल सलूशन <math>\mathbf{x}</math> '''बेसिक ''B'' के साथ एक बेसिक फीज़बल सलूशन''' है यदि इसके सभी गैर-शून्य चर को ''B'' द्वारा अनुक्रमित किया जाता है, अर्थात सभी के लिए <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>.
 == गुण ==
-. एक BFS केवल LP (आव्यूह) की बाधाओं से निर्धारित होता है <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" />
+. फीज़बल सलूशन <math>\mathbf{x}</math> यदि-और-केवल-यदि आव्यूह के कॉलम बेसिक हैं <math>A_K</math> रैखिक रूप से स्वतंत्र हैं, जहां K गैर-शून्य तत्वों के सूचकांकों का समूह है <math>\mathbf{x}</math>.<ref name="gm06" />
 . प्रत्येक बेसिक एक अद्वितीय 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 है। यह [[बाउर अधिकतम सिद्धांत]] का परिणाम है: एक रैखिक कार्यक्रम का उद्देश्य उत्तल है; फीज़बल सलूशन का समुच्चय उत्तल है (यह हाइपरस्पेस का प्रतिच्छेदन है); इसलिए उद्देश्य फीज़बल सलूशन के समुच्चय के चरम बिंदु पर अपनी अधिकतम सीमा प्राप्त करता है।
-चूँकि BFS-s की संख्या सीमित और परिबद्ध है <math>\binom{n}{m}</math>किसी भी LP के लिए एक इष्टतम समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>BFS-एस. LP को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम BFS-s की अधिक कुशल तरीके से जांच करता है।
+चूँकि BFS-s की संख्या सीमित और परिबद्ध है <math>\binom{n}{m}</math>किसी भी LP के लिए एक ऑप्टीमल समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>BFS-s. LP को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम BFS-s की अधिक कुशल तरीके से जांच करता है।
 == उदाहरण ==
@@ Line 56: / Line 56: @@
 \forall i\in\{1,\ldots,5\}: x_i&\geq 0
 \end{align}</math>
-आव्यूह ए है:
+आव्यूह ''A'' है:
 <math>A =
@@ Line 67: / Line 68: @@
 \mathbf{b} = (14~~7)</math>
-यहां, m=2 और 2 सूचकांकों के 10 उपसमुच्चय हैं, हालांकि, उनमें से सभी बेसिक नहीं हैं: सेट {3,5} कोई बेसिक नहीं है क्योंकि कॉलम 3 और 5 रैखिक रूप से निर्भर हैं।
+यहां, m=2 और 2 सूचकांकों के 10 उपसमुच्चय हैं, हालांकि, उनमें से सभी बेसिक नहीं हैं: समुच्चय {3,5} कोई बेसिक नहीं है क्योंकि कॉलम 3 और 5 रैखिक रूप से निर्भर हैं।
-आव्यूह के बाद से सेट B={2,4} एक बेसिक है  <math>A_B =
+आव्यूह के बाद से समुच्चय B={2,4} एक बेसिक है  <math>A_B =
 \begin{pmatrix}
 & 4
@@ Line 89: / Line 90: @@
 समाधान है <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math>.
-== एक इष्टतम BFS ढूँढना ==
+== एक ऑप्टीमल BFS ढूँढना ==
-BFS खोजने के लिए कई तरीके हैं जो इष्टतम भी हैं।
+BFS खोजने के लिए कई तरीके हैं जो ऑप्टीमल भी हैं।
 === सिम्प्लेक्स एल्गोरिथ्म का उपयोग करना ===
-व्यवहार में, इष्टतम BFS खोजने का सबसे आसान तरीका सिंप्लेक्स एल्गोरिदम का उपयोग करना है। यह अपने निष्पादन के प्रत्येक बिंदु पर, एक वर्तमान बेसिक ''B'' (''n'' चर में से ''m'' का एक उपसमूह), एक वर्तमान BFS और एक वर्तमान झांकी रखता है। झांकी रैखिक कार्यक्रम का प्रतिनिधित्व है जहां बेसिक चर को गैर-बेसिक के संदर्भ में व्यक्त किया जाता है:<ref name="gm06" /><math display="block">\begin{align}
+व्यवहार में, ऑप्टीमल BFS खोजने का सबसे आसान तरीका सिंप्लेक्स एल्गोरिदम का उपयोग करना है। यह अपने निष्पादन के प्रत्येक बिंदु पर, एक वर्तमान बेसिक ''B'' (''n'' चर में से ''m'' का एक उपसमूह), एक वर्तमान BFS और एक वर्तमान झांकी रखता है। झांकी रैखिक कार्यक्रम का प्रतिनिधित्व है जहां बेसिक चर को गैर-बेसिक के संदर्भ में व्यक्त किया जाता है:<ref name="gm06" /><math display="block">\begin{align}
 x_B &= p + Q x_N
 \\
@@ Line 99: / Line 100: @@
 \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>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>z</math> तब तक बढ़ता है जब तक यह इष्टतम BFS तक नहीं पहुंच जाता।
+यदि यह प्रक्रिया सावधानीपूर्वक की जाए तो इसकी गारंटी संभव है <math>z</math> तब तक बढ़ता है जब तक यह ऑप्टीमल BFS तक नहीं पहुंच जाता।
+=== किसी भी ऑप्टीमल समाधान को ऑप्टीमल BFS में परिवर्तित करना ===
+सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। अशक्त बहुपद समय एल्गोरिदम में LP को हल करने के लिए एल्गोरिदम हैं | अशक्त-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे सामान्यतः ऑप्टीमल समाधान लौटाते हैं जो बेसिक नहीं होते हैं।
+हालाँकि, LP के किसी भी ऑप्टीमल समाधान को देखते हुए, एक ऑप्टीमल फीज़बल सलूशन ढूंढना आसान है जो बेसिक भी हो।<ref name=":0" />
-=== किसी भी इष्टतम समाधान को इष्टतम BFS में परिवर्तित करना ===
+=== एक ऐसा बेसिक ढूंढना जो प्रारंभिक-ऑप्टीमल और दोहरे-ऑप्टीमल दोनों हो ===
-सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में LP को हल करने के लिए एल्गोरिदम हैं | कमजोर-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे सामान्यतः इष्टतम समाधान लौटाते हैं जो बेसिक नहीं होते हैं।
+यदि समाधान हो तो LP के बेसिक बी को 'दोहरा-ऑप्टीमल' कहा जाता है <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> दोहरे रैखिक कार्यक्रम का एक ऑप्टीमल समाधान है, अर्थात यह न्यूनतम करता है <math display="inline">\mathbf{b^T} \mathbf{y}</math>. सामान्य तौर पर, एक प्रारंभिक-ऑप्टीमल बेसिक आवश्यक रूप से दोहरे-ऑप्टीमल नहीं होता है, और एक दोहरे-ऑप्टीमल बेसिक आवश्यक रूप से प्रारंभिक-ऑप्टीमल नहीं होता है (वास्तव में, एक प्रारंभिक-ऑप्टीमल बेसिक का समाधान दोहरे के लिए भी अव्यवहार्य हो सकता है, और इसके विपरीत)।
-हालाँकि, LP के किसी भी इष्टतम समाधान को देखते हुए, एक इष्टतम फीज़बल सलूशन ढूंढना आसान है जो बेसिक भी हो।<ref name=":0" />
+अगर दोनों <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 के लिए एक ऑप्टीमल समाधान इनपुट करता है, और एक ऑप्टीमल बेसिक देता है।
-यदि समाधान हो तो 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> प्राइमल LP का एक इष्टतम BFS है, और <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> दोहरी LP का एक इष्टतम BFS है, तो बेसिक बी को 'पीडी-इष्टतम' कहा जाता है। इष्टतम समाधान वाले प्रत्येक LP में पीडी-इष्टतम बेसिक होता है, और यह सिम्प्लेक्स एल्गोरिदम द्वारा पाया जाता है। हालाँकि, सबसे खराब स्थिति में इसका रन-टाइम तेजी से बढ़ता है। [[निम्रोद मेगिद्दो]] ने निम्नलिखित प्रमेय सिद्ध किये:<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 के लिए एक इष्टतम समाधान इनपुट करता है, और एक इष्टतम बेसिक देता है।
+* यदि एक सशक्त बहुपद समय एल्गोरिथ्म उपस्थित है जो केवल प्रारंभिक LP (या केवल दोहरी LP) के लिए एक ऑप्टीमल समाधान इनपुट करता है और एक ऑप्टीमल बेसिक देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम उपस्थित है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।
-* यदि एक सशक्त बहुपद समय एल्गोरिथ्म उपस्थित है जो केवल प्रारंभिक LP (या केवल दोहरी LP) के लिए एक इष्टतम समाधान इनपुट करता है और एक इष्टतम बेसिक देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम उपस्थित है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।
 मेगिद्दो के एल्गोरिदम को सिम्प्लेक्स एल्गोरिदम की तरह ही एक झांकी का उपयोग करके निष्पादित किया जा सकता है।

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 20:17, 30 July 2023

Contents

परिभाषाएँ