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

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

परिभाषाएँ

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

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

अधिकतम करें ${\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}$.

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 इस पॉलीटोप के एक शीर्ष से मेल खाता है।

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

जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक बेसिक 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 और एक वर्तमान झांकी रखता है। झांकी रैखिक कार्यक्रम का प्रतिनिधित्व है जहां बेसिक चर को गैर-बेसिक के संदर्भ में व्यक्त किया जाता है:

$${\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 के किसी भी ऑप्टीमल समाधान को देखते हुए, एक ऑप्टीमल फीज़बल सलूशन ढूंढना आसान है जो बेसिक भी हो।

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

यदि समाधान हो तो 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-ऑप्टीमल बेसिक होता है, और यह सिम्प्लेक्स एल्गोरिदम द्वारा पाया जाता है। हालाँकि, सबसे खराब स्थिति में इसका रन-टाइम तेजी से बढ़ता है। निम्रोद मेगिद्दो ने निम्नलिखित प्रमेय सिद्ध किये:

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

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

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

बाहरी संबंध

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