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

Revision as of 10:12, 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-एस. 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={\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 है, तो बेसिक बी को 'पीडी-इष्टतम' कहा जाता है। इष्टतम समाधान वाले प्रत्येक LP में पीडी-इष्टतम बेसिक होता है, और यह सिम्प्लेक्स एल्गोरिदम द्वारा पाया जाता है। हालाँकि, सबसे खराब स्थिति में इसका रन-टाइम तेजी से बढ़ता है। निम्रोद मेगिद्दो ने निम्नलिखित प्रमेय सिद्ध किये:^[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: @@
-[[रैखिक प्रोग्रामिंग|लीनियर प्रोग्रामिंग]] के सिद्धांत में, एक बेसिक फैसिबल सलूशन (बीएफएस) गैर-शून्य चर के न्यूनतम सेट वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक बीएफएस व्यवहार्य समाधानों के[[ बहुतल ]]के एक कोने से मेल खाता है। यदि कोई इष्टतम समाधान उपस्थित है, तो एक इष्टतम बीएफएस भी उपस्थित है। इसलिए, एक इष्टतम समाधान खोजने के लिए, बीएफएस-एस पर विचार करना पर्याप्त है। इस तथ्य का उपयोग [[सिम्प्लेक्स एल्गोरिथ्म]] द्वारा किया जाता है, जो अनिवार्य रूप से एक इष्टतम समाधान मिलने तक एक बीएफएस से दूसरे तक यात्रा करता है।<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 5: / Line 5: @@
 === प्रारंभिक: लीनियर-इंडिपेंडेंट रोव के साथ समीकरणात्मक रूप ===
-नीचे दी गई परिभाषाओं के लिए, हम पहले लीनियर प्रोग्राम को तथाकथित समीकरणात्मक रूप में प्रस्तुत करते हैं:
+नीचे दी गई परिभाषाओं के लिए, हम पहले लीनियर प्रोग्राम को तथाकथित ''समीकरणात्मक रूप'' में प्रस्तुत करते हैं:
 :अधिकतम करें <math display="inline">\mathbf{c^T} \mathbf{x}</math>
 :का विषय है <math>A\mathbf{x} = \mathbf{b}</math> और <math>\mathbf{x} \ge 0</math>
@@ Line 21: / Line 21: @@
 ===संभव समाधान===
-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 का एक फीज़बल सलूशन कोई भी वेक्टर है <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 का आधार ''ए'' का एक [[उलटा मैट्रिक्स|उलटा आव्यूह]] सबआव्यूह है जिसमें सभी ''एम'' पंक्तियां और केवल ''एम''<''एन'' कॉलम हैं।
+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>. इस स्थिति में, हम बी को 'LP का आधार' कहते हैं।
+कभी-कभी, बेसिक शब्द का प्रयोग उपाव्यूह के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के सेट के लिए किया जाता है। मान लीजिए ''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>.
 == गुण ==
-. एक बीएफएस केवल 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" />
-. प्रत्येक आधार एक अद्वितीय बीएफएस निर्धारित करता है: एम सूचकांकों के प्रत्येक आधार बी के लिए, अधिकतम एक बीएफएस होता है  <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> विपरीत सत्य नहीं है: प्रत्येक बीएफएस कई अलग-अलग आधारों से आ सकता है। यदि का अनोखा समाधान <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>किसी भी LP के लिए एक इष्टतम समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>बीएफएस-एस. LP को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम बीएफएस-एस की अधिक कुशल तरीके से जांच करता है।
+चूँकि BFS-s की संख्या सीमित और परिबद्ध है <math>\binom{n}{m}</math>किसी भी LP के लिए एक इष्टतम समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>BFS-एस. LP को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम BFS-s की अधिक कुशल तरीके से जांच करता है।
 == उदाहरण ==
@@ Line 66: / Line 66: @@
 ~~~~~
 \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 76: / Line 77: @@
 </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" />
+[[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" /><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>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>x_5</math> गैर-बेसिक है और इसका गुणांक है  <math>r</math> सकारात्मक है, तो इसे 0 से ऊपर बढ़ाने पर बन सकता है <math>z</math> बड़ा. यदि अन्य बाधाओं का उल्लंघन किए बिना ऐसा करना संभव है, तो बढ़ा हुआ चर बेसिक हो जाता है (यह बेसिक में प्रवेश करता है), जबकि समानता की बाधाओं को बनाए रखने के लिए कुछ बेसिक चर को घटाकर 0 कर दिया जाता है और इस प्रकार गैर-बेसिक बन जाता है (यह बेसिक से बाहर हो जाता है)।
-यदि यह प्रक्रिया सावधानीपूर्वक की जाए तो इसकी गारंटी संभव है <math>z</math> तब तक बढ़ता है जब तक यह इष्टतम बीएफएस तक नहीं पहुंच जाता।
+यदि यह प्रक्रिया सावधानीपूर्वक की जाए तो इसकी गारंटी संभव है <math>z</math> तब तक बढ़ता है जब तक यह इष्टतम BFS तक नहीं पहुंच जाता।
-=== किसी भी इष्टतम समाधान को इष्टतम बीएफएस में परिवर्तित करना ===
+=== किसी भी इष्टतम समाधान को इष्टतम BFS में परिवर्तित करना ===
-सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में LP को हल करने के लिए एल्गोरिदम हैं | कमजोर-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे सामान्यतः इष्टतम समाधान लौटाते हैं जो बुनियादी नहीं होते हैं।
+सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में LP को हल करने के लिए एल्गोरिदम हैं | कमजोर-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे सामान्यतः इष्टतम समाधान लौटाते हैं जो बेसिक नहीं होते हैं।
-हालाँकि, LP के किसी भी इष्टतम समाधान को देखते हुए, एक इष्टतम व्यवहार्य समाधान ढूंढना आसान है जो बुनियादी भी हो।<ref name=":0" />
+हालाँकि, 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>. सामान्य तौर पर, एक प्रारंभिक-इष्टतम आधार आवश्यक रूप से दोहरे-इष्टतम नहीं होता है, और एक दोहरे-इष्टतम आधार आवश्यक रूप से प्रारंभिक-इष्टतम नहीं होता है (वास्तव में, एक प्रारंभिक-इष्टतम आधार का समाधान दोहरे के लिए भी अव्यवहार्य हो सकता है, और इसके विपरीत)।
+यदि समाधान हो तो 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 का एक इष्टतम बीएफएस है, और <math>\mathbf{y_B} = {A^T_B}^{-1}\cdot c</math> दोहरी LP का एक इष्टतम बीएफएस है, तो आधार बी को 'पीडी-इष्टतम' कहा जाता है। इष्टतम समाधान वाले प्रत्येक 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 के लिए एक इष्टतम समाधान इनपुट करता है, और एक इष्टतम आधार देता है।
+अगर दोनों <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 10:12, 30 July 2023

Contents

परिभाषाएँ