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

Revision as of 01:34, 30 July 2023

लीनियर प्रोग्रामिंग के सिद्धांत में, एक बेसिक फैसिबल सलूशन (बीएफएस) गैर-शून्य चर के न्यूनतम सेट वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक बीएफएस व्यवहार्य समाधानों केबहुतल के एक कोने से मेल खाता है। यदि कोई इष्टतम समाधान उपस्थित है, तो एक इष्टतम बीएफएस भी उपस्थित है। इसलिए, एक इष्टतम समाधान खोजने के लिए, बीएफएस-एस पर विचार करना पर्याप्त है। इस तथ्य का उपयोग सिम्प्लेक्स एल्गोरिथ्म द्वारा किया जाता है, जो अनिवार्य रूप से एक इष्टतम समाधान मिलने तक एक बीएफएस से दूसरे तक यात्रा करता है।^[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 का आधार ए का एक उलटा आव्यूह सबआव्यूह है जिसमें सभी एम पंक्तियां और केवल एम<एन कॉलम हैं।

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

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

बुनियादी व्यवहार्य समाधान

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

गुण

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

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

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

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

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

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

उदाहरण

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

${\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}}$ गैर-एकवचन है.

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

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

100x100 पिक्सल

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

दोहरी समस्या के लिए बुनियादी व्यवहार्य समाधान

जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक आधार बी एक अद्वितीय बुनियादी व्यवहार्य समाधान को परिभाषित करता है $\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$ .

एक इष्टतम बीएफएस ढूँढना

बीएफएस खोजने के लिए कई तरीके हैं जो इष्टतम भी हैं।

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

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

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

जहाँ

x_{B}

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

x_{N}

n गैर-बुनियादी चर का वेक्टर है, और

z

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

p

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

z_{0}

.

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

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

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

किसी भी इष्टतम समाधान को इष्टतम बीएफएस में परिवर्तित करना

सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में 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 का एक इष्टतम बीएफएस है, और $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ दोहरी LP का एक इष्टतम बीएफएस है, तो आधार बी को 'पीडी-इष्टतम' कहा जाता है। इष्टतम समाधान वाले प्रत्येक 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: @@
-{{one source|date=December 2018}}
+[[रैखिक प्रोग्रामिंग|लीनियर प्रोग्रामिंग]] के सिद्धांत में, एक बेसिक फैसिबल सलूशन (बीएफएस) गैर-शून्य चर के न्यूनतम सेट वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक बीएफएस व्यवहार्य समाधानों के[[ बहुतल ]]के एक कोने से मेल खाता है। यदि कोई इष्टतम समाधान उपस्थित है, तो एक इष्टतम बीएफएस भी उपस्थित है। इसलिए, एक इष्टतम समाधान खोजने के लिए, बीएफएस-एस पर विचार करना पर्याप्त है। इस तथ्य का उपयोग [[सिम्प्लेक्स एल्गोरिथ्म]] द्वारा किया जाता है, जो अनिवार्य रूप से एक इष्टतम समाधान मिलने तक एक बीएफएस से दूसरे तक यात्रा करता है।<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 का आधार ''ए'' का एक [[उलटा मैट्रिक्स|उलटा आव्यूह]] सबआव्यूह है जिसमें सभी ''एम'' पंक्तियां और केवल ''एम''<''एन'' कॉलम हैं।
-कभी-कभी, आधार शब्द का प्रयोग सबमैट्रिक्स के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के सेट के लिए किया जाता है। मान लीजिए ''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> बी द्वारा अनुक्रमित यदि <math>A_B</math> बीजगणितीय वक्र#एकवचन है, बी द्वारा अनुक्रमित स्तंभ [[स्तंभ स्थान]] का एक [[आधार (रैखिक बीजगणित)]] हैं <math>A</math>. इस स्थिति में, हम बी को 'LP का आधार' कहते हैं।
 के पद से <math>A</math> एम है, इसका कम से कम एक आधार है; तब से <math>A</math> इसमें n कॉलम हैं, इसमें अधिकतम है <math>\binom{n}{m}</math> आधार.
@@ Line 35: / Line 34: @@
 == गुण ==
-. एक बीएफएस केवल एलपी (मैट्रिक्स) की बाधाओं से निर्धारित होता है <math>A</math> और वेक्टर <math>\mathbf{b}</math>); यह अनुकूलन उद्देश्य पर निर्भर नहीं है.
+. एक बीएफएस केवल LP (आव्यूह) की बाधाओं से निर्धारित होता है <math>A</math> और वेक्टर <math>\mathbf{b}</math>); यह अनुकूलन उद्देश्य पर निर्भर नहीं है.
 . परिभाषा के अनुसार, एक 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 को 'संभाव्य आधार' कहा जाता है।
+. प्रत्येक आधार एक अद्वितीय बीएफएस निर्धारित करता है: एम सूचकांकों के प्रत्येक आधार बी के लिए, अधिकतम एक बीएफएस होता है  <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-s की संख्या सीमित और परिबद्ध है <math>\binom{n}{m}</math>किसी भी एलपी के लिए एक इष्टतम समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>बीएफएस-एस. एलपी को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम बीएफएस-एस की अधिक कुशल तरीके से जांच करता है।
+चूँकि BFS-s की संख्या सीमित और परिबद्ध है <math>\binom{n}{m}</math>किसी भी LP के लिए एक इष्टतम समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है <math>\binom{n}{m}</math>बीएफएस-एस. LP को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम बीएफएस-एस की अधिक कुशल तरीके से जांच करता है।
 == उदाहरण ==
@@ Line 57: / Line 56: @@
 \forall i\in\{1,\ldots,5\}: x_i&\geq 0
 \end{align}</math>
-मैट्रिक्स ए है:
+आव्यूह ए है:
 <math>A =
@@ Line 69: / Line 68: @@
 यहां, m=2 और 2 सूचकांकों के 10 उपसमुच्चय हैं, हालांकि, उनमें से सभी आधार नहीं हैं: सेट {3,5} कोई आधार नहीं है क्योंकि कॉलम 3 और 5 रैखिक रूप से निर्भर हैं।
-मैट्रिक्स के बाद से सेट B={2,4} एक आधार है  <math>A_B =
+आव्यूह के बाद से सेट B={2,4} एक आधार है  <math>A_B =
 \begin{pmatrix}
 & 4
@@ Line 97: / Line 96: @@
 \\
 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> एम मूल चर का वेक्टर है, <math>x_N</math> n गैर-बुनियादी चर का वेक्टर है, और <math>z</math> अधिकतमीकरण उद्देश्य है. चूंकि गैर-बुनियादी चर 0 के बराबर हैं, वर्तमान बीएफएस है <math>p</math>, और वर्तमान अधिकतमीकरण उद्देश्य है <math>z_0</math>.
 यदि सभी गुणांक में <math>r</math> तो फिर, नकारात्मक हैं <math>z_0</math> एक इष्टतम समाधान है, क्योंकि सभी चर (सभी गैर-बुनियादी चर सहित) कम से कम 0 होने चाहिए, इसलिए दूसरी पंक्ति का तात्पर्य है <math>z\leq z_0</math>.
@@ Line 106: / Line 105: @@
 === किसी भी इष्टतम समाधान को इष्टतम बीएफएस में परिवर्तित करना ===
-सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में एलपी को हल करने के लिए एल्गोरिदम हैं | कमजोर-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे आम तौर पर इष्टतम समाधान लौटाते हैं जो बुनियादी नहीं होते हैं।
+सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में LP को हल करने के लिए एल्गोरिदम हैं | कमजोर-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे सामान्यतः इष्टतम समाधान लौटाते हैं जो बुनियादी नहीं होते हैं।
-हालाँकि, एलपी के किसी भी इष्टतम समाधान को देखते हुए, एक इष्टतम व्यवहार्य समाधान ढूंढना आसान है जो बुनियादी भी हो।<ref name=":0" />
+हालाँकि, LP के किसी भी इष्टतम समाधान को देखते हुए, एक इष्टतम व्यवहार्य समाधान ढूंढना आसान है जो बुनियादी भी हो।<ref name=":0" />
 === एक ऐसा आधार ढूंढना जो प्रारंभिक-इष्टतम और दोहरे-इष्टतम दोनों हो ===
-यदि समाधान हो तो एलपी के आधार बी को 'दोहरा-इष्टतम' कहा जाता है <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> प्राइमल एलपी का एक इष्टतम बीएफएस है, और <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> * एक सशक्त बहुपद समय एल्गोरिदम मौजूद है जो प्रारंभिक एलपी के लिए एक इष्टतम समाधान और दोहरे एलपी के लिए एक इष्टतम समाधान इनपुट करता है, और एक इष्टतम आधार देता है।
+अगर दोनों <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 के लिए एक इष्टतम समाधान इनपुट करता है, और एक इष्टतम आधार देता है।
-* यदि एक सशक्त बहुपद समय एल्गोरिथ्म मौजूद है जो केवल प्रारंभिक एलपी (या केवल दोहरी एलपी) के लिए एक इष्टतम समाधान इनपुट करता है और एक इष्टतम आधार देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम मौजूद है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।
+* यदि एक सशक्त बहुपद समय एल्गोरिथ्म उपस्थित है जो केवल प्रारंभिक LP (या केवल दोहरी LP) के लिए एक इष्टतम समाधान इनपुट करता है और एक इष्टतम आधार देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम उपस्थित है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।
 मेगिद्दो के एल्गोरिदम को सिम्प्लेक्स एल्गोरिदम की तरह ही एक झांकी का उपयोग करके निष्पादित किया जा सकता है।

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 01:34, 30 July 2023

Contents

परिभाषाएँ