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

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

परिभाषाएँ

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

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

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

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 पिक्सल

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

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

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

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

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

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

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

$${\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 के किसी भी इष्टतम समाधान को देखते हुए, एक इष्टतम व्यवहार्य समाधान ढूंढना आसान है जो बुनियादी भी हो।

एक ऐसा आधार ढूंढना जो प्रारंभिक-इष्टतम और दोहरे-इष्टतम दोनों हो

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

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

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

बाहरी संबंध

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